Кластерный анализ

     Кластерный  анализ (англ. Data clustering) — задача разбиения заданной выборки объектов (ситуаций) на подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались. Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя. Кластерный анализ — это многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы (кластеры)(Q-кластеризация, или Q-техника, собственно кластерный анализ). Кластер — группа элементов, характеризуемых общим свойством, главная цель кластерного анализа — нахождение групп схожих объектов в выборке (примечание 1). Спектр применений кластерного анализа очень широк: его используют в археологии, медицине, психологии, химии, биологии, государственном управлении, филологии, антропологии, маркетинге, социологии и других дисциплинах. «Тематика исследований варьирует от анализа морфологии мумифицированных грызунов в Новой Гвинее до изучения результатов голосования сенаторов США, от анализа поведенческих функций замороженных тараканов при их размораживании до исследования географического распределения некоторых видов лишая в Саскачеване». Однако универсальность применения привела к появлению большого количества несовместимых терминов, методов и подходов, затрудняющих однозначное использование и непротиворечивую интерпретацию кластерного анализа.

     Кластерный  анализ выполняет следующие основные задачи:

1. Разработка типологии или классификации;
2. Исследование полезных концептуальных схем группирования объектов;
3. Порождение гипотез на основе исследования данных;

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

     Независимо  от предмета изучения применение кластерного  анализа предполагает следующие  этапы:

       1.Отбор выборки для кластеризации;

       2.Определение множества переменных, по которым будут оцениваться объекты в выборке;

       3.Вычисление значений той или иной меры сходства между объектами.

       4.Применение метода кластерного анализа для создания групп сходных объектов.

        5.Проверка достоверности результатов кластерного решения (примечание 1). 

     Кластерный  анализ предъявляет  следующие требования к данным:

• показатели не должны коррелировать между собой
• показатели должны быть безразмерными
• распределение показателей должно быть близко к нормальному
• показатели должны отвечать требованию «устойчивости», под которой понимается отсутствие влияния на их значения случайных факторов
• выборка должна быть однородна, не содержать «выбросов».

 

   Если  кластерному анализу предшествует факторный анализ, то выборка не нуждается в «ремонте» — изложенные требования выполняются автоматически самой процедурой факторного моделирования (есть ещё одно достоинство — z-стандартизация без негативных последствий для выборки; если её проводить непосредственно для кластерного анализа, она может повлечь за собой уменьшение чёткости разделения групп). В противном случае выборку нужно корректировать.

   Методы  кластеризации:

1. K-средних (K-means)
2. Метод нечеткой кластеризации C-средних (C-means)
3. Графовые алгоритмы кластеризации
4. Статистические алгоритмы кластеризации
5. Алгоритмы семейства FOREL
6. Иерархическая кластеризация или таксономия
7. Нейронная сеть Кохонена
8. Ансамбль кластеризаторов
9. Алгоритмы семейства КRAB
10. EM-алгоритм
11. Алгоритм, основанный на методе просеивания

 

     Группирование результатов поиска: Кластеризация используется для «интеллектуального» группирования результатов при поиске файлов, веб-сайтов, других объектов, предоставляя пользователю возможность быстрой навигации, выбора заведомо более релевантного подмножества и исключения заведомо менее релевантного — что может повысить юзабилити интерфейса по сравнению с выводом в виде простого сортированного по релевантности списка.

     Clusty— кластеризующая поисковая машина компании Vivísimo

     Nigma — российская поисковая система  с автоматической кластеризацией  результатов

     Quintura — визуальная кластеризация в  виде облака ключевых слов

Сегментация изображений (image segmentation): Кластеризация  может быть использована для разбиения  цифрового изображения на отдельные  области с целью обнаружения  границ (edge detection) или распознавания объектов.

     Интеллектуальный  анализ данных (data mining): Кластеризация  в Data Mining приобретает ценность тогда, когда она выступает одним  из этапов анализа данных, построения законченного аналитического решения. Аналитику часто легче выделить группы схожих объектов, изучить их особенности и построить для каждой группы отдельную модель, чем создавать одну общую модель для всех данных. Таким приемом постоянно пользуются в маркетинге, выделяя группы клиентов, покупателей, товаров и разрабатывая для каждой из них отдельную стратегию.

     k-means (иногда называемый k-средних) - наиболее популярный метод кластеризации. Был изобретён в 1950-х математиком Г. Штейнгаузом и почти одновременно С. Ллойдом. Особую популярность приобрёл после работы МакКвина.

     Действие  алгоритма таково, что он стремится  минимизировать суммарное квадратичное уклонение точек кластеров от центров этих кластеров:

       

     где k - число кластеров, Si - полученные кластеры,  и μi - центры масс векторов .

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

     Алгоритм  представляет собой версию EM-алгоритма, применяемого также для разделения смеси гауссиан. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k.

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

     Алгоритм  завершается, когда на какой-то итерации не происходит изменения кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множество конечно, а на каждом шаге суммарное квадратичное уклонение V уменьшается, поэтому зацикливание невозможно.

     Как показали Д.Артур и С.Вассилвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна

     Метод нечеткой кластеризации C-средних (C-means) позволяет разбить имеющееся множество векторов (точек) мощностью p на заданное число нечетких множеств. Особенностью метода является использование нечеткой матрицы принадлежности U с элементами uij, определяющими принадлежность i-го элемента исходного множества векторов - j-му кластеру. Кластеры описываются своими центрами сj - векторами того же пространства, которому принадлежит исходное множество векторов.

     В ходе решения задачи нечеткой кластеризации C-means решается задача минимизации следующей  целевой функции

     E=ΣΣuijm·||xi-cj||²

     при ограничениях Σjuij=1, i=1..p

     FOREL (Формальный Элемент) — алгоритм кластеризации, основанный на идее объединения в один кластер объектов в областях их наибольшего сгущения.

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

      

     где первое суммирование ведется по всем кластерам выборки, второе суммирование — по всем объектам x, принадлежащим  текущему кластеру Kj, а Wj — центр текущего кластера, ρ(x,y) — расстояние между объектами.

      Кластеризуемая  выборка

      Может быть задана признаковыми описаниями объектов — линейное пространство либо матрицей попарных расстояний между  объектами.

Замечание: в реальных задачах зачастую хранение всех данных невозможно или бессмысленно, поэтому необходимые данные собираются в процессе кластеризации

      Параметр R — радиус поиска локальных сгущений

      Его можно задавать как из априорных  соображений (знание о диаметре кластеров), так и настраивать скользящим контролем.

      В модификациях возможно введение параметра k — количества кластеров

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

     Нейронные сети Кохонена — класс нейронных сетей, основным элементом которых является слой Кохонена. Слой Кохонена состоит из адаптивных линейных сумматоров («линейных формальных нейронов»). Как правило, выходные сигналы слоя Кохонена обрабатываются по правилу «победитель забирает всё»: наибольший сигнал превращается в единичный, остальные обращаются в ноль.

     По  способам настройки входных весов  сумматоров и по решаемым задачам  различают много разновидностей сетей Кохонена. Наиболее известные из них:

     Сети  векторного квантования сигналов, тесно связанные с простейшим базовым алгоритмом кластерного анализа (метод динамических ядер или K-средних)

     Самоорганизующиеся  карты Кохонена (Self-Organising Maps, SOM)

     Сети  векторного квантования, обучаемые  с учителем (Learning Vector Quantization)

     Слой  Кохонена состоит из некоторого количества n параллельно действующих линейных элементов. Все они имеют одинаковое число входов m и получают на свои входы один и тот же вектор входных сигналов x = (x1,...xm). На выходе jго линейного элемента получаем сигнал

     

     где wji — весовой коэффициент iго входа jго нейрона, wj0 — пороговый коэффициент.

     После прохождения слоя линейных элементов  сигналы посылаются на обработку  по правилу «победитель забирает всё»: среди выходных сигналов yj ищется максимальный; его номер jmax  = argmax j{yj}. Окончательно, на выходе сигнал с  номером jmax  равен единице, остальные — нулю. Если максимум одновременно достигается для нескольких jmax , то либо принимают все соответствующие сигналы равными единице, либо только первый в списке (по соглашению). «Нейроны Кохонена можно воспринимать как набор электрических лампочек, так что для любого входного вектора загорается одна из них.»

     EM-алгоритм (англ. Expectation-maximization (EM) algorithm) — алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости.