Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки

в 13:10, , рубрики: data mining, Алгоритмы, классификатор, машинное обучение, ошибки, распознавание образов, фрактал

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

Определения и обозначения

Пусть задано некоторое исходное разбиение множества image объектов image на два подмножества (класса) image, таких, что
image, image.
(1)

Будем отождествлять двухклассовый классификатор с бинарной функцией вида
image
(2)

где image — случайные выборки-подмножества image из классов image, image -исследуемый объект, который необходимо отнести к одному из классов. Значения этой функции будут истолковываться в качестве «решений» в соответствии с правилом
Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 11
(3)

В зависимости от того, соответствуют или нет решения классификатора исходному разбиению image на классы, будем считать их соответственно «правильными» или «ошибочными». Договоримся также Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 13-ые элементы выборок image обозначать Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 15, так, что соответственно:
Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 16,
(4)

где image — объемы обучающих выборок. Полагаем множество image «погруженным» в image -мерное правостороннее евклидово пространство image. Тогда все элементы классов image, включая, естественно, и элементы обучающих выборок и исследуемый объект, можно рассматривать как его точки. Координаты объектов-точек из множества image будем помечать правым нижним индексом image. Координаты объектов Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 24 обучающих выборок запишутся как Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 25, исследуемого объекта image как -image. В зависимости от контекста, image понимается либо как имя объекта, либо как радиус-вектор.
Исходим из отсутствия проверочной последовательности, а оценки вероятности ошибки классификации image осуществим в режиме скользящего экзамена
image,
(5)

где
image,
(6)

image.
(7)

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

Скорректированный скользящий экзамен

Скользящий экзамен, как известно, отличает ряд недостатков. Эти недостатки могут быть в какой-то мере устранены через коррекцию скользящего экзамена. Скорректированные оценки, помечаемые левым штрихом, запишутся следующим образом
image,
(8)

image,
(9)

image.
(10)

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

Соклассификатор

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

image.
(12)

Тогда решение соклассификатора первого порядка классификатора (2), определяемого как
image,
(13)

истолковывается следующим образом
если image то классификатор (2) принял правильное решение относительно image,
если image, то классификатор(2) принял ошибочное решение относительно image.
(14)

При этом будем считать, что выборки Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 45 извлечены из неких классов Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 46 объектов, потенциально правильно либо ошибочно отнесенных классификатором (2).

При определении (13) предполагается, что объем выборки image не слишком мал. Таким образом, если располагаем лишь материалом обучающих выборок, а проверочные последовательности отсутствуют, то использовать соклассификатор рекомендуется в условиях, когда классификатор (2) допускает значительное количество ошибок. Если все же использовать соклассификатор в условиях малой выборки image, то его следует выбирать в достаточно простой форме. Например, если соклассификатор фишеровского типа, можно предположить диагональность ковариационной матрицы или даже ее единичность.

Подобно adaptive boosting, композиция классификаторов Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 49 может рассматриваться как коллективный классификатор, организованный существенно более нелинейно по сравнению с предложенными в [1].

Остановимся на вопросах, связанных с выбором конкретной формы соклассификатора. Пусть, например, выборки image извлечены из классов image с плотностями распределений image, причем классы сильно перекрываются. В этом случае зачастую может оказываться, что выборочные плотности Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 53 имеют близкие средние значения. В этом случае соклассификатор Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 54 может быть выбран, например, в форме линейного фишеровского классификатора, модифицированного с использованием процедуры Петерсона-Маттсона [2,3].

Фрактальный классификатор

Процесс синтеза соклассификаторов более высоких порядков может быть продолжен в рамках рекуррентной процедуры, когда первоначально осуществляется подстановка
Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 55,
(15)

затем, повторяя вышеописанный алгоритм, получаем на выходе соклассификатор второго порядка
image.
(16)

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

На практике нам приходилось использовать лишь соклассификаторы первого порядка. Они были разработаны нами много лет назад и зарекомендовали себя в качестве полезных инструментов при решении различных практических задач, в частности, при анализе отраженных радиосигналов для установок поиска пластиковых противопехотных мин [4], а также при создании системы LEKTON. Эта система позволила полностью автоматически проверять подлинность подписей на чеках, векселях и других документах и явилась первой реально используемой в банке системой такого типа.

Локальная вероятность ошибки

В практических исследованиях хорошо себя зарекомендовали локальные image — оценки вероятности ошибки классификации. Пусть классификатор (2) может быть представлен в форме
image,
(17)

где image — оценки плотностей image по выборкам image соответственно. Тогда локальная image — оценка вероятности ошибки этого классификатора может быть определена как
image,
(18)

где image.
Введем специальную image — оценку, которая может рассматриваться в качестве «размытого» классификатора
image
(19)

где image. Тогда будем считать, что Скорректированный скользящий экзамен, соклассификаторы, фрактальные классификаторы и локальная вероятность ошибки - 71 истолковывается как решение размытого классификатора, что image, image — как решение, что image. При этом, чем ближе image к нулю либо к единице, тем соответственные решения размытого классификатора более заслуживают доверия.

На основе оценки (19) можно обобщить определение классификатора (2), введя зону отказа либо зоны отказа. Обозначая ширину этих зон соответственно image, представим их в следующей форме
image
(20)

где image — границы зон. При отсутствии асимметрии в требованиях к зонам выбирается image.

Литература:

1. Archipov G. F. Collectives of determinative rules: optimal solutions and some of the characteristics of reliability of classification. – In the Collection of articles “Statistical problems of control”, Vilnius, 1983, vol.61, pp. 130-145.
2. Мясников В.В. O модификациях метода построения линейной дискриминантной функции, основанного на процедуре Петерсона-Маттсона. computeroptics.smr.ru/KO/PDF/KO26/KO26211.pdf.
3. Фукунага К. Введение в статистическую теорию распознавания образов. М. «Наука» 1979. стр. 105-130.
4. Archipov G., Klyshko G., Stasaitis D., Levitas B., Alenkowicz H., Jefremov S. Research of Metallic and Dielectric Underground Objects on the Basis of Original Computer Recognition Technique of Reflected Radio Signals. MIKON-2000., XII International Conference on Microwaves, Radar and Wireless Communications, Volume 2, pp. 495-498./>

Автор: GeorgijArchipov

Источник

Поделиться новостью

* - обязательные к заполнению поля