ГИПОТЕЗЫ КОМПАКТНОСТИ И А-КОМПАКТНОСТИ В МЕТОДАХ АНАЛИЗА ДАННЫХ¹) Н. Г. Загоруйко

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

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

К сожалению, при решении реальных задач распознавания образов такие условия не встречаются. Обучающая выборка каждого из k образов Sl,S₂,..., 5\,... представлена конечным числом т^ реализаций, описанных п характеристиками х1,х₂,.. ,... ,х_п. Сведений о законах и параметрах распределения генеральных совокупностей Gi образов нет. В частности, ничего не известно о зависимости V^ одних признаков от других. Не известна связь обучающей выборки с генеральными совокупностями (т. е. не известна степень «представительности» R выборки). Владелец обучающей выборки («заказчик») имеет туманные представления об априорной вероятности появления разных образов Р(к и о матрице стоимости ошибок распознавания С^. (Оставим пока в стороне те обычно сопутствующие факты, что выборка бывает очень небольшой, в данных есть ошибки и пробелы, признаки измерены в разных шкалах и среди них имеются неинформативные, шумящие признаки и пр.)

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

Дополнительные гипотезы могут носить общий характер или касаться мелких частностей. В данной работе будут описаны две базовые гипотезы — компактности и А-компактности — и показано их влияние на характер алгоритмов анализа данных.

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

Конечно, она подтверждается не всегда. Если, например, среди признаков имеется много случайных, не информативных, то точки одного образа могут оказаться далекими друг от друга. Но дополнительно предполагается, что в многомерном признаковом пространстве уже было найдено такое «информативное» подпространство, в котором точки одного класса действительно образуют явно выделяемые компактные сгустки. Назовем n признаков (х!,...,х„), входящих в информативное подмножество X, описывающими, а номинальный (n + 1)-й признак z, указывающий имя образа, — целевым. Обозначим множество объектов обучающей выборки через A, новый распознаваемый объект — через q, а тот факт, что объекты множества A «компактны» («эквивалентны», «похожи» или «близки» друг другу) в пространстве n характеристик X, — через C^X. Мера компактности может быть любой: она может характеризоваться средним расстоянием от центра тяжести до всех точек образа, средней длиной ребра полного графа или ребра кратчайшего незамкнутого пути, соединяющего точки одного образа, максимальным расстоянием между двумя точками образа и т. д. Например, компактными (эквивалентными) будем считать два объекта, если все признаки одного объекта равны соответствующим признакам другого, или: объекты компактны, если евклидово расстояние между векторами их признаков не превышает величину r.

Фактически гипотеза H+ равнозначна предположению о наличии закономерной связи между признаками X и z, и с учетом вышесказанного ее тестовый алгоритм может быть представлен следующим выражением: if (C^X'^z&C^X _q), then C^XZ, т. е. если объекты множества A компактны в пространстве (X, z) и объекты множества (A, q) компактны в пространстве описывающих свойств X, то объекты A и q будут компактными и в пространстве целевого признака z.

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

Заметим, что деление свойств на описывающие и целевые является условным. Мы можем целевой признак z включить в число описывающих, а в качестве целевого принять любой признак Xj из информативной системы X. Если при этом обучающие объекты множества A компактны в новом пространстве свойств {(xi, x₂,..., x_n-1, z), Xj} и множество (A, q) компактно в пространстве (xi, x₂,..., x_n-1, z), то значение нового целевого признака Xj у объекта q будет эквивалентным его значению у объектов множества A.

Целевыми могут быть не одна, а несколько характеристик. В частности, гипотеза H⁺ позволяет решать не только задачу анализа, когда по признакам X распознается образ z, но и обратную задачу — задачу синтеза, когда по имени образа z восстанавливаются наиболее правдоподобные значения характеристик X (например, путем приписывания объекту q с признаком z свойств «типичного» представителя образа z).

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

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

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

2.1. Гипотеза компактности в задачах распознавания образов. Сформулированное выше условие компактности для решения задачи распознавания образов является необходимым, но не достаточным. Мало того, чтобы точки образа A были близкими друг к другу, нужно еще чтобы точки образа B

не оказались к ним такими же близкими, т. е. нужно, чтобы сгустки точек раз_

ных образов не налагались друг на друга, что обозначим как С_АВ. С учетом этого гипотезу компактности H+ для распознавания образов можно записать в следующем виде: if (С_{А B}$zC_A'^z$zC_Aq), then

Если предполагать, что реализации одного и того же образа образуют один компактный сгусток (гипотеза унимодальной компактности (H+)), то его можно описать односвязной выпуклой оболочкой или аппроксимировать унимодальным распределением.

Ослабленный вариант обсуждаемой гипотезы (назовем его гипотезой полимодальной компактности (H+)) утверждает, что точки одного образа могут образовывать не один, а несколько компактных сгустков. На этом основании можно представлять образ несколькими многосвязными областями или смесью нескольких простых распределений.

Дальнейшее ослабление гипотезы H+ можно в пределе представить в виде следующего осторожного утверждения о свойстве ближайшего соседства: «обо всем распределении судить не берусь, но утверждаю, что в некоторой малой е-окрестности каждой реализации обучающей выборки образа Si может появиться только представитель этого же образа». На указанном основании построить общую модель распределения образа нельзя, но можно построить правило распознавания с опорой на все или на часть объектов обучающей выборки (т. е. с опорой на «прецеденты»). Будем называть этот вариант предположения гипотезой локальной компактности (H+).

Проекции компактных сгустков на координатные оси будут также компактными. Если, кроме того, проекции разных образов окажутся еще и не совпадающими друг с другом, то появляется возможность разделять их не сразу в многомерном пространстве признаков, а поочередно, по каждому признаку в отдельности. При таком подходе можно различать еще три варианта гипотезы компактности: гипотезу унимодальной проективной (H+_p), полимодальной проективной (H+_p) и локальной проективной компактности (H+).

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

А дальше пути разных школ распознавания расходятся. Большая часть из них, базируясь на гипотезе H+, строит модели унимодальных распределений генеральных совокупностей распознаваемых образов и потом для построения решающих правил применяет аппарат математической статистики. Другие ориентируются на гипотезу полимодальной компактности, строят модели распределений в виде смеси простых распределений, после чего применяют те же статистические методы, но как бы для большего числа образов. Те, кто ориентируется на локальную компактность, строят решающие правила, опирающиеся на одного или k ближайших соседей. Наконец, те, кто предполагает, что компактность в многомерном пространстве проявляется в компактности проекций сгустков на координатные оси, используют последовательные покоординатные процедуры.

2.2. Гипотеза компактности в алгоритмах таксономии. Гипотеза унимодальной компактности лежит в основе многочисленных алгоритмов таксономии, с помощью которых получаются таксоны простой геометрической формы — в виде гиперсфер или гиперпараллелепипедов. Например, алгоритмы семейства FOREL [2] формируют сферические таксоны заданного радиуса R. При этом сфера охватывает максимально возможное количество точек, а центр сферы оказывается в центре локального сгустка точек, попавших в данный таксон. В качестве характеристики компактности объектов используются их расстояния до центра таксона. Два объекта (a и b) считаются принадлежащими одному компактному подмножеству, если расстояние r от каждого из них до центра таксона c не превышает величины радиуса R:

if {[r(a, c) < R]&[r(b, c) < R]}, then C£,.

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

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

2.3. Гипотеза компактности в алгоритмах выбора признаков. В задачах распознавания образов обычно предполагается, что исходная система g признаков X = {x\,x2,... ,xj,... ,x_g), описывающих обучающую выборку A, содержит некоторое подмножество «информативных» признаков, т. е. таких, в подпространстве которых реализации образов компактны и хорошо отделяются друг от друга. Если, кроме этого, в системе содержатся «неинформативные» описывающие признаки, т. е. такие, закономерная связь которых с целевым признаком отсутствует или очень мала, то они «размывают» компактность и не помогают, а лишь затрудняют принятие правильных решений.

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

При использовании гипотезы локальной компактности критерием информативности подсистемы признаков может служить количество опорных точек или «прецедентов», необходимых для безошибочного распознавания обучающей последовательности. Чем меньше прецедентов, тем информативнее признаки. Используются и другие критерии информативности.

Если предполагается проективная компактность, то информативным считается минимальный набор признаков, проекции обучающей выборки на которые позволяют построить выпуклую оболочку в виде гиперпараллелепипедов с гранями, перпендикулярными координатным осям. На такую форму оболочек опираются, например, логические решающие функции [4,5]. Выбор п информативных признаков из исходного множества, содержащего g признаков, можно делать методом последовательного добавления [6] наиболее информативных.

2.4. Гипотеза компактности в задаче заполнения пробелов. Реальные таблицы объект-свойство могут содержать пробелы: значение Ь^ некоторых характеристик у некоторых объектов a_i в таблице не указаны. Если при этом таблица содержит избыточную информацию, т. е. если в ней описаны объекты, похожие друг на друга, или если имеются свойства, зависящие друг от друга, то есть надежда предсказать достаточно правдоподобное значение пропущенного элемента. Нужно только выявить эти скрытые похожести и зависимости.

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

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

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

Эти предположения эквивалентны принятию гипотезы полимодальной компактности: в таблице данных можно выделить такое подмножество Л объектов и такое подпространство X' свойств, что для них выполняется условие компактности С .

На использовании именно этой гипотезы основан алгоритм заполнения пробелов ZET [2]. Дополнительно к этому в алгоритме предполагается, что из всех видов имеющихся в таблице зависимостей достаточно использовать самые простые — линейные зависимости. Приведем краткое описание алгоритма ZET.

Элементы, стоящие в строке (ц и столбце Xj, на пересечении которых находится предсказываемый элемент, будем называть базовыми. Выбирается компетентная подматрица, в которую попадают V строк, наиболее похожих на базовую строку ац, и г столбцов, наиболее тесно связанных с базовым столбцом Xj. Мерой близости строк может служить расстояние между ними в евклидовом пространстве признаков, а мерой связанности (зависимости) признаков — модуль коэффициента корреляции. Каждой 1-й строке компетентной подматрицы приписывается вес Ьи, пропорциональный ее компетентности, которая тем выше, чем меньше расстояние между г-й и 1-й строками. Точно так же компетентность Ьj_k каждого ^го столбца тем больше, чем больше его корреляция с ]-м

столбцом.

Далее строится г линейных регрессий между '-м столбцом и всеми г компетентными столбцами. По каждой такой регрессии между '-м и ^м столбцами, зная значение элемента Ь^ в ^м столбце, можно получить вариант предсказания значения пропущенного элемента в '-м столбце — ЬУсреднение полученных вариантов с весами компетентности дает вариант, выработанный с

г г

участием всех г столбцов: b_ij_V = ^ Ь^ * Lj_k/ ^ Lj_k.

k=l k=l

Затем определяется вариант, полученный при усреднении подсказок от всех V строк. Поскольку из похожести строк по г признакам следует похожесть и по (г + 1)-му признаку Xj, то в качестве подсказок Ь^ от каждой 1-й строки будем брать значение признака Xj для этой строки, т. е. величину bj_l.

При усреднении подсказок эти значения будут учитываться с весом, про-

V V

порциональным компетентности Li_l этих строк: bij_V = ^ Ьл * Lц/ ^ L_il.

1=1 1=1

Окончательный вариант предсказываемого значения получается, например, путем простого усреднения подсказок от строк и от столбцов: = {Ь^_г +

^bijv^} / 2.

При анализе результата возникает естественный вопрос о доверии к нему. Гипотеза компактности позволяет дать на него достаточно обоснованный ответ. Строки компетентной подматрицы близки (эквивалентны) друг другу в пространстве V описывающих свойств. Условие их компактности в пространстве свойств V + 1 удовлетворяется, если значения (V + 1)-го свойства, т. е. признака хл, у всех V объектов также близки между собой. При этом варианты Ьл заполнения пропущенного элемента также будут мало отличаться между собой, в чем можно убедиться, если определить дисперсию d этих вариантов. Чем меньше d, тем с большим доверием можно относиться к предсказанному значению пропущенного элемента. Аналогичным образом проверяется состоятельность гипотезы компактности и для столбцов.

Эксперименты показали, что между дисперсией d и ошибкой предсказания пропущенного элемента имеется достаточно сильная зависимость: коэффициент корреляции между ними обычно достигает величины 0,7.

2.5. Гипотеза компактности в алгоритмах прогнозирования. Прогнозирование будущего обычно основывается на сравнении текущей ситуации с ситуациями в прошлом. Если в протоколе прошлых событий обнаруживается ситуация Х{:, «аналогичная», «эквивалентная» текущей ситуации Х₀, то считается, что состояния системы Х^ и Х₀₊₁ в моменты времени, следующие за этими похожими ситуациями, будут также похожими. Чтобы убедиться, что такой вариант гипотезы компактности действительно имеет место для данного момента времени Х₀, в алгоритме LGAP [8] делается выбор не одной, а нескольких «компетентных» прошлых ситуаций. Каждая прошлая ситуация порождает свой вариант прогнозируемого состояния Х₀₊₁, дисперсия которых d показывает, насколько обоснованна вера в то, что одинаковые прошлые состояния соседствуют во времени с одинаковыми будущими состояниями.

Опорную текущую ситуацию Х₀ можно задавать по-разному. Каждому варианту описания Х₀ соответствует своя стратегия прогнозирования. Как выбрать лучшую стратегию, которая давала бы наименьшую ошибку прогноза? Обычно ответ на этот вопрос ищется путем сравнения стратегий на ретроспективном прогнозировании: прогнозируются значения по возможности большего количества прошлых состояний и определяются ошибки, получаемые при использовании разных стратегий. И предпочтение отдается той стратегии F, которая на материале прошлого давала наиболее точные прогнозы.

Однако из протокола сравнения стратегий можно увидеть, что пусть редко, но бывали случаи, когда некоторая другая стратегия F' оказывалась более прозорливой и давала прогноз, более точный, чем стратегия F. По-видимому, стратегия F' более точно соответствовала тем закономерностям процесса, которые проявляли себя именно в данный конкретный момент.

Какую же стратегию использовать для реального прогнозирования неизвестных величин? Где гарантия, что стратегия, чаще других в прошлом приводившая к успеху, будет лучшей и в этом конкретном случае?

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

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

3. Гипотеза А-компактности. Гипотеза компактности оперирует абсолютными значениями расстояний между векторами в пространстве характеристик. Однако на некоторых примерах можно показать, что важную роль в задачах анализа данных играют не столько сами расстояния, сколько отношения между ними. Так, расстояние между точками 5 и 6 на рис. 1 меньше, чем между 6 и 7, но, делая «вручную» таксономию этого множества точек на два

таксона, эксперты обычно проводят границу по ребру 5-6. Глаз человека улавливает на этой границе нарушение однородности расстояний между соседними точ-р_ис і ками и придает этому факту большее значение, чем

^Рис абсолютной величине расстояний.

Зрительный аппарат человека обладает уникальными способностями делать классификацию (таксономию) множества объектов, если они представлены точками на плоскости [9]. На рис. 2 представлены примеры множеств, таксономия которых для человека не составляет труда. Результаты же получаемой при этом естественной для человека таксономии (границы между таксонами отмечены пунктиром) не могут быть получены или объяснены с позиций гипотезы компактности. Гипотеза же Л-компактности позволяет легко получать и просто объяснять такие результаты.

1  Работа поддержана грантами Государственной научно-технической программы «Перспективные информационные технологии» (№ 0201.05.011) и Российского фонда фундаментальных исследований (код проекта 97—06—80312)

© 1998 Загоруйко Н. Г.