И.Д. Мандель - Кластерный анализ (1185344), страница 25
Текст из файла (страница 25)
Поэтому целесообразно перед использованием рассмотренных процедур убедиться в наличии корреляций в исходных данных (это не касается критериев (2.3) — (2.5)). 2.4. ЭКСПЕРИМЕНТАЛЬНОЕ СРАВНЕНИЕ КЛАСТЕР-ПРОЦЕДУР ЗЛЛ. ПОСТАНОВКА ЗАДАЧИ И РАЗВИТИЕ ИДЕЙ Как видно из 2.2, 2.3, теория классификации наблюдений далека от завершения, а подавляющее большинство алгоритмов лежит вне каких-либо обобщений. Наиболее перспективным представляется путь синтеза теоретических представлений с обширными экспериментальными исследованиями. В них можно выделить несколько направлений.
1. Реальные массивы данных с неизвестной структурой. Берется какой-либо набор данных и обрабатывается разными алгоритмами. Результаты сравниваются между собой или с экспертным разбиением, если оно имеется. Понятно, что этот способ малоубедителен для общих выводов, но очень полезен в конкретном исследовании, где близость результатов почти всегда говорит о наличии структурированности в данных. 2.
Реальные массивы данных с известной структурой. Существует несколько опубликованных массивов данных, на которых уже опробывались различные алгоритмы классификации и которые поэтому могут служить хорошими тестами для проверки новых процедур. Это матрица 19 социологических параметров Каля — Дейвиса [84, 103] — см. 3.1; матрица четырехмерных данных по 150 ирисам Фишера [84[; некоторые наборы данных Меззиха [84[ и др.
Число приз- Ю7 нанных наборов весьма невелико, и по каждому из них имеется разное количество сравнений. Данные такого типа, безусловно, весьма привлекательны, но и они не могут убедительно ответить на вопрос о качестве алгоритмов в общем случае, так как успешное разбиение на конкретной выборке не гарантирует успеха на другой. 3. Искусственные массивы данных с известной структурой. Подбираются массивы данных (обычно двумерные), в которых кластеры выделяются визуально, а затем сравниваются результаты работы нескольких процедур [125 и др.). Такой подход важен прежде всего для сопоставления формальной и человеческой классификации. Но как раз прямое участие человека в формировании каждой выборки предопределяет ограничения подхода — трудно установить устойчивые характеристики алгоритмов, связанные со случайным разбросом.
К тому же двумерная ситуация не является универсальной. 4. Искусственные массивы данных с известной структурой, генерируемые на ЭВМ и обрабатываемые в режиме ста-истического моделирования. Решается задача типа 3, но задаются не отдельные кластеры, а общие свойства кластерной структуры, данные генерируются на ЭВМ в режиме многократного воспроизведения.
Этот путь органически сочетает в себе различные черты вышеописанных подходов н выглядит наиболее предпочтительным. Можно выделить два направления в сравнении процедур на сгенерированных данных. В первом работа идет с некоторой «хорошо устроенной» матрицей расстояний, на которую накладываются искажения, обычно в форме нормально распределенной ошибки [!21, 114) .
Во втором генерируются непосредственно точки в многомерном простраястве, структурированном определенным образом, причем исходная структура может искажаться различными контролируемыми способами [127, 144, 140, !34). Последний способ более универсален, так как позволяет строить самые разнообразные структуры и вводить ошибки любых типов. При дальнейшем расширении работ по данной проблематике следует учесть два обстоятельства: необходимость вовлечения в расчеты новых алгоритмов кластеризации и желательность сравнения уже проверенных алгоритмов на новых типах сгенерированных данных. Рассмотрим результаты, полученные нами в [58]. 2.4Л. схемА ГенеРАции дАнных И СРАВНЕНИЕ АЛГОРИТМОВ Объекты генерируются в гн-мерном гиперкубе, каждая вершина которого имеет координаты по осям, равные 0 или 1. Плоскостями, проходящими через центр куба и середины ребер, ортогонально им куб разделен иа 2" «маленьких кубиков», каждый из которых является зоной размещения одного кластера.
Собственно генерация происходит следующим образом. Задается число классов й и число наблюдений л!. Случайно отбирается й кубиков, в которых фиксированы центральные точки. !08 3атем с помощью датчика равномерно распределенных случайных чисел выбирается пт длин интервалов по всем признакам в каждом кластере.
Интервалы задают область изменения значений переменных в кластере относительно его центра, совпадающего с центром кубика, в обе стороны симметрично. Таким способом формируются центрированные гиперпараллелепипеды («ящики») со случайными координатами. Эти координаты вершин «ящиков» снова подаются на вход процедуры рандомизации в качестве крайних значений равномерного распределения, после чего формируется требуемое количество точек в классе лг, которое определяется пропорционально доле данного «ящика» в суммарном объеме всех других.
Величину интервалов, задающих удаление от центров классов, можно менять так, что она будет регулировать плотность класса, например, разрешать границами «заступать» в соседние кубики или, напротив, не доходить до их граней и т. д.
Кроме точек, попадающих в кластеры, генерируются также шумящие объекты, координаты которых равномерно распределены на всем интервале (О, 1). Их количество задается от общего числа классифицируемых объектов в процентах; эти объекты предназначены только для того, чтобы «сбнвать с толку» алгоритмы классификации, но в расчете различных показателей, связанных с разбиением, не участвуют.
Рассмотренная схема непосредственно гарантирует изолированность и внутреннюю компактность кластеров, причем ими можно управлять, меняя границы интервалов по всем признакам (в [140] изолированность достигается более сложными приемами). После генерации данных и их обработки каким-либо алгоритмом требуется сравнить результаты сгенерированного и полученного разбиений. Как и в [140], сравнение осуществлялось с помощью коэффициента близости разбиений, полученного как единица минус нормированное расстояние Хемминга между классификациями. В зарубежной литературе эта величина известна как коэффициент Рэнда !!461. Однако практически такой же козффнцнент был предложен Б. Г.
Миркиным в !60! эа два года до !!46). Кроме этого нами использовался коэффициент сопряженности Крамера, основанный на статистике кэ [61]. Внутренним критерием качества классификации является сумма внутрикластерных дисперсий по всем признакам (г"! в 2.5) точнее, рассчитывается не сама эта величина, а отношение дисперсии алгоритмического разбиения к дисперсии сгенерярованной выборки.
Хотя очень редко (в 1 — 2 ог' случаев) алгоритм выделяет классы, более плотные, чем сгенерированные (т. е. с меньшей дисперсией), можно считать, что чем ближе такой показатель к единице, тем лучше проведено разбиение. В табл. 2.5 приведены конкретные параметры наших и более ранних экспериментов. !09 Т а бл и ца 2.6. Управляемые параметры расчетов в разнмх схемах моделирования работы алгоритмои классификаций Принимаемые значения в схемах № п/и Параметр И. Манделя Л. Черного [58) Г. Миллнга- Ф. Кьюипена [140, ра, Л.
Фише- 141) ра [127) ' Число признаков Число кластеров Число наблюдений в одной сгенериро- ванной выборке Число генерируемых выборок при фик- сированных значениях остальных оа- раметров доля шумяших объектов, в о4 к объ- ему выборки Число сравниваемых алгоритмов Характер распределения в кластере 3,5,7 3,5,7 4, 6, 8 2, 3, 4, 5 2, 3, 4, 5 2, 3, 4, 5 20 10,30 О, 20, 40 !4 равномерное 15 6 нормальное нормальное Предлагаемая нами в табл. 2.6 схема (гр. 3.) отличается от двух других (гр.
4, 5) способом генерации, характером распределения и особенностью расчета. На каждый фиксированный набор параметров в [140) произведен расчет лишь по одиой выборке. Г. Миллиган использовал и другие типы задания в данных ошибок, кроме введения шумяших объектов (искажение расстояний, ведение новых переменных и др.).
Из этого видно„что степень статистической подтвержденности каждой выдвигаемой гипотезы у него недостаточно велика. В обшей сложности им расклассифицировано около !000 наборов данных, на которых меняется 8 параметров; в нашей схеме было обработано около 2000 выборок при изменении 4 параметров, поэтому есть основания считать полученные выводы статистики более устойчивыми. 2.4.2. Результаты эиспериментдпьнОГО сРАВнения Сравнивалась работа 14 достаточно популярных алгоритмов классификации, часть из которых подвергалась экспериментальному сопоставлению раньше (в скобках приводится номер алгоритма по табл. 2.3). А) — метод й-средних, вариант Болла и Холла (алг.
34). А2 — метод й-средних, вариант Мак-Кина (алг. 35). АЗ вЂ” метод А1, объединенный с алгоритмом Боннера (алг. 54), порог равен 0,25. А4 — метод й-средних, вариант Хартигана (алг. 36). В алгоритмах А1, А2, А4 выбор начальных й центров класса осушествлялся по эвристической схеме (алг. 40). А5 — метод ближнего соседа (алг. 2). А6 — метод дальнего соседа (алг. 3).
11О ' Приводимые параметры не варьировались в полном объеме друг с другом; в основном в [127] работа шла с двумерными даннымн. х х ! ! А7 — медиана (алг. 7). А8 — простое среднее (алг. 6). А9 — групповое среднее (алг. 5). А10 — центроид (алг. 4). А!1 в метод Уорда (минимизации приращения дисперсии) (алг. 8). А12 — метод А( при случайном выборе центров классов. А13 — метод А2 при случайном выборе центров классов. А!4 в метод А! с предварительным выбором разбиения по «центроиду», который представляет собой искусственную ось в пространстве параметров, полученную сложением отдельных показателей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
