Интеллектуальный анализ данных
 Скачать 7.76 Mb.
|
|
NB! Отметим,чтотермин «pattern», кроме значения «образ», имеет еще значение «модель, стиль», «режим», «закономерность», «образ действия». В теории распознава- ния образов этот термин употребляют в самом широком смысле, имея в виду, что «об- раз» – это некоторое структурированное приближенное (обратите внимание – прибли- женное!) описание (эскиз) изучаемого объекта, явления или процесса. Идея классификации заключается в группировании однотипных объектов на основании гипотезы компактности. Суть гипотезы компактности состоит в том, что реализации одного и того же образа отображаются в пространстве характеристик геометрически близко распо- ложенными точками, т.е. образуют «компактные» сгустки. В идеальном случае эти сгустки, образованные проекциями различных образов, не пересекаются. Более простыми словами эту гипотезу можно изложить так: объекты, схожие между со- бой, образуют в пространстве характеристик компактные сгущения. В формальном виде гипотеза компактности представляется следующим об- разом: пусть имеется два объекта, обладающие k+1 характеристиками, причем последняя характеристика (z) является качественной и представляет собой имя класса. Тогда при равенстве (или, строго говоря, различии на величину не более малой величины ε для количественных переменных) k характеристик объектов x и b совпадает и k+1-я характеристика z: k b k k 2 2 1 1 z z x b ... x b x b Замечание. Разделение характеристик объекта на описывающие (1, …, k) и целе- вые (z) является в задачах анализа данных весьма условным. Мы можем включить целе- вую характеристику z в число описывающих, а в качестве целевой (неизвестной) выбрать любую другую характеристику (x j ). Если при этом реализации некоторого образа А = {а 1 , а 2 , …, а n } сохраняют компактность в новом пространстве характеристик {х 1 , х 2 , …, х k- 2 , z, x j }, а множество (А, b) компактно в пространстве характеристик (признаков) {х 1 , х 2 , …, х k–1 ,z}, то значение новой целевой переменной x j будет эквивалентным (в применяе- мой р) значению реализаций образа А. В математической постановке – это задача рег- рессии. Целевыми могут быть не одна, а несколько характеристик. В частности, гипотеза компактности позволяет решать не только задачу анализа, но и обратную задачу – синте- за, когда по имени класса (образа) А восстанавливаются (прогнозируются) наиболее правдоподобные значения характеристик некоторого объекта b также отнесенного к клас- су A. Несколько позже стало развиваться и другое направление группирования объектов, основанное только на сходстве их характеристик, при абсолютном от- сутствии каких-либо данных об их «классовой принадлежности» – кластеризация. По этой причине, основываясь на том, что при классификации 109 имена классов и их границы задаются априорно, ее стали называть распознава- нием с учителем (с обучением), а кластеризацию – распознаванием без обучения (без учителя), автоматической кластеризацией, таксономией. NB! Термин «таксономия» чаще всего применяют для иерархической кла- стеризации. Ввиду различия подходов к группированию объектов, далее методы клас- сификации и кластеризации рассматриваются раздельно. Сходство и различие распознавания с обучением и без. И класси- фикация, и кластеризация предназначены для решения одного класса задач – оп- ределения некоторой характеристики объекта, выраженной в номинальной шкале – имени класса, либо кластера. Основное же различие состоит в том, что имена и другие характеристики классов задаются заранее (в этом, собственно, и состоит процесс обучения сис- темы распознавания); кластеры же формируются в ходе группирования объектов. В ряде случаев кластеры Среди других различий подходов к распознаванию следует выделить: а) Применяемый математический аппарат. Для решения задачи классифи- кации используются статистические (вероятностные), структурные и логические методы математики. В кластеризации используется только одна характеристика: сходство объектов, выражаемое, обычно, расстоянием между ними в заданном признаковом пространстве. б) Классификация, как правило, однозначна. Иными словами, при заданных условиях и неизменном математическом аппарате решение (минимальное рас- стояние до прообраза класса, максимальная вероятность принадлежности к клас- су и т.п.). Результаты некоторых алгоритмов кластеризации зависят, к примеру, от выбора начальных центров кластеров. Постановка задачи классификации. Обычно используется следующая математическая постановка задачи распознавания с учителем: задана некоторая предметная область (М) разбитая на классы (прообразы) A i ; i = 1,2, … k так, что 1 { ) ; ; k i i j i A M A A j i Каждый класс описан набором характеристик, позволяющих их различить: {X} = {x 1 , x 2 , …, x m } – признаками. NB! Совокупность признаков принято называть словарем признаков. Далее будет показано, что словарь признаков при решении некоторых задач классифи- кации образует признаковое пространство. Задается также некоторый объект b, называемый реализацией, также пред- ставленный набором характеристик {b 1 , b 2 , …, b m }. Требуется найти качественную характеристику (ρ) распознаваемого объекта b, совпадающую с именем одного из классов, такую, что выполняется условие гипотезы компактности. Таким образом, задача классификации сводится к задаче выявления отношений эквивалентности на множестве объектов. 110 NB! Совокупность математических методов определения сходства класса и реализации, на основании которых определяется ρ, называется решающим пра- вилом. 2. Алгоритм типовой системы классификации Формируется рабочий словарь признаков, включающий только те характе- ристики, которые имеются и у реализации, и у описания класса. NB! Характеристика свойства объекта становится только тогда, когда с ее помощью определяются схожесть объектов! Проводится поочередное сравнение характеристик реализации с каждым из К классов. На основании заданных решающих правил принимается решение о при- надлежности реализации к одному из классов. 1. NB! Необходимо отметить, что строгая математическая постановка задачи достаточно далека от реалий действительности. Разбиение признакового про- странства на практике не всегда применимо. Рис.1. Алгоритм типовой системы классификации Рис.2-3. Разбиение и покрытие 111 Чаще области классов пересекаются в признаковом пространстве, что принято называть его покрытием. В этом случае решение о принадлежности объек- та к одному из классов может носить ве- роятностный характер. Кроме того, воз- можны ситуации, когда покрытие непол- ное, то есть некоторые области признако- вого пространства не отнесены ни к одно- му из классов. При попадании реализации именно в эту область компьютерные алгоритмы не в со- стоянии решить задачу – происходит от- каз от распознавания. В этом случае требуется участие человека для уточнения границ классов (либо задания области нового класса) в призна- ковом пространстве. Очевидно, что в некоторых случаях возможно и сочетание неполного по- крытия с пересечением. Обилием вариантов описания классов и их размещением в призна- ковом пространстве и обусловлено существова- ние множества методов классификации. 3. Классификация методов распозна- вания с учителем Несмотря на достаточно долгий период разработки методов распознавания, их обще- принятой классификации не сложилось. Наиболее часто для этой цели использу- ются следующие основания: – степень формализации решающих правил; – способы описания классов объектов; – используемый математический аппарат решающих правил; – степень определенности результата. Далее при описании методов распознавания с учителем мы будем придер- живаться данной классификации. 3.1. Классификация по степени формализации решающих правил По данному основанию выделяют формальный и эвристический подходы. Формальный подход предполагает построение математической модели предметной области, обеспечивающего применение математических методов для решения поставленной задачи. Рассматриваемые далее методы классификации относятся к формальным. Эвристический подход основывается на попытке смоделировать опыт и ин- туицию человека. Примером такого подхода является использование для распо- знавания искусственных нейронных сетей. NB! Методы формального подхода более общие, чем эвристического, од- нако, любая формализация предполагает некоторое «огрубление» исходных дан- ных. Рис. 4. Неполное покрытие Рис. 5. Неполное покрытие с пересечением 112 3.2. Классификация по способу описания классов объектов По данному основанию выделяют интенсиональный и экстенсиональный подходы. Суть интенсионального подхода заключается в замещении объектов клас- са некоторым абстрактным объектом – эталоном класса, либо, в некоторых слу- чаях, определения признака как случайной величины с известным законом рас- пределения, матрицей связи признаков и т.п. Экстенсиональный подход, напротив, предполагает использование всех доступных объектов класса для определения принадлежности к одному из клас- сов. Этот подход оперирует понятием «прототипа», которым может быть любой объект или их группа. NB! При исследовании динамики объектов термин «прототип» принято за- менять на «прецедент». NB! Необходимо подчеркнуть, что в основе этого разделения лежат фунда- ментальные закономерности человеческого познания! Так, полагается, что для правого полушария человеческого мозга целостное представление окружающего мира, то для левого – выделение закономерностей, отражающих связи атрибутов объектов окружающего мира. Очевидный вывод из изложенного состоит в том, что для успешного решения задач (хотя мы об этом и не задумываемся) необходимо совместная работа обоих полушарий. 3.3. Классификация по используемому математическому аппарату 4. Методы классификации Статистические методы. Группа статистических методов наиболее многочисленна, что обусловлено достаточно длительным периодом развития ста- тистики как науки. Рис.5. Классификация по используемому математическому аппарату 113 Первоначально данные методы развивались в русле классической пара- метрической статистики, для которой характерно использование интенсиональ- ных методов. К ним относятся методы, основанные на оценках плотностей распределе- ния значений признаков. Нетрудно видеть, что данные методы предполагают зна- ние закона распределения признака как случайной величины (в приведенном примере – нормального). Эти методы относятся к вероятностным. Для них разра- ботан достаточно серьезный математический аппарат принятия решения о при- надлежности реализации к одному из классов. NB! Для данных методов достаточно существенны ограничения на приме- нение центральной предельной теоремы теории вероятностей. Тем не менее, при наличии достаточно большого объема количественных данных необходимо про- вести проверку возможности их аппроксимации каким-либо известным законом распределения. Идея методов, основанных на предположении о классах решающих функ- ций состоит в разделении признакового пространства на области, каждая из кото- рых соответствует только одному классу. В простейшем случае – это линейная разделяю- щая поверхность (на случай многомерного про- странства – гиперплоскость). NB! Процедуры построения линейных решающих функций разработаны в 50-х годах XX века Ф. Розенблатом для использования в перпцептроне (устройства для распознавания изображений). Один из способов, расширяющий область применения решающих функций, заключается в использовании кусочно-линейных функций, позволяющих разде- Рис.6. Классификация методом оценки вероятностей Рис.6. Классификация методом разделяющей 114 лять достаточно сложные области. Другое расширение данного метода – метод опорных векторов (Support Vector Machine) – позволяет изменять геометрию признакового пространства с целью его разделения на области классов. Методы, основанные на операциях с объектами, наиболее популярны в статистике объектов нечисловой природы. Кроме того, они применимы и при об- работке количественных характеристик, особенно если неизвестен закон распре- деления признака как случайной величины. В основе рассматриваемых методов лежит метрика, рассматриваемая как величина, обратно пропорциональная сходству объектов. Логические методы. Логические методы классификации основаны на ус- тановлении логических связей между признаками и классами объектов (в качестве последних также могут рассматриваться различные состояния одного и того же объекта). Первоначально логические методы предусматривали построение высказы- ваний булевой алгебры истинность или ложность которых при подстановке в них значений характеристик реализации свидетельствовала об ее принадлежности к одному из классов. При этом необязательно, чтобы характеристики были булевы- ми переменными. Одним из современных направлений развития методов классификации, обеспечивающий подстановку значений характеристик реализации в высказыва- ние вида «ЕСЛИ… И … ТО …» является математический аппарат деревьев ре- шений. Структурные методы. При структурном подходе к классификации объ- екты (прообразы) классов описываются не множеством характеристик, а структу- рой их элементов: каждый объект в таком представлении есть множество атомар- ных (или непроизводных) элементов, связанных определенными отношениями (соединенных между собой определенными способами). Это очень похоже на син- таксис (грамматику) естественных языков – любой объект может быть описан не- которым «предложением» формальной грамматики (существенно более простой относительно естественных языков). Процедура классификации образа сводится к синтаксическому разбору «предложения», его описывающего, с целью определения корректности с точки зрения формальной грамматики, что эквивалентно проверке возможности порож- дения такого предложения в рамках фиксированного подмножества формальной грамматики, описывающей некоторый класс (прообраз). NB! Методы формальной грамматики используются в языке описания изо- бражений (Picture Definition Language, PDL). Классификация по степени определенности результата. По данному ос- нованию выделяются вероятностные и детерминированные методы. К вероятностным относятся методы, основанные на оценке плотности распреде- ления значений признаков (рис. 5) и некоторые другие, основанные на методах классической параметрической статистики. Все прочие методы относятся к детерминированным, дающим однозначный ответ о принадлежности реализации. Тем не менее, некоторые из методов обес- печивают количественную оценку принятого решения, выражающуюся, к примеру, либо разностью расстояний до объектов различных классов, либо «степенью уве- 115 ренности» – количеством присутствия данной градации признака у объектов раз- личных классов. Вопросы для самопроверки: 1. В чем состоит гипотеза компактности? 2. Чем отличаются обучение с учителем и без учителя? 3. Что называется кластеризацией? 4. Когда используется термин таксономия? 5. Что называется признаками? 6. Приведите формализованную постановку задачи классификации? 7. Что такое признаковое пространство? 8. Что называется решающим правилом? 9. Приведите алгоритм типовой системы классификации. 10. Что называется разбиением? Покрытием? неполным покрытием? 11. Приведите классификацию методов распознавания по степени формализации решающих правил. 12. Приведите классификацию методов распознавания по используемому матема- тическому аппарату. 13. Как реализуются методы классификации, основанные на оценках плотностей распределения значений признаков? 14. Как реализуются логические методы классификации? 15. Перечислите методы оценивания информативности признаков 116 ЛЕКЦИЯ 13 ОЦЕНИВАНИЕ ИНФОРМАТИВНОСТИ ПРИЗНАКОВ Для оценки способности признаков разделять объекты, относящиеся к раз- личным классам существует множество методов. Перечислим некоторые из них: – метод сравнения расстояний; – метод накопленных частот; – энтропийный подход. Метод сравнения расстояний Метод сравнения расстояний основан на буквальном понимании гипотезы компактности признаковое пространство полагается тем более лучшим, чем больше среднее межклассовое расстояние и меньше среднее внутриклассовое. В формальном виде это описывается следующими выражениями: j i j i ) A , A ( J , где Ω k – средняя длина ребер графа, соединяющего все объекты k-го класса, оп- ределяется как ) a , a ( d C j m i m i j i m k 1 1 1 2 1 , где m – количество объектов в классе; С– количество сочетаний, d(a i , a j ) – рас- стояния между парами объектов класса. d(A i , A j ) – среднее расстояние между i-м и j-м классами: ) a , a ( d m m 1 ) A , A ( d jl m 1 k m i l ik j i j i i j |