Определение «точек сгущения»

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

Сначала несколько объектов, выбранных по каким-либо соображениям (возможно даже произвольно), назначаются центрами кластеров. Затем поочередно все остальные объекты относятся к тем кластерам, центры которых к ним ближе всего. Центры кластеров пересматриваются либо после включения каждого нового объекта, либо после отнесения всех объектов. Некоторые кластеры могут быть ликвидированы, если для них не выполняется заданный критерий качества. Также могут образовываться новые кластеры. Описанная процедура повторяется до получения устойчивой классификации.

К наиболее известным представителям данной группы алгоритмов относятся алгоритмы Форель /Загоруйко Н. Г. и др., 1985/, Isodata /Ту Дж. и др., 1978/, методы динамических сгущений и менее сложные эвристические алгоритмы, такие как k эталонов, «взаимного поглощения» и др., рассмотренные в /Айвазян С. А. и др., 1989/.

Сравнительный анализ различных алгоритмов автоматического группирования был проведен в работе Дж. Меззиха /Классификация…, 1980/. Сравнивались следующие алгоритмы: факторный анализ объектов, один оптимизационный кластерный алгоритм, два алгоритма поиска «точек сгущения» и три варианта иерархической процедуры. По результатам исследования на четырех наборах реальных данных сделан вывод, что наилучшим образом зарекомендовали себя два алгоритма (из трех самых распространенных) иерархического группирования. Собственный опыт и опыт других авторов (например Александров В. В. и др., 1990) подтверждает этот вывод. Для практического исследования структуры многомерных данных с помощью алгоритмов автоматического группирования часто оказывается достаточным иметь в пакете прикладных программ один иерархический алгоритм группирования объектов по принципу ближайшего соседа и один алгоритм, группирующий объекты по принципу «центров тяжести» или «средней связи».

Пример кластерного анализа

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

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

В рассматриваемом примере будут исследованы 16 известных инвестиционных фондов для оценки их состояния. В качестве переменных используются следующие характеристики (большинство из них описывается в условных единицах): доходность за пятилетний период — переменная Five_Yr, риск — переменная Risk, ежегодный процент дохода ( performance) (для каждого года) — Perf90, Perf91, Perf92, Perf93, Perf94, расходная часть — переменная Expence и налоговые рейтинги — переменная Tax. Ниже приводится таблица с исходными данными по исследуемым фондам. В первом столбце указано наименование фонда, а в последнем — рекомендации экспертов по операциям с ценными бумагами этих фондов. Данные заимствованы из руководства по применению STATGRAPHICS Plus for Windows.

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

Таблица 7. 4

Fund	Five_Yr	Risk	Perf 90	Perf 91	Perf 92	Perf 93	Perf 94	Expence	Tax	Recom.
F. Chip	16476	2	10	25	6	55	4	1.22	89	Buy
F. Contra	15476	2	– 1	21	16	55	4	1.03	90	Buy
F. Destiny	14757	3	4	26	15	39	– 3	0.7	69	Buy
Vista A	15145	4	– 1	20	13	71	– 6	1.49	96	Hold
Berger 100	15596	5	– 7	21	9	89	– 6	1.7	95	Hold
Gab. Assett	13640	1	0	22	15	18	– 6	1.33	85	Buy
Neub. Focus	14081	3	1	16	21	25	– 6	0.85	75	Buy
F. Magellan	13827	3	– 2	25	7	41	– 5	0.96	73	Buy
Janus	13187	2	– 1	11	7	43	– 1	0.91	85	Sell
L. Mason Value	13029	4	1	12	11	35	– 17	1.82	92	Hold
Gabelli Growth	12301	3	– 3	11	4	34	– 2	1.41	80	Buy
Franklin Growth	11793	2	3	7	3	27	2	0.77	90	Sell
Janus 20	12441	4	– 7	3	2	69	1	1.02	95	Sell
AARP Capital	11728	4	– 10	16	5	41	– 16	0.97	68	Sell
Kemper Growth A	11386	4	– 6	2	– 2	67	4	1.09	86	Sell
20th Cent. Growth	11258	4	– 8	15	– 4	32	0	1	60	Buy

Введем приведенные данные в электронную таблицу STATGRAPHICS и сохраним их в файле с именем growth. Выберем Special | Multivariate Methods | Cluster Analysis. Система отобразит окно диалога для ввода данных в кластерный анализ (Рис. 7. 20).

Дважды щелкнем левой кнопкой мыши на переменных Expence, Five_Yr, Perf90, Perf91, Perf92, Perf93, Perf94, Risk и Tax для задействования их в анализе.

Введем характеристику Fund в поле Point Labels и оставим поле данных Select пустым. На Рис. 7. 20 показан пример заполнения окна диалога для ввода информации в кластерный анализ.

Рис. 7. 20. Пример заполнения окна диалога ввода данных для кластерного анализа

Нажмем OK. Система выдаст окно с первичной сводкой кластерного анализа.

Так как в нашем случае желательно, чтобы кластерный алгоритм хорошо работал с небольшим количеством наблюдений (у нас их всего 16) и был нацелен на выделение кластеров с приблизительно равным числом членов, остановим свой выбор на методе Варда (Wards method).

Щелкнем правой кнопкой мыши — на экране появляется окно диалога для выбора параметров кластерного анализа.

Установим флажок Wards, а все остальные оставим в прежнем положении (Рис. 7. 21).

Рис. 7. 21. Пример заполнения окна диалога для выбора параметров кластерного анализа

Нажмем OK; на экране отобразится сводка кластерного анализа для выбранного метода.

Нажмем кнопку для задания графических опций (третья слева в верхнем ряду окна анализа). Система предоставит специальное окно диалога.

Выберем отображение в виде дендрограммы (Dendrogram) и нажмем кнопку OK. Система добавит к табличному окну графическое окно.

Дважды щелкнем на дендрограмме для максимального раскрытия этого окна (Рис. 7. 22).

Дендрограмма отображает иерархическую структуру группирования инвестиционных фондов. На ней отчетливо видны как минимум три группировки: одна заканчивается на фонде Gabelli Growth, вторая заканчивается на фонде Legg Mason Value и третья, достаточно плотная группировка, — на фонде 20^th Century Growth. Отсюда следует, что для более подробного рассмотрения группировок следует задать их количество равным 3.

Рис. 7. 22. Дендрограмма, полученная методом Варда для одного кластера

Дважды щелкнем на рисунке для минимизации размеров окна.

Щелкнем правой кнопкой мыши на окне сводки кластерного анализа — появится окно диалога для задания параметров проводимого исследования.

Изменим количество кластеров (Number of Clusters) с 1 до 3.

Нажмем кнопку OK. В соответствии с введенными изменениями будут произведены табличные преобразования (Рис. 7. 23 и 7. 24).

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

Например, по координатам центроидов (Рис. 7. 24) можно судить о том, какие переменные играют наиболее важную роль в каждом кластере. В частности, в первом кластере видно, что расходы были разумными: несмотря на низкие доходы в 1990 году, заметно, что в других годах состояние фондов 1‑го кластера постоянно улучшалось. Также в первом кластере индицируется самый низкий рейтинг риска среди всех кластеров, а налоговые сборы были тоже достаточно невысокими.

Рис. 7. 23. Сводка кластерного анализа (верхняя часть)

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

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

Рис. 7. 24. Сводка кластерного анализа (нижняя часть)

Нажмем кнопку табличных опций (вторая слева в верхнем ряду). Система предоставит соответствующее окно диалога.

Установим Membership Table (таблица принадлежности наблюдений), затем нажмем кнопку OK.

Дважды щелкнем левой кнопкой мыши на таблице населенности для максимального раскрытия окна.

В данной таблице описаны выбранные параметры кластерного анализа и затем дается полный список всех наблюдений, их имена и номера кластеров, в которые входят указанные наблюдения (Рис. 7. 25)