Пояснительная записка (1218768), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

где – число кластеров, – выделенные кластеры, и – центры масс векторов .

Работа алгоритма включает следующие этапы [18]:

– выбор k точек, являющихся начальными центрами кластеров – центроидами; выбор может быть как случайным, так и заранее заданным исследователем;

– соотнесение каждого объекта с ближайшим от него центроидом: вычисляются минимальные расстояния от переменных до центроидов; понятие «расстояние» определяется в соответствии с выбранной метрикой;

– пересчет координат центроидов на основании вычисленных минимальных расстояний;

– перераспределение объектов в соответствии с новыми центроидами;

– если не выполнен критерий остановки алгоритма, пересчет центроидов с последующим перераспределением точек выполняется снова.

Для алгоритма k-means определены следующие критерии остановки:

– кластерные центры стабилизировались, т.е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации;

– число итераций равно максимальному установленному значению[18].

На рисунке 5 приведен пример работы алгоритма k-средних для k, равного двум.

Данный метод обладает рядом недостатков:

– метод k-means не рассматривает все возможные варианты разбиения множества данных на кластеры в отличие от иерархических методов. Метод начинает свою работу с некоторого, как правило, произвольного начального разбиения, которое изменяется до тех пор, пока не выполнен критерий остановки. В силу этого, если на пути алгоритма встретился не глобальный максимум критерия, а локальный, метод может прекратить свою работу, не «дойдя» до глобально оптимального разбиения. Поэтому при его использовании очень важны начальные условия [18];

– исследователю необходимо заранее определять количество кластеров.

Рисунок 5 – Пример работы алгоритма k-средних для двух кластеров точек

Среди достоинств следует отметить простоту реализации данного метода и высокую скорость его работы.

2.7.2 Метод нечеткой кластеризации fuzzy c-means (FCM)

Алгоритм FCM разбивает набор данных на нечеткие группы, вычисляя координаты центров кластеров и минимизирует значение функции расстояния между центроидом и элементами кластера на каждом итерационном шаге. Степень принадлежности того или иного элемента данных конкретному кластеру оценивается числом в пределах от 0 до 1. Следует отметить, что сумма всех степеней принадлежности, определенных для одной точки данных, должна быть равной 1:

Целевая функция метода FCM имеет вид:

где – степень принадлежности -го объекта данных -у кластеру, принимает значения от 0 до 1; – центр -го нечеткого кластера ; – мера расстояний, характеризует степень близости -ой точки данных к -у центру кластера, как правило, выбирается евклидово расстояние (8); – экспоненциальный вес (любое действительное число, большее 1).

Алгоритм нечеткой кластеризации включает следующие этапы [19]:

– инициализация первоначальных значений параметров алгоритма:

а) экспонeнциальный вec (m);

б) мepa paccтояний;

в) уровeнь тoчнocти ;

г) максимальное число итepaций aлгopитмa;

д) количество кластеров.

После инициализации перечисленных параметров случайным образом генерируется первоначальная матрица принадлежности;

– вычислeниe цeнтpoв клacтepoв: каждому j-ому объекту набора данных ставится в соответствие действительное число, вычисляемое по формуле:

где – элемент данных, подвергающихся кластеризации;

– фopмиpoвaниe нoвoй матрицы принадлежности: пересчитываются степени принадлежности объектов с учетом вычисленных на пpeдыдущeм шаге цeнтpoв кластеров:

В случае, если для некоторого j-го кластера и i-го объекта , полагают, что степень принадлежности = 1, а для вcex ocтaльных клacтеров степень принадлежности равна 0;

– вычиcлeниe знaчения целевой функции: вычисленное значение сравниваeтcя со знaчeниeм, вычисленным на предыдущей итерации, и, если их разность не превышает заданной точности , считается, что клacтepизaция окончена; в противном случае, повторяются действия со второго шага алгоритма.

Среди недостатков алгоритма следует отметить следующие:

– необходимость заранее определять количество кластеров;

– для получения более точного результата рекомендуется инициализировать первоначальную матрицу принадлежности неслучайными значениями;

– наличие вероятности возникновения неопределенности с объектами, которые удалены от центров всех кластеров [19].

Однако, данный алгоритм позволяет определять объекты, которые находятся на границе кластеров, таким образом, решая один из недостатков метода k-means.

2.7.3 Метод горной кластеризации

Метод горной кластеризации может быть использован как дополнение к методам k-means и FCM, для определения начальных центров кластеров, необходимых на первой итерации этих методов, и в качестве самостоятельного метода кластеризации.

Алгоритм горного метода кластеризации основан на показателе плотности меры, называемой горной функцией [19].

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

На втором шаге формируется так называемая «горная» функция, которая отражает степень плотности данных:

где – множество узлов построенной сетки, – -я точка данных, – константа, значение которой влияет на гладкость результата кластеризации (рисунок 6).

Рисунок 6 – Результат кластеризации 2-D данных при значениях = 0,02,

= 0,1, = 0,2

Исходя из (9), можно сделать вывод о том, что в данном методе рассматривается влияние каждой точки данных на итоговое значение горной функции – так называемую высоту.

Третий шаг включает выбор первого центроида и переопределение горной функции для всех остальных точек с учетом только что выделенного центра. В качестве первого центроида выбирается узел сетки , имеющий наибольшее значение горной функции. Затем необходимо исключить влияние найденного центра на значения горной функции оставшихся узлов. Необходимость этой операции объясняется тем, что в общем случае выбранный центр окружен точками, в которых горная функция также принимает большие значения, т.е. самый высокий пик на графике функции будет окружен несколькими пиками чуть меньшей высоты (рисунок 7).

Рисунок 7 – Наиболее высокие пики
окружены пиками с меньшей высотой

Это может привести к появлению близко расположенных центроидов в результате кластеризации. Для того, чтобы избежать подобной ситуации, следует при вычислении значений горной функции в процессе поиска второго центроида, изменить формулу (9) следующим образом [19]:

где – первый выделенный центроид, –константа, аналогичная .

Название данный метод получил в виду того, что при визуализации распределения значений горной функции для объектов кластеризации, заданных двумя признаками, график принимает вид горного рельефа (рисунок 7).

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

Среди недостатков метода следует отметить экспоненциальный рост количества вычислений, требуемых для разбиения входных данных на кластеры при линейном увеличении количества измерений [19].

В чистом виде метод горной кластеризации на практике применяется редко в виду наличия его оптимизированного аналога, описываемого ниже.

2.7.4 Субтрактивный метод кластеризации

В основе алгоритма лежат идеи горного методa клacтepного aнaлизa. Данный метод также, как и горный, предназначен для непосредственного нахождения центров кластеров. В качестве его особенности следует выделить отсутствие необходимости заранее задавать их количество. Явным преимуществом субтрактивного метода на фоне вышеописанного горного метода является то, что количество вычислений в первом будет зависеть только от количества разделяемых данных без учета числа измерений [19].

В алгоритме субтрактивного метода кластеризации исходные данные рaccмaтривaются кaк пoтeнциaльныe цeнтpы клacтepов. Для кaждoй из ниx вычиcляeтcя знaчeниe тaк нaзывaeмoгo пoтeнциaлa, который характеризует плoтнocть рacпoлoжeния дpyгиx точек в eе oкрecтнocти. Чем ближе расположены соседние объекты по отношению к выбранному центру, тeм бoльшe значeниe eгo пoтeнциaлa.

С учетом того, что каждая точка рассматривается как потенциальный центр кластера, имеем следующий вид меры плотности:

где – положительная константа, определяет радиус, с помощью которого определяется значение плотности для каждого рассматриваемого элемента.

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

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

Характеристики

Список файлов ВКР