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

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

где:

$P_{n}$ – расстояние между центром $n$ -го таксона и всеми точками этого таксона;
$s_{nk}$ – расстояние между центром $n$ -го таксона и точкой $k$ этого таксона.

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

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

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

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

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

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

Шаг 2. Установить радиус гиперсферы $R_{1}~=~0.9R_{0}$ и перенести центр сферы в любую из внутренних точек (расстояние до которых меньше радиуса):

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

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

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

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

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

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

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