Гипотеза  компактности  (H)

      Гипотеза компактности состоит в том, что реализации одного и  того же хорошо организованного образа обычно отражаются в  признаковом  пространстве  в  геометрически близкие точки, образуя "компактные"  сгустки  [1].  При  всей  кажущейся  тривиальности  и   легкости   опровержения  указанная гипотеза лежит в основании большинства  алгоритмов  не только распознавания, но и многих других задач анализа данных.  
       Конечно, она подтверждается не всегда.  Если, например, среди  признаков имеется много случайных, не  информативных,  то  такой случай соответствует  плохой организации образов и точки  одного и того же  образа  могут  оказаться  далекими  друг  от  друга.  Но  дополнительно  предполагается,  что работа по организаци образов уже проведена и в  многомерном  признаковом пространстве   найдено   такое  ("информативное") 
подпространство, в котором  точки  одного  класса  действительно  образуют  явно  выделяемые   компактные   сгустки. 
         Назовем   n  признаков, входящих   в    информативное     подмножество     X, "описывающими", а номинальный (n+1)-й признак z, указывающий имя  образа,  "целевым".  Обозначим  множество   объектов   обучающей  выборки через А, новый распознаваемый  объект  через  q,  а  тот  факт,  что  объекты множества  A  "компактны"  ("эквивалентны", "похожи" или "близки" друг другу) в пространстве n характеристик  X, через  C(X/A). Мера "компактности"  может  быть  любой.  Например,  можно считать, что объекты компактны,  если Евклидово  расстояние между  векторами  их  признаков  не  превышает  величину  r. 
       Фактически гипотеза  H равнозначна предположению  о  наличии  закономерной связи между признаками X и z и ее тестовый алгоритм может быть представлен  следующим  выражением: 

if [C(X,z/A) & C(X/A,q)],  then  C(z/A,q).

        Т.е.,  если  объекты  множества  A компактны  в совместном пространстве  X,z  и объекты  множества  A,q  компактны   в пространстве описывающих свойств X, то объекты  A и q  будут  компактными и в пространстве целевого признака z. 
    Сформулированное  выше  условие  компактности  для   решения задачи  распознавания  образов  является  необходимым,   но   не достаточным. Мало того, чтобы точки образа A были близкими  друг к другу, нужно еще чтобы точки  образа  B  не  оказались  к  ним такими же близкими,  т.е.  нужно,  чтобы  сгустки  точек  разных образов не налагались друг на друга, что будем  обозначать  так:   C- .   С   учетом  этого,  гипотезу  компактности H для распознавания образов можно записать в следующем виде:

If [C-(X/A,B)&C(X,z/A)&C(X/A,q)], then C(z/A,q) .

      Различаются разные варианты гипотезы компактности: гипотеза "унимодальной" (Нu), "полимодальной" (Нp) и "локальной" компактности (Нl). Проекции компактных сгустков на  координатные оси будут также компактными, так что  можно  различать  еще  три варианта   гипотезы   компактности:    гипотезу    "унимодальной проективной"  (Нup),  "полимодальной   проективной"    (Нpp)   и "локальной проективной" компактности (Нlp).
    Гипотеза   унимодальной   компактности   лежит   в    основе многочисленных алгоритмов таксономии, с  помощью   которых получаются  таксоны  простой  геометрической  формы  -  в   виде гиперсфер или  гиперпаралеллепипедов.   Например,   алгоритмы семейства FOREL  [2]  формируют  сферические  таксоны  заданного радиуса R. 
    Если в системе содержатся "неинформативные" признаки, то они "размывают"  компактность  и  затрудняют   принятие   правильных решений. Задача выбора информативных признаков состоит в  поиске подпространства, в котором характеристика компактности достигает максимального значения. 
    При использовании гипотезы локальной компактности  критерием информативности подсистемы признаков  может  служить  количество опорных точек или "прецедентов", необходимых  для  безошибочного распознавания   обучающей   последовательности.  
    Реальные таблицы "объект-свойство" могут содержать  пробелы: значение некоторых характеристик у внекоторых объектов  в таблице не указаны.  Для  предсказания  значений  пропущенных  элементов используется гипотеза полимодальной компактности [2]. 
    

Гипотеза l-компактности  (lН)

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

                                                                             
Рис. 1.
       Гипотеза  же  l-компактности позволяет легко получать и просто объяснять такие результаты. 
       Формулировка  гипотезы  l-компактности  опирается  на  понятие  l-расстояния.  Если определить расстояния между всеми парами точек множества  A,  то  можно  построить полный граф,   который соединяет все m точек друг с другом. Если на этом графе выделить две вершины a и  b, обозначить длину связывающего их ребра через  a , а длину  минимального  из смежных  ему  ребер через bmin,  то  отношение длин этих ребер l=a / bmin   будет характеризовать  меру  локальной  неоднородности расстояний  или l-расстояние между  точками  a и b.  Пользуясь  этим  методом, вычислим l-расстояния между всеми парами из m точек,  и  построим   граф без петель,  который соединяет между  собой  все  точки  ребрами,  суммарная  l-длина которых  минимальна. Такой граф называется  ╚кратчайшим незамкнутым путем╩ (КНП). Теперь  l-расстоянием  между  двумя  любыми точками будем считать сумму l-длин тех ребер, по которым проходит путь между ними по  КНП.  Локальная  "неодинаковость" плотности точек, соседство "неоднородных" по длине участков  КНП легко улавливается зрением и однозначно связывается с  величиной l-характеристики.
    Исходя  из  этого,  по  аналогии  с  гипотезой   компактности гипотезу  l-компактности  (lН)   можно  сформулировать  следующим образом:  реализации одного и того же хорошо организованного  образа отражаются  в признаковом   пространстве    в    l-близкие    точки,    образуя "l-компактные" сгустки.  
    По аналогии с гипотезой компактности можно различать гипотезы унимодальной  (lHu),   полимодальной    (lHp) и  локальной   (lHl) l-компактности, а  также все их проективные версии: (lHup), (lHpp) и (lHlp).  
     На базе этой более сильной гипотезы можно построить новые алгоритмы анализа данных . Примером может служить алгоритм таксономии l-KRAB из данного пакета
Литература:
1. Аркадьев А.Г.,  Браверман Э.М.   Обучение   машины   распознаванию образов. √М: Наука, 1964. 
2. Загоруйко  Н.Г.,  Елкина  В.Н.,  Емельянов  С.В.,  Лбов   Г.С.  Пакет прикладных программ  ОТЭКС.  -М.:  Финансы  и  статистика, 1986.   
3.Загоруйко Н.Г. Гипотезы компактности и l-компактности в методах анализа данных. Сибирский журнал индустриальной математики. Изд. ИМ СО РАН. Том 1, N1, 1998, С.114-126.