§ 1. Гипотеза компактности

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

Конечно, она подтверждается не всегда. Если, например, среди признаков имеется много случайных, неинформативных, то точки одного образа могут оказаться далекими друг от друга и рассеянными среди точек других образов. Но дополнительно предполагается, что в многомерном признаковом пространстве уже было найдено такое (информативное) подпространство, в котором точки одного класса действительно образуют явно выделяемые компактные сгустки. Назовем  признаков, входящих в информативное подмножество , описывающими, а номинальный -й признак , указывающий имя образа, целевым. Обозначим множество объектов обучающей выборки через , новый распознаваемый объект через , а тот факт, что объекты множества  компактны (эквивалентны, похожи или близки друг другу) в пространстве  характеристик  — через . Мера компактности может быть любой: она может характеризоваться средним расстоянием от центра тяжести до всех точек образа; средней длиной ребра полного графа или ребра кратчайшего незамкнутого пути, соединяющего точки одного образа; максимальным расстоянием между двумя точками образа и т. д. Например, компактными (эквивалентными) считаем два объекта, если все признаки одного объекта равны соответствующим признакам другого. Или: объекты компактны, если евклидово расстояние между векторами их признаков не превышает величину .

Фактически гипотеза  равнозначна предположению о наличии закономерной связи между признаками  и , и с учетом вышесказанного ее тестовый алгоритм может быть представлен следующим выражением: . Т. е. если объекты множества  компактны в пространстве  и объекты множества  компактны в пространстве описывающих свойств , то объекты  и  будут компактными и в пространстве целевого признака . Часто эту гипотезу формулируют так: «Объекты, похожие по  описывающим свойствам , похожи и по -му целевому свойству ». Легко видеть, что в этой более краткой формулировке опущены весьма существенные дополнительные условия.

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

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

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

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