НЕПАРАМЕТРИЧЕСКИЙ АЛГОРИТМ АВТОМАТИЧЕСКОЙ КЛАССИФИКАЦИИ СТАТИСТИЧЕСКИХ ДАННЫХ
Непараметрический алгоритм автоматической классификации статистических данных 73
УДК 681.513
А. В. ЛАПКО, В. А. ЛАПКО, А. Н. ХЛОПОВ
НЕПАРАМЕТРИЧЕСКИЙ АЛГОРИТМ АВТОМАТИЧЕСКОЙ КЛАССИФИКАЦИИ СТАТИСТИЧЕСКИХ ДАННЫХ
Предлагается непараметрический алгоритм автоматической классификации статистических данных, основу которого составляют оценки плотности вероятности парзеновского типа. Применение алгоритма позволяет выделять компактные множества точек, соответствующих одномодальным фрагментам плотности вероятности.
Ключевые слова: непараметрическая статистика, автоматическая классификация, распознавание образов, плотность вероятности.
Методы автоматической классификации статистических данных широко используются при разработке математического обеспечения аппаратно-программных комплексов технического зрения, а также при создании систем обработки данных дистанционного зондирования Земли. Среди алгоритмов автоматической классификации, основанных на явном определении класса, следует отметить те, которые ориентированы на обнаружение множества объектов, соответствующих одномодальным фрагментам совместной плотности вероятности в заданном пространстве признаков [1, 2]. Определение класса связано с понятием закономерности в вероятностном смысле и имеет прикладную направленность в задачах синтеза структуры сложных систем, аппроксимации неоднозначных стохастических зависимостей.
Широкое распространение получили методы, основанные на оценивании смеси плотностей вероятности при неизвестном количестве классов и последующем анализе с помощью оптимизационных алгоритмов [3]. Выделение абстрактных образов рассматривается как поиск локальных экстремумов — максимумов непараметрической оценки плотности вероятности смеси. Однако реализация этого метода требует решения большого количества оптимизационных задач, равного числу классифицируемых объектов.
В настоящей статье задача автоматической классификации статистических данных решается формализованно в рамках задачи распознавания образов с помощью итерационной процедуры последовательного восстановления непараметрической оценки уравнения разделяющей поверхности между классами, соответствующими одномодальным фрагментам совместной плотности вероятности.
Базовый алгоритм классификации. Пусть имеется выборка V = xi , i = 1, n , состав-
ленная из значений признаков x = xv , v = 1, k , классифицируемых объектов. Необходимо разбить выборку V на группы компактных точек (классов), соответствующих одномодальным
фрагментам совместной плотности вероятности p ( x) . Априори количество M классов и вид
p ( x) неизвестны.
При синтезе данного базового алгоритма полагается, что минимальное расстояние меж-
M
∪ду элементами класса Ω j и области Ω j = Ωλ больше порогового значения d : λ=1, λ≠ j
min max
xi , xt v=1,k
xvi − xvt
> d,
xi ∈ Ω j , xt ∈ Ω j .
(1)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
74 А. В. Лапко, В. А. Лапко, А. Н. Хлопов
Восстановим непараметрическое уравнение разделяющей поверхности между классом
Ω j и областью Ω j , которое представляется следующим образом [4]:
∑ ∏f j j ( x) = ∏n
1
k
cv
n
σ(i)
i=1
k⎛ v=1 Φ ⎝⎜⎜
xv − xvi cv
⎞ ⎟⎠⎟ ,
v=1
(2)
где ядерные функции Φ (u) удовлетворяет условиям
+∞ +∞
0 ≤ Φ (u) < ∞ , ∫ Φ (u) du = 1, Φ (u) = Φ (−u), ∫ u2 Φ (u) du = 1, −∞ −∞
+∞
∫ um Φ (u) du < ∞ ∀ 0 ≤ m < ∞ ,
−∞
а cv = cv (n) , v = 1, k , — последовательности коэффициентов размытости ядерных функций,
убывающие с увеличением n . Для восстановления непараметрической оценки уравнения разделяющей поверхности
(2) необходимо идентифицировать
σ
(i
)
=
⎧⎪1 , ⎨⎩⎪−1
если xi ∈ Ω j ; , если xi ∈ Ω j
,
и определить оптимальные значения cv = cv (n) , v = 1, k .
Определим коэффициенты размытости для f j j ( x) исходя из условия минимума
критерия
( )+∞
W1 (c) = ∫
f j j ( x) − f j j ( x) 2 dx .
(3)
В выражении (3) статистика
−∞
f j j ( x) = Pj p j ( x) − Pj p j ( x)
является оценкой байесовского уравнения разделяющей поверхности [2]
f j j ( x) = Pj p j ( x) − Pj p j ( x) ,
где Pj , Pj — априорные вероятности принадлежности значения x к j-му классу и области Ω j , а Pj , Pj — их статистические оценки.
При синтезе f j j ( x) используются непараметрические оценки плотности вероятности
типа Розенблатта — Парзена [5]: например,
∑ ∏p j ( x) = ∏n j
1
k
cv i∈I j
k⎛ v=1 Φ ⎜⎝⎜
xv − cv
xvi
⎞ ⎠⎟⎟ ,
v=1
где I j — множество элементов j-го класса из выборки V , а n j — их количество.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
Непараметрический алгоритм автоматической классификации статистических данных 75
Преобразуем выражение (3):
( )+∞
W1 (c) = ∫
Pj
p j ( x) − Pj
pj
( x) − Pj
p j ( x) + Pj
pj (x)
2 dx =
−∞
( ) ( )+∞
=
∫
⎡ ⎣
Pj p j ( x) − Pj p j ( x)
−
Pj
p j ( x) − Pj
pj (x)
⎤2 ⎦
dx
=
−∞
( ) ( )+∞
=∫
Pj
p j ( x) − Pj
pj (x)
∫2 dx + +∞
Pj
p j ( x) − Pj
pj (x)
2dx −
−∞ −∞
+∞
( ) ( )−2 ∫ Pj p j ( x) − Pj p j ( x) Pj p j ( x) − Pj p j ( x) dx . −∞
Так как в соответствии с постановкой задачи автоматической классификации классы не пересекаются, то третье слагаемое равно нулю.
Аналогичным образом определим среднеквадратический критерий
W2
(c
)
=
+∞
∫
(
p
(
x)
−
p
(
x))2
dx
−∞
расхождения между совместной плотностью вероятности
p ( x) = Pj p j ( x) + Pj p j ( x)
и ее непараметрической оценкой
p ( x) = Pj p j ( x) + Pj p j ( x) .
Нетрудно показать, что W2 (c) отличается от W1 (c) только знаком третьего слагаемого,
которое в соответствии с определением класса равно нулю. Отсюда следует, что выбор оптимальных коэффициентов размытости ядерных функций
в непараметрическом уравнении разделяющей поверхности (2) сводится к их определению согласно условию минимума статистической оценки критерия
W2
(с)
=
⎡+∞
⎢∫
p2
(
x)
dx
−
+∞
2∫
p
(
x)p
(
x)
dx
+
+∞
∫
p2
(
x)
⎤ dx⎥
.
⎢⎣−∞ −∞
−∞ ⎥⎦
Так как третье его слагаемое не зависит от искомого параметра c , то, оценивая второе
слагаемое в виде среднего значения p ( x) , получаем критерий
∏ ∑ ∑ ∫ ∏W2 (с) =
n2
1
k
cv2
n i=1
n +∞ j=1 −∞
⎡k ⎢ ⎣⎢ v=1
⎛ Φ ⎜⎝⎜
xv
− cv
xvi
⎞ ⎟⎟⎠
Φ
⎛ ⎜⎝⎜
xv
− cv
xvj
⎞⎤ ⎠⎟⎟⎥⎦⎥ dx −
v=1
⎛⎞
∑ ∏ ∑∏−
2 n
n i=1
⎜ ⎜
1
⎜k
⎜⎜⎝ n v=1 cv
n j=1
k v=1
Φ
⎛ ⎜⎜⎝
xvi
− cv
xvj
i≠ j
⎞ ⎠⎟⎟
⎟ ⎟ ⎟ ⎟⎠⎟
,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
76 А. В. Лапко, В. А. Лапко, А. Н. Хлопов
минимизация которого позволяет найти оптимальные параметры статистики (2).
Таким образом, не зная вид f j j ( x) , можно определить ее параметры cv = cv (n) ,
v = 1, k . Будем считать, что с < d , где d — минимальное расстояние между классами Ω1 и Ω1 .
С учетом условия (1) для реализации базового алгоритма классификации необходимо выполнить следующие действия.
( )1. Выбрать из исходной выборки V = xi , i = 1, n , точку xi , в которой p xi ≠ 0 , и отне-
сти ее к первому классу, т.е. xi ∈ Ω1 и σ(i) = 1.
2. Осуществить первый этап классификации точек, принадлежащих классу Ω1 , в соответствии с правилом
∏xt
∈ Ω1
и
σ(t ) = 1, если
k1 v=1 cv
Φ
⎛ ⎝⎜⎜
xvt
− cv
xvi
⎞ ⎟⎟⎠
>
0
,
t∈I
(i),
I
= i = 1, n .
(4)
Справедливость правила (4) следует из условия cv < d , v = 1, k .
Обозначим множество номеров точек, принадлежащих в соответствии с правилом (4) к
первому классу, через I11 , включая номер i .
3. Провести классификацию точек, принадлежащих классу Ω1 , по следующему правилу:
∑ ∏xt ∈ Ω1 и σ(t ) = 1, если
1 I11
γ∈I11
σ
(
γ
)
1 cv
k⎛ v=1 Φ ⎜⎝⎜
xvt − xvγ cv
⎞ ⎟⎟⎠
>
0,
t∈I
I11 ,
I
=i
= 1, n ,
где I11 — количество элементов множества I11 .
Обозначим через I12 множество номеров точек, принадлежащих на втором и третьем шаге классификации к классу Ω1 .
4. Продолжить классификацию точек, принадлежащих классу Ω1 , по правилу
∑ ∏xt ∈ Ω1 и σ(t ) = 1, если
1 I12
γ∈I12
σ
(
γ
)
1 cv
k⎛ v=1 Φ ⎝⎜⎜
xvt − xvγ cv
⎞ ⎟⎟⎠
> 0,
t∈I
I12 .
5. Предложенную методику классификации продолжать до тех пор, пока на некотором
(S + 1) -м этапе в соответствии с правилом
∑ ∏xt ∈ Ω1 и σ(t ) = 1, если
1 I1S
γ∈I1S
σ
(
γ
)
1 cv
k⎛ v=1 Φ ⎜⎜⎝
xvt − xvγ cv
⎞ ⎟⎟⎠
>
0
к первому классу не будет отнесена ни одна из точек xt , t ∈ I I1S . Таким образом, множество точек xi , i ∈ I1S , образуют первый класс Ω1 , а xi ,
i ∈ I I1S , — объединение остальных классов Ω j , j = 2 , M .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
Непараметрический алгоритм автоматической классификации статистических данных 77
При этом непараметрическое уравнение разделяющей поверхности между классом Ω1 и
областью Ω1 имеет вид
∑ ∏f11
(x)
=
1 n
n
σ(i)
i=1
k v=1
1 cv
⎛ Φ ⎜⎝⎜
xv − cv
xvi
⎞ ⎠⎟⎟
,
где
σ
(i
)
=
⎪⎧1 , ⎨⎩⎪−1
если xi ∈ Ω1; , если xi ∈ Ω
1
.
Аналогичным образом можно выделить точки, принадлежащие второму классу и всем
остальным, если d < cv , v = 1, k . Ближайшим аналогом базового алгоритма классификации является алгоритм „Форель“ [6]. Обобщенный алгоритм классификации. Если расстояние между классами d = 0 , для
решения задачи автоматической классификации предлагается выполнить следующие действия. 1. Задать некоторое значение непараметрической оценки p1 > 0 совместной плотности
вероятности p ( x) и из исходной выборки V = xi , i = 1, n , выделить множество точек
( )V1 = xi : p xi > p1 , i = 1, n , со значением p ( x) , превышающим p1 .
Множество V1 может содержать точки, принадлежащие центру Ω1j некоторого класса
M
∪Ω j и области Ω1j = Ω1t , расстояние между которыми d1 > 0 . t =1 t≠ j 2. Используя базовый алгоритм автоматической классификации, провести декомпози-
цию выборки V1. Если d1 больше хотя бы одного из значений коэффициентов cv , v = 1, k ,
непараметрической оценки плотности вероятности p ( x) , то в соответствии с методикой,
принятой для базового алгоритма, будут обнаружены множества V1 ( j) , V1 ( j ) точек, опреде-
ляющих центры Ω1j , Ω1j класса Ω j и области Ω j . Для идентификации остальных точек j -го
класса перейти к п. 3.
Если центры классов не обнаружены, то необходимо увеличить значение p1 на величи-
ну ∆ p и перейти к п. 1. В этом случае расстояние d1 между центрами j -го класса и области
Ω1j увеличится и вероятность того, что d1 > cv , v = 1, k , повысится.
3. Сформировать обучающую выборку xi , σ (i) , i ∈ I1 , здесь I1 — множество номеров
точек из V1, а
σ
(
i
)
=
⎪⎧1 , ⎪⎨⎩−1
если xi ∈V1 (
, если xi ∈V1
j),
(j
).
4. Построить непараметрическое решающее правило распознавания образов
m1j
j
(x)
:
⎪⎧x ⎨ ⎪⎩x
∈ ∈
Ω Ω
j j
, ,
если если
f
1 jj
(x)
>
0;
f
1 jj
(x)
≤
0,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
78 А. В. Лапко, В. А. Лапко, А. Н. Хлопов
где
∑ ∏f
1 jj
(x)
=
1 I1
σ(i)
i∈I1
k v=1
1 сv
⎛ Φ ⎜⎝⎜
xv − cv
xvi
⎞ ⎟⎟⎠
.
5. В соответствии с правилом m1j j ( x) осуществить классификацию оставшихся точек
xi , i ∈ I I1 , из исходной статистической выборки. Нетрудно заметить, что j -му классу будут принадлежать новые точки xi , находящиеся в c -окрестности граничных точек множест-
ва V1 ( j) . 6. По результатам классификации расширить обучающую выборку xi , σ (i) , i ∈ I1 , где
I1 = I1∪ R ; R = Rj ∪ Rj — множество номеров точек, принадлежащих на шаге 5 к классу
Ω j и области Ω j . При этом
V1 ( j) = V1 ( j)∪ xi , i ∈ Rj ; V1 ( j ) = V1 ( j )∪ xi , i ∈ Rj .
7. Если все точки исходной выборки V распределены между классом Ω j и областью
Ω j , т.е. I1 = I , перейти к п. 8, иначе — вернуться к выполнению п. 4.
8. Провести повторную классификацию точек исходной выборки V = xt , t = 1, n , с помощью решающего правила
( ) (( ))mj j
xt
:
⎧ ⎪
xt
⎨ ⎪⎩
xt
∈ ∈
Ω Ω
j j
, ,
если если
fj j fj j
xt xt
> 0; ≤ 0,
где
( ) ∑ ∏f j j
xt
=
1 n
n
σ(i)
i=1
k v=1
1 cv
⎛ Φ ⎜⎝⎜
xvt − cv
xvi
⎞ ⎟⎟⎠
.
i≠t
На данном шаге уточняется граница между классом Ω j и областью Ω j , если им соот-
ветствуют несимметричные фрагменты оценки плотности вероятности p ( x) . Действия на
шаге 8 повторяются до тех пор, пока не будет завершено перераспределение точек между классом Ω j и областью Ω j .
9. Осуществить проверку на однородность класса Ω j . Для этого в соответствии с пп. 1,
2 проверить возможность разбиения выборки V1 ( j) на группы точек, соответствующих од-
номодальным фрагментам оценки плотности вероятности в области Ω j . Исследование начи-
нается с уровня p1 оценки плотности вероятности, при котором ранее были выделены центры
класса Ω j и области Ω j . При обнаружении неоднородности выборки V1 ( j ) осуществляется
ее декомпозиция согласно пп. 1—8. Если в области Ω j дополнительно классы не выделены, то перейти к обнаружению но-
вого класса в соответствии с приведенной выше методикой, анализируя выборку V1 ( j ) в об-
ласти Ω j .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
Непараметрический алгоритм автоматической классификации статистических данных 79
Исследования, результаты которых представлены в настоящей статье, выполнены в рамках Федеральной целевой программы „Научные и научно-педагогические кадры инновационной России“ на 2009—2013 гг., гос. контракт № 02.740.11.0621.
СПИСОК ЛИТЕРАТУРЫ
1. Дорофеюк А. А. Алгоритмы автоматической классификации // Автоматика и телемеханика. 1971. № 12. С. 78—113.
2. Цыпкин Я. 3. Основы теории обучающихся систем. М.: Наука, 1970.
3. Самообучение распознаванию образов по методу смешанных распределений / В. И. Васильев, В. В. Коноваленко, Ф. П. Овсянникова. Киев, 1974. (Препринт / АН УСССР. Ин-т кибернетики; № 74—30).
4. Лапко А. В., Лапко В. А., Соколов М. И., Ченцов С. В. Непараметрические системы классификации. Новосибирск: Наука, 2000.
5. Parzen E. On estimation of a probability density function and mode // Ann. Math. Statistic. 1962. Vol. 33, N 3. P. 1065—1076.
6. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Ин-та математики, 1999.
Александр Васильевич Лапко Василий Александрович Лапко
Алексей Николаевич Хлопов
Сведения об авторах — д-р техн. наук, профессор; Институт вычислительного моделирования
СО РАН, Красноярск; E-mail: lapko@icm.krasn.ru — д-р техн. наук, профессор; Сибирский государственный аэрокосмиче-
ский университет им. акад. М. Ф. Решетнёва, кафедра космических средств и технологий, Красноярск; Е-mail: lapko@icm.krasn.ru — аспирант; Сибирский государственный аэрокосмический университет им. акад. М. Ф. Решетнёва, кафедра космических средств и технологий, Красноярск; E-mail: alexhl@list.ru
Рекомендована СибГАУ
Поступила в редакцию 19.11.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
УДК 681.513
А. В. ЛАПКО, В. А. ЛАПКО, А. Н. ХЛОПОВ
НЕПАРАМЕТРИЧЕСКИЙ АЛГОРИТМ АВТОМАТИЧЕСКОЙ КЛАССИФИКАЦИИ СТАТИСТИЧЕСКИХ ДАННЫХ
Предлагается непараметрический алгоритм автоматической классификации статистических данных, основу которого составляют оценки плотности вероятности парзеновского типа. Применение алгоритма позволяет выделять компактные множества точек, соответствующих одномодальным фрагментам плотности вероятности.
Ключевые слова: непараметрическая статистика, автоматическая классификация, распознавание образов, плотность вероятности.
Методы автоматической классификации статистических данных широко используются при разработке математического обеспечения аппаратно-программных комплексов технического зрения, а также при создании систем обработки данных дистанционного зондирования Земли. Среди алгоритмов автоматической классификации, основанных на явном определении класса, следует отметить те, которые ориентированы на обнаружение множества объектов, соответствующих одномодальным фрагментам совместной плотности вероятности в заданном пространстве признаков [1, 2]. Определение класса связано с понятием закономерности в вероятностном смысле и имеет прикладную направленность в задачах синтеза структуры сложных систем, аппроксимации неоднозначных стохастических зависимостей.
Широкое распространение получили методы, основанные на оценивании смеси плотностей вероятности при неизвестном количестве классов и последующем анализе с помощью оптимизационных алгоритмов [3]. Выделение абстрактных образов рассматривается как поиск локальных экстремумов — максимумов непараметрической оценки плотности вероятности смеси. Однако реализация этого метода требует решения большого количества оптимизационных задач, равного числу классифицируемых объектов.
В настоящей статье задача автоматической классификации статистических данных решается формализованно в рамках задачи распознавания образов с помощью итерационной процедуры последовательного восстановления непараметрической оценки уравнения разделяющей поверхности между классами, соответствующими одномодальным фрагментам совместной плотности вероятности.
Базовый алгоритм классификации. Пусть имеется выборка V = xi , i = 1, n , состав-
ленная из значений признаков x = xv , v = 1, k , классифицируемых объектов. Необходимо разбить выборку V на группы компактных точек (классов), соответствующих одномодальным
фрагментам совместной плотности вероятности p ( x) . Априори количество M классов и вид
p ( x) неизвестны.
При синтезе данного базового алгоритма полагается, что минимальное расстояние меж-
M
∪ду элементами класса Ω j и области Ω j = Ωλ больше порогового значения d : λ=1, λ≠ j
min max
xi , xt v=1,k
xvi − xvt
> d,
xi ∈ Ω j , xt ∈ Ω j .
(1)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
74 А. В. Лапко, В. А. Лапко, А. Н. Хлопов
Восстановим непараметрическое уравнение разделяющей поверхности между классом
Ω j и областью Ω j , которое представляется следующим образом [4]:
∑ ∏f j j ( x) = ∏n
1
k
cv
n
σ(i)
i=1
k⎛ v=1 Φ ⎝⎜⎜
xv − xvi cv
⎞ ⎟⎠⎟ ,
v=1
(2)
где ядерные функции Φ (u) удовлетворяет условиям
+∞ +∞
0 ≤ Φ (u) < ∞ , ∫ Φ (u) du = 1, Φ (u) = Φ (−u), ∫ u2 Φ (u) du = 1, −∞ −∞
+∞
∫ um Φ (u) du < ∞ ∀ 0 ≤ m < ∞ ,
−∞
а cv = cv (n) , v = 1, k , — последовательности коэффициентов размытости ядерных функций,
убывающие с увеличением n . Для восстановления непараметрической оценки уравнения разделяющей поверхности
(2) необходимо идентифицировать
σ
(i
)
=
⎧⎪1 , ⎨⎩⎪−1
если xi ∈ Ω j ; , если xi ∈ Ω j
,
и определить оптимальные значения cv = cv (n) , v = 1, k .
Определим коэффициенты размытости для f j j ( x) исходя из условия минимума
критерия
( )+∞
W1 (c) = ∫
f j j ( x) − f j j ( x) 2 dx .
(3)
В выражении (3) статистика
−∞
f j j ( x) = Pj p j ( x) − Pj p j ( x)
является оценкой байесовского уравнения разделяющей поверхности [2]
f j j ( x) = Pj p j ( x) − Pj p j ( x) ,
где Pj , Pj — априорные вероятности принадлежности значения x к j-му классу и области Ω j , а Pj , Pj — их статистические оценки.
При синтезе f j j ( x) используются непараметрические оценки плотности вероятности
типа Розенблатта — Парзена [5]: например,
∑ ∏p j ( x) = ∏n j
1
k
cv i∈I j
k⎛ v=1 Φ ⎜⎝⎜
xv − cv
xvi
⎞ ⎠⎟⎟ ,
v=1
где I j — множество элементов j-го класса из выборки V , а n j — их количество.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
Непараметрический алгоритм автоматической классификации статистических данных 75
Преобразуем выражение (3):
( )+∞
W1 (c) = ∫
Pj
p j ( x) − Pj
pj
( x) − Pj
p j ( x) + Pj
pj (x)
2 dx =
−∞
( ) ( )+∞
=
∫
⎡ ⎣
Pj p j ( x) − Pj p j ( x)
−
Pj
p j ( x) − Pj
pj (x)
⎤2 ⎦
dx
=
−∞
( ) ( )+∞
=∫
Pj
p j ( x) − Pj
pj (x)
∫2 dx + +∞
Pj
p j ( x) − Pj
pj (x)
2dx −
−∞ −∞
+∞
( ) ( )−2 ∫ Pj p j ( x) − Pj p j ( x) Pj p j ( x) − Pj p j ( x) dx . −∞
Так как в соответствии с постановкой задачи автоматической классификации классы не пересекаются, то третье слагаемое равно нулю.
Аналогичным образом определим среднеквадратический критерий
W2
(c
)
=
+∞
∫
(
p
(
x)
−
p
(
x))2
dx
−∞
расхождения между совместной плотностью вероятности
p ( x) = Pj p j ( x) + Pj p j ( x)
и ее непараметрической оценкой
p ( x) = Pj p j ( x) + Pj p j ( x) .
Нетрудно показать, что W2 (c) отличается от W1 (c) только знаком третьего слагаемого,
которое в соответствии с определением класса равно нулю. Отсюда следует, что выбор оптимальных коэффициентов размытости ядерных функций
в непараметрическом уравнении разделяющей поверхности (2) сводится к их определению согласно условию минимума статистической оценки критерия
W2
(с)
=
⎡+∞
⎢∫
p2
(
x)
dx
−
+∞
2∫
p
(
x)p
(
x)
dx
+
+∞
∫
p2
(
x)
⎤ dx⎥
.
⎢⎣−∞ −∞
−∞ ⎥⎦
Так как третье его слагаемое не зависит от искомого параметра c , то, оценивая второе
слагаемое в виде среднего значения p ( x) , получаем критерий
∏ ∑ ∑ ∫ ∏W2 (с) =
n2
1
k
cv2
n i=1
n +∞ j=1 −∞
⎡k ⎢ ⎣⎢ v=1
⎛ Φ ⎜⎝⎜
xv
− cv
xvi
⎞ ⎟⎟⎠
Φ
⎛ ⎜⎝⎜
xv
− cv
xvj
⎞⎤ ⎠⎟⎟⎥⎦⎥ dx −
v=1
⎛⎞
∑ ∏ ∑∏−
2 n
n i=1
⎜ ⎜
1
⎜k
⎜⎜⎝ n v=1 cv
n j=1
k v=1
Φ
⎛ ⎜⎜⎝
xvi
− cv
xvj
i≠ j
⎞ ⎠⎟⎟
⎟ ⎟ ⎟ ⎟⎠⎟
,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
76 А. В. Лапко, В. А. Лапко, А. Н. Хлопов
минимизация которого позволяет найти оптимальные параметры статистики (2).
Таким образом, не зная вид f j j ( x) , можно определить ее параметры cv = cv (n) ,
v = 1, k . Будем считать, что с < d , где d — минимальное расстояние между классами Ω1 и Ω1 .
С учетом условия (1) для реализации базового алгоритма классификации необходимо выполнить следующие действия.
( )1. Выбрать из исходной выборки V = xi , i = 1, n , точку xi , в которой p xi ≠ 0 , и отне-
сти ее к первому классу, т.е. xi ∈ Ω1 и σ(i) = 1.
2. Осуществить первый этап классификации точек, принадлежащих классу Ω1 , в соответствии с правилом
∏xt
∈ Ω1
и
σ(t ) = 1, если
k1 v=1 cv
Φ
⎛ ⎝⎜⎜
xvt
− cv
xvi
⎞ ⎟⎟⎠
>
0
,
t∈I
(i),
I
= i = 1, n .
(4)
Справедливость правила (4) следует из условия cv < d , v = 1, k .
Обозначим множество номеров точек, принадлежащих в соответствии с правилом (4) к
первому классу, через I11 , включая номер i .
3. Провести классификацию точек, принадлежащих классу Ω1 , по следующему правилу:
∑ ∏xt ∈ Ω1 и σ(t ) = 1, если
1 I11
γ∈I11
σ
(
γ
)
1 cv
k⎛ v=1 Φ ⎜⎝⎜
xvt − xvγ cv
⎞ ⎟⎟⎠
>
0,
t∈I
I11 ,
I
=i
= 1, n ,
где I11 — количество элементов множества I11 .
Обозначим через I12 множество номеров точек, принадлежащих на втором и третьем шаге классификации к классу Ω1 .
4. Продолжить классификацию точек, принадлежащих классу Ω1 , по правилу
∑ ∏xt ∈ Ω1 и σ(t ) = 1, если
1 I12
γ∈I12
σ
(
γ
)
1 cv
k⎛ v=1 Φ ⎝⎜⎜
xvt − xvγ cv
⎞ ⎟⎟⎠
> 0,
t∈I
I12 .
5. Предложенную методику классификации продолжать до тех пор, пока на некотором
(S + 1) -м этапе в соответствии с правилом
∑ ∏xt ∈ Ω1 и σ(t ) = 1, если
1 I1S
γ∈I1S
σ
(
γ
)
1 cv
k⎛ v=1 Φ ⎜⎜⎝
xvt − xvγ cv
⎞ ⎟⎟⎠
>
0
к первому классу не будет отнесена ни одна из точек xt , t ∈ I I1S . Таким образом, множество точек xi , i ∈ I1S , образуют первый класс Ω1 , а xi ,
i ∈ I I1S , — объединение остальных классов Ω j , j = 2 , M .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
Непараметрический алгоритм автоматической классификации статистических данных 77
При этом непараметрическое уравнение разделяющей поверхности между классом Ω1 и
областью Ω1 имеет вид
∑ ∏f11
(x)
=
1 n
n
σ(i)
i=1
k v=1
1 cv
⎛ Φ ⎜⎝⎜
xv − cv
xvi
⎞ ⎠⎟⎟
,
где
σ
(i
)
=
⎪⎧1 , ⎨⎩⎪−1
если xi ∈ Ω1; , если xi ∈ Ω
1
.
Аналогичным образом можно выделить точки, принадлежащие второму классу и всем
остальным, если d < cv , v = 1, k . Ближайшим аналогом базового алгоритма классификации является алгоритм „Форель“ [6]. Обобщенный алгоритм классификации. Если расстояние между классами d = 0 , для
решения задачи автоматической классификации предлагается выполнить следующие действия. 1. Задать некоторое значение непараметрической оценки p1 > 0 совместной плотности
вероятности p ( x) и из исходной выборки V = xi , i = 1, n , выделить множество точек
( )V1 = xi : p xi > p1 , i = 1, n , со значением p ( x) , превышающим p1 .
Множество V1 может содержать точки, принадлежащие центру Ω1j некоторого класса
M
∪Ω j и области Ω1j = Ω1t , расстояние между которыми d1 > 0 . t =1 t≠ j 2. Используя базовый алгоритм автоматической классификации, провести декомпози-
цию выборки V1. Если d1 больше хотя бы одного из значений коэффициентов cv , v = 1, k ,
непараметрической оценки плотности вероятности p ( x) , то в соответствии с методикой,
принятой для базового алгоритма, будут обнаружены множества V1 ( j) , V1 ( j ) точек, опреде-
ляющих центры Ω1j , Ω1j класса Ω j и области Ω j . Для идентификации остальных точек j -го
класса перейти к п. 3.
Если центры классов не обнаружены, то необходимо увеличить значение p1 на величи-
ну ∆ p и перейти к п. 1. В этом случае расстояние d1 между центрами j -го класса и области
Ω1j увеличится и вероятность того, что d1 > cv , v = 1, k , повысится.
3. Сформировать обучающую выборку xi , σ (i) , i ∈ I1 , здесь I1 — множество номеров
точек из V1, а
σ
(
i
)
=
⎪⎧1 , ⎪⎨⎩−1
если xi ∈V1 (
, если xi ∈V1
j),
(j
).
4. Построить непараметрическое решающее правило распознавания образов
m1j
j
(x)
:
⎪⎧x ⎨ ⎪⎩x
∈ ∈
Ω Ω
j j
, ,
если если
f
1 jj
(x)
>
0;
f
1 jj
(x)
≤
0,
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
78 А. В. Лапко, В. А. Лапко, А. Н. Хлопов
где
∑ ∏f
1 jj
(x)
=
1 I1
σ(i)
i∈I1
k v=1
1 сv
⎛ Φ ⎜⎝⎜
xv − cv
xvi
⎞ ⎟⎟⎠
.
5. В соответствии с правилом m1j j ( x) осуществить классификацию оставшихся точек
xi , i ∈ I I1 , из исходной статистической выборки. Нетрудно заметить, что j -му классу будут принадлежать новые точки xi , находящиеся в c -окрестности граничных точек множест-
ва V1 ( j) . 6. По результатам классификации расширить обучающую выборку xi , σ (i) , i ∈ I1 , где
I1 = I1∪ R ; R = Rj ∪ Rj — множество номеров точек, принадлежащих на шаге 5 к классу
Ω j и области Ω j . При этом
V1 ( j) = V1 ( j)∪ xi , i ∈ Rj ; V1 ( j ) = V1 ( j )∪ xi , i ∈ Rj .
7. Если все точки исходной выборки V распределены между классом Ω j и областью
Ω j , т.е. I1 = I , перейти к п. 8, иначе — вернуться к выполнению п. 4.
8. Провести повторную классификацию точек исходной выборки V = xt , t = 1, n , с помощью решающего правила
( ) (( ))mj j
xt
:
⎧ ⎪
xt
⎨ ⎪⎩
xt
∈ ∈
Ω Ω
j j
, ,
если если
fj j fj j
xt xt
> 0; ≤ 0,
где
( ) ∑ ∏f j j
xt
=
1 n
n
σ(i)
i=1
k v=1
1 cv
⎛ Φ ⎜⎝⎜
xvt − cv
xvi
⎞ ⎟⎟⎠
.
i≠t
На данном шаге уточняется граница между классом Ω j и областью Ω j , если им соот-
ветствуют несимметричные фрагменты оценки плотности вероятности p ( x) . Действия на
шаге 8 повторяются до тех пор, пока не будет завершено перераспределение точек между классом Ω j и областью Ω j .
9. Осуществить проверку на однородность класса Ω j . Для этого в соответствии с пп. 1,
2 проверить возможность разбиения выборки V1 ( j) на группы точек, соответствующих од-
номодальным фрагментам оценки плотности вероятности в области Ω j . Исследование начи-
нается с уровня p1 оценки плотности вероятности, при котором ранее были выделены центры
класса Ω j и области Ω j . При обнаружении неоднородности выборки V1 ( j ) осуществляется
ее декомпозиция согласно пп. 1—8. Если в области Ω j дополнительно классы не выделены, то перейти к обнаружению но-
вого класса в соответствии с приведенной выше методикой, анализируя выборку V1 ( j ) в об-
ласти Ω j .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4
Непараметрический алгоритм автоматической классификации статистических данных 79
Исследования, результаты которых представлены в настоящей статье, выполнены в рамках Федеральной целевой программы „Научные и научно-педагогические кадры инновационной России“ на 2009—2013 гг., гос. контракт № 02.740.11.0621.
СПИСОК ЛИТЕРАТУРЫ
1. Дорофеюк А. А. Алгоритмы автоматической классификации // Автоматика и телемеханика. 1971. № 12. С. 78—113.
2. Цыпкин Я. 3. Основы теории обучающихся систем. М.: Наука, 1970.
3. Самообучение распознаванию образов по методу смешанных распределений / В. И. Васильев, В. В. Коноваленко, Ф. П. Овсянникова. Киев, 1974. (Препринт / АН УСССР. Ин-т кибернетики; № 74—30).
4. Лапко А. В., Лапко В. А., Соколов М. И., Ченцов С. В. Непараметрические системы классификации. Новосибирск: Наука, 2000.
5. Parzen E. On estimation of a probability density function and mode // Ann. Math. Statistic. 1962. Vol. 33, N 3. P. 1065—1076.
6. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Ин-та математики, 1999.
Александр Васильевич Лапко Василий Александрович Лапко
Алексей Николаевич Хлопов
Сведения об авторах — д-р техн. наук, профессор; Институт вычислительного моделирования
СО РАН, Красноярск; E-mail: lapko@icm.krasn.ru — д-р техн. наук, профессор; Сибирский государственный аэрокосмиче-
ский университет им. акад. М. Ф. Решетнёва, кафедра космических средств и технологий, Красноярск; Е-mail: lapko@icm.krasn.ru — аспирант; Сибирский государственный аэрокосмический университет им. акад. М. Ф. Решетнёва, кафедра космических средств и технологий, Красноярск; E-mail: alexhl@list.ru
Рекомендована СибГАУ
Поступила в редакцию 19.11.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 4