Классификация объектов в пространстве статистически
зависимых стохастических характеристик
В. А. Никулин
инженер-программист,
ИПУ им. В.А. Трапезникова РАН, г. Москва
Введение
Существует
глубокая аналогия между двумя фундаментальными задачами естествознания — задачей
исследования зависимости случайных величин [2, стр. 182] и задачей классификации множества объектов.
Аналогия эта подмечена давно и многими авторами. В частности, она широко
используется при конструировании непараметрических методов анализа
Вапника–Червоненкиса [1]. Однако впервые разработан и реализован на
вычислительной машине метод, который непосредственно решает обе задачи по
одному алгоритму.
Основания метода
Метод
основан на свойствах нового математического объекта — «пространства, метризованного плотностью вероятности»[1].
Объект непосредственно получается из одномерных распределений вероятности
посредством специального «рангового
преобразования».
; где: (1)
-
— преобразованное значение
координаты;
-
— исходное значение координаты;
-
— значение генерального
распределения вероятности (то есть, вероятность того, что в ходе случайного
испытания по данной оси будет получена координата не превосходящая ).
Для
пространств, построенных из преобразованных осей, А. В. Когановым
доказана специальная Теорема 1
(публикуется с согласия автора): если
все оси характеристического пространства независимы, как полные группы
случайных событий, и только в этом случае, плотность вероятности в
«пространстве, метризованном плотностью вероятности», будет равномерна
(обратное тривиально) [2].
Это
полезное свойство используется для решения двух задач:
-
задачи выявления зависимости (независимости) характеристик, которые
рассматриваются как стохастические случайные величины, и
-
задачи классификации, которая искусственно представляется как
классический мысленный эксперимент по извлечению цветных шаров из «чёрного
ящика» наугад.
Выявление зависимости
(независимости) характеристик
Пусть
имеются 
характеристик,
которые можно считать стохастическими случайными величинами. Причём такими, —
что их множества допустимых значений упорядочены (в простейшем случае — двузначны).
Будем говорить, что на значениях каждой характеристики определено отношение
больше или равно.
Преобразуем
каждую характеристику в соответствии с формулой
; где: (2)
-
и 
— координаты
эмпирических точек на преобразованной оси (численные значения 
‑го и 
‑го рангов, в порядке возрастания);
-
и 
— число
эмпирических точек с ‑ой и ‑ой (в порядке возрастания) величинами рангов;
-
— объём выборки.
Несложно
заметить, что Формула 2 есть своеобразный аналог Формулы 1, —
сформулированный на языке рекурсии и «в терминах» эмпирических частот.
Потому такое преобразование мы также будем называть «ранговым».
Здесь,
вопреки обычной практике, когда непрерывное распределение заменяется дискретным,
мы всегда полагаем, что частотная «масса», сосредоточенная в эмпирической
точке, размазывается по соответствующему интервалу оси. Однако следует пояснить,
что в Формуле 2 эмпирические точки не находятся на правых (бо́льших)
границах своих интервалов, как можно было бы ожидать из Формулы 1, но
смещены к их середине. В самом деле, если не сделать такой поправки, точка с
наибольшей координатой всегда получит максимальный ранг — 1, но в общем
случае нет никакой уверенности, что точки с ещё большим рангом не существуют
(возможно, они просто не попали в выборку). Таким образом, в угоду здравому
смыслу, мы допускаем определённый произвол,
связанный с тем, что генеральное распределение вероятности по интервалу нам
неизвестно, и, следовательно, только одну — эмпирическую точку интервала мы
можем однозначно «привязать» к исходной — не преобразованной оси. На практике,
связанные с этим неудобства не существенны либо устранимы.
Задача
о независимости немедленно будет решена, если в пространстве, построенном из преобразованных
осей (будем называть его далее «ранговым
пространством»), достоверно локализовать моды генеральной плотности
вероятности. Для этих целей используем кластерный анализ с кластерами типа
«слабого сгущения» [3, стр. 46] (существует такое расстояние 
(назовём его «радиусом цельности» кластеров), что
для каждой точки кластера найдётся ещё хотя бы одна точка того же кластера отстоящая
от данной не более чем на , но в других кластерах ни одной такой точки не найдётся).
На практике[3]
также используются две метрики — эвклидова (предпочтительна для непрерывных
пространств) и манхэттенская (предпочтительна для решёток):
; (3)
; где: (4)
-
и 
— соответственно
эвклидово и манхэттенское расстояния между точками 
и 
;
-
— расстояние между проекциями
этих точек на ‑ую ось;
-
— мерность пространства.
Метрики взаимозаменяемы
(с некоторой потерей информативности решения) и служат лишь инструментом
выявления мод. Вместо них (в качестве естественной меры близости) можно
непосредственно использовать плотностные показатели[4].
Для этого каждой паре эмпирических точек и достаточно
сопоставить «ящик пары» (“box”) —
многомерный параллелепипед, определённый соотношением
; где: (5)
-
— произвольная точка «ящика» 
, заданного парой точек и ;
-
— открытый отрезок между
проекциями этих точек на ‑ую ось (
и 
принадлежат отрезку);
-
— проекция точки на ту же ось;
-
— мерность пространства.
Естественной мерой близости
точек и , которая наиболее пригодна для выявления мод плотности,
будет величина
; где: (6)
-
— плотностная мера
близости точек и ;
-
— число эмпирически
точек, заключённых внутри «ящика» пары точек и ;
-
— объём «ящика» равный 
, где 
— длина открытого отрезка
, которая равна[5] расстоянию
между проекциями точек и на ‑ую ось, увеличенному на величину 
, где 
и 
— число эмпирических
точек, имеющих на ‑ой оси проекции и соответственно;
-
— мерность пространства;
-
— объём выборки.
Полезно
рассмотреть кластеры, построенные при различных уровнях «радиуса цельности» (), ибо они ценны как представители отдельных мод
генеральной плотности. Однако малые значения полезны для
анализа малых мод, который не всегда возможен.
Достоверность
«нулевой» гипотезы о равномерной плотности вероятности в соответствии с Теоремой 1
может служить оценкой качества решения задачи в целом («оценкой качества кластеризации»). Аналогично, для каждой
выявленной моды можно оценить достоверность её существования — отличия
«модальной» плотности от равномерной. Это будет «оценка качества отдельных кластеров».
Для
построения «оценки качества
кластеризации в целом» используем 
‑критерий согласия Пирсона [2, стр. 453–458], согласно которому распределение
величины
; где: (7)
-
— вероятность «попадания»
эмпирической точки в область пространства, аппроксимирующую 
‑ый кластер;
-
— реальное число
эмпирических точек, попавших в эту область;
-
— число кластеров,
— с ростом объёма выборки будет
асимптотически стремиться к ‑форме[6].
При маловероятном — большом значении этого критерия «нулевую» гипотезу
(вероятность равна объёму
аппроксимирующей области) можно будет отвергнуть[7].
Для
«оценки качества отдельных кластеров» адаптируем
непараметрический критерий Вапника–Червоненкиса[8].
Запишем его в форме
; где: (8)
-
— уклонение выборочной частоты 
, где — число
эмпирических точек в области, аппроксимирующей ‑ый кластер, от вероятности «попадания»
эмпирической точки в область;
-
— вероятность того, что для
первой же выборки объёма заданное
уклонение будет превышено;
-
— число кластеров.
Практически[9]
используется 
. Следовательно, максимальное значение 
зависит только
от значений , и . Оценивается достоверность «измерения» модальной
плотности с заданной точностью.
Способ
аппроксимации кластеров может быть любой — лишь бы аппроксимирующие области не
пересекались; заключали в себе как можно больше точек «своих» кластеров и как
можно меньше «чужих»[10].
Задача классификации
Назовём
«формальной коллекцией» матрицу
данных, которая описывает все или некоторые экземпляры реальной коллекции
заданным набором параметров[11].
Причём такую, что экземпляры с заданными значениями параметров представлены тем
большим числом строк, чем ближе эти значения к архетипу какого-либо таксона[12].
Теперь
поместим экземпляры «формальной
коллекции» в «чёрный ящик» и поставим классический мысленный эксперимент[13].
Очевидно, что экземпляры c более типичным сочетанием
признаков будут представлены в выборке большим числом строк. Таким образом,
задача классификации, в смысле отыскания архетипов — эталонных сочетаний
признаков всех таксонов [3, стр. 74–75 — о важности задачи выбора
эталонов], искусственно сводится к отысканию мод многомерной плотности «вероятности»[14] в
«ранговом пространстве».
Для
того чтобы требования «формальной
коллекции» были удовлетворены в «реальной» коллекции обычно проводят «чистку»[15].
Однако провести эту чистку всеми возможными способами нереально, и степень
соответствия «чищенных» данных требованиям «формальной
коллекции» всегда вызывает сомнения. На нашем искусственном — вероятностном
языке это означает, что выборка будет непредставительна, и предложенные выше
статистические оценки будут неприменимы.
Для
оценки качества полученных результатов более подойдёт следующий критерий: «для любых 
точек, случайным образом добавленных к
«ранговому пространству», найдётся такой «радиус цельности» кластеров , при котором
новые точки присоединятся к уже существующим — «старым» кластерам или образуют
новые, но никакой «старый» кластер не раздробится и никакие два — не
объединятся[16]. Формулы для вычисления максимального различаются, при
использовании эвклидовой, манхэттенской метрик, и плотностной меры близости.
Для эвклидовой метрики найдётся из
неравенства
; где: (9)
-
и 
— длины проекций
«радиусов цельности» и «слияния»[17] кластеров на 
‑ю ось;
-
и 
— размерности[18] «ящиков пар», где расстояния между
точками равны соответственно «радиусу
цельности» и «слияния»[19];
-
— число классифицируемых
экземпляров (без учёта ).
Неравенство преобразуется к полному многочлену 4‑й
степени, корни которого легко найти перебором натуральных значений . Аналогично для манхэттенской метрики неравенство
имеет вид
, (10)
который легко преобразуется к полному многочлену 2‑й
степени.
Сжатый
формат доклада позволяет привести только краткое доказательство для эвклидовой
метрики[20].
Для манхэттенской метрики схема рассуждений аналогична[21].
Для
плотностной меры получим[22]
; где: (11)
-
и 
— число
«неигровых» экземпляров внутри «ящиков
пар», с плотностями «радиуса
слияния» и «радиуса цельности» соответственно[23];
-
и 
— число «неигровых»
экземпляров, проекции которых на ‑ой оси лежат внутри проекций тех же «ящиков»;
-
— мерность пространства.
Отметим,
что для всех трёх неравенств 
будет решением[24].
Литература
1.
Вапник В. Н. Восстановление зависимостей по эмпирическим
данным. М: «Наука». 1979.
2.
Геральд Крамер. Математические методы статистики. М: «Мир». 1975.
3.
Мандель И. Д. Кластерный анализ. М: «Финансы и
статистика». 1988.