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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2009
Hauptverfasser:	Капустий, Б.Е., Таянов, В.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2009
Schlagworte:	Обучающие и экспертные системы
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/8197
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации / Капустий Б.Е., Таянов В.А. // Штучний інтелект. — 2009. — № 4. — С. 349-359. — Бібліогр.: 10 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-8197
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-81972025-02-09T11:56:06Z Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации Вплив розміру навчаючої вибірки на узагальнюючу властивість метричних алгоритмів класифікації The Influence of the Training Set Size on the Generalized Ability of the Metrical Classifiers Капустий, Б.Е. Таянов, В.А. Обучающие и экспертные системы В работе предлагается поход, обеспечивающий оценку влияния уменьшения размера классов базы данных на уровень распознавания в случае использования kNN метрических классификаторов, а также дает возможность определения по данной выборке оптимального значения k. Проведено симулятивное моделирование результатов влияния уменьшения обучающей выборки на результаты распознавания. Полученные результаты могут быть использованы для дальнейшего формирования обучающей выборки и её коррекции. В роботі пропонується підхід, який забезпечує оцінку впливу зменшення розміру класів бази даних на рівень розпізнавання при застосуванні kNN метричних класифікаторів, а також дає можливість визначення на даній вибірці оптимального значення k. Проведене симулятивне моделювання результатів впливу зменшення навчаючої вибірки на результати розпізнавання. Отриманні результати можуть бути використані для подальшого формування навчаючої вибірки та її корекції. In this paper the approach giving the estimate of the class size reduction influence on the recognition rate for the kNN classifiers has been proposed. The approach also gives the possibility to estimate the optimal k value of the nearest neighbours. The simulative modeling of the training set reduction influence on the recognition process results has been carried out. The obtained results can be used for the training set formation and its correction. 2009 Article Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации / Капустий Б.Е., Таянов В.А. // Штучний інтелект. — 2009. — № 4. — С. 349-359. — Бібліогр.: 10 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8197 004.93+519.2 ru application/pdf Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Обучающие и экспертные системы Обучающие и экспертные системы
spellingShingle	Обучающие и экспертные системы Обучающие и экспертные системы Капустий, Б.Е. Таянов, В.А. Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации
description	В работе предлагается поход, обеспечивающий оценку влияния уменьшения размера классов базы данных на уровень распознавания в случае использования kNN метрических классификаторов, а также дает возможность определения по данной выборке оптимального значения k. Проведено симулятивное моделирование результатов влияния уменьшения обучающей выборки на результаты распознавания. Полученные результаты могут быть использованы для дальнейшего формирования обучающей выборки и её коррекции.
format	Article
author	Капустий, Б.Е. Таянов, В.А.
author_facet	Капустий, Б.Е. Таянов, В.А.
author_sort	Капустий, Б.Е.
title	Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации
title_short	Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации
title_full	Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации
title_fullStr	Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации
title_full_unstemmed	Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации
title_sort	влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2009
topic_facet	Обучающие и экспертные системы
url	https://nasplib.isofts.kiev.ua/handle/123456789/8197
citation_txt	Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации / Капустий Б.Е., Таянов В.А. // Штучний інтелект. — 2009. — № 4. — С. 349-359. — Бібліогр.: 10 назв. — рос.
work_keys_str_mv	AT kapustijbe vliânierazmeraobučaûŝejvyborkinaobobŝaûŝuûsposobnostʹmetričeskihalgoritmovklassifikacii AT taânovva vliânierazmeraobučaûŝejvyborkinaobobŝaûŝuûsposobnostʹmetričeskihalgoritmovklassifikacii AT kapustijbe vplivrozmírunavčaûčoívibírkinauzagalʹnûûčuvlastivístʹmetričnihalgoritmívklasifíkacíí AT taânovva vplivrozmírunavčaûčoívibírkinauzagalʹnûûčuvlastivístʹmetričnihalgoritmívklasifíkacíí AT kapustijbe theinfluenceofthetrainingsetsizeonthegeneralizedabilityofthemetricalclassifiers AT taânovva theinfluenceofthetrainingsetsizeonthegeneralizedabilityofthemetricalclassifiers
first_indexed	2025-11-25T22:46:01Z
last_indexed	2025-11-25T22:46:01Z
_version_	1849804206562607104
fulltext	«Штучний інтелект» 4’2009 349 7К УДК 004.93+519.2 Капустий Б.Е.1, Таянов В.А.2 1 НУ «Львовская политехника», г. Львов, Украина 2 ФМИ им. Г.В. Карпенко НАН Украины, г. Львов, Украина vtayanov@ipm.lviv.ua Влияние размера обучающей выборки на обобщающую способность метрических алгоритмов классификации В работе предлагается поход, обеспечивающий оценку влияния уменьшения размера классов базы данных на уровень распознавания в случае использования kNN метрических классификаторов, а также дает возможность определения по данной выборке оптимального значения k. Проведено симулятивное моделирование результатов влияния уменьшения обучающей выборки на результаты распознавания. Полученные результаты могут быть использованы для дальнейшего формирования обучающей выборки и её коррекции. Введение На сегодняшний день метрические алгоритмы классификации являются одни- ми из самых распространенных при проектировании практических целевых систем распознавания (СР). Среди таких систем часто встречаются биометрические СР. Для метрических алгоритмов классификации характерна простота настройки и доста- точное быстродействие. В целом разработка алгоритмов классификации является отдельной и сложной задачей [1-3]. Поскольку построение СР включает этапы генерации признаков, их селекции, построения классификаторов и их оптимизации в зависимости от выбран- ных признаков, формирования доверительного интервала принятия решения и опре- деления его достаточного размера, формирования базы эталонных объектов и т.д. [1], [4-7], то в большинстве случаев используют метрические алгоритмы классификации [2], [3], [8]. Среди них чаще всего рассматривают правило ближайшего соседа (nearest neighbor, 1NN), реже – правило k ближайших соседей (k nearest neighbors, kNN) и совсем редко – взвешенный kNN классификатор [3]. Метод парзеновского окна и метод потенциальных функций в таких системах практически не используют. Одним из главных недостатков этих алгоритмов является то, что выборку необходимо со- хранять полностью, а время распознавания прямо пропорционально длине обучаю- щей выборки. Поэтому и возникает необходимость в разработке подходов, которые дали бы возможность эффективно уменьшить обучающую выборку так, чтобы при этом уровень распознавания был не менее заданного согласно техническому зада- нию на разработку СР. Для СР сокращение обучающей выборки означает умень- шение размерности классов базы данных. При этом необходимо обязательно провес- ти стратификацию (stratification) классов. Итак, далее установим, как влияет уменьшение размерности классов на достоверность классификации при помощи kNN алгоритма. Кроме того, что ожидаемые результаты моделирования пригодны для оценива- ния влияния размера обучающей выборки на результаты распознавания, они также могут использоваться для формирования такой обучающей выборки, которая бы по- Капустий Б.Е., Таянов В.А. «Искусственный интеллект» 4’2009 350 7К зволила минимизировать эффект переобучения. Данный поход позволяет провести предварительную оценку выборки, её потенциальных возможностей обучения и кор- ректности. После его предварительной апробации необходимо осуществить исключение малоинформативных и искажающих объектов из обучающей выборки. Постановка задачи. Пусть X – пространство объектов (object space); Y – мно- жество имен классов (class name set); YXy  : – целевая функция (target function), значения которой известны лишь на объектах конечной обучающей выборки длины l : YXyxX l iii l  1),( , )( ii xyy  [3]. В базе данных существуют классы эталонов (class patterns) iC , ni ,1 , причём \|\| ii Cs  – размеры классов. Предполагается, что размеры is всех классов одинаковые и равны s . Поскольку существует выборка конт- рольных образов U , подающихся на распознавание, то общее количество образов, принимающих участие в процессе распознавания, равно \|\| Usn  . Пусть оцененная частота ошибок (error frequency) алгоритма классификации )( lXa  на обучающей выборке Ll XX  :    Ux uyua U Ua )]()([ \|\| 1),( , где запись Ux означает, что объект относится к контрольной последовательности, а запись )]()([ uyua  должна пониматься как функция индикации несовпадения ответа, даваемого алгоритмом )(ua , и правильного ответа )(uy для этого объекта. Задача состоит в оценивании величины    Ux uyua U Ua )]()(~[ \|\| 1),( ~ при понижении информационного по- крытия (information class coverage reduction) \|\| iC классов-эталонов, где ) ~ (~ lXa  – алгоритм, построенный на основании выборки размера l~ . В качестве алгоритма классификации используется алгоритм kNN. При такой общей постановке задачи наиболее пригодным подходом к её решению является комбинаторный подход. Оче- видно, что в каждом конкретном случае понижение информационного покрытия классов (information class coverage reduction) может проводиться не обязательно оптимальным образом, однако общая статистика всех возможных понижений клас- сов и результатов таких понижений должна дать ответ на вопрос об эффективности информационного покрытия классов-эталонов в целом. Алгоритм ближайшего соседа. Представим данные, подающиеся на класси- фикатор a , в виде двоичной последовательности {0,1} , посортированной по минимуму расстояний объектов базы данных от тестового объекта, где 1 ставятся в соответствие образам, поддерживающим правильное распознавание (образы своего класса), а 0 – образам, мешающим такому распознаванию (образы чужих классов). Пример такой последовательности подан на рис. 1.  ...1111000...110001111001110001111111111 },{ 332211     mk kmkmkmkml nn Рисунок 1 – Модель распознавания при задании начального размера класса в виде двоичной последовательности Из приведенного рисунка видно, что последовательность образов, поддер- живающих распознавание, имеет размерность skl  . Однако различные образы существенно отличаются друг от друга по возможностям этой поддержки. Действи- Влияние размера обучающей выборки на обобщающую способность… «Штучний інтелект» 4’2009 351 7К тельно, при использовании 1NN классификатора удаление 1l образов из класса- эталона не изменит результатов распознавания. С другой стороны, какой бы длинной ни была последовательность из k образов, она не сможет поддержать распознавание при отсутствии стратегической последовательности размером l и присутствии последо- вательности размером m . При понижении размера обучающей выборки необходимо учитывать тот факт, что если последовательность размером l присутствует в начальном классе, то в классе с меньшим информационным покрытием s она может исчезнуть, и наоборот, если её не было, то может появиться, однако с меньшим размером l . Рассмотрим возможности 1NN классификатора. Определяющим преимущест- вом этого классификатора является простота реализации, а к недостаткам можно от- нести следующие [3]: – неустойчивость к погрешностям, созданным выбросами в обучающей выборке (вы- бросом называют объект определенного класса, находящийся в окружении объектов чужих классов); – полную зависимость алгоритма от метрики между объектами и отсутствие парамет- ров для настройки по обучающей выборке методами скользящего контроля или иными. – низкое качество классификации. Несмотря на указанные недостатки, 1NN классификатор может иметь сущест- венно лучшую устойчивость к эффекту понижения размера обучающей выборки. Это связано с тем, что данный классификатор менее чувствительный к размеру клас- сов, чем kNN. Итак, возможны два случая: начальное распознавание правильное либо непра- вильное, и необходимо определить вероятность его успешности после понижения размера обучающей выборки. То есть для первого случая необходимо определить вероятность того, что распознавание останется правильным, а для второго – вероят- ность перехода распознавания из категории неправильного в категорию правиль- ного. Представим вероятность правильного распознавания при применении 1NN классификатора как отношение событий, поддерживающих успешное распознава- ние, к общему количеству событий:                 . ,1 ; , )!(! )!(!1 ),,( случаеобратном в sk sks ssk C CC slkP s s s k s s (1) При вычислении вероятностей (1) учтено, что если  sk и начальное распо- знавание было правильным, то понижение размера обучающей выборки не приведет к ухудшению результатов распознавания, то есть 1)1)(\|(   sPskP . Выражение (1) определяет вероятность того, что распознавание будет успешным независимо от того, каким образом был уменьшен размер обучающей выборки для своего и чужих классов. Таким образом, эта вероятность является оценкой сверху по отношению к точному (в смысле комбинаторики) значению вероятности правильного распознава- ния. Сам принцип оценок сверху вероятности успешного распознавания состоит в том, что вычисление точного значения соответствующей вероятности требует применения многошагового итерационного процесса. Уточнить значение вероятности (1) можно путем введения еще одной оценки сверху вероятности того, что перед последовательностью }{ ik после понижения размера обучающей выборки базы данных не будет находиться последовательность ijm j j },{ . Капустий Б.Е., Таянов В.А. «Искусственный интеллект» 4’2009 352 7К После исключения из модели (рис. 1) стратегической последовательности она трансформируется к такому виду:  ...1111000...11000111100111000 },{ 332211    mk kmkmkmkm nn Рисунок 2 – Модель распознавания в виде двоичной последовательности при }{l Таким образом, задача сводится к определению вероятности успешного распо- знавания после понижения размера обучающей выборки для случаев, когда начальное распознавание было неправильным. Эти вероятности вычисляются n раз для пар последовательностей   nikm ii ,1 ,,  . Итак, на данном этапе исходной последователь- ностью из всех единиц будет последовательность размера k . Определение. Показателем выживания подпоследовательности  ii km , явля- ется вероятность того, что в результате всех возможных комбинаций вхождений объектов из этой подпоследовательности в другие в ней останется хотя бы один объект из исходной подпоследовательности. Указанную вероятность можно записать в виде:                      . ,1 ;,,1)}{,,( случаеобратном в smmskk C C C C lkmP iis s s kk s s s ms ii ii (2) Если все образы из своего класса в результате их сортировки по величине расстояний от тестового образа попали в пределы списка },{ km , то выражение (2) определяет вероятность того, что в этом списке будут находиться такие образы из своего и чужих классов, при которых распознавание пройдёт успешно. Эта вероят- ность вычисляется рекурсивно-итерационным способом на основании подпоследо- вательностей },{ ii mk :             1 1 1 2 1 2 1 1 1 1 1 1 1 2 1 2 1 2 1 2 { } ,{ } ,{ } { } ,{ } { } 1 , , ; { } ,{ } ,{ } ,{ } ,{ } { } ,{ } ,{ } { } ,{ } 1 s s s m k k s s l k s s s s m m k k k s s s s P l k m P l k P m C C k k s m m s C C P l k k m m P l k k P m m C C C C                                                                          2 1 2 1 2 1 1 1 1 , , ; .................................................................................................. { } ,{ } ,{ } { } ,{ } { } i i n n n n i i i i i i i i s s m s k k k s m m m s P l k m P l k P m C C                                   1 , , . i i s k k i is s i is C k k s m m s C                         (3) Влияние размера обучающей выборки на обобщающую способность… «Штучний інтелект» 4’2009 353 7К В формулах (3) значения n определяются условиями   skls i i та  sms i i , поскольку все дальнейшие вероятности )(P равны 1. Произведение всех вероятностей (3) является глобальной вероятностью правильного распознавания. Алгоритм k ближайших соседей. Представим результаты распознавания подоб- но тому, как они были представлены для 1NN случая, то есть в виде двоичной после- довательности. Пример такой последовательности показан на рис. 3.  ...00111000001111111110001111111111 332211 mlmlml  Рисунок 3 – Результаты распознавания в виде двоичной последовательности При использовании kNN классификатора важно, чтобы среди k ближайших соседей было относительное либо абсолютное большинство образов своего класса среди других образов. Рассмотрим более простой случай, предусматривающий отно- сительное большинство. Успешная работа kNN классификатора состоит в том, что для k ближайших соседей выполняется условие ...3,2,1 ,~~  iml i i i i  , (4) где ii ml ~,~ – группы, образующиеся после понижения информационного покрытия классов. Под группой понимается однородная последовательность элементов. В после- довательность (рис. 3) входят образы всех классов, хотя в общем случае однозначного соответствия между количеством групп и количеством классов не существует. Если рассматривать лишь случай нечётных значений k в kNN классификаторе, то исключа- ется неоднозначность классификации, наблюдаемая при чётных значениях k и равенст- ве голосов за различные классы. Оценим эффект от понижения информационного покрытия классов при исполь- зовании kNN классификатора. Примем, что размеры всех суженных классов одина- ковые и равны s . Для kNN классификатора, в отличие от 1NN, не имеет такого принципиального значения последовательность первых образов своего класса. Поэтому произвольную последовательность образов своего класса можно обозначить как il . Рассмотрим сначала случай 1 2       kENTs . Определим вероятности того, что среди последовательности образов своего класса заданной длины будут выбраны комбинации из s образов. Такие вероятности носят доверительный характер и харак- теризуют степень покрытия несжатого класса последовательностью из  i il образов, среди которых выбирается s . Кроме них, найдём также вероятности того, что не будут выбраны соответствующим способом определённые образы из чужих классов. Вероятность правильной работы kNN классификатора является произведением этих двух вероятностей. Капустий Б.Е., Таянов В.А. «Искусственный интеллект» 4’2009 354 7К Обозначим вероятность ошибочной классификации, обусловленной образами чужих классов, для соответствующих групп im как jq : ;...1 2 inf ;...1 2 inf ;1 2 inf ;1 2 inf 1 213 12 1                                                                                    kENTmmPq kENTmmmPq kENTmmPq kENTmPq j ji i ij ii i i i i i i i     (5) Вероятность jq для каждого из значений доверительной вероятности равна     s s s m j C C q ji ji , 1 . (6) Соответствующую доверительную вероятность можно представить в виде:    s s s l i iq C C lPP i i j   )( . (7) Итак, вероятность успешной работы kNN классификатора равна                                                  2 , 1 , 1 , 1 1)1(, s s s m s s s ls s s m s s s l jq ji ji i ij C CC C C C C C qPmlP ji ji i i ji ji i i j     . (8) При 00 q и 1 2       kENTm i i эта вероятность составляет               s s s l i iq i i C C lPPkENTmP i i  )(1 2 00 . (9) Рассмотрим второй случай       skENT 1 2 и определим для него вероятность ошибочной классификации, обусловленной образами чужих классов: 1 2 , , 1 1 1 2 , 1 , 1                      kENTm C CC q ji jis s s kENTj js ms j m j ji ji ji ji   . (10) Влияние размера обучающей выборки на обобщающую способность… «Штучний інтелект» 4’2009 355 7К Вычислим доверительную вероятность для произвольной последовательности из образов своего класса:               s s s kENTj js ls j l q C CC P i i i i j 1 1 2  . (11) Вероятность успешного распознавания при применении kNN классификатора определяется произведением вероятности (11) и дополнения к вероятности (10).   . )1( 2 1 1 2 1 1 2 1 1 2 , 1 , 1                                                            s s s kENTj js ms j m s kENTj js ls j l s s s kENTj js ls j l jqj C CCCC C CC qPP ji ji ji ji i i i i i i i i j   (12) Эта вероятность для ошибки 00 q составляет: .1 2 1 1 2 0                          s s s kENTj js ls j l i i C CC kENTmP i i i i   (13) Итак, при  skENT 1) 2 ( вероятность правильного распознавания для kNN классификатора вычисляется по формуле (8), а при       skENT 1 2 – по формуле (12). Результаты симулятивного моделирования. Было проведено моделирование процесса распознавания с разными последовательностями образов своего и чужих классов для 1NN и kNN классификаторов в случае относительного большинства. Моделирование использовано для оценивания результатов работы системы распо- знавания лиц людей [9], [10]. В связи с этим начальный размер классов был принят равным 18. На рис. 4, 5 представлены результаты моделирования влияния уменьшения раз- мера обучающей выборки на вероятность правильного распознавания для 1NN класси- фикатора. На рис. 4 показана зависимость доверительной вероятности правильного рас- познавания от размера последовательности образов своего класса и размера классов базы эталонов. Как видно из рисунка, доверительная вероятность уменьшается при уменьшении размера эталонных классов и последовательности образов своего класса. На рис. 5 изображена зависимость вероятности правильного распознавания от размера последовательностей образов своего и чужих классов в случае их попарного разде- ления. Моделирование проводилось следующим образом. Формировалась последо- вательность переменного размера из образов своего класса, а к ней периодически прибавлялось по одному образу из чужого класса, что привело к формированию сово- купной переменной последовательности из образов своего и чужого классов. Для каж- Капустий Б.Е., Таянов В.А. «Искусственный интеллект» 4’2009 356 7К дой такой последовательности и соответствующего размера класса вычислялась вероятность правильного распознавания. Из рисунка видно, что увеличение после- довательности из образов чужого класса приводит к уменьшению вероятности пра- вильного распознавания. Рисунок 4 – Доверительная вероятность правильного распознавания как функция размера классов базы эталонов (ось x ) и размера последовательности образов сво- его класса (ось у) для 1NN классифика- тора Рисунок 5 – Вероятность правильного распо- знавания как функция размера классов базы эталонов (ось x ) и размера последователь- ности образов своего и чужих классов (ось у) для 1NN классификатора Рисунок 6 – Доверительная вероятность правильного распознавания как функция размера классов базы эталонов (ось x ) и размера последовательности образов своего класса (ось y ) для kNN класси- фикатора при 1 2       kENTs Рисунок 7 – Вероятность правильного распоз- навания как функция размера классов базы эталонов (ось x ) и размера последова- тельности образов своего и чужих классов (ось y ) для kNN классификатора при 1 2       kENTs На рис. 6, 7 представлены результаты моделирования влияния уменьшения раз- мера обучающей выборки на вероятность правильного распознавания для kNN клас- сификатора в случае, когда 1 2 kENT s       . Влияние размера обучающей выборки на обобщающую способность… «Штучний інтелект» 4’2009 357 7К На рис. 6 показана аналогичная к рис. 4 зависимость. Как видно из рисунка, доверительная вероятность уменьшается при увеличении числа ближайших соседей. Результаты, изображённые на рис. 7, указывают на то, что вероятность правильного распознавания уменьшается при увеличении размера класса и последовательности образов чужого класса. На рис. 8, 9 приведены результаты моделирования для случая kNN классифи- катора и       skENT 1 2 . На рис. 8 представлена зависимость доверительной вероят- ности от размера класса и значения 1 2       kENT . Размер класса периодически увели- чивался, и также периодически формировалась переменная последовательность об- разов своего класса. Общая последовательность представлена одной из координат, а второй – значение 1 2       kENT . Зависимости на рис. 9 построены для таких случаев: 1 2 kENT       {1,3,5,7,9,11,13,15,17} . Вероятность правильного распознавания будет тем больше, чем меньше последовательность образов чужих классов и больше раз- ница между 1 2       kENT и s . Рисунок 8 – Доверительная вероятность правильного распознавания как функция размера классов (ось x ) и значения 1 2       kENT (ось y ) Капустий Б.Е., Таянов В.А. «Искусственный интеллект» 4’2009 358 7К a b c d e f g h i Рисунок 9 – Вероятность правильного распознавания как функция 1 2       kENT (ось x) и общей последовательности образов своего и чужих и классов (ось y ) Выводы На основании комбинаторного подхода можно анализировать и оптимизиро- вать kNN классификатор. Подход даёт возможность определять соотношение между оптимальным значением k ближайших соседей и пониженным размером класса s . Это соотношение зависит от результатов распознавания на начальных (несжатых) Влияние размера обучающей выборки на обобщающую способность… «Штучний інтелект» 4’2009 359 7К классах. Подход также даёт дополнительную информацию о составе обучающей вы- борки и степени её корректности для того, чтобы в дальнейшем использовать эту ин- формацию при минимизации процесса переобучения и максимизации вероятности правильного распознавания. Литература 1. Капустий Б.Е. Оптимизация классификаторов в условиях малых выборок / Б.Е. Капустий, Б.П. Русын, В.А. Таянов // Автоматика и вычислительная техника. – 2006. – Вып. 5. – С. 25-32. 2. Капустий Б.Е. Математическая модель систем распознавания с малыми базами данных / Б.Е. Капустий, Б.П. Русын, В.А. Таянов // Проблемы управления и информатики. – 2007. – № 5. – С. 142-151. 3. [Електронний ресурс]. – Режим доступу : http:// www.ccas.ru/voron/teaching.html. 4. Ивахненко А.Г. Моделирование сложных систем по экспериментальным данным / А.Г. Ивахненко, Ю.П. Юрачковский. – М. : Радио и связь, 1987. – 120 c. 5. Feature Selection Using a Piecewise Linear Network / [Jiang Li, Michael T. Manry, Pramod L. Narasimha, and Changhua Yu] // IEEE Transactions on Neural Network. – September 2006. – Vol. 17, № 5. – P. 1101-1115. 6. Levner I. Automated Feature Extraction for Object Recognition / I. Levner // Proceedings of the Image and Vision Computing New Zealand Conference. – 2003. – P. 653-655. 7. Osborne M.R. A new approach to variable selection in least squares problems / M.R. Osborne, B. Presnell and B.A. Turlach // IMA Journal of Numerical Analysis. – 2000. – 20. – P. 389-404. 8. Mullin M. Complete cross-validation for nearest neighbor classifiers / M. Mullin, R Sukthankar // Procee- dings of International Conference on Machine Learning. – 2000. – P. 639-646. 9. Капустій Б.О. Розподіл середньоквадратичних відстаней між об’єктами в просторі R2 / Б.О. Капустій, Б.П. Русин, В.А. Таянов // Відбір і обробка інформації. – 2003. – Випуск 19(95). – C.110-114. 10. Капустій Б.О. Новый подход к определению вероятности правильного распознавания объектов множеств / Б.О. Капустій, Б.П. Русин, В.А. Таянов // УСиМ. – 2005. – № 2. – С. 8-13. Б.О. Капустій, В.А. Таянов Вплив розміру навчаючої вибірки на узагальнюючу властивість метричних алгоритмів класифікації В роботі пропонується підхід, який забезпечує оцінку впливу зменшення розміру класів бази даних на рівень розпізнавання при застосуванні kNN метричних класифікаторів, а також дає можливість визначення на даній вибірці оптимального значення k. Проведене симулятивне моделювання результатів впливу зменшення навчаючої вибірки на результати розпізнавання. Отриманні результати можуть бути використані для подальшого формування навчаючої вибірки та її корекції. B.O. Kapustiy, V.A. Tayanov The Influence of the Training Set Size on the Generalized Ability of the Metrical Classifiers In this paper the approach giving the estimate of the class size reduction influence on the recognition rate for the kNN classifiers has been proposed. The approach also gives the possibility to estimate the optimal k value of the nearest neighbours. The simulative modeling of the training set reduction influence on the recognition process results has been carried out. The obtained results can be used for the training set formation and its correction. Статья поступила в редакцию 08.07.2009.

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

Institution

Ähnliche Einträge