И.Д. Мандель - Кластерный анализ (1185344), страница 26
Текст из файла (страница 26)
Такой быстрый прием иногда рекомендуется для начала работы алгоритмов й-средних. Расчеты проводились в предварительном и окончательном вариантах на ЭВМ ЕС-1020 и ЕС-1060'. Опишем их основные результаты. Оби(ая характеристика расчетов. На предварительном этапе выяснилась бесперспективность процедур А12 — А!4. Разбиения, полученные с их помощью, резко отличались по всем параметрам от разбиений, полученных другими алгоритмами. Это вполне согласуется с результатами 11401, где также отмечена неэффективность случайного выбора центров классов. Поэтому для очень популярных процедур типа й-средних надо прежде решать дополнительную задачу о выборе подходящего начального разбиения. Эвристика А14 для такой цели явно не годится. Поэтому в целях экономии в дальнейшем изложении алгоритмы А12 — А!4 будут опущены.
Т а б л и ц а 2.7. Зависимость крмтернев качества от числа признаков и числа классов (уровень шума !Оох5)' й-средних Аз ближний сосед А5 Число классов Число призна- ков метод Уорда А!1 групповое среднее А9 9! 73 73 63 55 50 95 86 87 74 74 69 1,!6 1,62 1,68 2,57 2,30 2,64 90 85 85 97 89 94 1,05 1,17 1,18 1,05 1,17 1,05 2,2! 2,94 2,87 5,27 4,48 4,79 90 90 91 80 82 80 78 60 59 35 28 21 93 94 96 98 97 92 86 77 74 70 65 60 1,19 1,46 1,55 2,29 1,92 2,08 79 65 70 5! 50 43 ' Программное обеспечение осушествлено главным образом А. Зыряновым с участием Л.
Черного; расчеты выполнены А. Зыряновым и Н. Шишковой. ' К, Х вЂ” средние значения коэффициентов Крамера и Хемминга, умноженные на 100; Д вЂ” отношение внутриклассовой дисперсии алгоритмического разбиения к дисперсии сгенерированного разбиения. Зависимость качества классификации от размерности пространства и числа классов. Из табл. 2,7 легко видеть, что для всех алгоритмов, кроме А11, показатели почти монотонно меняются от первой строчки к последней: К, Х снижаются, Д растет, то есть по мере уменьшения числа классов и увеличения размерности пространства качество классификации снижается. Этот вывод подтверждается и на всех других алгоритмах.
Что касается А! 1, то он, как видно, постоянно дает значения критериев, близкие к наилучшим (см. подробнее ниже), так что их колебания можно считать случайными. Зависимость величины Х от числа классов была замечена н раньше [127] и в определенной мере (но не полностью) объясняется особенностями самого коэффицлента.
То же самое можно сказать о коэффициенте к, который уменьшается с уменьшением числа классов. Но коэффициент Д по своему построению никак не связан с числом классов, хотя имеет такую же четкую тенденцию. Следовательно, отмеченная зависимость связана с характером процесса классификации. Зависимость критериев качества от размерности пространства раньше практически не изучалась.
По нашим данным эта зависимость существенна (хотя в целом ниже, чем от числа классов), причем более заметно проявляется прн большом числе классов, что обусловливается не видом используемых коэффициентов, а реальными свойствами разбиений. Полученные выводы не вполне тривиальны и нуждаются в обосновании. Скорее всего эффект размерности связан с увеличением общего объема, занимаемого кластером, ростом расстояний по абсолютной величине, благодаря чему возрастает и общий разброс в матрице расстояний. Для евклидова пространства это справедливо и в формальном отношении [54]. Поэт!)му алгоритмы чаще сбиваются и отходят от истинной структуры.
Положительное влияние роста числа классов на уровень восстанавливаемости можно объяснить особенностями работы алгоритмов. Иерархические процедуры агломеративного типа почти не ошибаются на первых шагах (когда объединяются ближайшие объекты) и с большей вероятностью могут сбиться на последующих, когда число классов становится меньше. Процесс переноса объектов из класса в класс в алгоритмах й-средних при большом числе классов становится куда более вариативным, чем при малом, что создает возможность достижения более глубокого оптимума качества классификации. В целом можно сделать вывод, что следует стремиться обрабатывать массивы невысокой размерности 'и выделять по возможности достаточно большое число классов — результаты будут надежнее.
Первая часть вывода вполне согласуется с концепцией работы в сокращенных пространствах (факторов или исходных признаков— см. 3.1), а вторая — с положением о том, что лучше выделить больше кластеров, чем их есть на самом деле, так как при этом не происходит потери информации [14! ] .
Взаимосвязи критериев качества. Определялись коэффициенты линейной корреляции между критериями качества классификации. В Табл ц ца 2.8. Связь между ноказателямн качества класснфнкацнн !чцсло признаков 7, доля шума !Оош коэффнцценты умножены на 100) Коэффициенты Крамера н Хем- 1Крамера — отноше-1 Хеммннга — отномцнга 1 нця дисперсий 1 шення дисперсий Среднее модулей Алгорнтмы число классов 5 7 — 63 — 64 — 47 — 60 — 50 — 63 — 65 — 67 — 75 — 73 — 79 — 86 — 84 — 83 — 75 — 46 — 82 — 59 — 63 — 84 — 72 — 73 — 67 — 84 — 85 — 79 — 51 — 78 — 75 — 85 — 80 — 83 — 61 — 80 — 76 — 83 — 72 — 80 — 77 — 76 — 85 — 89 — 90 — 61 — 61 — 72 — 61 — 64 — 46 — 59 — 65 — 74 — 67 — 73 — 80 71 73 66 67 52 68 68 71 74 77 67 59 67 52 60 76 45 81 67 60 86 46 — 70 — 71 — 67 — 55 — 18 — 74 — 44 — 56 — 66 — 64 — 89 79 79 78 74 47 72 71 79 76 80 68 56 56 34 63 58 59 72 63 68 73 49 А! А2 Аз А4 АБ Аб А7 АБ А9 А10 А11 Среднее модулей 77 79 73 61 73 64 Общие средние 113 табл.
2.8 числа представляют корреляции, рассчитанные на множестве из 50 выборок, по каждой из которых после классификации определялись К, Х, Д. Как видно, связи К вЂ” Х и К вЂ” Д в целом не очень высокие, то есть коэффициент Крамера недостаточно тесно связан с внутренним критерием качества. Существенно выше связи Х— Д, что подтверждает тезис в [141] о пригодности коэффициента Хемминга для восстановления кластерной структуры.
У отдельных алгоритмов в среднем похожий уровень согласованности критериев, за исключением А5, у которого она существенно ниже. В целом видно, что коэффициенты отражают различные аспекты близости разбиений. Близость алгоритмов классификации. В табл. 2.9 приведены две матрицы линейных корреляций между характеристиками разбиений, полученных разными алгоритмами.
Над диагональю — коэффициенты корреляции между коэффициентами Хемминга, под диагональю— между относительными дисперсиями. Видно, что связь между различными алгоритмами слабая. Можно выделить только две пары алгоритмов, дающих сравнительно близкие результаты (это подтверждается и при других параметрах): А1 — А2 и в меньшей степени А9— А10. Остальные алгоритмы могут дать рассогласованные результаты. В целом этот вывод является довольно неожиданным.
Правда, Т а 6 л н ц а 2.9. Матрица корреляций между характеристиками разбиений, полученных разными алгоритмами (число признаков 7, число классов 7, доля шума 10%) Козффициенты Хеммннга Алгорит- мы А1 А4 А5 А2 АЗ Аб А7 А8 А9 А10 А!1 26 38 30 27 89 42 45 29 28 43 44 43 49 34 23 40 42 45 43 31 50 43 5! 40 27 46 57 58 37 43 55 39 48 63 49 66 29 32 43 38 52 33 42 54 73 35 32 16 30 !4 42 45 46 23 !8 А! А2 АЗ А4 А5 Аб' . А7 А8 А9 А10 А11 88 31 30 19 !9 20 48 30 30 30 42 33 33 20 26 52 37 31 25 50 19 !9 19 42 44, 41 15 33 08 31 37 32 34 21 04 12 33 26 36 О! 46 31 44 12 34 33 32 26 20 54 44 21 54 36 !7 Козффициеиты отношений дисперсий 114 точно измерять связь между алгоритмами следует непосредственно по матрицам парной сопряженности классификаций.
Из-за технических сложностей такие расчеты не проводились. Коэффициенты корреляции в табл. 2.9 говорят лишь о том, например, что изменение коэффициента Х и алгоритма А1 на разных выборках плохо согласуется с изменением этого же коэффициента у алгоритма А4 (связь 0,29). Но косвенно это свидетельствует о разнице в разбиениях. Так что данные табл. 2.9 четко говорят о том, что выбор алгоритма классификации является ответственной задачей. Влияние шума на качество классификации.
В табл. 2.10 приведены сведения об изменении двух критериев качества при возрастании шума от 10 до 30%. Для коэффициентов Х число в таблице означает разность коэффициентов при уровнях шума 30 и 10 % (знак « — » говорит о том, что с ростом шума качество снижается); для Д приведены темпы прироста коэффициента (%) при повышении уровня шума, т. е. величина 28 в первой строке означает, что для А! при повышении шума отношение дисперсий возрастает на 28 %, качество классификации ухудшается. Видно, что устойчивость методов к ошибкам снижается в зависимости от роста размерности и числа классов для обоих коэффициентов. Так что сделанная выше рекомендация о надежности выделения большого числа кластеров нуждается в уточнении — уровень качества действительно растет, но растет и чувствительность к возможным ошибкам.
Т а бл и ц а 2.10. Зависимость критериев качества от уровни шума Отношения дисперсий, Л, % Козффицненты Хеммиига, Х При- знаки сред- нее сред- нее 3 7 3 3 7 3 7 — 2,3 — 0,3 — 6,4 — 4,2 — 3,3 — 8,6 Среднее 0,6 34 55 27 20 24 40 Т а 6 л и ц а 2. 11. Уяорядоченне алгоритмов ао сгеаени нк устойчивости к шгзмущеяням Алгоритмы обладают разным .уровнем чувствительности — даже по средним оценкам для дисперсии величина показателя может возрасти в два раза (А5) илн подняться лишь на 13% (АЗ). В табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
