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

     Кластерный  анализ (англ. 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-шага на следующей итерации. Алгоритм выполняется до сходимости.

     Часто EM-алгоритм используют для разделения смеси гауссиан.

     Кластерный  анализ предназначен для разбиения совокупности объектов на однородные группы (кластеры или классы).

     По  сути это задача многомерной классификации  данных.

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

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

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

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

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

Кластер Муж 30-50 лет >50 лет Рук. Мед Льготы з/п стаж Образов.

1 80% 90% 5% 70% 10% 12% 95% 30% 30%

2 40% 35% 45% 13% 60% 70% 60% 40% 20%

3 50% 70% 10% 5% 30% 20% 70% 20% 50% 

      Поясним, как сформирована приведенная выше таблица:

      В первом столбце расположен номер  кластера - группы, данные по которой  отражены в строке. Например, первый кластер на 80% составляют мужчины. 90% первого кластера попадают в возрастную категорию от 30 до 50 лет, а 12% респондентов считает, что льготы очень важны. И так далее.

      Попытаемся  составить портреты респондентов каждого  кластера.

        Первая группа - в основном мужчины  зрелого возраста, занимающие руководящие  позиции. Соцпакет (MED, LGOTI, TIME-своб  время) их не интересует. Они  предпочитают получать хорошую зарплату, а не помощь от работодателя.

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

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

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

      Data Mining (рус. добыча  данных, интеллектуальный  анализ данных, глубинный  анализ данных) — собирательное название, используемое для обозначения совокупности методов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Термин введён Григорием Пиатецким-Шапиро в 1989 году.

      Английское  словосочетание «Data Mining» пока не имеет  устоявшегося перевода на русский язык. При передаче на русском языке используются следующие словосочетания: просев информации, добыча данных, извлечение данных, а, также, интеллектуальный анализ данных. Более полным и точным является словосочетание обнаружение знаний в базах данных (knowledge discovering in databases, KDD).

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

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

      Методы Data Mining (или, что то же самое, Knowledge Discovery In Data, сокращённо, KDD) лежат на стыке  баз данных, статистики и искусственного интеллекта.

      Исторический  экскурс

      Область Data Mining началась с семинара (англ. workshop), проведёного Григорием Пятецким-Шапиро в 1989 году.

      Ранее, работая в компании GTE Labs, Григорий Пятецкий-Шапиро заинтересовался вопросом: можно ли автоматически находить определённые правила, чтобы ускорить некоторые запросы к крупным базам данных. Тогда же было предложено два термина — Data Mining (который следует переводить как «раскопка данных») и Knowledge Discovery In Data (который следует переводить как «открытие знаний в базах данных»).

      В 1993 году вышла первая рассылка «Knowledge Discovery Nuggets», а в 1994 году был создан один из первых сайтов по Data Mining.

      Постановка  задачи

      Первоначально, задача ставится следующим образом:

имеется достаточно крупная база данных;

предполагается, что в базе данных находятся некие  «скрытые знания».

Необходимо  разработать методы обнаружения  знаний, скрытых в больших объёмах  исходных «сырых» данных.

      Что означает «скрытые знания»? Это должны быть обязательно знания:

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

      Этими требования во многом определяют суть методов Data mining и то, в каком виде и в каком соотношении в  технологии Data mining используются системы  управления базами данных, статистические методы анализа и методы искусственного интеллекта.

      Data mining и базы данных

      Методы Data mining имеет смысл применять  только для достаточно больших баз  данных. В каждой конкретной области  исследований существует свой критерий «великости» базы данных. 

      Развитие технологий баз данных сначала привело к созданию специализированного языка — языка запросов к базам данных. Для реляционных баз данных — это язык SQL, который предоставил широкие возможности для создания, изменения и извлечения хранимых данных. Затем возникла необходимость в получении аналитической информации (например, информации о деятельности предприятия за определённый период), и тут оказалось, что традиционные реляционные базы данных, хорошо приспособленные, например, для ведения оперативного учёта (на предприятии), плохо приспособлены для проведения анализа. это привело, в свою очередь, к созданию т.н. «хранилищ данных», сама структура которых наилучшим способом соответствует проведению всестороннего математического анализа.

      Data mining и статистика

      В основе методов Data mining лежат математические методы обработки данных, включая  и статистические методы (). В промышленных решениях, нередко, такие методы непосредственно  включаются в пакеты Data mining. Однако, следует учитывать, что статистические методы, во-первых, основываются на статистической природе анализируемых явлений (например, обычно постулируют форму распределения случайной величины), а, во-вторых, результаты статистических методов, как правило, являются тривиальными (легко рассчитываются), практически бесполезными (например, всевозможные средние) и трудно интерпретируемыми (те же средние), что полностью расходится с целями и задачами Data mining. Тем не менее, статистические методы используются, но их применение ограничивается выполнением только определённых этапов исследования.

      Data mining и искусственный интеллект

      Знания, добываемые методами Data mining принято  представлять в виде моделей. В качестве таких моделей выступают:

• ассоциативные правила;
• деревья решений;
• кластеры;
• математические функции.

      Методы  построения таких моделей принято  относить к области т.н. «искусственного  интеллекта».

      Задачи

      Задачи, решаемые методами Data Mining, принято разделять  на

описательные (англ. descriptive); предсказательные (англ. predictive).

      В описательных задачах самое главное — это дать наглядное описание имеющихся скрытых закономерностей, в то время как в предсказательных задачах на первом плане стоит вопрос о предсказании для тех случаев, для которых данных ещё нет.

      К описательным задачам относятся:

• Поиск ассоциативных правил или паттернов (образцов).
• Группировка объектов или кластеризация.
• Построение регрессионной модели.

      К предсказательным задачам относятся:

• Классификация объектов (для заранее заданных классов).
• Построение регрессионной модели.

      Алгоритмы обучения

      Для задач классификации характерно «обучение с учителем», при котором  построение (обучение) модели производится по выборке, содержащей входные и  выходные векторы.

      Для задач кластеризации и ассоциации применяется «обучение без учителя», при котором построение модели производится по выборке, в которой нет выходного параметра. Значение выходного параметра («относится к кластеру …», «похож на вектор …») подбирается автоматически в процессе обучения.

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