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

методе классификации и наличии обучения. Например, при классифи­ кации нормальных наблюдений с помощью линейной разделяющей поверхности достаточно знать лишь р + 1 чисел, а при локальном ме­ тоде классификации требуется помнить все р (т1 + /л2) чисел.

Локальный метод, устраняя одну трудность — наличие сведений об общем виде распределения наблюдений,—сразу же заменяет ее дру­ гой — трудностью выбора расстояния между точками-наблюдателя- ми. Эту трудность можно преодолеть, как будет показано ниже, заме­ нив ее другой неопределенностью.

Остановимся коротко на некоторой модификации правила клас­ сификации (1), описанного выше. Эта модификация для двух классов описана, например, в работе [13] и состоит в том, что можно для точки Z принимать, как описано в § 2, п. 4, три решения:

di — отнести точку к классу і (г= 1, 2) и d0 — воздержаться от приня­ тия решения.

Предлагается следующая процедура:

в зависимости от т1 и тг -—числа точек обучающих последователь­ ностей выбираются числа к и к ' ^ [к/2] + 1;

выбираются к ближайших к точке Z точек из множества т1 + т2 точек обучающих выборок;

точка Z относится к классу і (і = 1,2), если в числе к ближайших точек имеется более к' точек из обучающей выборки класса і. Если же

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

48

Вполне естественно, что в качестве весовой функции К(лД), х(2\ . . . , х (р'>} можно взять любую интегрируемую в области от 0 до оо и неотрица­ тельную функцию ер (г) одномерного параметра, где вместо аргумен­ та г стоит норма ||Х||. Если ф (г) еще и монотонно убывающая функция,

z<2>, .... z <p >)

тр

[16], что оценка fm (zC), z(2), ... , z <p >) состоятельна в точках непрерыв­ ности Z плотности / (Z), а величина

fт (7) / (Z)

асимптотически {т оо) нормальна с математическим ожиданием О и единичной дисперсией.

Легко проверить, что последовательности B j m = ш4+р удовлетво­ ряют всем необходимым условиям. Для таких последовательностей

сходимость оценки fm (Z) к плотности / (Z) определяется скоростью убывания дисперсии, равной

Следовательно, скорости сближения оценок в методах, описанных в работе [7] и в работе [16], совпадают для этого частного случая и рав­

ны /п<2 + р/2). Очевидно, что функции

Ф (z) = e~czZ (с > 0), ( a + b z 2) - 1, ( ^ ^ ) 2 и т - д -’

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

49

В работе [5] доказано, что оценка плотности с весовой функцией

ции, и производится подсчет числа голосов Г (Z, Sz) за I-й класс следу­

Г (Z, X „ )= 2 /? n (Z , x tl).

II

Суммирование здесь ведется по всевозможным наборам р' координат из р (число таких наборов равно Ср).,Тогда величина T(Z, Si) равна

ті

T (Z ,St) = 2 r ( Z , X u). і = 1

Пусть задано некоторое число ц ^ 1. Вектор Z £ X относится к тому классу I, при котором

Г (Z, Sj)

для всех j Ф I. Если такого I не существует, то вектор Z не может быть классифицирован.

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

1 Этот метод разработан Ю. И. Журавлевым (ВЦ АН СССР).

50

§ 4. КЛАССИФИКАЦИЯ С ЧАСТИЧНЫМ ОБУЧЕНИЕМ. ПАРАМЕТРИЧЕСКИЙ СЛУЧАЙ

В области социально-экономических исследований сравнительно распространены ситуации, в которых исследователю неизвестно зара­ нее сколько типов (классов, объектов) представлено в изучаемой вы­ борке

{Хі) = Хь Х2, ..., Х п,

однако, предварительные сведения или специальные экспертные оцен­ ки помогают выделить определенные, как правило, небольшие «пор­ ции» данных вида {Хгг} из выборки {Ху} или помимо нее, о каждой из которых известно, что эта порция представляет лишь один какой-то класс.

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

Предположим, что каждый из векторов наблюдений Ху исследуемой выборки извлечен из какой-то нормальной генеральной совокупности, принадлежащей семейству

{N(ah 2)}, /= 1, 2, ..., К,

где

'ö j 1»''

(.т—s) >. (р—1), где, как и прежде, т —общее число наблюдений, сос­ тавляющих s частичных обучающих выборок.

Введем в рассмотрение априорные вероятности я г (I = 1,2, ..., К) появления объекта /-го класса, или иначе л г — это удельный вес /-го класса среди всех исследуемых классов. При этом, вообще говоря, аи 2, К и я г (/ = 1, 2, ..., К) нам неизвестны, а К может быть и + оо. Будем для определенности предполагать, что наблюдения, участвую­ щие в частичных обучающих выборках, не входят в состав исследуемой выборки {Ху}. Этого всегда можно добиться с помощью предваритель­ ного исключения этих наблюдений из состава выборки {Ху}.

1. Описание процедуры классификации

Следуя [9] и [15], определим понятие минимального дистанционного разбиения

Sft(2) = {S!(Z), S2(Z), ...,Sk(Z)j

51

относительно заданных центров

и заданного числа классов k. Выше и далее Z* — вектор в рассматри­ ваемом намир-мерном пространстве/?^) с заданной в нем метрикой р./ В соответствии с этим разбиением класс 5 г (Z) состоит из точек про­ странства /?(р>, ближайших в смысле метрики р к Zг, причем точки, рав­ ноотстоящие от нескольких центров Z;, относятся к классу с наимень­ шим индексом. Так что, если ввести множества1

то

S1(Z) = St(Z),

Sa(Z)= S;(Z)flSi(Z),

случае совпадает с текущим номером последовательно извлекаемых из {Ху} наблюдений Хѵ.

Сущность описываемой процедуры в предварительном (по ѵ) уточ­

и их числа k (ѵ), а затем использование получаемой на последнем п-м шаге последовательности центров Z(n) для образования классов

<Si(Z(n))> S2(Z(*>), .... S*(n)(Z<»>)

с помощью определенного выше минимального дистанционного раз­

типа между случайными векторами X и Y в исследуемом р-мерном про­ странстве /?(р)

р2(Х, F) = (X ~ F )'S - 1(X -F ),

где 2 — ковариационная матрица и для X и для У.

Пусть 2 — оценка максимального правдоподобия с устраненным смещением для 2 , построенная по совокупности частичных обучающих

выборок, р~2 (X, Y) = (X — Y)' 2 - 1 (X — Y ),

V ; (V)

52