Методы кластеризации. Алгоритм Forel

     

     где:

• – расстояние между центром -го таксона и всеми точками этого таксона;
• – расстояние между центром -го таксона и точкой этого таксона.

     Сумма таких внутренних расстояний для  всех таксонов равна:

     

     Целью работы алгоритма FOREL является найти такое разбиение множества объектов на таксонов, чтобы величина была минимальной.

     Работа  алгоритма заключается в перемещении  гиперсферы определенного радиуса  в геометрическом пространстве до получения  устойчивого центра тяжести наблюдений, попавших в эту гиперсферу. До начала работы алгоритма признаки объектов нормируются так, чтобы их значения находились между нулем и единицей.

                 Алгоритм выполнения:

1. Случайно  выбираем текущий объект из выборки;
2. Помечаем объекты выборки, находящиеся на расстоянии менее, чем R от текущего;
3. Вычисляем их центр тяжести, помечаем этот центр как новый текущий объект;
4. Повторяем шаги 2-3, пока новый текущий объект не совпадет с прежним;
5. Помечаем объекты внутри сферы радиуса R вокруг текущего объекта как кластеризованные, выкидываем их из выборки;
6. Повторяем шаги 1-5, пока не будет кластеризована вся выборка.

     Наблюдения:

• Доказана  сходимость алгоритма за конечное число  шагов
• В линейном пространстве центром тяжести может выступать произвольная точка пространства, в метрическом — только объект выборки
• Чем меньше R, тем больше таксонов (кластеров)
• В линейном пространстве поиск центра происходит за время О(n), в метрическом O(n²)
• Наилучших результатов алгоритм достигает на выборках с хорошим выполнением условий компактности
• При повторении итераций возможно уменьшение параметра R, для скорейшей сходимости
• Кластеризация сильно зависит от начального приближения (выбора объекта на первом шаге)
• Рекомендуется повторная прогонка алгоритма для исключения ситуации «плохой» кластеризации, по причине неудачного выбора начальных объектов.

     Пример  работы алгоритма.

     Допустим, было дано некоторое множество классифицируемых объектов. Пусть каждый объект обладает только двумя свойствами; это позволит отобразить исходные данные на геометрической плоскости:

     

     Шаг 1. Построить гиперсферу радиуса охватывающую все множество точек:

     

     Шаг 2. Установить радиус гиперсферы и перенести центр сферы в любую из внутренних точек (расстояние до которых меньше радиуса):

     

     Шаг 3. Вычислить новый центр тяжести и перенести в него центр сферы:

     

     Шаг 4. Если новый центр тяжести отличается от предыдущего необходимо вернуться к шагу 2 и повторить цикл. Цикл будет повторяться до тех пор пока центр тяжести не перестанет смещаться. Таким образом, центр сферы перемещается в область локального сгущения точек. В предложенном примере центр сферы , поэтому: необходимо установить новый радиус сферы и перенести центр сферы в произвольную внутреннюю точку:

     

     Шаг 5. Вычислить новый центр тяжести и перенести в него центр сферы. Новый центр тяжести , поэтому внутренние точки текущей сферы объединяются в таксон:

     

     Шаг 6. Точки принадлежащие новому таксону исключаются из анализа и работа алгоритма повторяется с шага №1. И так до тех пор пока все точки не будут исключены из анализа:

     

     Процедура алгоритма Форель является сходящейся за конечное число шагов в евклидовом пространстве любой размерности  при произвольном расположении точек  и любом выборе гиперсферы.

     Если  начальную точку, в которую переносится  центр сферы, на шаге №2 менять случайным  образом, может получиться несколько  вариантов таксономии, из которых  выбирается тот, на котором достигается  .

     Алгоритм  FOREL-2 является модификацией исходного алгоритма и применяется в тех случаях, когда необходимо получить изначально заданное количество кластеров (таксонов). Радиус сферы по мере надобности может изменяться на заданную величину, которая от итерации к итерации будет уменьшаться.

     Наилучшему  варианту таксономии отвечает при числе таксонов равном заданному.

     Преимущества модифицированного алгоритма:

1. Точность  минимизации функционала качества (при удачном подборе параметра R);
2. Наглядность визуализации кластеризации;
3. Сходимость алгоритма;
4. Возможность операций над центрами кластеров — они известны в процессе работы алгоритма;
5. Возможность подсчета промежуточных функционалов качества, например, длины цепочки локальных сгущений;
6. Возможность проверки гипотез схожести и компактности в процессе работы алгоритма.

     Недостатки модифицированного алгоритма:

1. Относительно  низкая производительность (решается введение функции пересчета поиска центра при добавлении 1 объекта  внутрь сферы);
2. Плохая применимость алгоритма при плохой разделимости выборки на кластеры;
3. Неустойчивость алгоритма (зависимость от выбора начального объекта);
4. Произвольное по количеству разбиение на кластеры;
5. Необходимость априорных знаний о ширине (диаметре) кластеров.

     После работы алгоритма над готовой  кластеризацией можно производить  некоторые действия:

1. Выбор наиболее репрезентативных (представительных) объектов из каждого кластера. Можно выбирать центры кластеров, можно несколько объектов из каждого кластера, учитывая априорные знания о необходимой репрезентативности выборки. Т. О. по готовой кластеризации мы имеем возможность строить наиболее репрезентативную выборку
2. Пересчет кластеризации (многоуровненвость) с использованием метода КНП

     Область применения

1. Решение задач  кластеризации
2. Решение задач ранжирования выборки

     4.2 Процедура, реализующая алгоритм FOREL

     procedure TForm1.Button4Click(Sender: TObject);

     var i,j,d,n,m,f,l: integer;

         r: array of array of real;

         s,e,min, max: real;

         tk,p: array [1..10] of real; 

     begin

       n:= StrToInt(Edit1.Text);

       m:= StrToInt(Edit2.Text);

       e:= StrToFloat(Edit3.Text);

       SetLength(r,n);

       for i:=0 to n-1 do

       SetLength(r[i],m);

       for i:=0 to n-1 do begin

       for j:=0 to m-1 do begin

       r[i][j]:= StrToFloat(StringGrid3.Cells[j+1,i+1]);

       end;end;

       min:=500;

       for i:=0 to n-1 do begin

         max:=-100;

           for j:=0 to m-1 do begin

             if(r[i][j] > max) then max:=r[i][j];

           end;

         if(max < min) then min:=max;

       end;

       s:=min-e;

       for i:= 0 to n-1 do tk[i]:=0;

       f:=1;

       repeat

         max:=-1;

         for i:=0 to n-1 do begin

           p[i]:=0;

           for j:=0 to m-1 do begin

             if (r[i,j] < s) and(tk[j]=0) and(tk[i]=0)then p[i]:=p[i]+1;

           end;

           if (p[i]> max) then begin

             max:=p[i];

             l:=i;

           end;

         end;

         tk[l]:=f;

         for i:=0 to n-1 do if (r[l][i]<s) then tk[i]:=f;

         f:=f+1;

         d:=0;

         for i:=0 to n-1 do if (tk[i]=0) then d:=1;

       until  d=0;

       for i:=0 to f-1 do begin

         Memo1.Lines.Add('в таксон с центром '+IntToStr(i)+' вошли:');

           for j:=0 to n-1 do begin

             if (tk[j]=i) then Memo1.Lines.Add(FloatToStr(tk[j]));;

           end;

       end;

     end;

 

ЗАКЛЮЧЕНИЕ

     Таким образом, кластерный анализ решает широкий  спектр статистических задач, без которых  не обходятся экономические, математические и социологические исследования.

     В данном курсовом проекте рассмотрены  области применения кластерного  анализа, его основные методы, наиболее подробно рассмотрен алгоритм кластеризации  Forel, его пошаговое выполнение, приведена процедура, реализующая данный алгоритм.

 

     СПИСОК  ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Н. Г. Загоруйко. Прикладные методы анализа данных и знаний.- Новосибирск; Изд-во Ин-та математики, 1999.
2. А.Е.Лепский, А.Г. Броневич. Математические методы распознания образов, курс лекций. – Таганрог; Изд-во ТИЮФУ, 2009.
3. www.MachineLearning.ru