4.3. Классификация, основанная на близости описаний

4.3.0. Общее обсуждение и примеры

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

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

Рис. 4.5. Отклонения содержания углерода-13 и кислорода-18 (относительно стандарта PDB) в образцах мрамора из античных карьеров. Треугольниками обозначены обломы, перечисленные в табл. 4.1 (Крейг и Крейг, 1972).

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

Мы рассмотрим сначала реальную задачу классификации, которая затем послужит нам для иллюстрации разнообразных вопросов. Имеется в виду задача, связанная с работой Крейга и Крейга (1972), в которой метод, разработанный для физических исследований, был применен к археологии и истории. Определение источника материала

исследуемого фрагмента каменной кладки или скульптуры называется установлением его происхождения. Крейги попытались установить происхождение классической греческой скульптуры, измеряя относительное количество различных изотопов химических элементов в мраморе. Они обнаружили, что мрамор из античных карьеров можно отличить по отношению концентраций углерода-13 к углероду-12 и кислорода-18 к кислороду-16. На рис. 4.5 представлены проведенные Крейгами измерения, в которых использовались образцы из различных карьеров 1). В табл. 4.1 собраны результаты

Таблица 4.1 (см. скан) Диализ археологических мраморных обломов при помощи изотопов (Крейг и Крейг, 1972)

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

4.3.1. Определения

По определению евклидова расстояния (см. (1)) квадрат расстояния между двумя точками в равен

Интуитивно ясно, что объект с описанием х похож на объекты с описаниями, принадлежащими некоторому множеству если мало среднее значение квадрата расстояния между х и точками из Таким образом, точка х близка к множеству если величина

мала. Рис. 4.5 может служить иллюстрацией такому понятию близости. ближе к точкам множества Пентели, чем к точкам множества Наксос.

Чтобы сравнить два множества, надо оценить среднее расстояние между парами точек, взятых по одной из каждого множества. Пусть множества X и содержат соответственно точек. Тогда среднее квадрата расстояния между X и Y равно

Чем дальше в среднем друг от друга точки из X и Y, тем больше значение (42). По этому критерию, например, точки множества Пентели лежат ближе к множеству Наксос, чем к множествам Парос и Гиметт (рис. 4.5).

Для оценки плотности расположения точек внутри множества нужна соответствующая мера. Пусть ею будет среднее квадрата расстояния между точками этого множества:

Эта величина тем меньше, чем ближе друг к другу точки множества. По этому критерию скопление точек в множестве Пентели более плотное, чем в множестве Наксос.

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

где — симметричная -матрица, Это значит, что компоненты вектора х задаются равенствами