close

Вход

Забыли?

вход по аккаунту

?

«Быстрый» непараметрический алгоритм классификации множеств случайных величин.

код для вставкиСкачать
Математика и информатика
МАТЕМАТИКА И ИНФОРМАТИКА
УДК 681.513
А.В. Лапко, В.А. Лапко
«БЫСТРЫЙ» НЕПАРАМЕТРИЧЕСКИЙ АЛГОРИТМ КЛАССИФИКАЦИИ
МНОЖЕСТВ СЛУЧАЙНЫХ ВЕЛИЧИН
На основе последовательных процедур формирования решений разработаны непараметрические алгоритмы классификации множеств случайных величин, обладающие высокой вычислительной эффективностью.
Введение. Непараметрические алгоритмы классификации множеств случайных величин впервые были предложены и исследованы в работах [1,2]. Идея подхода заключается в заменене операций над множествами X на преобразования статистических оценок функций распределения их элементов F x с помощью методов непараметрической статистики.
С этих позиций непараметрическое решающее правило классификации в двуальтернативной задаче
распознавания образов представляется в виде
 X  1 , если f12  X   0
(1)
m12 ( x) : 
 X   2 , если f12  X   0 ,
где уравнение разделяющей поверхности
1
k
 k
 n
 max F x   Fi x  

f12  X    n  D v   i    




D

v
v 1 

 v 1
 i 1
восстанавливается по обучающей выборке X i ,  i  , i  1 , n объема n ;


 1 , если X i  
1
 i   
– «указания учителя».
 1 , если X i   2
Основные и значительные временные затраты при использовании решающего правила m12  X 
связаны с построением и проверкой гипотезы о тождественности эмпирических функций распределения
F xv  , Fi xv  признаков элементов множеств X , X i , i  1 , n в соответствии с критерием Смирнова
( D – пороговое значение критерия).
v
Возникает проблема повышения вычислительной эффективности непараметрических алгоритмов
классификации множеств случайных величин, которая в работе решается на основе применения последовательных процедур формирования решений.
Постановка задачи. Имеется обучающая выборка V  X i ,  i  , i  1 , n , составленная из мно-




жеств X i независимых наблюдений признаков x  x j , j  1 , k , классифицируемых объектов a i и
«указаний учителя» об их принадлежности к одному, например, из двух классов A1 , A2 .
Законы
распределения
неизвестны
и
характеризуются
x Xi


наблюдениями
X i  x j , j  1 , ni , i  1 , n .
Обозначим через 1 ,  2 – образы классов объектов A1 , A2 в пространстве их признаков x , а

Исследования выполнены в рамках гранта РФФИ №03-01-00081.
50
Вестник КрасГАУ. 2006. №10
12  1   2 . Определим центры x i множеств X i и будем считать, что плотности вероятностей
p1 x   x  1 , p2  x   x   2 достаточно гладкие и имеют хотя бы первые две производные по
компонентам xv , v  1 , k .
Пусть m12 ( X ) , m12 ( x ) – решающие правила классификации множеств случайных величин на основе традиционного подхода (1) и построенные с позиций замены X на x .
Необходимо построить обобщенное решающее правило классификации множеств случайных величин
M12 m12 ( x ) , m12 ( X ) , по вычислительной эффективности значительно превышающее теоретически
обоснованный алгоритм распознавания образов m12 ( X ) .


Синтез алгоритма классификации. Сформируем обучающую выборку V1  x i ,  i  , i  1 , n для
построения решающего правила
 x  1 , если
m12 ( x ) : 
 x  2 , если
f12 x   0
(2)
f12 x   0 ,
где
f12  x   P1 p1 x   P2 p2  x 
(3)
– уравнение разделяющей поверхности между классами, оптимальное в смысле минимума вероятности
ошибки распознавания образов; P1 , P2 – априорные вероятности классов.
Компоненты центров x i множеств X i определяются как средние значения признаков xv , вычисj
ляемых по выборкам xv , j  1 , ni , v  1 , k , i  1 , n .
Воспользуемся методами непараметрической статистики и построим статистическую оценку (3)
1
k 
 k
 n
x  xi 
f12 x    n cv 
 i   v v  ,
(4)


 cv 

v 1 
 v 1  i 1
где  – ядерные функции, удовлетворяющие свойствам положительности, симметричности относительно x i и нормированности [1]; сv – коэффициенты размытости ядерных функций, значения которых
сv n  0 при n   .





Соответствующее уравнению (4) решающее правило m12 ( x ) обладает высокой вычислительной
эффективностью. Однако обоснованное его применение возможно только при симметричных законах распределения элементов классифицируемых множеств.
Заметим, что значение ошибки классификации формируется в области пересечения классов 12 .
  X  . С этой целью организуем вычислительный экспеПоэтому определим в 12 решающее правило m12
римент на основе алгоритма m12 ( x ) для формирования обучающей выборки V2  X i ,  i  , i  I12 ,
элементы которой принадлежат области пересечения классов 12 .


С учетом (1) осуществим синтез оценки решающего правила m12  X  на основе разделяющей поверхности
1
k




f12  X   n12
D v
 i  h X , X i ,


v 1

 iI12
где
k  max F x   F x  
i
;
h X, Xi 



D v
v 1 






51


Математика и информатика
1 , если F x   Fi x   Dv
 max F x   Fi x   



 
Dv
 

 
 0 , если F x  Fi x  Dv ,
n12 – количество элементов множества I12 .
Тогда «быстрый» алгоритм классификации множеств случайных величин представляется следующей
последовательной процедурой формирования решения:
 X  1 , если f12 x   0 и p2 x   0 ,

M ( X ) :  X  2 , если f12 x   0 и p1 x   0 ,
иначе перейти к алгоритму m   X  .
12

Отметим, что ошибки распознавания образов алгоритмов M  X  и m12  X  совпадают. Однако вы-
числительная эффективность M  X  выше, так как значительно сокращаются временные затраты на проверку гипотезы о тождественности эмпирических функций распределения из обучающей выборки и закона
распределения элементов контрольного множества.
Модификации алгоритма классификации. Дополнительно уменьшить время классификации можно
за счет сокращения количества задач
H0 : Fi x   F x  , i  I12
в процессе функционирования алгоритма m12  X  .
Введем дополнительные параметры, характеризующие множество случайных величин X i ,
Pvi  Fi xv  , v  1, k , i  I12 .
Так как
Pvi  F  xv   max Fi  xv   F  xv  ,
то гипотеза H 0 отвергается, если справедливо соотношение
Dv  Pvi  F xv  .
(5)
Проверка соотношения (5) требует значительно меньше временных затрат при формировании ядерных функций алгоритма m12  X  , чем при использовании традиционных условий критерия Смирнова.
Анализ алгоритма классификации. Для сравнения вычислительной эффективности непараметрических алгоритмов классификации множеств случайных величин обозначим через  , t – время, затрачи x  xi 
 max F xv   Fi xv  
v
v
 соответственно.
ваемое на вычисление ядерных функций  
и
 c



D v
v




Тогда время, затрачиваемое на классификацию ситуации X традиционным непараметрическим алгоритмов m12  X  (1), не превышает значения Tm  n k t , а решающим правилом
M  X  - TM  n 1  P   k  n p t k .
Здесь P – вероятность принадлежности множеств X i обучающей выборки области пересечения
классов 12 .
Время t увеличивается с ростом объема обучающей выборки. По результатам вычислительного эксперимента отношение t
 представляется линейной аппроксимацией типа  n . Тогда при достаточно
T
больших n отношение M
Tm
 P.
Заключение. Применение последовательных процедур формирования решений обеспечивает разработку непараметрических алгоритмов классификации множеств случайных величин с высокой вычислительной эффективностью. Структуру «быстрых» решающих правил составляют непараметрические алгоритмы
52
Вестник КрасГАУ. 2006. №10
распознавания образов в пространстве параметров центров анализируемых множеств и традиционные классификаторы множеств случайных величин, определенные в условиях неоднозначных решений. Вычислительная
эффективность предложенных методов повышается с сокращением области пересечения классов.
Литература
1. Непараметрические системы классификации / А.В. Лапко [и др.]. – Новосибирск: Наука, 2000. – 240 с.
2. Лапко, А.В. Непараметрические методики анализа множеств случайных величин / А.В. Лапко, В.А. Лапко
// Автометрия. – 2003. – №1. – С. 54–61.
УДК 519.7
В.А. Лапко, Р.В. Бадмаев
СИНТЕЗ И АНАЛИЗ НЕЛИНЕЙНЫХ НЕПАРАМЕТРИЧЕСКИХ КОЛЛЕКТИВОВ
РЕШАЮЩИХ ПРАВИЛ В ЗАДАЧАХ ВОССТАНОВЛЕНИЯ СТОХАСТИЧЕСКИХ
ЗАВИСИМОСТЕЙ, ОСНОВАННЫХ ПОСЛЕДОВАТЕЛЬНЫХ ПРОЦЕДУРАХ
ФОРМИРОВАНИЯ РЕШЕНИЙ
Рассматриваются нелинейные непараметрические коллективы решающих правил в задачах восстановления стохастических зависимостей, обеспечивающих
эффективное решения задач при малых выборках большой размерности. С помощью метода вычислительного эксперимента исследуются показатели эффективности нелинейных непараметрических коллективов. Полученные результаты сравниваются с традиционными непараметрическими решающими
правилами.
Введение. Последовательные процедуры принятия решений являются эффективным направлением
обхода проблем сложности и неопределенности при моделировании и оптимизации систем, что достигается
путем разбиения исходной задачи на ряд взаимосвязанных более простых задач [1]. Такая схема используется, например, в методе динамического программирования и методе группового учета аргументов (МГУА) [2–7].
Работа посвящена синтезу и анализу нелинейных непараметрических коллективов решающих правил
восстановления стохастических зависимостей для решения задач в пространствах большой размерности и
малых объемах обучающих выборок. Идея предлагаемого алгоритма заключается в декомпозиции исходной
задачи на ряд простых, решаемых в пространствах меньшей размерности. Основной проблемой при построении подобных систем принятия решений является выбор их эффективной структуры. Для решения
данной проблемы предлагается индуктивный метод выбора рациональной структуры системы, основанный
на принципах имитационного моделирования [8].
Синтез нелинейных непараметрических коллективов решающих правил. Пусть дана выборка


V  xi , y i , i  1, n из статистически независимых наблюдений значений y i неизвестной однозначной
зависимости
y   x   x  Rk
(1)
и ее аргументов x i , где x  x1 , x2 ,, xk  – вектор.
Эффективным подходом «обхода» проблемы малых выборок являются последовательные процедуры формирования решений, основанные на принципе декомпозиции исходной задачи.
Идея предлагаемого алгоритма состоит в построении семейства локальных решающих правил на основании конечных наборов признаков x  x j  , t  1 , m обучающей выборки и последующей их интеграции в едином нелинейном решающем правиле. Тогда при восстановлении искомой стохастической зависимости (1) предлагаются нелинейные непараметрические коллективы решающих правил с последователь-



Работа выполнена в рамках гранта Президента РФ №МД-2130.2005.9.
53
Документ
Категория
Без категории
Просмотров
4
Размер файла
424 Кб
Теги
величины, быстрый, алгоритм, случайных, множества, классификация, непараметрических
1/--страниц
Пожаловаться на содержимое документа