Интеллектуальный анализ данных учебное пособие. ИАД Лекции Замятин 20. Интеллектуальный анализ данных
 Скачать 2.95 Mb.
|
|
6.3.4. Классификация по методу машины опорных векторов Основная идеяметода машины опорных векторов (SVM класси- фикатора) – отображение исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с мак- симальным зазором в этом пространстве [37]. Суть работы стандартного классификатора SVM для случая двух классов можно представить с использованием следующего выражения: f(x, W) = sign(g(x, W)), где g(x, W) = < x, W > + b, (6.23) где параметры W (вектор весов) и b (свободный коэффициент) определяются процедурой обучения. Границы решения классифи- катора g(x,W)= 0представляют собой гиперплоскость порядка L – 1 6. Основные методы анализа и интерпретации данных 71 в L-мерном пространстве (рис. 15). Для определения параметров W и b решается задача квадратичной оптимизации: 1 ( ) min 2 1 1 1 0 C 1 0 1 i i j i j i j λ i i i L λ λ λ λ y y x ,x i i j λ ,i ,..., λ y i , (6.24) где y – вектор меток классов пикселей обучающих выборок y i = {1; –1}; C – управляющая константа метода решения задачи; – размер обучающих выборок. Для ее решения применяют последователь- ный метод активных ограничений (англ. incremental active set method, INCAS) [17]. Решение этой задачи позволяет найти вектор двойственных переменных λ = (λ 1 , …, λ n ), что, в свою очередь поз- воляет вычислить параметры алгоритма W и b как 1 , 0 1 i i i i i i i λ y x ;b ,x y λ ,i ... W W , (6.25) x 1 x 2 Рис. 15. Иллюстрация работы классификатора SVM для двумерного пространства Интеллектуальный анализ данных 72 Решение задачи классификации для случая нескольких классов может быть реализовано путем множественной попарной класси- фикации и объединения результатов (например, по мажоритарному правилу) [37]. Классификатор SVM отличается достаточно высокой алгоритмической сложностью, но при этом обладает высокой вы- числительной эффективностью. Кроме того, его отличают высокие точность и робастность результатов при различных статистических характеристиках обучающих данных. 6.3.5. Деревья решений Деревья принятий решений (деревья решений, англ. decision trees) – еще один распространенный метод контролируемой клас- сификации, позволяющий обеспечивать поддержку принятия ре- шений. В основе этого метода классификации лежит использова- ние ориентированного 1 дерева как связного ациклического графа 2 (рис. 16). Дерево решений имеет одну вершину (корень), а завершается вершинами с нулевой степенью исхода (из них не исходит ни одна дуга) – листьями. При этом принято, что дерево решений растет вниз (а не вверх, как настоящее дерево). Кроме того, дерево решений имеет различные метки: – узлы (вершины, не являющиеся листьями) – переменные набора данных; – на дугах (ветвях) отмечают атрибуты (значения перемен- ных), от которых зависит целевая функция; – в листьях отмечают значения целевой функции. Если все узлы дерева имеют по две дуги, то такое дерево назы- вают бинарным. 1 Только одна вершина имеет степень захода 0 (в нее не ведут дуги – корень дерева), а все остальные вершины имеют степень захода 1 (в них ведет только по одной дуге). 2 Связность – наличие путей между любой парой вершин, ацикличность – отсут- ствие циклов и наличие между парами вершин единственного пути. 6. Основные методы анализа и интерпретации данных 73 Рис. 16. Пример ориентированного дерева Узел Лист Лист Узел Лист Узел Лист Лист Родительский узел (предок) Дочерние узлы (потомки) Корневой узел Возраст > 40 Выдать кредит Высшее … Образование Имеется дом Доход > 5 000 Отказать Выдать кредит Нет Да Н ет Д а Нет Да Среднее … Специальное … Интеллектуальный анализ данных 74 Область применения деревьев решений обширна (в банковском деле –при оценке кредитоспособности клиентов, в промышленно- сти – при контроле качества, в медицине – при диагностике заболе- ваний и т.п.) и может быть разделена на три класса: – Описание данных (деревья не только позволяют сохранять ин- формацию об исходных данных в компактной форме, но и могут быть логически интерпретируемыми). – Классификация (возможна в случае дискретных значений це- левой переменной). – Регрессия (если целевая переменная имеет непрерывные зна- чения, может быть установлена ее зависимость от независимых входных переменных, например в задаче численного прогнозиро- вания). Построение дерева. Пусть имеется обучающая выборка приме- ровT = {x i , f(x i ) =ɷ i }, где x i – переменные, каждой из которых соответствуют некоторый набор атрибутов (атрибут – условие пе- ремещения по дуге) Q i = {Q j , j = 1, …, q}, а ɷ i – классы, которым принадлежат переменные. Если переменная, которая проверяется в узле, принимает катего- риальные значения, то каждому возможному значению соответствует ветвь, выходящая из узла дерева. Если значением переменной явля- ется число, то проверяется – больше или меньше это значение неко- торой константы. Иногда область числовых значений разбивают на интервалы и выполняют проверку попадания значения в один из интервалов. Для классификации методом дерева решений следует разбить множество T на некоторые подмножества. Для этого выбирается один из признаков x, имеющий два и более отличных друг от друга значений x 1 , x 2 , ..., x n . T разбивается на подмножества T 1 , T 2 , ..., T n , где каждое подмножество T i содержит все примеры, имеющие зна- чение f(x = x i ) для выбранного признака. Эта процедура будет ре- курсивно продолжаться до тех пор, пока конечное множество не бу- дет состоять из примеров, относящихся к одному и тому же классу. Фиксируя эти преобразования в виде элементов дерева решений, будет выполнено его построение сверху вниз. 6. Основные методы анализа и интерпретации данных 75 Другими словами, построение дерева решений по известным обучающим данным с использованием указанных обозначений вы- глядит следующим образом: 1. Выбрать переменную x i , поместив ее в корень дерева (x i имеет n значений, что позволяет разбить T на n подмножеств). 2. Далее создается n потомков корня, каждому из которых по- ставлено в соответствие свое подмножество, полученное при разби- ении T. 3. Повторять рекурсивно для всех i шаги 1 и 2, пока: – в вершине не окажутся примеры из одного класса (тогда она становится листом, а класс, которому принадлежат ее примеры, бу- дет решением листа); – вершина оказалась ассоциированной с пустым множеством (тогда она становится листом, а в качестве решения выбирается наиболее часто встречающийся класс у непосредственного предка этой вершины). Такой процесс построения дерева «сверху вниз» является приме- ром наиболее распространенного поглощающего «жадного» алго- ритма. Рассмотрим конкретный пример построения дерева решений для некоторого набора данных. Предположим, нам известна некоторая статистика игры фут- больной команды, а мы на ее основе хотим предсказать исход сле- дующего матча (табл. 6). Т а б л и ц а 6 Статистика игр футбольной команды x 1 x 2 x 3 x 4 f(x) Соперник по турнирной таблице Место проведения Наличие лидеров команды Погодные условия Результат Выше Дома На месте Осадки Поражение Выше Дома На месте Без осадков Победа Выше Дома Пропускают Без осадков Победа Ниже Дома Пропускают Без осадков Победа Ниже В гостях Пропускают Без осадков Поражение Ниже Дома Пропускают Осадки Победа Выше В гостях На месте Осадки Поражение Ниже В гостях На месте Без осадков ? Интеллектуальный анализ данных 76 Построим дерево решений, выбрав в качестве корневого узла пе- ременную x 1 , а остальные атрибуты выберем по порядку упомина- ния в табл. 6 (рис. 17). Очевидно, чем меньше глубина 1 построен- ного дерева, чем меньше в нем количество узлов и ветвей, тем им легче оперировать на практике. Рис. 17. Пример дерева решения с корнем x 1 1 Максимальный уровень листа дерева – длина самого длинного пути от корня к листу. Матч проходит Соперник в турнирной таблице Матч проходит Лидеры команд Идет дождь Ниже Выше 1 0 Дома В гостях 0 Дома В гостях 1 0 1 Да Нет На месте Пропускают матч 6. Основные методы анализа и интерпретации данных 77 Теперь построим аналогичное дерево решений, но порядок появ- ления узлов зададим иначе (рис. 18). Рис. 18. Пример дерева решения с корнем x 4 Очевидно, полученное дерево (см. рис. 18) существенно проще, а его глубина в два раза меньше, чем дерева на рис. 17. При этом оно позволяет решать ту же задачу прогнозирования результатов матча по известным параметрам. Это означает, что аналогичное де- рево решений может быть построено для одних и тех же исходных данных различными способами, выбирая очередность для той или иной переменной x i и ее атрибутов. Поэтому именно критерий выбора очередной переменной при построении дерева решений отличает наиболее распространенные алгоритмы построения деревьев решений: – Алгоритм ID3: выбор атрибута происходит на основании при- роста информации (англ. Gain) либо на основании индекса Джини (англ. Gini). – Алгоритм C4.5: модифицированная версия алгоритма ID3, выбор атрибута происходит на основании нормализованного приро- ста информации (англ. Gain Ratio). – Алгоритм CART: для бинарных деревьев, выбор атрибута зависит от отношений числа примеров в правом и левом потомке к общему числу примеров. Соперник в турнирной таблице Идет дождь Матч проходит Да Нет Ниже Выше Дома 1 0 0 1 В гостях Интеллектуальный анализ данных 78 Следует отметить, что задача построения наилучшего, опти- мального дерева не может быть решена данными методами и тре- бует построения всех возможных вариантов деревьев решений и полного их перебора (т.е. является NP-полной) [22]. Достоинства и недостатки. Использование деревьев решений в сравнении с другими распространенными методами классифика- ции, прогнозирования или регрессионного анализа имеет несколько существенных достоинств: – Не требуется предварительной обработки данных. Напри- мер, не нужны нормализация, добавление фиктивных переменных, удаление пропущенных данных. Метод способен работать как с ка- тегориальными, так и с интервальными переменными. – Имеется возможность интуитивного понимания и интер- претации. Правила передвижения по узлам деревьев могут иметь четкую логику («белый ящик») и могут быть формализованы даже там, где это затруднительно сделать эксперту. Отметим, что нейросеть такой возможности пользователю, как правило, не предо- ставляет («черный ящик»). – Высокие надежность и точность. Сравнительно высокие надежность и точность модели могут быть статистически оценены. Отсутствие априорных предположений о законах распределения данных относит их к непараметрическим, устойчивым к данным различных априори неизвестных законов распределения. – Высокая вычислительная эффективность. Метод отличает быстрый процесс обучения (построения дерева), а также высокая вычислительная эффективность обработки значительных объемов данных за счет простоты структуры данных дерева решений. Вместе с важными достоинствами метода отмечают и его недо- статки: – Проблематичность построения оптимального дерева реше- ний. Построение и поиск такого дерева решений является NP-полной задачей, сложно разрешимой на практике. Поэтому практическое построение деревьев решений связано с применением эвристиче- ских «жадных» алгоритмов, оптимальных только в каждом узле де- рева, но неоптимальных для дерева в целом. При этом требуется 6. Основные методы анализа и интерпретации данных 79 обеспечить непростой баланс между точностью и сложностью дерева, уделять внимание опасности переобучения, для чего приме- нять дополнительные алгоритмы регулирования глубины или упро- щения дерева (англ. pruning, reduction). – Вероятность построения избыточно сложного дерева. Воз- можны случаи, при которых применение традиционных алгоритмов построения дерева решений приведет к описанию модели «слож- ным» путем и непомерно большому дереву (например, когда число возможных атрибутов велико, а не просто «да» / «нет») [21]. В этом случае потребуются дополнительная проработка постановки задачи и формирование иных суждений о предметной области. – Вероятность ошибок при построении дерева. Ключевым эле- ментом алгоритма построения дерева является порядок выбора оче- редной переменной при построении очередного узла. В случае, если набор исходных данных включает категориальные переменные, больший информационный вес априори присваивается тем пере- менным, которые имеют большее количество уровней [95]. Таким образом, метод с использованием деревьев решений наиболее эффективно может быть применен для задач с дискрет- ными (категориальными) значениями с четким набором отличных атрибутов, а также в тех случаях, где важно понимать логику полу- чения и интерпретации результатов. Примеры алгоритмов. Выше изложены базовые принципы по- строения деревьев решений, на которых основано подавляющее большинство применяемых на практике алгоритмов. Основное от- личие таких алгоритмов друг от друга заключается в способах опре- деления очередности для той или иной переменной и ее атрибутов при построении очередного узла дерева. Очевидно, наиболее удачным будет считаться атрибут, который позволит получить такие подмножества данных, которые будут при- надлежать в подавляющем большинстве элементов к одному классу. Алгоритм ID3. Алгоритм ID3 (англ.Iterative Dichotomizer,ите- ративный дихотомайзер), предложенный Д. Куинланом, определяет очередность переменной и ее атрибутов через их информационную значимость (информационную энтропию) [30]. Для этого следует Интеллектуальный анализ данных 80 найти энтропию всех неиспользованных признаков и их атрибутов относительно тестовых экземпляров и выбрать тот, для которого эн- тропия минимальна (а информативность – максимальна). Энтропию при условии неравновероятных событий p i находят по известной формуле Шеннона: 𝐼 = − ∑ 𝑝 𝑖 𝑙𝑜𝑔 2 𝑝 𝑖 𝑖 , (6.26) где I – количество информации в битах,которую можно передать, используя m элементов в сообщении при n буквах в алфавите, при- чем p i = m/n. В случае с деревом решений m – число значений целевой функ- ции f(x i ) для x i (поэтому корректнее использовать запись m i ), n – об- щее число элементов (записей) исходного набора (множества Т). Тогда энтропия множества Tпо отношению к свойству S= f(x i ), ко- торое может принимать s значений,может быть найдена как H (T, S) = − ∑ 𝑚 𝑖 𝑛 log 2 𝑚 𝑖 𝑛 𝑠 𝑖=1 . (6.27) Если свойство S бинарное(т.е. целевая функция f(x i ) может при- нимать только два значения), то запись для энтропии будет выгля- деть так: H (T, S) = − 𝑚 𝑛 log 2 𝑚 𝑛 − 𝑛−𝑚 𝑛 log 2 𝑛−𝑚 𝑛 . (6.28) В этом случае, если вероятность появления S равна 0,5 (т.е. рав- новероятно), то энтропия равна 1 (т.е. нужен 1 бит информации для ее кодирования). Если же появление S не будет равновероятно, то энтропия будет меньше, а значит закодировать информацию из T именно для такого S = f(x i ) будет более эффективно. Этот пример показывает, что выбор признака x i следует осуществлять так, чтобы соответствующая ему энтропия стала минимально возможной. В общем случае энтропия будет различной для различных по- томков узла, поэтому итоговый результат нужно считать с учетом того, сколько исходов осталось в рассмотрении в каждом из потом- ков. Например, если множество T со свойством S = f(x i ) классифи- цировано признаком x i c атрибутом Q, имеющим q возможных зна- чений, то прирост информации определяется как Gain(T, S) = H (T, S) – ∑ |𝑇 𝑘 | |𝑇| 𝑞 𝑘=1 H(T k , S), (6.29) 6. Основные методы анализа и интерпретации данных 81 или, используя более обобщенную запись имеем выражение: Gain(T, S) = Info(T) – Info S (T), (6.30) где T k – множество элементов T, для которых атрибут Q имеет зна- чение k. На каждом шаге алгоритм выбирает тот атрибут Q, для ко- торого это прирост информации максимален. Результат разницы в выражении (6.30) может быть найден в этом алгоритме альтернативно с использованием индекса Джини, упомя- нутого выше. Рис. 19. Иллюстрация зависимости двух переменных Info(T) и Info S (T) и кривой Лоренца, используемых в расчете индекса Джини Индекс Джини начали применять для оценки неравномерности распределения некоторого изучаемого признака (например, годо- вого дохода) для различных социальных групп и широко исполь- зуют в экономических, социальных и демографических исследова- ниях [5]. В алгоритме ID3 для его расчета применяется зависимость двух величин (например, Info(T) и Info S (T)), упорядоченных по воз- растанию и обычно нормированных в процентах (рис. 19). Индекс Джини численно равен площади под кривой Лоренца, которая мо- жет принимать значения от 0 до 1. 0 20 40 60 80 100 120 0 20 40 60 80 100 Со во ку пн ы й до хо д, % Население, % |