Интеллектуальный анализ данных
 Скачать 7.76 Mb.
|
|
Метод накопленных частот Сущность метода накопленных частот состоит в следующем: для значений одного из признаков (x) каждого из классов строится гистограмма. Далее для каж- дого интервала подсчитываются накопленные частоты – количество объектов ка- ждого класса от начала гистограммы до текущего значения включительно. Макси- мальная разность накопленных частот и будет оценкой информативности. Следует отметить относительность полученной оценки. Насколько хороша измеренная ей информативность, можно судить только по сравнению с аналогич- ными расчетами для других признаков этих же классов. Энтропийный подход В терминах теории информации мерой информативности признака служит энтропия (H) распределений плотности вероятности прообразов (классов). Суть методов заключается в определении изменения энтропии как меры неопределен- ности до и после измерения признака. Наиболее распространенными методами оценки информативности в этом подходе являются: – метод Шеннона; – метод Джини; – метод Кульбака. Метод Шеннона. Рассмотрим метод Шеннона на следующем примере. 117 Пусть распределения объектов k классов проецируются на ось признака х с точностью до t градаций. Вероятность попадания объектов i-го образа в j-ю града- цию обозначим P(j/i) (очевидно, что она определяется как отношение объектов i-го класса, попавшим в j-ю градацию к общему количеству объектов в нем). Просуммировав для j-й градации вероятности всех попадания в нее объек- тов всех k классов, получим величину k i j ) i \ j ( P P 1 Вклад i-го класса в эту сумму определяется как j j P ) i \ j ( P r В соответствии с положениями теории информации энтропия j-й градации выражается как k i i i j r log r H 1 Из свойства аддитивности энтропии следует, что общая неопределенность классификации по признаку х имеет вид k i i i x P H H 1 Если исходная неопределенность H 0 ситуации равнялась log k, то количест- во информации I x , получаемой в результате измерения признака x, равна H 0 – H x Метод Джини Показатель (индекс) Джини позволяет определить информативность раз- биения объектов обучающей выборки по некоторому правилу. При этом узлов Рис.7. Пример расчета информативности по Шеннону 118 разбиения может быть только два, а классов в обучающей выборке – произволь- ное количество. Смысл данного индекса в буквально соответствует гипотезе компактности: разбиение тем лучше, чем оно «чище», то есть, если в нем со- держатся объекты, принадлежащие только одному классу. Метод Джини, по суще- ству, оценивает количество «мусора» в разбиении, поэтому, чем меньше его зна- чение, тем выше качество разбиения. Количественная оценка качества разбиения множества Т на два подмноже- стваТ 1 и Т 2 , содержащих соответственно по N 1 и N 2 элементов, по методу Джини определяется следующим образом: ) T ( G N N ) T ( G N N ) T ( G S 2 2 1 1 , где G(T i ) – собственно индекс Джини – определяется как K j j i P ) T ( G 1 2 1 Здесь К – количество классов в выборке; P j – частота вхождения j-го класса в подмножество. Метод Кульбака Показатель информативности признака, получивший назва- ние дивергенция Кульбака, вычисляется по следующей формуле: 2 1 2 2 1 1 j j j t j j P P log ] P P [ ) x ( I , где t – количество градаций признака. Вероятность появления j-й градации в i-м классе определяется как ) A ( card m P i ji ji Здесь m ji – частота появления j-й градации в i-м классе, а card(A i ) – мощ- ность множества элементов, отнесенных к i-му классу, то есть количество объек- тов данногокласса в обучающей выборке. NB! Заметьте: дивергенция Кульбака несимметрична, хотя, ее иногда назы- вают расстоянием. Ее значение будет зависеть от того, какой из классов назначен первым. На практике первым классом назначается некоторая эталонная модель, сравниваемая с экспериментальными данными, представляющими второй класс объектов. Сравнительный анализ методов Метод сравнения расстояний в рассмотренном множестве – единствен- ный, позволяющий оценить за один «проход» информативность рабочего сло- варя признаков, при этом он не требует разбиения области значений признака на градации. Все остальные методы оценивают одновременно информатив- ность только одного признака и предполагают введение градаций. При этом только метод Шеннона и Джини дают абсолютную оценку информативности. Прочие методы позволяют говорить об оценке только в относительном плане – более высокая или более низкая. Так, для метода накопленных частот оцен- ка информативности одного признака сопоставима только с оценкой другого признака, либо для других примеров обучающей выборки аналогичного объе- ма и состава. Обязательным условием для данного метода, кроме того, явля- ется равное количество объектов различных классов в обучающей выборке. 119 Наконец только методы Шеннона и Джини позволяют оценивать информатив- ность для произвольного количества классов. NB! Следует отметить, что метод накопленных частот является наиболее про- стым для вычислений. Сравнительный анализ методов приведен в таблице. М е то д П р е д м е т о ц е н и в а н и я З а в и си м о ст ь о т сп о с о б а ко д и р о в а н и я К о л -в о с р а в н и в а е м ы х кл а с со в З а в и си м о ст ь о т о б ъ е м а в ы б о р ки О ц е н ка и н ф о р м а ти в н о - ст и Н е о б хо д и м о ст ь в в е д е - н и я г р а д а ц и й п р и зн а ка Сравнения расстоя- ний простран- ство да 2 нет отно- сит. нет Накоплен- ных частот признак да 2 рав- ное для классов отно- сит. есть Энтропийные методы Шеннона признак нет лю- бое нет абсол. есть Джини признак нет лю- бое нет абсол. есть Кульбака признак нет 2 нет отно- сит. есть NB! Следует, наконец, пояснить необходимость оценки информативности признаков. Первоначально актуальность этой задачи обосновывалась необходи- мостью экономии ресурсов вычислительной техники: чем меньше признаков об- рабатывалось совместно, тем быстрее решалась задача классификации. В настоящее время необходимость формирования эффективного признако- вого пространства обусловлена тем, что низкоинформативные признаки, как пра- вило, вносят в процесс распознавания избыточный уровень «шумов», что нега- тивно сказывается на результате. Поэтому одной из задач реализации процесса распознавания с учителем является подбор эффективного признакового про- странства. Необходимо отметить, что информативность отдельного признака может быть гораздо более низкой, чем их совокупности. В этом случае принято говорить о зависимых признаках. Рассмотренные ранее способы оценивания информатив- ности признаков или признакового пространства в целом предполагают независи- мость признаков. Строгих математических методов, позволяющих выделить среди множества зависимых признаков подмножество достаточно информативных, кроме прямого перебора, не существует. Однако такая операция весьма трудоемка даже для со- временных компьютеров. 120 Вопросы для самопроверки: 1. Перечислите методы способности признаков разделять объекты. 2. В чем состоит метод сравнения расстояний? 3. В чем состоит метод накопленных частот? 4. Назовите наиболее распространенные методы оценки информативности в энтропийном подходе. 5. Опишите метод Шеннона. 6. Что определяет индекс Джини? 7. Что называется дивергенцией Кульбака? 8. Сравните методы анализа информативности признаков. 121 ЛЕКЦИЯ 14 МЕТОДЫ КЛАССИФИКАЦИИ Основываясь на возможности распространения концепции расстояния на все области статистики, следует пояснить различия интенсионального и экстен- сионального подходов к описанию объектов прообраза (класса). В интенсиональном подходе при использовании концепции расстояния множество образов, относящихся к одному прообразу (классу), заменяется неко- торым абстрактным объектом, обладающим усредненными характеристиками всех объектов данного класса – эталоном класса. В экстенсиональном подходе важную роль играет прототип – ближайший к реализации объект класса. В наиболее простых методах распознавания с учителем решение об отне- сении реализации к одному из образов принимается по критерию минимального расстояния между реализацией и эталоном класса или прототипом, как это пока- зано на рис. 10. 2. NB! Недостатком рассмотренных методов является высокая зависимость результата от распределения прообразов в признаковом пространстве, а также высокая чувствительность к «выбросам» – аномальным объектам класса. Не- сколько снизить влияние аномалий позволяет описанный ниже метод. 1. Метод k-ближайших соседей Суть метода состоит в том, что решение об отнесении реализации (b) к од- ному из классов принимается не по одному примеру (эталону или прототипу), а по некоторому множеству наиболее близких к ней объектов, что позволяет несколько сгладить влияние выбросов. Для этого вокруг реализации строится область (ок- ружность, а в многомерном пространстве – гиперсфера), в которую попадают «го- лосующие» объекты обучающей выборки, принадлежащие различным классам. Радиус гиперсферы выбирается таким, чтобы в нее попали k объектов обучающей Рис.10. Критерий минимального расстояния 122 выборки (отсюда и название метода). Его значение, точнее, значение k, зависит от объема обучающей выборки (N): обычно полагают k ≈ N 1/2 , k ≈log 2 (N) и т.п. Основной проблемой метода k-ближайших соседей является принятие ре- шения при четном k и равном представительстве объектов различных классов в выделенной области. В этом случае значение k либо увеличивается, либо умень- шается на единицу. NB! Здесь и далее принято, что размерность алфавита классов равна двум. На практике же их может быть и больше. Однако здесь можно воспользоваться принципом «здорового шовинизма», полагая, что алфавит классов содержит «нужный класс» и класс «все остальные». 2. Метод дробящихся эталонов Другим методом, в котором приняты меры для нейтрализации неоднород- ного распределения объектов различных классов в признаковом пространстве, является метод «дробящихся эталонов», разработанный Н.Г. Загоруйко. Идея ме- тода состоит в последовательном уточнении эталонных описаний, в результате чего признаковое пространство разбивается на области, принадлежащие различ- ным классам. NB! На заключительных этапах дробления в признаковом пространстве мо- гут оказаться области, не отнесенные ни к одному из классов. В этом случае для распознавания реализации может быть применен любой другой из рассмотренных выше методов. 3. 1R-правила Достаточно тривиальным алгоритмом для формирования правил классифи- кации объектов является так называемый 1R-алгоритм. NB! Его название расшифровывается как «one rule» или в русскоязычном переводе – «1-правило». Идея 1R-алгоритма (на примере номинальных переменных) состоит в сле- дующем: для каждой градации переменной по известной обучающей выборке оп- ределяется достоверность проявления в каждом из классов. Пара «градация- класс» с наибольшей достоверностью и представляет собой 1-правило. NB! Существенным недостатком 1R-алгоритма является сверхчувствитель- ность (overfitting). Дело в том, что для уникальных значений достоверность опре- деляется максимальной. Чтобы избежать этого, целесообразно ввести градации количественной переменной, как это и показано в примере. Несмотря на простоту реализации, 1R-алгоритм во многих случаях обеспе- чивает достаточно надежное распознавание. Кроме того, немногочисленность по- лученных правил позволяет легко интерпретировать и использовать полученные результаты. 4. Метод потенциальных функций Свое название данный метод получил в связи с использованием аналогии электрических потенциалов: объекты, относящиеся к одному классу, наделяются единичным зарядом (потенциалом) одинаковой полярности. Объекты другого 123 класса обладают точно таким же по значению потенциалом, но противоположной полярности. NB! При размерности алфавита классов более двух можно выделить «нуж- ный класс» и «прочие классы». Из курса физики известно, что суммарный наведенный потенциал в некото- рой точке определяется как сумма потенциалов всех зарядов, находящихся дос- таточно близко к этой точке: 2 1 1 N N i i ) x , x ( K ) x ( K где N 1 ,N 2 - размеры обучающих выборок из первого и второго класса. K(x, x j ) называют потенциальной функцией i-го заряда. Она, как и электри- ческий заряд, убывает с ростом расстояния между x и x i Чаще всего в качестве потенциальной используется функция, имеющая максимум при x = x i и монотонно убывающая до нуля при \ x x \ i Этим требованиям удовлетворяет, например, функция ) ) x , x ( d exp( ) x , x ( K i i 2 2 , или функция 1 2 2 1 ) ) x , x ( d ( ) x , x ( K i i где a – параметр функции, определяющий скорость ее убывания; d(x, x i ) – рас- стояние между точками x и x i Изолинии, соединяющие точки с нулевым потенциалом, будут являться границами класса в признаковом пространстве. Впрочем, их построение необяза- тельно: можно просто рассчитать кумулятивный потенциал только в той точке признакового пространства, которая соответствует реализации. Графическая иллюстрация метода на примере одного признака приведена на рис. 11. Классификация неизвестного наблюдения осуществляется по знаку потенциальной функции в точке его расположения. При этом ограничений на построение потенциальных функций в многомер- ном пространстве нет. NB! Выбор параметра a достаточно неоднозначен. Так, если потенциаль- ная функция убывает очень быстро, то можно добиться практически безошибоч- ного разделения объектов обучающей выборки. Однако при этом могут возникнуть зоны неопределенности (там, где потенциал близок к нулю). При слишком «поло- гих» склонах функции может необоснованно увеличиться количество ошибок рас- познавания, в том числе и на обучающих объектах. Некоторые рекомендации в этом отношении можно получить, рассматривая метод потенциальных функций со статистических позиций (восстановление плотности распределения вероятностей p(x) или разделяющей границы по выборке с использованием про- цедуры типа стохастической аппроксимации), однако, этот вопрос выходит за рамки учебника. NB! В приведенном примере использован так называемый «наивный под- ход», основанный на суммировании потенциалов. Из примера видно, что потенци- ал класса А «нейтрализуется» потенциалом класса В. Особенно это заметно при количественном превосходстве объектов одного класса над другим. Для устране- 124 ния этого недостатка разработаны специальные методы, основанные на подборе весовых коэффициентов объектов обучающей выборки. Рис.11. Метод потенциальных функций 125 5. Классификатор Байеса В основе байесовского классификатора лежит теорема Байеса, с которой Вы уже знакомы из курса теории вероятностей: ) B ( P ) H \ B ( P ) H ( P ) B \ H ( P где P(H) – априорная вероятность гипотезы H; P(H|B) – апостериорная вероят- ность гипотезы H при наступлении события В; P(B|H) – вероятность наступления события В при истинности гипотезы А; P(B) – полная вероятность события В. NB! «… теорема Байеса является основой теории вероятности, точно так же как и теорема Пифагора есть основа геометрии». [Jeffreys, Harold (1973), Scientific Inference (3rd ed.), CambridgeUniversity Pres s, p. 31] С приведенным определением трудно не согласиться: она позволяет пере- ставить местами причину и следствие. Так, зная, с какой вероятностью причина приводит к некоторому событию, с помощь этой теоремы можно рассчитать веро- ятность того, что именно эта причина привела к проявлению наблюдаемого собы- тия. |