И.Д. Мандель - Кластерный анализ (И.Д. Мандель - Кластерный анализ.djvu), страница 11

Бравермана, А. А. Дорофеюка, И. Б. Мучника и др.— по процедурам типа последовательного формирования кластеров и диагонализации; В. Н. Елкиной, Н. Г. Загоруйко — по эталонным алгоритмам н ряд других исследований. В конце 60-х— начале 70.х годов появился ряд обзоров по проблеме [35, 74, 102 и др.[; особое значение по широте охав~а материалов н комплексности изложения имели обзоры А.

А. Дорофеюка [30) н Р Кормака [1!9), а также [33[. Для 70-х годов характерны уменьшение числа предлагаемых процедур классификации и попытки осмысления уже накопленных алгоритмов и опыта нх применения. В этом смысле типичны работы, посвященные теоретическому и экспериментальному сравнению кластер-процедур (см. 2.4). Установлены соответствия между эвристическими и оптимизационными процедурамн в ряде случаев. Вышел ряд книг, по.разному освещающих различные аспекты кластер-анализа: Н.

Джардайна и Р. Сибсона [136), в которой излагается не столько состояние проблемы, сколько собственная формализованная концепция авторов; М. Андерберга [1!3), Дж. Эверита [125), Г Спата [149), дающих довольно широкое представление о различных методах; расширенное переиздание книги [150) (1973 г.) н др.

Особое значение приобрела монография Дж. Хартигана [131), в которой разбирается множество процедур (главным образом эталонного типа и иерархнческик) н ставится ряд важных теоретических вопросов. В советской литературе наиболее полное н разностороннее изложение узловых проблем кластер-анализа предпринято в книге С. А. Айвазяна, 3. И. Бежаевой, О. В.

Староверова, [5[, а также в определенных аспектах в книгах Б. Г. Миркина [62, 61), И. И. Елисеевой, В. О. Рукавишникова [34[. 44 Последннй период характеризуется уменьшением числа предлагаемых новых процедур прямой кластернзацнн (внднмо, все основные направления уже исчерпаны) н, наоротнв, увеличением колнчества работ, в которых зтн процедуры получают все большую осмысленность (относнтельно нахождения общих свойств с другими алгорнтмамн, особенностей нспользовання, единого программного обеспечения н др.). Сильное развнтне получили иерархические процедуры — очень быстрые алгоритмы, разработанные М. Жамбю н др., позволяющне обрабатывать тысячи объектов ((35).

Интенснвно развивается в трудах Э. Лиде н др. теория »талонных процедур (29). Помимо упомянутых монографий (29, (35) вышли кннгн Б. Г. Маркина (63), И. Ромесбурга (148) н др Прикладное значение процедур прямой классификации остается чрезвычайно большим. Подавляющая часть практических исследований выполнена с помощью именно таких алгоритмов. Их основные преимушества перед оптимизационными и аппроксимационными процедурами заключаются в следующем: относительная простота алгоритмов, их содержательная ясность, что важно для «заказчик໠— процесс классификации происходит как бы у него на глазах; допустимость контролируемого вмешательства в работу алгоритма — изменение параметров, смысл которых обычно понятен (чего не наблюдается в строгих процедурах); возможность визуализации данных и принятия непосредственных решений; выделение классов по дендограмме или по упорядоченной матрице расстояний; невысокая трудоемкость алгоритмов, часто намного меньшая, чем у оптимизационных процедур.

Этот фактор во многих ситуациях является важным; и как следствие перечисленного — высокая содержательная ясность результатов классификации и практические удобства в ее осуществлении. 2.2.2. ОПРЕДЕЛЕНИЕ КЛАСТЕРОВ Рассмотрим возможные способы точного определения кластеров, на выделение которых ориентированы прямые алгоритмы. Ограничимся ссылками на работы, где о них сказано (не обязательно впервые), или дадим формулировку сами.

СЕ Класс типа сгущения [62, с. 235]. Все расстояния между объектами внутри класса меньше любого расстояния между объектами класса и остальной частью множества. В [10] такой класс называется компактной группой, в [70[ — классом типа ядра. На рис. 2.( такими кластерами являются А и В; классы Е и С, Е и М не разделяются с помощью этого определения. Посредством С! нельзя различить не только разнотипные (В и С) или пересекающиеся кластеры (К и Н), но и отличить большие классы от малых (Й и Я).

С2. Класс с центром (модифицированное определение из [70] ). Существует порог т)0 и некоторая точка в пространстве, занимаемом объектами кластера 5~ (в частности, элемент этого множества), х,* такие, что если а 65и топи..«-т, а если а,бА/5и то а„«)т. Здесь а,бА — объект из универсального множества А, б — расстояние. Точка х7 называется центром класса; часто им является центр тяжести, т. е. координаты центра определяются как средние значения признаков у объектов класса. В паре В и С класс В является классом с центром, С вЂ” не является; в паре Е и Р класс 'Р с центром, Š— нет. С3. Класс типа слабого сгущения [62]. Существует т)0 такое, что для любого а,65, найдется такой объект а,65ь что с(л(т, а для любого аьбА/5~ справедливо би)т.

В [70] такие кластеры называются классами типа ленты. Все кластеры типа сгущения являются кластерами типа ленты, но не наоборот. На рис. 2.! слабые сгущения представляют собой В и С, Е и Р, К и Н. С4. Класс типа сгущения и среднем [62]. Среднее расстояние внутри класса меньше среднего расстояния объектов класса до всех остальных объектов. На рис. 2.! многие кластеры являются сгущением в среднем, но в паре Е и Р все наоборот — среднее расстояние Е больше, чем у Š— Р. Сб.

Сильный кластер (модифицированное определение из [63] ). Среднее внутреннее расстояние не менее чем в Ь)! раз меньше, чем среднее расстояние от любого объекта, не принадлежащего классу, до всех объектов класса (в [63] Ь=2). Сб. Класс типа среднего сгущения с центром. 5~ называется классом, если среднее расстояние до центра объектов класса меньше, чем их среднее расстояние до центра остальных объектов А. Понятие по свойствам аналогично С4. С7. Класс типа изолированного облака. Существует т)0 такое, что для всех д, 65~ н б, сА/5~ бч)т. Это определение выдвигает самое слабое требование: независимо от внутренней плотности кластера учитывается только внешняя изоляция. Такими свойствами обладают все непересекающиеся кластеры рис.

2.!. Приведенные типы определений исчерпывают основные способы выделения кластеров, но, конечно, не все. В определениях С4 — Сб среднюю можно заменить медианой, ввести понятие диаметра класса и др. С некоторыми определениями мы познакомимся в 2.2.3. Наличие набора определений понятия кластера подчеркивает особенность кластер-анализа, отличающую его от других разделов многомерной статистики: сильную зависимость результатов расчетов от предварительных установок исследователя на содержательном уровне. Общая гносеологическая проблема унификации научных определений [50, 57] здесь приобретает вполне осязаемый характер.

4в и.з. описании алгоритмов Принятые обозначения и формулы см. в табл. 2.2. Табл и ца 2.2. Условные обозначенна и вспомогательные формулы дли описания алгоритмов кластер-анализа рй п/п Содержание параметра, формула Обозначения а„а,; 1=1. Л" обозначение объекта и его номера; (а„ а,) — неупорядоченная пара объ- ектов; номер признака; обозначения и номера классов; множество номеров объектов 1-го класса; число объектов 1-го класса; л~ — по. роговое значение; матрица расстояний между объектами; д,=о, г(п)0, неравенство треугольни- ка не обязательно (см. 1.2); пороги для расстояний: если г(ч<п', то (о„г(;)~5п расстояние между классамн (произ- вольной формы).

Примеры: среднее попарных расстояний объектов двух классов; обычное расстояние между центрами тяжести классов; расстояние Махаланобиса между двумя выборка- ми с равными матрицами коварнацнй; рч пороговое значение; )7 — порог для расстояния объекта до класса рп' если ра()7, то а,~5ь Варианты измерения р». 1) среднее расстояние объекта до всех объектов иласса; 2) расстояние до центра класса р(аь а ), где а~ — центр тяжести класса; минимальная типичность объекта, представляющего свой класс, опреде- ляется в алгоритме; дисперсия Рго признака в ! классе; а~, — пороговое значение )=1,т 5о 5„5,; 1=1, й й и=!" Алхл А<А<...

Ри !о ой 47 Основные характеристики алгоритмов классификации приведены в табл. 2.3. Алгоритмы сгруппированы в некоторые классы, которые впоследствии обсуждаются. Описание алгоритмов в соответствии с табл. 2.3 (обозначения см. в табл. 2.2) проводится обычно по схеме: первый шаг или начальное состояние; р-й шаг, критерий останова (КО). Ф Х Ф 6 Х Х й. 1- са са са а сО со' О д а 2 Х Ф Ф ~ а -х о Х 34 Ф .6 С 2 Ф х Х ХО са СО а а Ос сй 3 О Х Х О. Х о Ф 1 63 а,с Ф о Ф о О. Х Ц Х о о Ф о о,. ф О ФХ ОЭ С асс ЦХ ЗХ а Ф О Х Ф Х Ф 1О Х Ф 63 3 а о О с 48 М Я~ и и Ф 3 В Х Х С Х О Х л х «3 о а а . Х 2 д о «4 О. с 63 2 2 й.

2 Ц а Ф 3 С0 2 3 ХФ оо дс с 3 с О Ф с 1 2 ф х 2 о„са ЬС3 сс сч а Х Ф Ф л Ф Х с о Ф а. д в. а 63 3 цЗ 2 о Ф хо Х сс а 63 о Х рй С'3 8 ЖХ са 33„са 3.3 а,„- й Х Хс о~ 2 О х„- 63 Ф Х ~„а ОХ 2",-О~О Х о. й а хоа 63 а. а а а 2 с;,,а 3 а ха 6 Хай о а Х Ф Ф 2 1< Х а 'Хо х Ха %'* ! 2 Ф М2 о Ф Ы ХФ Х о а 3ОИЙВО 2 36 3 '-й о с о 'а оса 6 ВХ ФХ" "Я Ца. с лс сс 63-2 3И 22 \ 3 а Ф :6 Х С а 6 8'й х а 3 'О Фас ХХЛ Х Ф Фоо а Х а. Фа о Х а. а ЕОФ с О сс О Ос О Ос 3 Х Ф ~Р Ф ° ' о 2; а 33 ФФ Ф Ф о а 2 О.Ф дс Ф Ф ФС а хл а а Ф 2 о 2 ' О.