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

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

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

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

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

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

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

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

Дата добавления: 2015-07-15