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

Понятно, что при другом способе нормирования результаты будут иными. 4.3.2. ПРОБЛЕМА АДЕНВАТИОСТИ МЕР БЛИЗОСТИ Расстоянием (метрикой) между объектами в пространстве параметров называется такая величина с(аь, которая удовлетворяет аксиомам: А! с(,ь)0, й =0; А2. йаь=йьа,' АЗ. йаь+иьс .й., (неравенство треугольника). Мерой близости (сходства) обычно называется величина р,ь, имеющая предел и возрастающая с возрастанием близости объектов. Приведем возможное определение [1091: 1 2 3 4 з а х1 Рис.

1.5. Классификация: а — по исходны данным; Ь вЂ” по стандартнаоаанным дан ным 28 ВП р ь непрерывна, т. е. малому изменению положении точек в пространстве отвечает малое изменение меры; Вг. р.ь=р; ВЗ. О:=р.ь~к р.,=з- =Ь. Заметим, что АЗ не является конструктивным требованием: оно почти никогда не учитывается в расчетах, и в принципе пригодны измерители близости, не удовлетворяющие неравенству треугольника. Требование непрерывности для 1л может быть распространено и на метрики, однако в обоих случаях оно не универсально — в пространствах номинальных признаков о' и 1л могут принимать, видимо, только дискретные значения.

Существует возможность простого перехода от расстояний к мерам близости: достаточно применить, например„преобразование р — — 1/(1+д). Обратное также справедливо, но не все вычисленные через )з расстояния будут удовлетворять АЗ. Поскольку любую меру близости можно рассматривать как порожденную некоторым расстоянием, дальнейшие результаты приведем в терминах и, не нарушая общности. Все вышеприведенные примеры касались фактически одной проблемы: можно ли сконструировать такой показатель близости между объектами, который не зависел бы от способа измерения переменных.

Если такой показатель возможен, то его использование будет давать одинаковые результаты при любых допустимых преобразованиях шкал, вроде изображенных на рис. ! А и 1.5. Такая постановка является типичной для теории измерений [69] в ее прикладном аспекте: 'любые показатели и алгоритмы в принципе должны быть проверены на адекватность относительно допустимых преобразований. Не вполне строго будем считать, что адекватной является статистика, либо не меняющаяся при допустимых . преобразованиях шкал, либо меняющаяся контролируемыль образом.

Примером статистики, адекватной в первом смысле, является линейный коэффициент корреляции, величина которого не меняется при любых линейных преобразованиях шкал (т. е. он адекватен в шкалах отношений и интервалов [69] ). Во втором смысле адекватной является в этих же шкалах среднее арифметическое: скажем, при изменении масштаба в К раз во столько же раз меняется и среднее. Имеются ли адекватные статистики для измерения расстояния между объектами? Основные результаты получены в [109]. Если исходные значения показателей на объектах обозначать через х, у ..., а полученные допустимым преобразованием шкал— х', у' ..., то адекватной назовем такую меру сходства (удовлетворяющую аксиомам Вт' — ВЗ), что если 1л„„(1ь,ь, то 1ь,,„,(1ь,,, (допустимые преобразования не меняют отношения нестрогого порядка на множестве пар объектов).

Это требование, как видно, менее сильное, чем требование совпадения значений. Основное утверждение [!09] можно сформулировать в следующей теореме: класс адекватных мер сходства для шкал порядка (при лт)1), интерва- лоа и отношений (при т в2) пуст. Пример адекватной меры при пх=! для шкалы отношений: !а=1/(1+х~ — хх) (гп — число признакои; допустимые преобразования шкал указаны в табл. 1.1). Предлагаемые и [69] адекватные статистики типа косинуса угла между векторами, соединяющими точки с началом координат, действительно не зависят от линейных преобразований пространства, но и не являются мерами сходства в формальном и содержательном отношениях.

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

также [33, с. 19]). Итак, теорема приводит к весьма неутешительным выводам относительно теоретической и практической ценности всевозможных метрик: результаты работы алгоритмов классификации могут непредсказуемо меняться в зависимости от такого, вообще говоря, случайного обстоятельсгиа, как выбор того или иного способа измерения показателей'.

Поэтому универсальные правила выбора той или иной меры отсутствуют; конкретные особенности мер близости рассмбтрены и 1.3.2, а рекомендации по их обоснованию — в 4.2.2. тдсз. хдрдктвристики влизостм овъвктов Рассмотрим основные способы определения близости между объектамн. В табл.

1.3 приведены некоторые употребительные расстояния и меры близости, используемые для признаков, измеренных в разных шкалах. Материал таблицы не претендует на широту обзора; 27 мер сходства приведены и [21], около 50 — а [47]; традиционные меры и расстояния для количественных шкал описаны в [33, 62, 5 и др.]. Попытаемся охарактеризовать специфику некоторых приведенных показателей.

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

Другой (классический) пример — определение расстояния между домами по кварталам, а не напрямик; особыми статистическими и геометрическими свойствами. С помощью линейной метрики лучше всего выделяются «плоские» клас- ' Близкие в идейном смысле результаты получены в: Сатаров Г.

А. Сравнение двух алгоритмов шкалирования дихотомических данных//Математические методы в социологических исследованиях. — Мл Наука, !98Ь вЂ” С. 90 — 98. теры, расположенные почти на гиперплоскостях, особенно если они ортогональны каким-либо координатным осям. Если есть основания предполагать, что кластеры имеют такую форму, есть смысл исполь- зовать такую метрику.

Т а б л н ц а 1.3. Характеристика близости ебъшпов ио набору признаков, измеренных в разлвчнык шкалах' Формулы Показатели для количественных шкал (расстояния) [33] с( ..= ~~ ]х! — х!1 ц(=~, ! г=! Линейное расстояние Евклидова расстояние м Н, =(гг„(к.— к!) ) р Обобщенное степенное расстояние Мин- ковского !(м..— — (х,— х.) йг (х! — х.) Рассгояние Махаланобиса (меры сходства) [21, 47] ря=р,/т Для номинальных шкал Коэффициент Рао Коэффициент Хеммиига Кгвффициент Роджерса — Таниного Коэффициент Жаккарда Для произвол ьных шкал рг= ~Р а, !=! т Л,. = 4~~~ о ]Л!4/т ! ! «ч=~ 4,'т г= ! Мера близосги Журавлева [3б] Мера близости Воронина [21] Мера близости Миркина [б3] 31 ' к[ — значение !го признака у !го объекта, 1= 1,т;!, ] =1л; х, — векторстолбец значений всех признаков на г-и объекте; йГ ' — матрица, обратная ковариацнонной; ро — общее число совпадающих значений свойств (нулевых и единичных, где 1 — наличие свойства, Π— отсутствие); л" — число совпадающих единичных свойств; л' — число единичных значений свойств; 1, если )х — х!!)(еъ ] О в любом другом случае; Евклидово расстояние является самой популярной метрикой в кластерном анализе: оно отвечает интуитивным представлениям о близости и, кроме того, очень удачно вписывается своей квадратичной формой в традиционно статистические конструкции.

Геометрически оно лучше всего объединяет объекты в шарообразных скоплениях, которые весьма типичны для слабо коррелированных совокупностей. На рис. 1.ба приведены два разбиения. Предположим, требуется разбить совокупность на две группы и классификацию провести каким-либо обычным объединяющим алгоритмом типа ближнего соседа. По линейному расстоянию объединятся как ближайшие все объекты на одной линии. По евклидову же расстоянию сначала объединятся объекты ! н 2 и т. д.

(нз разных линий); скачок в,расстояниях возникает только на границе между точками 3 — 5 и 4 — 6, поскольку там небольшой сдвиг. Видно, что результаты классификации кардинально противоположны, причем более ценно разбиение по линейной метрике. Обобщенное степенное расстояние представляет только математический интерес как универсальная метрика. Во всяком случае нам не известны примеры его использования при произвольных РФ!,2,оо (в последнем случае г( переходит в так называемую супремум-норму с( „=шах(хг — х(1 которая может представлять интерес).

Расстояние Махаланобиса является своеобразной конструкцией. Рассмотрим эту метрику подробнее. На рис. 1.66 изображены 6 точек, распадающихся на 2 класса (см. табл. !.4). Как видно, разница между матрицами очень заметная. Если по матрице с( можно легко выделить классы, видимые и на рис. 1.бб, в и Рис. 1.6. Зависимость результатов нлассификации от формы расстояния между объектами. Классификация объектов на два класса: а — по линейной (сплошная линия) и евклидовой (пуннтир) метрикам; б — по евклидовой или линейной метрикам )х( — х, '( где е~ — значение порога для (-га признака; Лт= 1 — ' — мера хг — хг близости объектов по (-му признаку (для номинальных признаков х~= ! в случае совпадения значений; Π— в случае несовпадения); ог — информационный вес признака, рассчитанный определенным образом; д,', для количественного признана определяется как х)х, '(х' нормированы стандартным образом), а для номинального признака при несовпадении значений — д,',=О, при совпадении (т.

е. при попадании значений в з-ю градацию, з= 1,т~) д~,= 1/п(~я~ в 1, где и,' — число наблюдений в з-й градации, тг — число градаций. Величина рн получена из некоторых модельных соображений (см. 163, с. 83 — 931, а также 2.3А). 32 Т а бл н ца 1.4. Матрацы расстанная меноту точаамн, наебраженнымн на рнс. 1.Вб а — еехлнлоео расстоянае б — расстояние Махаланобнса то по матрице Нм — весьма произвольно. Существенно, что при переходе от Ы к д сильно уменьшилось расстояние с( ае стянувшее классы. Поэтому возможны такие разбиения, как 1, 2, 3, 4/5, 6 (пунктир в табл.

1.4б) и др. Общая согласованность между порядкам'и расстояний в двух матрицах (так называемый кофенетический коэффициент корреляции) невелика — коэффициент Спирмена между упорядочениями расстояний равен 0,6!. Такая рассогласованность может приводить, естественно, к различным результатам классификации. Причина расхождения заключается в особенности расстояния с( . Если считать, что все признаки не коррелированы, то можно убезт зт диться, что лм = †' +... + , где Л~ — разница значений 1-го приза от от 1 м пака у двух объектов, т. е. евклидово расстояние по каждой оси уменьшается пропорционально дисперсии. Это приводит к своеобразному уравниванию всех признаков, напоминающему процедуру нормирования г'. Такое свойство корректировки может оказаться полезным в ситуациях, когда, например, после нормировки сохраняется большая разница в дисперсиях, которую желательно нивелировать.

И, наоборот, при стандартной нормировке и нулевых связях с( =с(м. Но в целом процесс корректировки расстояний является малоуправляемым. Могут возникать курьезные ситуации типа изображенной на рис. 1.6: расстояние между точками 3 и 4 становится вдруг существенно меньше, чем между точками 2 и 3 (см. табл. 1.4), несмотря на сильную коррелированность признаков (0,986).