5.2. Расстояния между отдельными объектами и меры близости объектов друг к другу

Наиболее трудным и наименее формализованным в задаче автоматической классификации является момент, связанный с определением понятия однородности объектов.

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

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

Конечно, выбор метрики (или меры близости) является узловым моментом исследования, от которого решающим образом зависит окончательный вариант разбиения объектов на классы при заданном алгоритме разбиения. В каждой конкретной задаче этот выбор должен производиться по-своему. При этом решение данного вопроса зависит в основном от главных целей исследования, физической и статистической природы вектора наблюдений X, полноты априорных сведений о характере вероятностного распределения X. Так, например, если из конечных целей исследования и из природы вектора X следует, что понятие однородной группы естественно интерпретировать как генеральную совокупность с одновершинной плотностью (полигоном частот) распределения, и если к тому же известен общий вид этой плотности, то следует воспользоваться общим подходом, описанным в гл. 6. Если, кроме того, известно, что наблюдения извлекаются из нормальных генеральных совокупностей с одной и той же матрицей ковариаций, то естественной мерой отдаленности двух объектов друг от друга является расстояние махаланобисского типа (см. ниже).

В качестве примеров расстояний и мер близости, сравнительно широко используемых в задачах кластер-анализа, приведем здесь следующие.

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

Здесь — ковариационная матрица генеральной совокупности, из которой извлекаются наблюдения а А — некоторая симметричная неотрицательно-онределенная матрица «весовых» коэффициентов , которая чаще всего выбирается диагональной [195, 279].

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

Обычное евклидово расстояние

К ситуациям, в которых использование этого расстояния можно признать оправданным, прежде всего относят следующие:

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

компоненты вектора наблюдении X однородны по своему физическому смыслу, причем установлено, например с помощью опроса экспертов, что все они одинаково важны с точки зрения решения вопроса об отнесении объекта к тому или иному классу;

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

«Взвешенное» евклидово расстояние

Обычно применяется в ситуациях, в которых так или иначе удается приписать каждой из компонент вектора наблюдений X некоторый неотрицательный «вес» <ой, пропорциональный степени его важности с точки зрения решения вопроса об отнесении заданного объекта к тому или иному классу. Удобно полагать при этом .

Определение весов связано, как правило, с дополнительным исследованием, например получением и использованием обучающих выборок, организацией опроса экспертов и обработкой их мнений, использованием некоторых специальных моделей. Попытки определения весов только по информации, содержащейся в исходных данных [72, 330], как правило, не дают желаемого эффекта, а иногда могут лишь отдалить от истинного решения. Достаточно заметить, что в зависимости от весьма тонких и незначительных вариаций физической и статистической природы исходных данных можно привести одинаково убедительные доводы в пользу двух диаметрально противоположных решений этого вопроса - выбирать пропорционально величине среднеквадратической ошибки признака либо пропорционально обратной величине среднеквадратической ошибки этого же признака [332, 72, 330].

Хеммингово расстояние. Используется как мера различия объектов, задаваемых дихотомическими признаками. Оно задается с помощью формулы

и, следовательно, равно числу несовпадений значений соответствующих признаков в рассматриваемых объектах.

Другие меры близости для дихотомических признаков.

Меры близости объектов, описываемых набором дихотомических признаков, обычно основаны на характеристиках , где — число нулевых (единичных) компонент, совпавших в объектах X, и Так, например, если из каких-либо профессиональных соображений или априорных сведений следует, что все признаков исследуемых объектов можно считать равноправными, а эффект от совпадения или несовпадения нулей такой же, что и от совпадения или несовпадения единиц, то d качестве меры близости объектов используют величину

Весьма полный обзор различных мер близости объектов, описываемых дихотомическими признаками, читатель найдет в [136, 29].

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

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

в противном случае, то с помощью этой функции удобно строить обычные эмпирические гистограммы (оценки плотности распределения по имеющимся наблюдениям Действительно, легко видеть, что

где — число наблюдений, попавших в класс содержащий точку — объем области (геометрическая интерпретация для одномерного случая показана на рис. 5.1).

Если в исследуемом факторном пространстве задана метрика , то можно не связывать себя заранее зафиксированным разбиением на классы, а задавать как монотонно убывающую функцию расстояния .

Например,

Приведем здесь еще лишь одну достаточно общую форму связи между , в которой расстояние выступает как функция некоторых значений потенциальной функции К:

Рис. 5.1, Гистограмма построенная с помощью разбиения на группы выборочной одномерной совокупности

В частности, выбрав в качестве скалярное произведение векторов U и V, т. е. положив

получим по формуле (5.3) обычное евклидово расстояние .

Легко понять, что и в случае задания потенциальной функции в виде соотношений (5.2) формулы (5.1) позволяют строить статистические оценки плотности распределения (5.1), хотя график функции будет уже не ступенчатым, а сглаженным. При отсутствии метрики в пространстве функции могут быть использованы в качестве меры близости объектов и и V, а также объектов и целых классов и классов между собой.

В первом случае эта мера позволяла получить лишь качественный ответ: объекты близки, если U и V принадлежат одному классу, и объекты далеки — в противном случае; в двух других случаях мера близости является количественной характеристикой.

О физически содержательных мерах близости объектов. В некоторых задачах классификации объектов, не обязательно описываемых количественно, естественнее использовать в качестве меры близости объектов (или расстояния между ними) некоторые физически содержательные числовые параметры, так или иначе характеризующие взаимоотношения между объектами. Примером может служить задача классификации с целью агрегирования отраслей народного хозяйства, решаемая на основе матрицы межотраслевого баланса [97]. Таким образом, классифицируемым объектом в данном примере является отрасль народного хозяйства, а матрица межотраслевого баланса представлена элементами где под подразумевается сумма годовых поставок в денежном выражении отрасли в . В качестве матрицы близости в этом случае естественно взять, например, симметризованную нормированную матрицу межотраслевого баланса. При этом под нормировкой понимается преобразование, при котором денежное выражение поставок из отрасли в заменяется долей этих поставок по отношению ко всем поставкам отрасли. Симметризацию же нормированной матрицы межотраслевого баланса можно проводить различными способами. Так, например, в [97] близость между отраслями выражается либо через среднее значение их взаимных нормированных поставок, либо через комбинацию из их взаимных нормированных поставок.

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

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

Чаще всего в подобных ситуациях в качестве мер близости между отдельными признаками так же как и между наборами таких признаков, используются различные характеристики степени их коррелированности и в первую очередь коэффициенты корреляции. Проблеме сокращения размерности анализируемого признакового пространства специально посвящен раздел III книги. Более подробно вопросы построения и использования расстояний и мер близости между отдельными объектами рассмотрены в [136, 288, 296, 29].