Лекция (8)

Лекция 7:Задача классификации и деревьярешенийЗадачи классификацииПеременная отклика Y является категориальной – например,почтовое сообщение может принадлежать одному из следующихклассов C = (spam; ham) (ham = обычная почта), изображениецифры может принадлежать одному из классов C = {0, 1, …, 9}.Цель задачи: Построить классификатор C(X), который связывает меткукласса из множества C с неразмеченным образцом X. Оценка степени неточности для каждой классификации Понимание роли различных предикторов средиПример: Банкротство покредитным картамЗадача классификацииСуществует ли идеальная C(X)? Пусть K классов в множестве Cпронумерованы как 1, 2,…, K. ПустьЭто условные вероятности классов в точке x. Тогда оптимальныйклассификатор Байеса в точке x:Качество классиффикации:Задача классификации KNNТакже может быть использовано усреднение методомближайших соседей.Хотя такой подход плохо применим при возрастанииразмерности.Пример: KNN для двух измеренийМетоды БайесаВероятностная постановка задачи прогнозирования:В явном виде вычисляется вероятность для каждой гипотезы (вариантапрогноза), очень важно для многих задачВозможность дообучения:Каждый размеченный пример итеративно увеличивает/уменьшаетвероятность корректности гипотезы Априорные знания легко внедрить в модельВероятностный прогноз:Несколько вариантов гипотез с оценкой достоверностиДе факто - эталон:Даже когда методы Байеса вычислительно трудоемки, они могут бытьполезны в качестве разовой оценки для сравнения с более быстрымиметодами в плане оценки точности последнихТеорема БайесаТеореме Байеса:Если Z - тренировочный набор, то апостериорная вероятностьгипотезы h, P(h|Z) удовлетворяет соотношению:P(h | Z )  P(Z | h)P(h)P(Z )MAP (maximum posteriori) гипотезаh argmax P(h | Z )  argmax P(Z | h)P(h).MAP hHhH«Необходимые» оценки вероятностей:P(Z) – константа для всех классов P(h) - относительная частота класса в выборке Надо найти h такое, что P(h|Z) максимально = h такое, чтоP(Z|h)·P(h) максимальноПроблема:вычисление P(Z|h) на всех комбинациях переменныхвычислительно сложно или невозможноМетод Naïve БайесаNaïve упрощение:Атрибуты независимы: P(x1,…,xn|C) = P(x1|C)·…·P(xn|C)Оценка P(xi|C):Если атрибут категориальный, то относительная частота того, сколькопримеров с классом С имеют значение атрибута xi Если атрибут числовой, то по плотности распределения, например:где μk – это среднее, и 2 - дисперсия (в классе k). И так, и так считается быстроПредположение о независимостиДелает метод вычислительно эффективнымПриводит к оптимальному классификатору (если и правданезависимые атрибуты), но на практике почти всегда зависимыПопытки преодолеть эти ограничения:Байесовские сетиПример: построить модель прогнозавозможности поиграть в теннисOutlooksunnysunnyovercastrainrainrainovercastsunnysunnyrainsunnyovercastovercastrainTemperaturehothothotmildcoolcoolcoolmildcoolmildmildmildhotmildHumidityhighhighhighhighnormalnormalnormalhighnormalnormalnormalhighnormalhighP(p) = 9/14P(n) = 5/14WindyfalsetruefalsefalsefalsetruetruefalsefalsefalsetruetruefalsetrueClassNNPPPNPNPPPPPNoutlookP(sunny|p) = 2/9P(sunny|n) = 3/5P(overcast|p) = 4/9P(overcast|n) = 0P(rain|p) = 3/9P(rain|n) = 2/5temperatureP(hot|p) = 2/9P(hot|n) = 2/5P(mild|p) = 4/9P(mild|n) = 2/5P(cool|p) = 3/9P(cool|n) = 1/5humidityP(high|p) = 3/9P(high|n) = 4/5P(normal|p) = 6/9P(normal|n) = 2/5windyP(true|p) = 3/9P(true|n) = 3/5P(false|p) = 6/9P(false|n) = 2/5ПримерНовый пример:Расчет вероятностей:x = <rain, hot, high, false>P(x|p)·P(p) = P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p) =3/9·2/9·3/9·6/9·9/14 = 0.010582P(x|n)·P(n) = P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n) =2/5·2/5·4/5·2/5·5/14 = 0.018286Вывод:P(x|n)·P(n) > P(x|p)·P(p)Значит скорее всего не поигратьМетоды, основанные надеревьях решенийЭти методы используют стратификацию илисегментирование пространства признаков на области.Для сегментации пространства признаков можетиспользоваться набор правил, который можно представить ввиде дереваДеревья решений могут применяться как к задачам регрессии,так и к классификации.Методы, основанные на деревьях, просты в интерпретации, приэтом показывают достаточно хорошие результаты по точностипрогнозирования.Нестабильные модели – это плюс для ансамблей бэггинг,методы случайного леса и бустинг.

Эти методы строятмножество деревьев, результаты прогнозирования которыхпотом объединяются для получения итогового прогноза.Деревья решений в задачахклассификации и регрессииДерево решений - граф (древовидная структура), в котором:Внутренние узлы – условия на атрибутыКаждая исходящая ветка соответствует выходному значениюусловия, ветка целиком – альтернативное решениеВ листьях метки классов (или распределение меток классов) илизначения целевой переменной для регрессииКаждому узлу соответсвует область в пространсве признаков RОбласти для листьев – финальные, не содержат внутри другихобластейПостроение дерева обычно – 2 фазыПостроение: в начале в корне все примеры, далее рекурсивноеразбиение множества примеров по выбранному атрибуту «отсечение» ветвей pruning - выявление и удаление ветвей(решений), приводящих к шуму или к выбросамПрименение дерева решений для нового объектаПроверка атрибутов – путь по ветви до листа.

В листе отклик.Пример: категориальный отклик1008060X140200999999999999 91999999991999999999911199911111119999999999999999 9999999 91 999999991999999999999999191999999999999999999999 9999999 9999999119199999999999999999999999991999999 919 99999999999999999999 999 999 9999 1999 991999999919999999 1999999999991199999 99 9991991 99711 19 9 991991 99 9 99 9 9 99119 9717 1 1 119919 911979997711111171111111111111 1191 71 97 7717999711111771 1997 7 7 77777171171111117711 1 1 111119 9779719777177771771 117 111111 717771779777771 7771777779917111111177717117771711111717791771111177111917777119717717717117111171111717777777777117971717171911111777711119199171197111777777171771111 11 11199719020406080100X10Пример: непрерывный отклик50MEDV35205.9.7NOX.5.3 357RM9Проекция непрерывного отклика напространство признаков.9NOX.8.7.6.5.4.3RM3456789Дерево решений для классификацииX1<38.5yesnoX10<.5X10<51.5X10<40.57 (96%)1 (78%)X1<.5X10<17.57 (91%)9 (99%)X1<.51 (95%)1 (80%)X10<71.5X10<611 (56%)1 (64%)7(73%)9 (87%)Множественные разбияния (небинарное дерево)X10<11-41X17 (96%)<1X101-651 (94%)1 (79%)669 (75%)<2223-327 (84%)1 (70%)52X142-51337 (66%)<11 (82%)1-267 (61%)279 (99%)Дерево решений для регрессииRM<6.9NOX<.67RM<6.5NOX<.5119RM<7.41427NOX<.6322NOX<.6627331646Листья = Логические правилаIf RM  {values} and NOX  {values}, then MEDV=value.LeafRMNOXPredicted MEDV1<6.5<.51222<6.5[.51, .63)193<6.5[.63, .67)274[6.5, 6.9)<.67275<6.9.67146[6.9, 7.4)<.663377.4<.664686.9.6616Разбиение пространствапризнаков на области.9NOX.81416.727.619.527 334622.4.3RM3456789Многомерная ступенчатая функцияMEDV5035205.9.7NOX.5.3735RM9Регионы решений дляклассификации100801960X14020 7017019120714060X1080100Листья дерева решений дляклассификацииLeafPr(1|x)Pr(7|x)Pr(9|x)Decision1.03.96.0172.09.91.0073.56.44.0014.95.05.0015.80.10.1016.64.09.2717.00.13.8798.10.73.1779.78.01.21110.01.00.999Процесс построения деревьеврешенийРазделяем пространство признаков (то есть, набор возможныхзначений для X1, X2,…,Xp ) в J отдельных и непересекающихсяобластей R1,R2,…,RJ.

Таким образом, чтобы поведение откликав каждой области было «однородным».Теоретически, области могут иметь любую форму. Тем неменее, чаще всего используются многомерные прямоугольникидля простоты и удобства интерпретации полученной модели.Цель состоит в том, чтобы найти прямоугольные области R1,...,RJ, так чтобы минимизировать некий целевой критерий –критерий разбиения.Процесс построения деревьеврешенийВычислительно нецелесообразно рассматривать всевозможные разбиения пространства признаков в J областей.По этой причине используется нисходящий, жадный подход,известный как рекурсивное разделение.Подход называется нисходящий, потому что он начинается вверхней части дерева, а затем последовательно разбиваетпространство признаков; каждое разбиение приводит кобразованию новых ветвей, расположенных ниже по дереву.Подход называется жадным, потому что на каждом этапепроцесса построения деревьев лучшее разбиениеосуществляется на конкретном шаге, вместо того, чтобыпросматривать дальше и выбирать разбиение, котороеприведет к лучшему дереву в дальнейшем.Процесс построения деревьеврешенийСначала выбирается переменная Xj и точка разбиения s, такчто разбиение пространства признаков на области {X|Xj < s} и{X|Xj >= s} приводит к максимально возможному улучшениюкритерия (для бинарного дерева).Затем повторяется этот процесс и ищется лучшая переменнаяи точка разбиения в каждой из результирующих областей.Однако на этот раз, вместо разделения всего пространствапризнаков, мы разделяем одну из ранее выделенных областей.Процесс продолжается до тех пор, пока не будет достигнуткритерий останова; например, мы можем продолжать процессдо тех пор, пока не останется областей, содержащих более пятинаблюдений.Шаг разбиения узлаD1 = 364D7 = 364D9 = 336n = 1064yesD1 = 293D7 = 363D9 = 42n = 698X1<38.5noD1 = 71D7 = 1D9 = 294n = 366Разбиение деревом глубины 11008060X1402009 91999999999999999999999911999 91111119 9991119911999999999999999999 999 99 99999 919199999999999999999999999999 99 999 99 9911 91999 99999 999 99999999991 9199999999999 9999 9999911999999 999999 9999 999999999999199999999999999 1 9 9 9999999999999999 1919999999991199 9 999999 99 917119 991 99199911 99 9 9 9 9 91919 9971 1 1 11799 919911799977711111111111911 71 97 77111111971997111111117771 19911177777117711177717111971 1 1 11111 9 977977 777777771177771 71 11 7 111111 717 7977797777971 77717711111117711177171117771111171911911717119171771177771771117719171717177777717171711111119797791717771 11711119119771171777177717777777111111 1 1 1119171777911711190204060X1080100Глубина 2RootD1 = 293D7 = 363D9 = 42n = 698yesD1 = 8D7 = 220D9 = 1n = 229X10<0.5D1 = 71D7 = 1D9 = 294n = 366noD1 = 285D7 = 143D9 = 41n = 469yesD1 = 67D7 = 1D9 = 18n = 86X10<51.5noD1 = 4D7 = 0D9 = 276n = 280Разбиение деревом глубины 2100199999999 91999999999999999999119999919111111199999199999999999999999 91 99999999199999999999999999999191999999999999999999 9999999 999998011919999999999999999999 99999999119999999 9999999999999999999919999999 999999 1 99 999999991996099999 199999999999991999991199X199919711 199 9 9919919409 9 99 9 9 99911197171 119919919179997111117171111997 71 11111111 11119120 1779977111 1171997 7 7 7777717117117111711119 97797111 1 11111977777777171111 719777117777971 77711117777779177111111177111770 71777777717711777171917197111117171711777177111719177111171797171717111111197991117771117111179797711717771111 11 111917777777179111119020406080100X10Финальное разбиение1008060X1402009999999999 9199999999999999991119999991111111999991999999999999999 9999999 91 99999999199999999999191999999999999999999999 9999999 9999999119199999999999999999999999991999999 919 99999999999999999999 999 999 9999 1999 991999999919999999 1999999999991199999 99 9991991 99711 19 9 991991 99 9 99 9 9 99119 9717 1 1 119919911979997711111171111111111111 1191 71 97 7717999711111771 1997 7 7 77777171171111117711 1 1 111117711 9 9 9977 77777771711171977117111111111777777971 777177779177711171771177119717791771111117119177777177177171171111711117177777711117777777179717171711111777711119791997711771711911977111177171111 11 111979117020406080100X10РассмотримПоискразбиения попеременнымОрдинальнымКатегориальнымМножественныеразбиенияКритерии разбиенияУменьшениеразнородностиХи2 тестРегрессионныедеревьяПропущенные значенияVariableX10X10X10X1X1...Values0.51.811, 462.41, 4, 61...Разбиение по ординальнойпеременнойSplits1—23412—34123—4 3  3 1 1—2—341—23—412—3—4 3  3 2 1—2—3—4 3   1 3  L 1( L  1)! B  1  ( B  1)! ( L  B )! L  1L 121l 2  l  1 LОрдинальные переменныеX.201.73.33.5142515ln(X)–1.6.531.21.32.67.8123456rank(X)Потенциальные точки разбиенияРазбиение категориальнойпеременной1—2342—1343—1244—12312—3413—2414—231—2—341—3—241—4—232—3—142—4—133—4—121—2—3—4S( L, B)  B  S( L  1, B)  S( L  1, B  1)LB:23456789234total11314761141525105131906520263 301 350876127 966 1701 4139255 3025 7770 21146Основные моменты поискаразбиенияТолькобинарное разбиениеординальные = L  1категориальные = 2L  1  1АгломеративнаякластеризацияВариантов разбиенияKass (1980)Минимальныйразмер листаМножественное или бинарное1253123454Кластеризация гипотезКритерии разбиения длякатегороиального откликаX1:<38.5 38.512937173631942294Gini entropy logworth.197.504140.255.600172X10: <0.5 1-41 42-51 51.5191436514772218815491416315Уменьшение разнородностиParentimpurity0n0Child1impurity1n1Child2impurity2n2Child3impurity3n3Child4impurity4n4 n1n3n2n4i  i(0)   i(1)  i(2)  i(3)  i(4) n0n0n0 n0Индекс Джиниr1   p2j  2 p j pkj 1jkВысокая вариация, низкая чистотаPr(interspecific encounter) = 1-2(3/8)2-2(1/8)2 = .69Низкая вариация, высокая чистотаPr(interspecific encounter) = 1-(6/7)2-(1/7)2 = .24ЭнтропияH  p1 , p2 ,r, pr    pi log 2  pi i 11.0r20.52 p1 1  p1 0.00.00.5p11.0Хи2 тестНаблюдаемыечастотыОжидаемые(по гипотезе)O  E 2X1: <38.538.5E129371.342239 125122373631.342239 12564123942294 .316225 116149 273.656 .344 n=1064  2O  E 2E 644  (3  1)(2  1)  2Корректировка p-ValueX1: 38.51 293 717 363 19 42 294X1: 17.5 36.51 249 42 737 338 25 19 26 16 294X10: 0.5 41.5 51.51 9 143 65 1477 221 88 1 549 14 16 3152 log10 (P)m log10 (mP)644214096138660414145601378146172 156849 167Пропущенные значения1,2,3,?12,3,?1,2,3,?11,2,3,?1,?2,33,?131,??321,2,3,?31,2,3,?11,2,3,?1,2,32,?1,2,3,?1,2,3,?1,2,?3,?1,2,3,?1,2,3,?1,222,3?1,2,3,?1,23?123?Суррогатные разбиенияУровень согласия=76%NoX1<38.5Yes19 919999999999999999999911999 9111119 9991991911199999999999999999999 91 999 999 99 9999919999999999999999999999 99 999 99 9911 91999 99999 999 9999991 9199999999999999999999 99119999999 99 999 9999999999999999999199999999999 1 9 9 99999 99999 99999999 191999999999911999 9 9 999 99 911 9912 354711991911 99 99 9 9 99 9 91919 9971 1 1 11799 919 2449454117999777711111111111911 71 97 771111119719971111111117771 19911777771177111777711119111 9 977977 77777111 1 1177717177771 7 11 7 111111 717 7977797777971 7771777111111171117717717117779117777111711711711777177171717711111797111717171111117991117771 1171111717971199711771977717111111 1 1 1119119177777171117117777777717911119YesX10 < 41.5NoВажность переменных12Gini( s( x2 ,2))Gini( s( x3 ,2))Gini( s( x1 ,2))Gini( s( x1 ,1))Gini( s( x3 ,1))Gini( s( x2 ,1))3Gini( s( x2 ,3))Gini( s( x1 ,3))Gini( s( x3 ,3))Непрерывный откликПлотностьNOXRM025MEDV50Уменьшение вариацииParenti(0)n0Child1i(1)n1Child2i(2)n2Child3i(3)n3Child4i(4)n4 n1n3n2n4i  i(0)   i(1)  i(2)  i(3)  i(4) n0n0n0 n0Уменьшение вариацииn  506y  23€  9.2yesn  430y  20€  6.3RM<6.94non  76y  37€  8.9One-Way ANOVAny SStotal SSbetween   n  B F ~ FB 1, n  B SSwithin   B  1 Bn1y1 SS1nBn2y2  ...