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

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

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

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

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

     Сложности иерархических методов кластеризации: ограничение объема набора данных; выбор меры близости; негибкость полученных классификаций.

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

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

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

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

1) Метод  полных связей.

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

2) Метод  максимального локального расстояния.

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

3) Метод  Ворда.

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

4) Центроидный  метод.

     Расстояние  между двумя кластерами определяется как евклидово расстояние между  центрами (средними) этих кластеров:

d2 ij  =  (`X –`Y)Т(`X –`Y) Кластеризация идет поэтапно на каждом из n–1 шагов объединяют два кластера G и p, имеющие минимальное значение d2ij Если n1 много больше  n2,  то центры объединения двух кластеров близки друг к другу и характеристики  второго кластера при объединении кластеров практически игнорируются. Иногда этот метод иногда называют еще методом взвешенных групп. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. Дендограммы

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

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

Рис. 1 

     На  рисунке 1 показан один из примеров  дендограммы. Рис 1 соответствует случаю шести объектов (n=6) и k характеристик (признаков). Объекты А и С наиболее близки и поэтому объединяются в один кластер на уровне близости, равном 0,9. Объекты D и Е объединяются  при уровне 0,8. Теперь имеем 4 кластера:

(А, С), (F), (D, E), (B).

     Далее образуются кластеры (А, С, F) и (E, D, B), соответствующие  уровню близости, равному 0,7 и 0,6. Окончательно все объекты группируются в один кластер при уровне 0,5.

     Вид дендограммы зависит от выбора меры сходства  или расстояния между объектом  и кластером и метода кластеризации. Наиболее важным моментом является выбор меры сходства или меры расстояния между объектом и кластером.

     Число алгоритмов кластерного анализа  слишком велико. Все их можно  подразделить на иерархические  и неиерархические.

     Иерархические алгоритмы связаны с построением дендограмм и делятся на:

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

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

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

Заключение 

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

     Образование сегментов зависит от имеющихся данных, а не определяется заранее.

     Переменные, которые являются основанием для  кластеризации, следует выбирать, исходя из опыта предшествующих исследований, теоретических предпосылок, проверяемых  гипотез, а также по усмотрению исследователя. Кроме того, следует выбрать соответствующую меру расстояния (сходства). Особенность иерархической кластеризации — разработка иерархической или древовидной структуры. Иерархические методы кластеризации могут быть агломеративными или дивизивными. Агломеративные методы включают: метод одиночной связи, метод полной связи и метод средней связи. Широко распространенным дисперсионным методом является метод Барда. Неиерархические методы кластеризации часто называют методами k-средних. Эти методы включают последовательный пороговый метод, параллельный пороговый метод и оптимизирующее распределение. Иерархические и неиерархические методы можно применять совместно. Выбор метода кластеризации и выбор меры расстояния взаимосвязаны.

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

Список  литературы

1. Васильев В.И. и др. Статистический анализ объектов произвольной природы. Введение в статистику качества .- М.: ИКАР, 2004.
2. Экономико-статистический анализ /Под ред. Ильенковой С.Д. –М.: ЮНТИТ, 2002.
3. Парсаданов Г.А. Прогнозирование и планирование социально-экономической системы страны.- М.: ЮНИТИ, 2001