Methods of analysis of different-type features informativity .pdf Одним из подходов повышения качества распознавания образов и снижения вычислительных затрат является проведение предварительного анализа обучающей информации [1, 2]. Целью такого анализа является оценка основных информативных характеристик обучающей выборки, в частности оценка информативности признаков, оценка значений признаков, выделение наиболее представительных объектов.С метрической точки зрения различают следующие типы признаков.Количественные (числовые) признаки - это признаки, замеренные в определенной шкале и в шкалах интервалов и отношений.Качественные (ранговые, порядковые, балльные) - используются для выражения терминов и понятий, не имеющих цифровых значений (например, тяжесть состояния) и замеряются в шкале порядка.1 Работа выполнена при финансовой поддержке РФФИ (проекты № 09-01-99014-р_офи, № 07-01-00452).Номинальные (например, профессия, группа крови, тип хозяйства, национальность, пол) - это признаки, замеренные в шкале наименований. При анализе таких признаков каждую отметку номинальной шкалы считают отдельным самостоятельным признаком. Он принимает всего два значения (как правило, используют значения 0 и 1), разность которых можно интерпретировать как степень важности несовпадения данного признака при сравнении двух объектов. Такие признаки называют двоичными, бинарными, дихотомическими признаками [4, 5 - 9]. После проведения дихотомизации [5] (преобразования исходных показателей в набор признаков с двумя градациями) номинальные измерения становятся доступны для применения широкого спектра различных методов многомерного количественного анализа с учетом специфики данного вида измерений.В практических задачах распознавания первоначальные описания объектов содержат все доступные наблюдению (или измерению, вычислению) характеристики или параметры, поэтому в описании объектов участвуют несколько десятков (сотен) величин (например, в задачах медицинской диагностики, геологического, технического и социологического прогнозирования и т. д.). Однако набор большого числа прецедентов часто требует дорогостоящих и трудоемких работ (в некоторых случаях медицинской диагностики, прогнозирования редких металлов вообще невозможен) [1 - 3]. В прикладных работах наиболее распространенный пример объектов нечисловой природы - разнотипные данные. Так, в реляционной базе данных (как разновидности обучающего множества) информация о реальном объекте описывается вектором, часть координат которого - значения количественных признаков, а часть - качественных (номинальных и порядковых).При принятии решения о выборе класса, которому принадлежит анализируемый объект, возникает проблема его оценки по нескольким признакам и корректного учета этих оценок при их обобщении или совместном рассмотрении на этапе принятия итогового решения [1 - 7]. Эта проблема в свою очередь подразделяется на две подпроблемы: установление вида решающего правила (так называемого «обобщенного признака») и определение весовых коэффициентов - коэффициентов важности «частных» (характеристических) признаков [1-7, 9], отражающих свойства объектов.В данной работе рассматриваются особенности дискретного подхода к оценке информативности разнотипных признаков и анализируются статистические подходы, предложенные в [12, 16]. Применимость вероятностных и статистических подходов к оцениванию информативности признаков в интеллектуальных системах принятия решений возможна в случае пропусков данных; большой размерности задачи и пр. и никак не связана с тем, в какой шкале измеряются значения оцениваемых признаков.1. Основные определения и понятияВ общих чертах задача распознавания состоит в следующем [1 - 3, 7, 9].Исследуется некоторое множество объектов O = {O1, Om}. Известно, что O представимо в виде объединения K подмножеств S1, ..., SK , называемых классами. Наиболее общим определением класса является следующее [7]: класс - это совокупность (семейство) объектов, обладающих общими свойствами. Информация о свойствах объекта может быть получена путем наблюдений, измерений, оценок и т.п. и представлена совокупностью признаков, значения которых выражаются в числовых и/или вербальных шкалах. Входящие в один тот же класс объекты считаются неразличимыми (эквивалентными), а каждый класс объектов характеризуется некоторым качеством, отличающим его от других классов. Вместе все классы должны составлять исходную совокупность объектов.Наряду с классом используется понятие образа [9]. В матричной модели представления данных и знаний, включающей матрицу описаний (Q) объектов в пространстве характеристических признаков и матрицу различений (R) объектов в пространстве классификационных признаков [9], множество всех неповторяющихся строк матрицы R сопоставлено множеству выделенных образов. Элементами образа являются объекты, представленные строками матрицы Q, сопоставленными одинаковым строкам матрицы R.Если имеется единственный механизм классификации, матрица различений вырождается в столбец, что соответствует традиционному представлению знаний в задачах распознавания образов [1, 9].Объекты из O описываются некоторой системой признаков {z1, zM}. Имеется конечный набор O1,..., Om объектов из O, о которых известно, каким классам они принадлежат. Это прецеденты, или обучающие объекты. Пусть их описания имеют вид q1 = (q„, дш ) , Ч2 = (Ч21, Чш) , 4m = (4m1, 4mM) , здесь qti-значение признака z,- для объекта O, . Требуется по предъявленному набору значений признаков (b1, bM), описывающему некоторый объект из O (не входящий в обучающее множество O1,..., Om), о котором неизвестно, какому классу он принадлежит, определить этот класс.2. Постановка задачиТребования к подготовке данных (в соответствии с целями исследования) для математического анализа, для оценки характера распределения в исследуемой выборке (предварительный анализ данных) диктуют выполнение следующих работ [1 - 7]:1))проверку однородности выбранных групп наблюдения, в том числе контрольных, что может быть проведено или экспертным путем, или методами многомерной статистики (например, с помощью кластерного анализа);2)нормализацию переменных, т.е. устранение аномалий показателей в матрице данных (согласование мнений);3)снижение размерности пространства признаков (формальными методами путем оценки информативности);4))стандартизованное описание признаков;5))построение классификационных шкал признаков, т.е. процедуру идентификации и установления физических границ изучаемых параметров и представление информации в квантованной форме (каждому значению признака соответствует определенное кодовое число).Поставим, во-первых, задачу определения формальных подходов математической обработки и оценки информативности разнотипных признаков (п. п. 1, 3) -наиболее важных из вышеперечисленных как на этапе предварительного (для оценки характера распределения в исследуемой выборке), так и окончательного анализа в соответствии с целями исследования; во-вторых, задачу оценивания вероятностного распределения минимально необходимого числа информативных признаков, обеспечивающих заданный уровень надежности алгоритма (процедуры) распознавания, если известно вероятностное распределение признаков (что естественно для приложений, где накоплены соответствующие статистические данные).3. Методы оценки информативности разнотипных признаковРассматриваются пять подходов к отбору информативных признаков: на основе дискретных методов поиска в обучающей выборке информативной зоны [2, 3]; на основе методов кластеризации [5 - 7, 10]; на основе предположения о нормальности распределений объектов в кластерах [11 - 14]; на основе теоретико-информационного понятия энтропии [15, 16]; на основе непараметрических оценок плотности [19].3.1. Нахождение в обучающей выборке информативной зоныВ [2, 3] описывается методика предварительного анализа обучающей информации, основанная на нахождении в обучающем материале информативной зоны (информативными считаются такие подописания (или фрагменты описаний), которые позволяют различать объекты из разных классов или отличать данный объект от всех объектов, не принадлежащих тому же классу, что и рассматриваемый) и типичных для своих классов объектов (наиболее представительных). Информативная зона выделяется на основе оценки типичности значений каждого признака. Предлагается два способа выделения типичных объектов: 1) типичными считаются объекты, описания которых состоят из типичных значений признаков; 2) типичными являются объекты, которые правильно распознаются на скользящем контроле. Так, к нетипичным («шумящим») признакам относятся признаки, принимающие много значений или значения которых редко встречаются во всех классах (про такие признаки нельзя сказать, что они являются значимыми). Каждый объект обучающей выборки, лежащий на границе между классами, также не является «типичным» для своего класса, поскольку его описание похоже на описания объектов из других классов.Поиск информативных фрагментов основан на использовании аппарата дискретной математики, в частности булевой алгебры, теории дизъюнктивных нормальных форм, теории покрытий булевых и целочисленных матриц. Решению этой задачи посвящены работы [1 - 3, 9]. Так, в алгоритмах вычисления оценок, разработанных Журавлевым Ю.И. и его учениками [1 - 3], находятся оценки ансамблей признаков, которые являются обобщениями коэффициентов информативности, рассмотренных в [2].Для тестовых алгоритмов распознавания образов в [2] введена мера важности признака (его информационный вес) как отношение числа вхождений признака во все безызбыточные (тупиковые) тесты к числу всех безызбыточных тестов. В работе [9] на основе матричной модели представления данных и знаний получена формула, выражающая числовую оценку различающей способности признака (весовой коэффициент признака).Перечисленные в [1 - 3, 9] методы оценки информативности признаков показывают хорошие результаты в прикладных задачах. При этом под качеством распознавания понимается качество алгоритма вне обучающей выборки (способность алгоритма к обобщению или экстраполяции), которое оценивается долей (в процентах) правильно распознанных объектов при проведении процедуры скользящего контроля [10].Отметим, что применение дискретного подхода оказывается во многих случаях сложным в силу чисто вычислительных трудностей переборного характера, возникающих на этапе поиска информативных фрагментов описаний объектов [3]. При числе признаков, равном М, число непустых подмножеств составляет 2м 1 и прямой перебор всех подмножеств оказывается невозможным уже при М порядка 20 даже на самых современных компьютерах. В силу экспоненциального роста числа фрагментов при возрастании размерности описаний, решение проблемы только за счет повышения производительности вычислительной техники нереально, поэтому дискретные методы трудно применимы для предварительного анализа большого объема обучающей информации.Наиболее полное изложение методов дискретного анализа информации в задачах распознавания можно найти в [1 - 3, 10].3.2. Отбор информативных признаков на основе методов кластеризацииКластеризационные методы отбора признаков позволяют разбить выборку признаков на кластеры, состоящие из схожих признаков, и выделить в каждой группе по одному наиболее типичному представителю. Для применения методов кластеризации, рассмотренных, например, в [4 - 6, 10, 11], необходимо ввести метрику на множестве признаков Z. Рассмотрим возможные метрики на признаках.Пусть z1, z2 - два произвольных признака из Z. Выборочные векторы значений признаков (для объектов выборки O объема n) обозначим соответственно через z1 =(z1(O1),z1(O2),...,z1(On)) и z2 =(z2(O1),z2(O2),...,z2(On)). Рассмотрим три варианта определения функции расстояния p(z1, z2).1..Метрика на основе коэффициента линейной корреляции r(z1, z2), применимая для количественных признаков:nP(z1, z2)= 1 - |r(z1, z2)|, Г (z1, = g ^' (O, ) z2, (O, ),i =1где z/ (Oi), z2' (Oi) - нормированные и центрированные значения признаков z1, z2.Расстояние p(z1, z2) = 0 тогда и только тогда, когда признаки связаны линейной зависимостью.2..Метрика Кендалла - Кемени, применимая для порядковых признаков. Она определяется как доля пар объектов O;, Oj с различными порядковыми отношениями между значениями признаков z1 и z2:p(z1, = -C.|sign(z1 (Oi) - z (Oj)) - sign(z2 (O,) - z2 (Oj ))| .2 ^ Cn i=1 j=iЭто расстояние равно нулю тогда и только тогда, когда признаки связаны монотонной зависимостью, то есть существует монотонная функция f такая, чтоzx(Pj) = f (z2(Oj)) (j = 1, . . . , n).3..Метрика Хэмминга, применимая для номинальных признаков с одинаковыми множествами допустимых значений D = Dz^, которая обращается в нуль тогда и только тогда, когда векторы z1 и z2 совпадают:p(z1,z2) = g[z1(Oi) * z2{Ol)].i=1Для номинальных признаков с различными множествами значений ищется соответствие о: D Dz^, при котором расстояние Хэмминга минимально (без ограничения общности предполагается, что JDz11 > |Dz21):Если необходимо найти метрику между разнотипными признаками, измеренными в разных шкалах, то они сначала приводятся к одной общей шкале [6 - 8, 11].Отметим следующие особенности применения методов кластеризации.Во-первых, если в исходном множестве признаков будут присутствовать неинформативные признаки, то могут появиться кластеры, целиком состоящие из неинформативных признаков.Во-вторых, вышеупомянутые метрики используют информацию о попарном сходстве между признаками, но не решают проблему мультиколлинеарности признаков (набор попарно некоррелированных признаков может оказаться линейно зависимым).В-третьих, классификация по принципу минимального расстояния пригодна, если кластеры, соответствующие разным классам, разнесены достаточно далеко друг от друга [7], т.е. значения признаков, описывающих объекты из разных образов, достаточно далеки друг от друга.3.3. Статистический кластер-алгоритмАлгоритм построения кластеров в предположении о нормальности распределений объектов в кластерах (что является естественным во многих практических приложениях) использует кластер-критерий, предложенный в [12], и свойство оценок Мешалкина Л. Д. [13] оценивать параметры распределения кластера, наибольшего по количеству точек. Отметим, что условия критерия К. Пирсона [14] проверки гипотезы о совпадении центров двух многомерных нормальных совокупностей с известными ковариациями, различающихся сдвигом, являются непригодными для кластер-анализа в силу жесткости используемых предположений.Идея построения кластер-алгоритма, разбивающего выборку признаков на кластеры, состоящие из схожих признаков, заключается в следующем.Кластер-критерием на уровне значимости а проверяется гипотеза о принадлежности выборки одному нормальному распределению. Если гипотеза принимается, то выборка с вероятностью 1 - а содержит один кластер. Если гипотеза отвергается, то самый большой кластер вырезается эллипсоидом на уровне значимости а и к оставшимся точкам применяется описанная процедура в цикле. Процедура выделения кластеров заканчивается, когда все точки распределены по кластерам либо их количество невелико (а-остатки от проверки гипотез).В отличие от большинства алгоритмов кластерного анализа данный статистический кластер-алгоритм не требует предварительного указания числа K классов, на которое надо поделить совокупность точек наблюдения, и решает задачи со сложными наложениями и пересечениями нескольких классов (случай, когда признаки могут принимать одинаковые значения для объектов из разных образов).3.4. Методы оценки информативности признаков на основе энтропииВ терминах теории информации мерой трудности распознавания служит энтропия H распределений плотности вероятности образов [6, 15, 16].1. Метод на основе формализма мультимножеств и теоретико-информационном понятии энтропии. Основанный на формализме мультимножеств [17] метод определения весовых коэффициентов признаков при принятии решения в интеллектуальных тестовых распознающих системах с матричным представлением данных и знаний [9] учитывает вклад признаков в распознающую способность теста с учетом их взаимозависимости и базируется на представлении совокупности всех различимых пар объектов из разных образов для каждого признакаzt, i = 1, M , в виде мультимножества [18].Поставим данному признаку в соответствие совокупность различимых i-м признаком пар объектов из разных образов и будем говорить, что признак zi порождает мультимножество {kP (u) u | u е U, kPj (u) e Z+ }. Таким образом, представленные признаки [17] являются множествами с повторяющимися элементами u eU (мультимножествами), при этом мощность мультимножества определяется как общее число его элементов, где множество U - домен или универсальное множество [17], откуда «черпают» свои возможные значения мультимножества, порожденные соответствующими признаками. Заметим, что элементы домена u являются обозначениями пар объектов из разных образов, поэтому элементы (i-j) и (j-i) (пары номеров объектов) считаются эквивалентными (ižj, i,je{1, K}). Обозначим через P(v / i) вероятность «проявления» v-го элемента домена дляi-го образа, тогда вероятность v-го элемента домена для всех K образов равнакPv =^P(v/i). С учетом условия нормировки доля i-го образа в этой суммеi =1ri = P(v / i)/ P(v) и энтропия v-го элемента домена выражается следующим значе-книем: Hv ="Х ri ■ log2 ri .i =1Из свойства аддитивности энтропии следует, что общая неопределенность приNuраспознавании образов по признаку zi имеет вид Hz =Hv ■ Pv . Количествоv=1информации, получаемой в результате измерения признака zi , равно H0 - HZj, H0 - исходная неопределенность относительно образов H0 = log2 K .При качественном анализе эмпирических данных роль вероятностей P(v / i) (вероятность «проявления» v-го элемента домена для i-го образа) играют их выборочные оценки (частости, доли).В реальных таблицах данных зависимость между признаками наблюдается очень часто. А если признаки зависимы, то при выборе наиболее информативной подсистемы признаков оценками их индивидуальной информативности руководствоваться нецелесообразно.2. Анализ взаимосвязи признаков на основе энтропии. Трактовка статистической связи между переменными zt и Zj сводится к оценке количества информации I(zi, Zj) = H(Zj) - H(Zj / zi), которое уменьшает неопределенность того, какое значение примет zj, если известно значение zi. В качестве оценки меры сопряженности примем долю сопряженного разнообразия величины zj, включенной в систему (zi, Zj), по сравнению с разнообразием (энтропией) Zj, рассматриваемой отдельно: I(zi, zj)/H(zj), где в явной форме величина I(zi, zj) определяется по формулеI (Z,, Zj ) = -£ £p( XS , Ук )l0g2=-£ I>( XS , yk )l0g2 ?Х',Ук) ,где l - число градаций признаков.Отметим, что в силу симметричности выражения I(zi, Zj) относительно zi, Zj значения количества информации, заключенного в признаке zt о признаке Zj и заключенного в признаке Zj о признаке zi, равны [14], т.е. среднее количество информации есть мера соответствия двух признаков, характеристика их связи, а не характеристика одного из признаков.Взаимная информация I(zi, zj) обращается в нуль тогда и только тогда, когда признаки zt и Zj статистически независимы. Максимальное значение взаимной информации, равное H(zi) или H(Zj), соответствует функциональной зависимости (полной связи) признаков zt и Zj, когда каждому значению признака zt соответствует единственное значение признака Zj. Заметим, что использование коэффициента I(zi, Zj)/H(Zj) для разделения признаков на «зависимые» и «определяющие», вообще говоря, не имеет достаточного обоснования.Отметим, что построение теоретико-информационной меры связи может осуществляться не только на основе энтропии. Важным примером такой меры служит коэффициент Валлиса, реализующий принцип «пропорциональной предик-ции», согласно которому мерой связи должно служить относительное уменьшение вероятности ошибки предсказания признака Zj при знании признака zt в сравнении с вероятностью ошибки прогноза Zj без знания zi. Интерпретация коэффициента Валлиса весьма проста: если, например, его значение равно 0,5, то знание Zi уменьшает число ошибок прогноза значения Zj вдвое. Однако в выборочных исследованиях предпочтительнее пользоваться не коэффициентом Валлиса, а информационными мерами связи, значимость которых может быть установлена, например, в соответствии с критерием Пирсона [14].3.5. Оценка информативности разнотипных признаков на основе непараметрических оценок плотностиМетоды оценивания плотности вероятности в пространствах общего вида предложены и первоначально изучены в [19]. В частности, в задачах классификации объектов нечисловой природы предлагается использовать непараметрические ядерные оценки плотности типа Парзена - Розенблатта (этот вид оценок и его название введены в [19] по имени американских ученых Парзена и Розенблатта, ранее использовавших подобные статистики в случае X = Rl, р( xt, x) = |xi - X ):где K: R+ - R - ядерная функция; {x1,x2,...,xn}е X - выборка, по которой оце-нивается плотность; р( xi, x) - расстояние между элементом выборки xi и точкой х, в которой оценивается плотность; последовательность показателей размытости {hn } такова, что при n --со hn 0 и nhn --со ; vn (hn, x) - нормирующий множитель, обеспечивающий выполнение условия | fn (x)dц = 1.XВ [19] показано, что оценка плотности типа Парзена - Розенблатта fn (x) является состоятельной (fn (x) - f (x) по вероятности при n - со) и оценена сред-неквадратическая скорость сходимости ядерных оценок a n = E (fn (x) - f (x ))2.Поскольку пространство разнотипных признаков - это декартово произведение непрерывных и дискретных пространств, то для случая фиксированного числа градаций качественных признаков непараметрическую оценку плотности можно свести к произведению частоты попадания в точку в пространстве качественных признаков на классическую оценку Парзена - Розенблатта [19] в пространстве количественных признаков. Расстояние р( x, y) можно рассматривать как сумму евклидова расстояния р1 между количественными факторами, расстояния р2 между номинальными признаками (р2 (x, y) = 0, если x^y, и р2 (x, y) = 1, если x = y), и расстояния р3 между порядковыми переменными (если x и y - номера градаций, то р3 (x, y) = |x - y|).4. Двусторонние оценки для вероятности минимального числа признаков, обеспечивающих гарантированный уровень качества процедуры распознаванияРассмотрим подход к оценке качества алгоритма распознавания образов как функции «качества» обучающей выборки (объема и содержания выборки в виде «объект-признак»). Основу данного подхода к оценке качества процедуры распознавания составляет заданная информация о частотах встречаемости признаков (оценках вероятностей проявления признака) для каждого из классов (образов). Получим двусторонние оценки для вероятности минимального числа признаков, обеспечивающих гарантированный уровень качества процедуры распознавания, при этом будем использовать вероятностную модель пересечения случайным процессом определенного уровня.Пусть ^ = ^ (m) - случайная величина (с.в.), означающая число корректнораспознанных объектов на обучающей выборке признаком zt, i = 1, n (n - число признаков, m - число объектов).представляет собой долю корректно рас-познанных объектов по n первым признакам, ранжированным каким-либо образом, например, по убыванию весовых коэффициентов признаков, вычисленных по обучающей выборке (например, по формулам, предложенным в [20]), и является числовой интерпретацией меры надежности распознавания, или качества работы алгоритма распознавания [10, 11].Введем с.в. (момент остановки случайного процесса Фn [21, 22]):т = inf{n > 1: Фn >где q0 - заданный уровень надежности (качества) процедуры (алгоритма) распознавания.Поставим задачу оценить вероятностное распределение Rn = P(t> n) величины т, или минимально необходимого числа информативных признаков, обеспечивающего заданный уровень надежности распознавания, если известно вероятностное распределение признаков.Знание распределения величины т, являющейся пороговым значением качества алгоритма распознавания, позволит: а) оценить требуемое количество признаков (n) для достижения заданного уровня качества распознавания; б) оптимизировать процедуру распознавания по параметрам n, m, а также их весовым коэффициентам. Так, в приложениях (геологических, медицинских и пр.) актуально решение вопроса о соотношении длины выборки данных (m) (например, дорогостоящее бурение дополнительной скважины) и числа характеристических признаков (n) (введение менее дорогостоящего дополнительного анализа для уже имеющихся данных).Обозначимч (к)== к) = х П plt П с1 - p«),уг = Щ( = X к ч (к), аг2 = D^. = X (к - Vi )2 ч (к)к=1 к=0и сформулируем результат проведенного исследования.Теорема. Пусть признак zi, i = 1,n, распознает объект Oj = {a(,j = 1, m, с вероятностью pn и справедливо условиек I qom-Vi \

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