Решение экономических задач в информационном обеспечении Интернет-проекта

Задача кластерного  анализа заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов G на m (m-целое) кластеров (подмножеств) Q1,Q2 ,….,, так, чтобы каждый объект принадлежал одному и только одному подмножеству разбиения. А объекты, принадлежащие одному и тому же кластеру, были сходными, в то время как объекты, принадлежащие разным кластерам, были разнородными.

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

,    

где – представляет собой измерения j-го объекта.

Кластер имеет следующие математические характеристики: центр, радиус, среднеквадратическое отклонение, размер кластера.

Центр кластера – это среднее геометрическое место точек в пространстве переменных.

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

Спорный объект – это объект, который по мере сходства может быть отнесен к нескольким кластерам. 

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

Неоднозначность данной задачи может быть устранена экспертом  или аналитиком.

Работа кластерного анализа  опирается на два предположения. Первое предположение – рассматриваемые  признаки объекта в принципе допускают  желательное разбиение пула (совокупности) объектов на кластеры. Второе предположение – правильность выбора масштаба или единиц измерения признаков.

Выбор масштаба в кластерном анализе имеет большое значение. Рассмотрим пример. Представим себе, что  данные признака х в наборе данных А на два порядка больше данных признака у: значения переменной х находятся  в диапазоне от 100 до 700, а значения переменной у – в диапазоне от 0 до 1.

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

Эта проблема решается при  помощи предварительной стандартизации переменных. Стандартизация (standardization) или нормирование (normalization) приводит значения всех преобразованных переменных к единому диапазону значений путем выражения через отношение этих значений к некой величине, отражающей определенные свойства конкретного признака. Существуют различные способы нормирования исходных данных:

,    ,    ,    ,

где , – соответственно среднее и среднеквадратическое отклонение ; , – наибольшее и наименьшее значение x .

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

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

2. Измерение близости объектов

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

 Отметим основные трудности, возникающие при этом: неоднозначность выбора способа нормировки и определения расстояния между объектами. Рассмотрим результаты небольшого обследования. Студенты группы записывают свои данные (вес, рост), оформляют в таблицу и строят по ним корреляционное поле. Масштабы по осям выбираются произвольно (рис.2.1).

Рис. 2.1.

На рис. 2.1а выделяются классы A – девушки, B – юноши. На рис. 2.1b выделяются классы A1 (юноши и девушки) и B1(часть юношей). Класс юношей C (пунктирная линия) на рис. 2.1б не выделит, поскольку расстояния между ближайшими объектами классов A1и B1 существенно больше, чем внутренние расстояния в A1, юноши из A почти никакими алгоритмами к B1 не присоединяются.

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

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

Расстоянием (метрикой) между объектами в пространстве параметров называется такая величина , которая удовлетворяет аксиомам:

A1.

A2.

A3.

Мерой близости (сходства) обычно называется величина , имеющая предел и возрастающая с возрастанием близости объектов.

B1. непрерывна,

B2. = ,

B3. 1 0.

Существует возможность  простого перехода от расстояний к  мерам близости:

.

 

3. Характеристики близости объектов

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

 Рассмотрим основные способы определения близости между объектами (Таблица 2.1):

Таблица 2.1

Показатели	Формулы
Для количественных шкал
Линейное расстояние     Евклидово расстояние     Квадрат евклидово расстояния     Обобщенное степенное  расстояние Минковского   Расстояние Чебышева     Расстояние городских  кварталов (Манхэттенское расстояние)

 

Евклидово расстояние является самой популярной метрикой в кластерном анализе. Оно попросту является геометрическим расстоянием в многомерном пространстве. Геометрически оно лучше всего объединяет объекты в шарообразных скоплениях.

Квадрат евклидова  расстояния. Для придания больших весов более отдаленным друг от друга объектам можем воспользоваться квадратом евклидова расстояния путем возведения в квадрат стандартного евклидова расстояния.

Обобщенное степенное расстояние представляет только математический интерес как универсальная метрика.

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

Манхэттенское расстояние (расстояние городских кварталов), также называемое "хэмминговым" или "сити-блок" расстоянием. Это расстояние рассчитывается как среднее разностей по координатам. В большинстве случаев эта мера расстояния приводит к результатам, подобным расчетам расстояния евклида. Однако, для этой меры влияние отдельных выбросов меньше, чем при использовании евклидова расстояния, поскольку здесь координаты не возводятся в квадрат.

Процент несогласия. Это расстояние вычисляется, если данные являются категориальными.

4. Методы кластерного анализа

Методы кластерного анализа  можно разделить на две группы:

• иерархические;
• неиерархические.

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

5. Иерархические алгоритмы

Суть иерархической кластеризации  состоит в последовательном объединении  меньших кластеров в большие или разделении больших кластеров на меньшие.

Иерархические агломеративные методы (Agglomerative Nesting, AGNES)

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

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

 Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA)

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

Принцип работы описанных  выше групп методов в виде дендрограммы показан на рис.2.2.

Рис 2.2.

 

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

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

Иерархические алгоритмы  связаны с построением дендрограмм (от греческого dendron – "дерево"), которые являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров.

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

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

Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться вертикально или горизонтально. Пример вертикальной дендрограммы приведен на рис. 2.3.

 

Рис 2.3. Пример дендрограммы

 

Числа 11, 10, 3 и т.д. соответствуют  номерам объектов или наблюдений исходной выборки. Мы видим, что на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение  таких наблюдений: 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На втором шаге продолжается объединение  в кластеры: наблюдения 11, 10, 3, 4, 5 и 7, 8, 9. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся  в один кластер.

Пусть – i -я группа (класс, кластер), состоящая из n объектов;

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

  – расстояние между группами и .

Обобщенная алгомеративная процедура. На первом шаге каждый объект считается отдельным кластером. На следующем шаге объединяются два ближайших объекта, которые образуют новый класс, определяются расстояния от этого класса до всех остальных объектов, и размерность матрицы расстояний D сокращается на единицу. На p-ом шаге повторяется та же процедура на матрице D(n- p)(n- p), пока все объекты не объединятся в один класс.