Алгоритмы Форель и Форель 2

Алгоритм Форель является примером эвристического дивизимного алгоритма классификации. В основе работы алгоритма Форель лежит использование гипотезы компактности: близким в содержательном смысле объектам в геометрическом пространстве признаков соответствуют обособленные множества точек, так называемые «сгустки». Если расстояние между центром n-го таксона и точкой k этого таксона обозначить , то сумма расстояний между центром и всеми точками k этого таксона будет равна:


где:

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

Это интересно

Смотрите также