Лекции по дисциплине «Анализ данных» Направление подготовки 38. 03. 05 «Бизнес-информатика»



страница2/17
Дата02.06.2016
Размер0.75 Mb.
ТипЛекции
1   2   3   4   5   6   7   8   9   ...   17

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


Кластерный анализ (англ. cluster analysis) — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы[1][2][3][4]. Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя.

Большинство исследователей (см., напр., [5]) склоняются к тому, что впервые термин «кластерный анализ» (англ. cluster — гроздь, сгусток, пучок) был предложен математиком Р. Трионом[6]. Впоследствии возник ряд терминов, которые в настоящее время принято считать синонимами термина «кластерный анализ»: автоматическая классификация, ботриология.

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

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



  • Разработка типологии или классификации.

  • Исследование полезных концептуальных схем группирования объектов.

  • Порождение гипотез на основе исследования данных.

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

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

  • Отбор выборки для кластеризации. Подразумевается, что имеет смысл кластеризовать только количественные данные.

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

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

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

  • Проверка достоверности результатов кластерного решения.

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

Типология задач кластеризации

Типы входных данных


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

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

  • Матрица сходства между объектами[8]. Учитывается степень сходства объекта с другими объектами выборки в метрическом пространстве. Сходство здесь дополняет расстояние (различие) между объектами до 1.

В современной науке применяется несколько алгоритмов обработки входных данных. Анализ путём сравнения объектов, исходя из признаков, (наиболее распространённый в биологических науках) называется Q-типом анализа, а в случае сравнения признаков, на основе объектов — R-типом анализа. Существуют попытки использования гибридных типов анализа (например, RQ-анализ), но данная методология ещё должным образом не разработана.

Цели кластеризации


  • Понимание данных путём выявления кластерной структуры. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»).

  • Сжатие данных. Если исходная выборка избыточно большая, то можно сократить её, оставив по одному наиболее типичному представителю от каждого кластера.

  • Обнаружение новизны (англ. novelty detection). Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров.

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

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


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


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

  1. Вероятностный подход. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Некоторые авторы (например, А. И. Орлов) считают, что данная группа вовсе не относится к кластеризации и противопоставляют её под названием «дискриминация», то есть выбор отнесения объектов к одной из известных групп (обучающих выборок).

    • K-средних (K-means)

    • K-medians

    • EM-алгоритм

    • Алгоритмы семейства FOREL

    • Дискриминантный анализ

  2. Подходы на основе систем искусственного интеллекта: весьма условная группа, так как методов очень много и методически они весьма различны.

  3. Логический подход. Построение дендрограммы осуществляется с помощью дерева решений.

  4. Теоретико-графовый подход.

    • Графовые алгоритмы кластеризации

  5. Иерархический подход. Предполагается наличие вложенных групп (кластеров различного порядка). Алгоритмы в свою очередь подразделяются на агломеративные (объединительные) и дивизивные (разделяющие). По количеству признаков иногда выделяют монотетические и политетические методы классификации.

    • Иерархическая дивизивная кластеризация или таксономия. Задачи кластеризации рассматриваются в количественной таксономии.

  6. Другие методы. Не вошедшие в предыдущие группы.

    • Статистические алгоритмы кластеризации

    • Ансамбль кластеризаторов

    • Алгоритмы семейства KRAB

    • Алгоритм, основанный на методе просеивания

    • DBSCAN и др.

Подходы 4 и 5 иногда объединяют под названием структурного или геометрического подхода, обладающего большей формализованностью понятия близости[10]. Несмотря на значительные различия между перечисленными методами все они опираются на исходную «гипотезу компактности»: в пространстве объектов все близкие объекты должны относиться к одному кластеру, а все различные объекты соответственно должны находиться в различных кластерах.

k-means (метод k-средних

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

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



v = \sum_{i=1}^{k} \sum_{x_j \in s_i} (x_j - \mu_i)^2

где k — число кластеров, s_i — полученные кластеры, i = 1, 2, \dots, k и \mu_i — центры масс векторов x_j \in s_i.

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

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

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

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

Как показали Дэвид Артур и Сергей Васильвицкий, на некоторых классах множеств сложность алгоритма по времени, нужному для сходимости, равна 2^{\omega(\sqrt{n})}.[6]

Нейронные сети Кохонена 

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

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



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

  • самоорганизующиеся карты Кохонена (англ. self-organising mapsSOM)[3];

  • сети векторного квантования, обучаемые с учителем (англ. learning vector quantization)[4].

Идея и алгоритм обучения


Задача векторного квантования состоит, по своему существу, в наилучшей аппроксимации всей совокупности векторов данных k кодовыми векторами w_j. Самоорганизующиеся карты Кохонена также аппроксимируют данные, однако при наличии дополнительной структуры в совокупности кодовых векторов (англ. codebook). Предполагается, что априори задана некоторая симметричная таблица «мер соседства» (или «мер близости») узлов: для каждой пары j,l (j,l=1,...k) определено число \eta_{jl} (0 \leq \eta_{jl} \leq 1) при этом диагональные элементы таблицы близости равны единице (\eta_{jj}=1).

Векторы входных сигналов x обрабатываются по одному, для каждого из них находится ближайший кодовый вектор («победитель», который «забирает всё») w_{j(x)}. После этого все кодовые векторы w_l, для которых \eta_{j(x)l}\neq 0, пересчитываются по формуле



w^{\rm new}_l=w^{\rm old}_l(1- \eta_{j(x)l} \theta)+x\eta_{j(x)l} \theta,

где \theta \in (0,1) — шаг обучения. Соседи кодового вектора — победителя (по априорно заданной таблице близости) сдвигаются в ту же сторону, что и этот вектор, пропорционально мере близости.

Чаще всего, таблица кодовых векторов представляется в виде фрагмента квадратной решётки на плоскости, а мера близости определяется, исходя из евклидового расстояния на плоскости.

Самоорганизующиеся карты Кохонена служат, в первую очередь, для визуализации и первоначального («разведывательного») анализа данных[7]. Каждая точка данных отображается соответствующим кодовым вектором из решётки. Так получают представление данных на плоскости («карту данных»). На этой карте возможно отображение многих слоёв: количество данных, попадающих в узлы (то есть «плотность данных»), различные функции данных и так далее. При отображении этих слоёв полезен аппарат географических информационных систем (ГИС). В ГИС подложкой для изображения информационных слоев служит географическая карта. Карта данных является подложкой для произвольного по своей природе набора данных. Карта данных служит заменой географической карте там, где карты данных просто не существует. Принципиальное отличие в следующем: на географической карте соседние объекты обладают близкими географическими координатами, на карте данных близкие объекты обладают близкими свойствами. С помощью карты данных можно визуализировать данные, одновременно нанося на подложку сопровождающую информацию (подписи, аннотации, атрибуты, информационные раскраски)[7]. Карта служит также информационной моделью данных. С её помощью можно заполнять пробелы в данных. Эта способность используется, например, для решения задач прогнозирования.


Самоорганизующиеся карты и главные многообразия[править | править вики-текст]


Идея самоорганизующихся карт очень привлекательна и породила массу обобщений, однако, строго говоря, мы не знаем, что мы строим: карта — это результат работы алгоритма и не имеет отдельного («объектного») определения. Есть, однако, близкая теоретическая идея — главные многообразия (англ. principal manifolds)[8]. Эти многообразия обобщают линейные главные компоненты. Они были введены как линии или поверхности, проходящие через «середину» распределения данных, с помощью условия самосогласованности: каждая точка x на главном многообразии m является условным математическим ожиданием тех векторов z, которые проектируются на x (при условии x=p(z), где p — оператор проектирования окрестности m на m),

x=\mathbf{e}(z|p(z)=x).

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



Каталог: files
files -> Методические рекомендации «Организация исследовательской деятельности учащихся»
files -> Актуальность исследования
files -> Рабочая программа дисциплины
files -> Программа курса предназначена для учащихся 9-11 класса и рассчитана на 128 часов. Периодичность занятий 1 раз в неделю по 4 учебных часа
files -> Предоставление максимально широкого поля возможностей учащимся, ориентированным на высокий уровень образования и воспитания, с учетом их индивидуальных потребностей
files -> Методические рекомендации по организации исследовательской и проектной деятельности младших школьников
files -> Программы
files -> Выпускных квалификационных работ


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   17


База данных защищена авторским правом ©psihdocs.ru 2017
обратиться к администрации

    Главная страница