The generalizing ability of algorithms by the measure of compactness.pdf Обобщающая способность относится к числу основных показателей, характеризующих качество распознающих алгоритмов [1]. Эта способность проявляется в умении определять принадлежность объектов к классам, которых алгоритм не видел в процессе обучения. Проверка истинности гипотезы о компактности лежит в основе многих критериев и методов теории распознавания образов. Так, в [1] описан профиль компактности для вычисления обобщающей способности семейств алгоритмов, имеющих бесконечную емкость в пространстве VC (Вапника-Червоненкиса) [2]. Для определения принадлежности произвольного допустимого объекта к классам при использовании таких семейств алгоритмов необходимо хранить в памяти всю выборку. Представителем семейства с бесконечной емкостью является алгоритм «ближайший сосед» (БС). В практических целях при вычислении обобщающей способности достаточно использовать локальные свойства (локальные ограничения) выборок объектов [1]. Локальным ограничением в [3] можно считать предложенный Н.Г. Загоруйко показатель компактности, определяемый по числу объектов-эталонов минимального покрытия, при котором распознавание объектов классов фиксированной выборки было корректным. Кроме показателя компактности кандидатами для включения в набор локальных ограничений являются число шумовых объектов, размерность признакового пространства, множество объектов оболочек (подмножества граничных объектов) классов [4] по заданной метрике. Интерес представляет предельное значение размерности, при превышении которого показатель компактности [3] увеличивается. Набор признаков, определяющий предельное значение, рассматривается как информативный для используемой меры близости. Размерность выше предельной приводит к размыванию сходства между объектами выборки. Существует потребность во введении новой меры измерения компактности с помощью безразмерных величин со значениями в [0, 1]. Значения этих величин требуются для анализа того, насколько реально получаемая (по заданной мере близости) структура обучающей выборки отличается от идеальной для распознавания. Идеальной считается структура, в которой число объектов-эталонов минимального покрытия равно числу классов. Меру компактности можно использовать для сравнения метрик и преобразований признакового пространства по отношению «лучше» на фиксированных выборках объектов. Анализ структуры выборок основывается на использовании свойств этого отношения. Методика анализа ориентирована на количественные показатели, вычисляемые по результатам разбиения объектов классов на непересекающиеся группы [4]. Гарантией единственности разбиения по числу групп и составу входящих в них объектов служит устойчивость используемого алгоритма. Влияние шумовых объектов на показатели обобщающей способности алгоритмов многократно рассматривалось в научных публикациях. По обширному перечню работ в [5] приводится обзор различных методов обнаружения и удаления шумовых объектов. Большинство из этих методов ориентировано на использование правила БС. Качество распознавания по правилу БС существенно зависит от чувствительности метрики к размерности признакового пространства. Изменение размерности связано как с отбором информативных признаков, так и с переходом к описанию объектов в пространстве из латентных признаков. В качестве инструментария для перехода к латентным признакам в [4, 6] предлагалось использовать два типа правил иерархической агломеративной группировки исходных признаков. Первый тип ориентирован на последовательное объединение двух признаков в один путем нелинейного отображения их значений на числовую ось. Группировка по правилам второго типа производится на основе значений критерия устойчивости объектов по заданной метрике в двухклассовой задаче распознавания. По каждой группе признаков вычисляется обобщенная оценка объекта. Методы, реализующие два типа правил иерархической группировки, можно идентифицировать как нелинейные и линейные. Нелинейные методы являются инвариантными к масштабам измерений признаков. У линейных методов свойство инвариантности отсутствует. Последовательность формирования групп и латентных признаков на их основе по двум типам правил определяет порядок по отношению степени информативности. Информативность признака вычисляется как экстремум критерия разбиения его (признака) значений на непересекающиеся интервалы в форме проверки степени истинности гипотезы: «Множества значений признака в описании объектов из разных классов при числе интервалов, равном числу классов, не пересекаются между собой». В данной работе рассматриваются непустые классы (множества) метрик, кластерные структуры обучающих выборок по которым совпадают (являются эквивалентными) по числу групп и составу входящих в них объектов. Информация о кластерной структуре позволяет вести последовательный отбор объектов-эталонов минимального покрытия, в каждом из которых определена локальная метрика. Способ вычисления весов локальных метрик аналогичен используемому в методе FRiS STOLP [3]. Для оценки обобщающей способности алгоритмов метода БС предлагается применять критерий, значения которого вычисляются в зависимости от размерности и состава набора признаков, количества удаляемых шумовых объектов и числа объектов-эталонов минимального покрытия. Оценки по критерию использовались для демонстрации устойчивости результатов отбора информативных признаков методом кросс-валидации на случайных выборках. 1. О разбиении объектов классов на непересекающиеся группы Использование частично обученной выборки (ЧОВ) для задания условий группировки описано в [7]. Примером условия служит указание подмножества из пар объектов выборки, которые при разбиении не должны попадать в одну группу. Принадлежность объектов к непересекающимся классам служит источником дополнительной информации для исследования кластерной структуры с помощью различных мер близости. Основные идеи приводимого ниже метода изложены в [4]. Целями разбиения объектов классов на непересекающиеся группы являются: - вычисление и анализ значений компактности объектов классов и выборки в целом; - поиск минимального покрытия обучающей выборки объектами-эталонами. Рассматривается задача распознавания в стандартной постановке. Считается, что задано множество E0 = {S1, ..., Sm} объектов, разделенное на l (l > 2) непересекающихся подмножеств (классов) K1, ..., Ki, 1 E0 = ^ K ■ Описание объектов производится с помощью набора из n разнотипных признаков 1=1 X(n) = (х1, ..., х«), из которых измеряются в интервальных шкалах, (п - 2) - в номинальной. На множестве объектов E0 задана метрика p(x, y). Обозначим через L(E0, р) подмножество граничных объектов классов, определяемое на Е0 по метрике р(х, у). Объекты Si, Sj е Kt, t = 1, ..., l считаются связанными между собой (Si ^ S), если {S e L(Eo, p) | p(S, Si) < ri and p(S, Sj) < r-} Ф 0 , где ri(rj) - расстояние до ближайшего от Si(Sj) объекта из CKt (CKt = Eo\Kt) по метрике p(x, y). Множество Gtv={ S ,...,SV }, c > 2, Gtv с Kt, v < |Kt| представляет область (группу) со связанными объектами в классе Kt, если для любых Sv ,Sv g G^ существует путь Sv. ^ SVi ^... ^ Sv, • Объект Si e Kt, t = 1, ..., l принадлежит группе из одного элемента и считается несвязанным, если не существует пути Si ^ Sj ни для одного объекта S- Ф Si и S- e Kt. Требуется определить минимальное число непересекающихся групп из связанных и несвязанных объектов по каждому классу Kt, t = 1, ..., l. Данная задача может рассматриваться и в альтернативной постановке (без задания признаков), если определена квадратная матрица близости {a-jmx m между m объектами и вектор F = (/1, ..., fm), fi e {1, ..., l} принадлежности объектов к классам K1, ..., Ki. Вектор F служит дополнительной информацией для задания условий группировки. При определении минимального числа групп из связанных и несвязанных объектов классов используется L(Eo, p) - подмножество граничных объектов (оболочка) классов по заданной метрике p и описание объектов в новом пространстве из бинарных признаков. Для выделения оболочки классов для каждого Si e Kt, t = 1, ..., l строится упорядоченная по p(x, у) последовательность S , S ,...,S , S = S . (1) i0 i1 ' 1m-1 ' i i0 V ' Пусть Slp e CKt - ближайший к Si объект из (1), не входящий в класс Kt. Обозначим через O(Si) окрестность радиуса ri = p(Si, S ) с центром в Si, включающую все объекты, для которых p(Si, Si )< ri, т = 1, ..., в - 1. B O(Si) всегда существует непустое подмножество объектов д={ ( s )1 р S ,s0=) р S' s0}- (2) m По (2) принадлежность объектов к оболочке классов определяется как L(Eo, p) = ^ Д . =1 Множество объектов оболочки из Kt П L(Eo, p) обозначим как L(Eo, p) = {S1, ..., S™}, п > 1. Значение п = 1 однозначно определяет вхождение всех объектов класса в одну группу. При п > 2 преобразуем описание каждого объекта Si e Kt в Si = (yn, ..., y„), где 1, р (Si, SJ )< r, yj ={ t л (3) [о, р (Si, Sj )> r. Пусть по (3) получено описание объектов класса Kt в новом (бинарном) признаковом пространстве, Q = Kt, 0 - число непересекающихся между собой групп объектов, S^ v St,, S^ л Sn - соответственно операции дизъюнкции и конъюнкции по бинарным признакам объектов S^, Sn e Kt. Пошаговое выполнение алгоритма разбиения объектов Kt на непересекающиеся группы G1, ..., G0 таково. Шаг 1: 0 = 0. Шаг 2: Выделить объект S e Q, 0 = 0 + 1, Z = S, G0 = 0 . Шаг 3: Выполнять Выбор S e Q and S л Z = true, Q = Q\S, G0 = G0 U S, Z = Z v S пока {S e Q | Sл Z = true } ф 0 . Шаг 4: Если Q Ф 0 , то идти 2. Шаг 5: Конец. Разбиение объектов Ео на непересекающиеся группы по описанному выше алгоритму используется для поиска минимального покрытия [4] обучающей выборки объектами-эталонами. Обозначим через Rs = p(S, S ) расстояние от объекта S e Kt до ближайшего объекта S из противоположного к Kt класса (S e CKt), через 5 - минимальное число непересекающихся групп из связанных и несвязанных объектов классов на Ео. Упорядочим объекты каждой группы Gu П K, u = 1, ..., 5, t = 1, ..., l по множеству значений R }SeG . В качестве меры близости между S е Gu, и = 1, ..., 5 и произвольным допустимым объектом S' используется взвешенное расстояние по локальной метрике d(S, S') = p(S, S')/rs. Решение о принадлежности S' к одному из классов Ki, ..., Ki принимается по правилу: S' е Kt если d(S„ S1) = min d(S}, S) and S^ е Kt and d(S„ S') Ф min d(S}, S) (4) Sj €Eq Sj € CKt Согласно принципа последовательного исключения, используемого в процессе поиска покрытия, выборка £0 делится на два подмножества: множество эталонов Eed и контрольное множество Ek, Е0 = Eed U Ek. В начале процесса Eed = Е0, Ek = 0 . Упорядочение по значениям из R}5eG , и = 1, ..., 5 используется для определения кандидата на удаление из числа объектов-эталонов по группе Gu. Идея отбора заключается в поиске минимального числа эталонов, при котором алгоритм распознавания по (4) остается корректным (без ошибок распознающим объекты) на Е0. Будем считать, что нумерация групп объектов отражает порядок \Gi\ > ... > |G5| и по группе Gp, p = 1, ..., 5 не производился отбор объектов-эталонов. Кандидаты на удаление из Eed последовательно выбираются начиная с S е Gp с минимальным значением rs. Если включение S в Ek нарушает корректность решающего правила (4), то S возвращается в множество Eed. 2. О мерах компактности в задачах распознавания с учителем Меры компактности востребованы для оценки обобщающей способности распознающих алгоритмов. При вычислении оценок используются результаты поиска и удаления шумовых объектов, отбора информативных наборов признаков, число объектов-эталонов минимального покрытия обучающих выборок. Рассмотрим метод формирования множества шумовых объектов, мощность которого зависит от проверки предлагаемого ниже условия. Пусть Skе Ki, p(Sk, Sr) = min p(Sk, S) и Z = |{S^ е K\ p(Sk, S„) < p(Sk, Sr)}\. Обозначим через Dt (D е CK) Sj ZCK; множество шумовых объектов класса Ki. Объект Sr е CKi включается в Di и рассматривается как шумовой, если выполняется условие: ZZ -1 1 ~W> тщ' (5) где ZZ = \{S, е K\ p(Sr, Sk) < pS Sk) < p(S,, Sk)}\, \b\ < min \K\, p(S^, Sk) = min p(S;, Sk). Значения Z и 1 2 определяется как Х = arg ma^ F (X (n), n). (10) Использование (10) основано на предположении, что вероятность отбора информативных наборов признаков с более высоким значением компактности по (8) близка к нулю при X, отличной от (10). В первом (в порядке изложения) критерии используются результаты покрытия объектов выборки гипершарами с учетом удаления шумовых объектов, во втором - оценки компактности по (7) на основе свойства связанности по объектам оболочек классов. Пусть O(Si, X(k)) (1 < k < n) - окрестность объекта Si е Ео П Kj, j = 1, ..., l, определяемая как O(Si, X(k)) = {S е Kj | p(S,S ) < p(Si, S )}, где S е CKj - ближайший к Si объект по метрике р(х, у) из дополнения к классу Kj по множеству признаков X(k). Определим оценку Si е E0 на X(k) как ад, X(k)) = Sema-k)) |O(S, X(k))|. (I1) Признак Xd е X(n) является кандидатом на включение в набор X(k), если Z Z(Si, X(k +1))> Z z(Si, - (k))' (12) St eT St eT где X(k + 1) = X(k) U {xd}, Tс E0. Обозначим через P подмножество индексов признаков из X(n); Dj(P) - множество шумовых объектов класса Kj по (5) на наборе {ха}аер при значении X, вычисленное по (10). Пошаговый отбор информативных наборов признаков с использованием (11) и (12) реализуется следующим образом. Шаг 1: Выбор i 1, j 1 е {1, ..., n}. P = {i 1, j 1}. Шаг 2: Выделить У Dj(P) по (5) на {ха}аеР. T=E C и N > Y, то Y = N,u = v; Шаг 4: Если Y> 0, то P = P U {u}, идти 2. Шаг 5: Вывод P. Шаг 6: Конец. Для отбора информативных наборов признаков по (7) предлагается следующий алгоритм. Шаг 1: Выбор i1, j е {1, ..., n}. P = {1,j\}. l Шаг 2: Выделить \JDj(P) по (5) на {xa}aeP. T = Eo\\JDj(P). Вычислить O(P) = {o,(P)}^r no j=1 j=1 ' (xa}aeP, где Oi (P) = | S^, Si e Kj p (Si, S^ ) < r, r = min p (Si, St )|. Вычислить разбиение на группы I Sf eCK j ^T I i G11, ..., Gln, n - l по (2) и (3) алгоритмом из п. 1, mij = |Gy|, mi = Zm-/ , Zm, = T• Вычислить {©Л no i Z mi © (6) и C m Шаг 3: u = 0. Y = C. Для всех v e {1, ..., n}\P i i выделить \ Dj (P U{v}) по (5) на {xa j^}, T = E0\ \ Dj (p U{v}) . j=1 j=1 Вычислить O(P U {v}) = {O,(P u {v})^ gt по К }oeMv}, где о- (Pu{v}) = jS,S eKj p(St,Sj< r,,r, = ^ min^p(S,,St)J . Вычислить разбиение на группы G11, ..., Gin, П - i по (2) и (3) алгоритмом из п. 1, mij = |Gj|, mi = Zmy i i Z m,©i Z mt = IT . Вычислить |©; }l по (6) и N = --. i=1 1 m Если N > Y, то Y = N, u = v. Шаг 4: Если u > 0, то P = P U {u}, идти 2. Шаг 5: Вывод P. Шаг 6: Конец. Для удобства дальнейшего изложения алгоритмы отбора информативных признаков (в порядке их описания) будем идентифицировать как ALG1 и ALG2. Для ослабления зависимости результатов отбора от выбора начальных приближений можно использовать модификацию этих алгоритмов. Модификация заключается в сочетании принципов пошагового включения в набор информативных признаков и удаления из набора малоинформативных признаков. Для сравнения информативных наборов, полученных по разным критериям, рекомендуется использовать (8) и (9). 3. О единственности выбора кластерной структуры на обучающей выборке Исследование единственности выражается в доказательстве существования множеств (классов) метрик, кластерные структуры фиксированных обучающих выборок при использовании которых совпадают по числу и составу групп объектов. Утверждается, что такому требованию удовлетворяют классы эквивалентных метрик {¥}. Например, эквивалентной к метрике р1 является метрика p2 = p1 . 1 + p1 Из р1, р2 e ¥ следует, что отношения близости между объектами на Ео по метрике р1 остаются таковыми и по метрике р2. Другим следствием эквивалентности является сходство объектов оболочек классов, ближайших объектов из противоположных классов, числа групп и их состава на Е0 при реализации алгоритма группировки из п. 1. Для вычисления меры компактности по (6) и (7) можно использовать любую метрику из класса эквивалентности u j i=1 Кластерные структуры, получаемые по разным метрикам из класса ¥, отличаются между собой лишь конфигурацией таксонов. Конфигурация таксонов влияет на значения весов локальных метрик, используемых в (4), а следовательно, на количество и состав объектов-эталонов минимального покрытия. Для сравнения кластерной структуры по метрике р е ¥ на данных, отличающихся количеством представителей классов и выборок в целом, предлагается использовать вычисление оценки по (6). Тогда компактность по обучающей выборке Ео по набору признаков X(k), k < п с учетом удаления шумовых объектов по (5) будет выглядеть так: Е 1 -K |K|®f U (E0, X (к), р,Х) - ^-ml-. (13) I - 1 Интерес представляет анализ результатов алгоритмов ALG1 и ALG2 при отборе информативных наборов признаков. В общем случае наборы, полученные по ALG1 и ALG2, по р е ¥ при совпадении номеров /1, ji на первом шаге различаются друг от друга. Так как при вычислении оценок по (7) и (11) учитывается порядок следования объектов, то р е ¥ и множество наборов совпадают по каждому алгоритму (ALG1 или ALG2), но не между алгоритмами. Локальные метрики объекта S е Ео, формируемые из класса ¥ и используемые в (4), в общем случае не являются эквивалентными. Эта особенность класса ¥ объясняет различие числа объектов-эталонов минимального покрытия обучающей выборки и его состава. 4. Вычислительный эксперимент Для демонстрации методики вычисления мер компактности и отбора информативных наборов признаков использовалась выборка данных GERMAN из [8]. Выборка представлена двумя непересекающимися классами K (700 объектов) и K2 (300 объектов). Объекты описываются 7 количественными и 13 номинальными признаками из набора X(20) = (Х1, ..., Х20) Для унификации масштабов измерений данных множество значений каждого количественного признаков пронормировано в [0, 1]. Зафиксируем одну метрику из класса эквивалентности ¥ и будем считать ее базовой для вычислительного эксперимента. При вычислении меры близости между объектами в качестве базовой использовалась метрика Журавлева р(х,y)=E\x, - y\ + !У' (14) isI isJ 1°' xi - yi' где I, J ^ {1, ..., 20} - множества номеров соответственно количественных и номинальных признаков. Из-за особенностей вычисления расстояний по локальным метрикам объектов Е0 число объектов-эталонов минимального покрытия выборки для р1, р2 е ¥ в общем случае различаются. Сходство топологических структур эквивалентных метрик выражается в совпадении как числа, так и состава шумовых объектов, определяемых по (5). Связь процесса выбора параметра X в (5) с оценками компактности (8) показана в табл. 1. В скобках указано число объектов-эталонов, вычисляемых по взве- -/1,4 *< \ Р (x' у ) шенным расстояниям на основе эквивалентной (14) метрике Р (x, y) -----. 1 + Р ( x У ) Таблица 1 Оценки компактности по метрике (14) с учетом удаления шумовых объектов X Число Оценка компактности по (8) на X(20) шумовых объектов объектов-эталонов 2 119 203 (200) 3,8235 1 148 171(172) 4,2451 0 217 161 (162) 3,8080 -1 239 141 (140) 4,1072 -2 261 122 (122) 4,4764 -3 261 122 (122) 4,4764 Результаты анализа структуры выборки из табл. 1 показывают, что оптимальное отношение между числом объектов-эталонов минимального покрытия и числом удаляемых шумовых объектов по (5) на X(20) достигается при значении параметра X = -2. На всех последующих этапах эксперимента число шумовых объектов по умолчанию определяется по X = -2 в (5). Рассмотрим зависимость числа и состава наборов информативных признаков от выбора начальных приближений в алгоритмахALG1 и ALG2. Каждое начальное приближение (табл. 2, табл. 3) задано парой индексов-признаков. Таблица 2 Отбор информативных признаков алгоритмом ALG1 Начальное приближение Информативный набор i1 = 1, j = 2 X1, X2, X3, X4, X5, X13, X14 i1 = 3, j = 4 X1, X2, X3, X4, X5, X13, X14 i1 = 6, j\ = 13 X1, X2, X3, X5, X6, X8, X13, X14, X18, X20 Таблица 3 Отбор информативных признаков алгоритмом ALG2 Начальное приближение Информативный набор Компактность по (7) i1 = 1, j1 = 2 X1, X2, X4, X5, X6, X7, X12, X20 0,6688 » = 3, j = 4 X1, X3, X4, X5, X6, X9, X13 0,6947 i1 = 6, j = 13 X2, X5, X6, X13, X18 0,6417 Анализ содержимого табл. 2 и табл. 3 показывает, что наборы признаков, полученные по алгоритмам ALG1 и ALG2, различаются при выборе одинаковых начальных приближений. Для демонстрации методики точности алгоритмов распознавания на выборке из 1 000 объектов будем использовать набор признаков, полученный по модифицированному алгоритму ALG1. Смысл модификации сводится к последовательному включению в набор двух информативных и удалению одного малоинформативного признака. При выборе в качестве начального приближения пары признаков (х17, Х18) информативный набор был представлен X(7) = (x1, Х2, Х3, X4, X5, X13, X14). Значения показателей распознавания объектов по исходному X(20) и информативному X(7) наборам признаков \ Р( X У) с использованием базовой метрики (14) и эквивалентной ей метрике р (x, y) ---:-т приводятся 1 + р (X, У ) в табл. 4. Таблица 4 Точность распознавания по выборке GERMAN Вычисляемые показатели Исходный набор X(20) Информативный набор X(7) по метрике базовой (14) эквивалентной (14) Число шумовых объектов 261 220 220 Число эталонов 122 109 109 Среднее (8) по эталону 4,4764 5,5816 5,5816 Число ошибок (точность, %) 156 (84,4%) 147 (85,3%) 143 (85,7%) Совокупный эффект от использования информативных наборов признаков (см. табл.4) с учетом удаления шумовых объектов более всего заметен по значениям (8) среднего числа объектов, притягиваемых одним объектом-эталоном минимального покрытия. Для исследования обобщающей способности алгоритмов использовалось случайное деление выборки на обучение и контроль в соотношении 9 : 1. Предварительный анализ результатов показывает, что определенное преимущество в смысле значений показателей обобщающей способности имеют наборы, полученные по алгоритму ALG2. Из табл. 5 видна прямая корреляционная зависимость между точностью распознавания и средним числом объектов, притягиваемых одним эталоном минимального покрытия. Т а б л и ц а 5 Обобщающая способность алгоритма по базовой метрике (14) Набор признаков Точность распознавания % Среднее по эталону Исходный X(20) 70,9 4,4407 X1, X2, X3, X4, X5, X13, X14 72,46 5,7088 X1, X2, X4, X5, X6, X7, X12, X20 72,82 5,8802 X1, X3, X4, X5, X6, X9, X13 73,27 6,0136 Оценки компактности (13) для ряда подмножеств объектов GERMAN приводятся в табл. 6. Вычисление оценок производится на исходном X(20) и информативном X(7) = (xi, Х2, хз, Х4, Х5, X13, X14) наборах признаков. Таблица 6 Оценки компактности по (13) № |K1| + K2| Набор признаков X(20) X(7) 1 624 + 276 0,2710 0,3183 2 633 + 267 0,2658 0,2470 3 629 + 271 0,2596 0,2739 4 641+259 0,2597 0,2719 Отсутствие прямой коррелированности оценок (13) между наборами X(20) и X(7) (см. табл. 6) объясняется тем, что существует подмножество объектов, на котором набор X(7) не является информативным. Заключение Показаны пути повышения обобщающей способности алгоритмов распознавания через удаление шумовых объектов и отбор информативных наборов признаков с использованием критериев компактности обучающей выборки. Предложенная технология может применятся при интеллектуальном анализе данных для построения информационных моделей с использованием алгоритмов распознавания.

Скачать электронную версию публикации