Файл: Айвазян, С. А. Классификация многомерных наблюдений.pdf

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

б) Классификация, основанная на оценке дискриминантной функции

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

Пусть Х хі, Х 2І, ..., Х т.і (і = 1, 2) обучающие последовательности

из р-мерных нормальных совокупностей с разными неизвестными сред­ ними аъ а2 и одинаковыми, но неизвестными ковариационными ма­

трицами 2. Используя оценки средних значений аг= — 2 Х ц и оцен-

т /= 1

ку общей ковариационной матрицы

z т-

1

[т1-\-т2— 2 £ = 1 /=1

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

сификации. Для равных вероятностей ошибок классификации пара­ метр с = 0.

Известно [1], что при тх — оо и т2->■ °о предельным распределе­

где р — расстояние Махалонобиса между классами, т. е.

р = (Сі—а2у 2 " 1(ах—а2).

Это означает, что при достаточно больших mt (і — 1, 2) вероятность неправильной классификации наблюдения X £ .V (аг,2) будет за­ даваться приближенным соотношением

43

В работе [6] доказано, что разделяющую поверхность можно пере­ двигать до тех пор, пока ошибки классификации обучающих последо­ вательностей не сравняются. Правда, это доказательство существен­ но опирается на предположения о нормальности распределений и о ра­ венстве ковариационных матриц. Кроме этого предполагается, что объемы обучающих последовательностей одинаковы (mx = т2).

Доказано, что точка z0 — пересечения поверхности 612 с прямой, сое­ диняющей центры классов а± и а2 при т1 = т2 -э- оо распределена

по нормальному закону со средним значением Mz0 = ai^ fl- и дис-

Персией

а количество ошибочно классифицируемых точек v (z0) при т1 оо нормально со средним

и дисперсией

Можно, по-видимому, показать, что такой метод улучшения поло­ жения делящей поверхности L (с)-состоятелен над семейством нор­ мальных распределений с одинаковыми ковариационными матрицами и разными средними.

Аналогичные результаты справедливы для числа классов k >. 2. Привлекательность линейной классификации привела к тому, что в работе [10] линейная классификация применяется и для разделения

нормальных совокупностей с разными ковариационными матрицами. В работе [3] предлагается распространить этот метод для классифика­ ции совокупностей с поверхностями постоянного уровня, состоящими из концентрических эллипсоидов. Известно [3], однако, что методы линейной классификации не являются L (с)-состоятельными уже над семейством нормальных распределений с разными средними и разными ковариационными матрицами.2

2.Непараметрические методы классификации

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

44

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

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

а) Методы, использующие понятие близости. Понятие близости можно задавать, на­ пример, следующим образом. Определим в пространстве на­

действительным числом г > 0 и сопоставляя каждой точке U из окрестности нуля ѵ0точ­ ку rlI,— (rud-'>, ги<?\ ..., г«(р>),

мы получим отображение ок­ рестности ѵ0 в некоторую по­ добную ей окрестность ѵ0 (г). Меняя г, будем иметь систему подобных окрестностей {п0 (г)} около точки 0. Тогда для

произвольной точки Z при заданном виде окрестности нуля ѵ0 можно рассмотреть соответствующие подобные окрестности (см. рис. 1.6).

vz {r) = {rU+ Z, и е М-

Таким образом, очевидно, что при заданных ѵ 0и Z для любой р-мерной точки факторного пространства X £ X можно определить множество действительных чисел Rx таких, что если только г■£ R x , то X £ vz(r).

Соответственно полагают, что из двух точек X и Y точка X располо­ жена ближе к точке Z (в смысле окрестности ѵ0), чем точка Y, если min Rx < min R Y-

Обычно понятие близости точек наиболее естественно вводится через расстояние р (X, Z) в пространстве признаков. В этом случае области ѵ2 (г) превращаются в систему «сфер» радиуса г и центром в точке Z.

Приведем вначале несколько способов классификации объекта Z, а затем остановимся более подробно на различных локальных оценках плотностей и отношений правдоподобия в точке Z, на основании ко­ торых производится классификация.

45

Методы классификации точки Z могут состоять в следующем.

1) В зависимости от объемов обучающих выборок определяется число к:

•— рассматривается к ближайших k Z точек из обучающих выборок;

— точка г относится к тому классу і, из которого в числе к ближай­ ших точек присутствует больше точек, чем точек из любого другого

2) В зависимости от объемов т* обучающих выборок класса і выби­ раются числа к ;:

— около точки Z для каждого і строится окрестность vz (р() наи­ меньшего радиуса р; такая, что она содержит не менее к* точек из обу­ чающей выборки класса і. Заметим, что определенный таким образом радиус р; является величиной случайной;

— точка Z относится к тому классу і, для которого рг ^ pj (/ =

- 1, 2, ..., k).

3) По непараметрическим оценкам плотностей около точки Z и, сле­ довательно, по оценке функций бг (Z) (или разделяющих поверхностей), точка Z относится к одному из классов аналогично тому, как это дела­ лось в § 2 настоящей главы.

Приведем некоторые общие результаты, которые показывают сос­ тоятельность наиболее изученного метода классификации (метод 1) на два класса при к - ^ - о о и т = т 1 = т 2 ->-оо. Через / (U) обозна­ чим плотность распределения точек, принадлежащих к одному клас­

Ѵг

тj f(U)dU

vz (r)

является состоятельной оценкой плотности / (U) в точке Z.

Для евклидова расстояния и сферы vz (г) аналогичные результаты получены в работе [14].

46

/ I 0)) оценка f (U) состоятельна для / (U | Ѳ), то правило классифи­ кации

HU 1Ѳх)

кг— 1

U U )

ЩРІ ’

где р — размерность каждого наблюдения, а к* — фиксированное чис­ ло точек в области vz (р0-

В этом случае f t (U) — асимптотически несмещенная (при т г ->- оо) оценка /у (U) и ее можно использовать для оценки отношения плотностей.

Если области vz (рг) различны для распределений fx (U) и для / 2 (U), а рг такие, что в область vz (рг) попадает равно к х и к 2 точек последо­

к= 2кі — 1 (метод 1).

Вработе [7] предлагается выбирать величину

4

к; = т 4.+р

1 I

для т1 = т2. Отличаясь от параметрических методов меньшими тре­ бованиями на плотности, локальный метод имеет ряд существенных не­ достатков. Отметим лишь некоторые из них:

при оценке отношения правдоподобия fx (U)/f2 (U) используются лишь точки, входящие в уменьшающуюся с ростом min {ть /п2} ок­ рестность классифицируемой точки Z. Это приводит к тому, что по­ рядок сближения (при min {т1, т 2} о о ) этого метода с наилучшим (основанном на fx (U)/f2 (U)) хуже, чем для параметрических проце­ дур, которые используют все данные обучения при классификации точки Z;

локальный метод классификации требует большей вычислительной работы при классификации новых данных, чем при параметрическом

47