Интеллектуальный анализ данных учебное пособие. ИАД Лекции Замятин 20. Интеллектуальный анализ данных
 Скачать 2.95 Mb.
|
|
Алгоритм С4.5. Алгоритм С 4.5 также предложен Д. Куинла- ном в развитие алгоритма ID3 и расширяет его возможности в ча- сти [5]: – дополнительной функциональности по отсечению ветвей во избежание проблемы переобучения; – построения дерева из обучающей выборки с пропусками дан- ных (отсутствуют значения для некоторых атрибутов); – работы не только с дискретными, но и с непрерывными чис- ловыми атрибутами. Основной недостаток алгоритма ID3 – склонность к переобуче- нию. Действительно, при большом количестве возможных значе- ний признака (возможно, несущественно отличающихся друг от друга) будет построено большое число ветвей с атрибутами этого признака. В крайнем случае число листьев такого дерева может быть эквивалентно числу имеющихся примеров обучающего мно- жества. Очевидно, для задач классификации такое дерево решений будет бесполезным. Более того, поиск верного признака x i при по- строении следующего узла в таком дереве также проблематичен – в (6.27) log 2 (1) = 0, поэтому в (6.30) прирост информации для всех x i максимален. Во избежание указанных проблем в алгоритме предусмотрено нормирование при расчете прироста информации путем расчета до- полнительного показателя с оценкой потенциальной информации, созданной при разбиении множества T на n подмножеств T i : Split_Info(T) = – ∑ [ |𝑇 𝑘 | |𝑇| log 2 ( |𝑇 𝑘 | |𝑇| )] 𝑛 𝑘=1 (6.31) Критерий прироста информации (6.30) с использованием выра- жения (6.32) модифицирован следующим образом: Split_Info(S)= Gain (T,𝑆) Split Info(T) (6.32) С учетом того, что способ расчета критерия прироста информа- ции (6.32) учитывает не только прирост, но и оценку ее потенциаль- ной информативности («полезности»), это способствует выбору более удачного атрибута, построению менее избыточного дерева решений и улучшению классификации. 6. Основные методы анализа и интерпретации данных 83 Еще одной отличительной особенностью алгоритма С4.5 по от- ношению к ID3 является наличие адаптации к присутствию пропус- ков данных в исходном обучающем множестве. Вообще проблема пропусков в данных является для практики очень важной, для ее решения на этапе предварительной обработки данных применяют различные приемы и технологии (см. разд. 6.1), позволяющие представить данные для обработки методами Data Mining без столь очевидных недостатков. Тем не менее для полноты представления алгоритма отметим суть вышеуказанной особенности работы с пропусками в данных. В алгоритме С4.5 предполагается, что экземпляры обучающего множества с неизвестными значениями имеют статистическое рас- пределение соответствующего признака согласно относительной частоте появления известных значений. Для фиксации этой харак- теристики введен параметр F, который представляет собой число наблюдений в наборе исходных данных с известным значением данного признака, отнесенное к общему числу наблюдений. Тогда модифицированный для работы с пропущенными значениями кри- терий прироста информации будет иметь вид: Gain(S) = F × [Info(T) – Info S (T)]. (6.33) Алгоритм CART. CART (англ. Classification and Regression Tree, дерево классификации и регрессии), предложенный в 1984 г., пред- назначен для построения бинарного дерева решений (каждый узел имеет только две ветви-потомка) [10]. Основными отличиями алгоритма CART от алгоритмов семей- ства ID3 являются: – бинарное представление дерева решений; – функция оценки качества разбиения; – механизм отсечения дерева; – алгоритм обработки пропущенных значений; – возможность построения деревьев регрессии. На каждом шаге построения дерева правило, формируемое в узле, делит заданное множество примеров на две части, в которых выполняется (первая часть) и не выполняется (вторая часть) реша- ющее правило. При этом производится перебор всех признаков, Интеллектуальный анализ данных 84 на основе которых может быть построено разбиение, и выбирается тот, который максимизирует значение некоторого показателя. Например, таким показателем может быть H(T) = 2 𝑃 𝐿 𝑃 𝑅 ∑ [𝑃 𝐿 ( 𝑗 ) − 𝑃 𝑅 ( 𝑗 )] 𝑞 𝑗=1 , (6.34) где P L и P R – отношение числа примеров в левом и правом потомках к их общему числу в обучающем множестве T, 𝑃 𝐿 ( 𝑗 ) и 𝑃 𝑅 ( 𝑗 ) – отношение числа примеров класса 𝑖 в левом и правом потомках соответственно к их общему числу в каждом из них. Также в качестве такого показателя применяют выражение, основанное на использовании индекса Джини. Если множество Т содержит данные n классов, тогда индекс Джини определяется как Gini(T) = 1 – ∑ 𝑝 𝑖 2 𝑛 𝑖=1 , (6.35) где p i – вероятность (относительная частота) класса 𝑖 в T. Для узла бинарного дерева с двумя ветвями-потомками после ряда преобра- зований и упрощений показатель «успешности» разбиения множе- ства рассчитывается как 𝐺 split = 1 𝐿 ∑ 𝑙 𝑖 2 𝑛 𝑖=1 + 1 𝑅 ∑ 𝑟 𝑖 2 𝑛 𝑖=1 , (6.36) где L, R – число примеров соответственно в левом и правом по- томке, l i и r i – число экземпляров 𝑖 -го класса в левом и правом потомке. Лучшим будет то разбиение, для которого величина G split будет максимальной. Алгоритм CART предусматривает построение не только класси- фикационных деревьев, но и регрессионных. Для этого процесс реализуется аналогично, но вместо меток классов в листьях будут располагаться числовые значения. 6.4. Неконтролируемая классификация (кластеризация) Любой способ кластеризации требует максимизации межклассо- вых расстояний и минимизации внутриклассовых расстояний. Вы- деляют целый ряд способов кластеризации, различающихся крите- рием построения кластеров. Критериями могут быть: – связность; – центроидность; 6. Основные методы анализа и интерпретации данных 85 – распределения; – плотность; – прочие. Неконтролируемая классификация (англ. clustering, кластериза- ция) позволяет разбить исходный набор данных на конечное коли- чество однородных в некотором смысле кластеров. Неконтролиру- емая классификация реализуется методами кластерного анализа и позволяет выявлять свойства данных группироваться около некото- рых значений (центров). В общем концепцию кластерного анализа многомерных данных можно определить как распределение всех возможных точек (объектов) P-мерного пространства признаков по соответствующим кластерам [70], т.е. разбиение пространства при- знаков на взаимно непересекающиеся области, каждая из которых соответствует некоторому кластеру С i с центром μ 𝑖 ′ (i = 1, …, M'). При этом объекты одного кластера группируются в признаковом пространстве компактно, т.е. расстояние между объектами одного кластера меньше, чем расстояние между объектами различных кла- стеров. Среди методов кластерного анализа можно выделить такие, как методы итерационной оптимизации (англ. Iterative Self Organizing Data Analysis Technique, ISODATA метод) [50], методы иерархиче- ской кластеризации [70], анализ пиков гистограмм [103]. Метод ISODATA осуществляет итерационную оценку струк- туры исходных многомерных данных. На каждой итерации опре- деляется новое уточненное пространство кластеров С i и их цен- тров μ 𝑖 ′ (рис. 20, б, в), исходя из условия минимума расстояния между точками и центрами каждого кластера. Для этого на каждом шаге определяются ближайшие к центрам кластеров элементы изображения и вычисляются новые центры, также осуществляется слияние близких кластеров на основе заданных критериев. В каче- стве совокупного критерия точности кластеризации метод ISODATA использует суммарную квадратичную ошибку S, опреде- ляемую как ' 1 ,μ i M ii i x C S d x (6.37) Интеллектуальный анализ данных 86 x 2 x 1 C2 C1 C3 C4 C5 C5 C4 C3 C2 C1 C5 C4 C3 C1 C2 x 2 x 1 x 2 x 1 а x 2 x 1 C2 C1 C3 C4 C5 C5 C4 C3 C2 C1 C5 C4 C3 C1 C2 x 2 x 1 x 2 x 1 б в Рис. 20. Иллюстрация процедуры кластерного анализа (итерационный метод ISODATA): а – начальное размещение центров; б – первая итерация; в – вторая итерация Таким образом, качество кластеризации будет наилучшим при наименьшем значении S, т.е. при минимальном значении суммы расстояний от всех точек кластеров C i до их центров µ' i (i = 1, …, M). Критерием останова итерационного процесса кластеризации мето- дом ISODATA является заданное количество итераций и порог 6. Основные методы анализа и интерпретации данных 87 суммарной квадратичной ошибки S (6.37). При этом в качестве меры близости между точками кластера C i и его центром µ' i могут быть использованы L1 или Евклидова метрика расстояния. L1 – рас- стояние между P-мерными вектором x и центром µ' i – определяется выражением: 1 1 ( ,μ ) μ P L i iv d x x , (6.38) а Евклидово расстояние – выражением: 2 1 ( ,μ ) ( μ ) P E i i iv d x x , (6.39) Отмечают, что метрика (6.39) более предпочтительна по крите- рию точности по сравнению с метрикой (6.38), поэтому ее исполь- зование при кластеризации более целесообразно. Алгоритм k-means (алгоритм k-внутригрупповых средних, k-средних).Основан на минимизации функционала Q суммарной выборочной дисперсии, характеризующего разброс элементов от- носительно центров кластеров: Q = ∑ |𝑋 𝑖 | ∑ 𝑑(𝐱, 𝐶 i ) x∈𝑋 𝑖 i → min, (6.40) где С 𝑖 = 1 |𝑋 𝑖 | ∑ x x∈X i – центр кластера X i Алгоритм выполняется итерационно (рис. 21). На каждой итера- ции находятся центры кластеров, а также производится разбиение выборки на кластеры. Вычисления продолжаются, пока функцио- нал Q не перестанет уменьшаться. Порядок выполнения алгоритма следующий: 1. Выделяются начальные центры кластеров С 1 (0) , … , С 𝑚 (0) , k = 0. 2. Выборка разбивается на m кластеров по принципу ближай- шего соседства, и получаются некоторые кластеры 𝑋 1 (𝑘) , … , 𝑋 𝑚 (𝑘) 3. Находим новые центры кластеров как 𝐶 𝑖 (𝑘+1) = 1 |𝑋 (𝑘) | ∑ x x∈X i (k) ., (6.41) 4. Если не выполняется условие с 𝑖 (𝑘+1) = с 𝑖 (𝑘) для всех k = 1, …, m, то переходим на шаг 2. Интеллектуальный анализ данных 88 Рис. 21. Графическая иллюстрация работы алгоритма k-средних Пересчет кла- стерных цен- тров (покоорди- натных сред- них) Пересчет кла- стерных центров (покоординат- ных средних) Перераспределение объектов Перераспределение объектов Назначение каждого объекта наиболее под- ходящему (похожему кластеру) k = 2 Произвольный выбор k объектов исходных цен- тров кластеров 6. Основные методы анализа и интерпретации данных 89 Преимуществом алгоритма k-средних являются быстрота и про- стота реализации. К его недостаткам можно отнести неопределен- ность выбора числа и исходных центров кластеров, неверный выбор которых может вести к неудовлетворительным результатам работы итерационной процедуры или чрезмерному количеству необходи- мых итераций. Кроме того, алгоритм может быть чувствителен к выбросам, которые могут существенно искажать среднее. В этом случае может быть применена модификация алгоритма с использо- ванием k-медианы, имеющая, однако, бóльшую вычислительную сложность, препятствующую работе с большими наборами данных. 6.5. Регрессия 6.5.1. Понятие регрессии Термин регрессия (англ. regression, обратное движение) введен в 1886 г. антропологом Ф. Гальтоном при изучении статистических закономерностей наследственности роста, которые позволили вы- явить линейную связь между средним ростом отцов и их сыновей. Причем рост отцов в среднем оказался выше, чем средний рост сы- новей, что позволило исследователю сделать вывод о «…регрессии к посредственности…», т.е. о снижении роста в популяции к ее среднему значению [18]. Вместе с подобным «прикладным» появ- лением термина «регрессия» справедливо отмечают и еще одно до- полнительное принципиальное основание. Термин регрессия также отражал новизну в очередности этапов исследования: сначала со- браны данные, а затем по ним угадана модель зависимости, в то время как традиционно данные использовались для проверки апри- ори построенных теоретических моделей. Позднее термин «регрес- сия» закрепился как канонический, отражающий методы восстанов- ления зависимостей между переменными. Сегодня под регрессией принято понимать зависимость среднего значения какой-либо величины от некоторой другой величины или от нескольких величин, а под регрессионным анализом – методы ис- следования взаимосвязи переменных. Если пространство объектов Интеллектуальный анализ данных 90 обозначить как X и множество возможных ответов как Y, то суще- ствует неизвестная целевая зависимость y*: X → Y, значения кото- рой известны только на объектах обучающей выборки X ℓ = (x i , y i ) ℓ i=1 , y i = y*(x i ). Требуется построить алгоритм, который принято назы- вать функцией регрессии f: X → Y, аппроксимирующий целевую зависимость y*. Наконец, задачу обучения по прецедентам (x i , y i ), позволяющую найти регрессионную зависимость y*, называют восстановлением регрессии [66]. Следует отметить, что регрессионный подход не только позво- ляет выявлять зависимости между признаками, но и решает задачи прогнозирования (например, временного ряда на основе ретроспек- тивных данных), а также задачи классификации (например, путем использования кривой регрессии в качестве разделяющей плоско- сти между классами), примеры которых рассмотрены в разд. 3.1.4. 6.5.2. Основные этапы регрессионного анализа Выделяют следующий обобщенный многоэтапный подход к ре- грессионному анализу: 5. Формулировка задачи. На этом этапе формируются предвари- тельные гипотезы о зависимости исследуемых явлений. 6. Определение зависимых и независимых (объясняющих) пере- менных. 7. Сбор статистических данных. Данные должны быть собраны для каждой из переменных, включенных в регрессионную модель. 8. Формулировка гипотезы о форме связи (простая или множе- ственная, линейная или нелинейная). 9. Определение функции регрессии (заключается в расчете чис- ленных значений параметров уравнения регрессии). 10. Оценка точности регрессионного анализа. 11. Интерпретация полученных результатов. 12. Полученные результаты регрессионного анализа сравнива- ются с предварительными гипотезами. Оцениваются корректность и правдоподобие полученных результатов. 13. Предсказание неизвестных значений зависимой переменной. 6. Основные методы анализа и интерпретации данных 91 6.5.3. Методы восстановления регрессии Существует целый ряд методов восстановления регрессии. Приме- рами таких методов являются непараметрическая регрессия с ядерным сглаживанием, линейная и нелинейная регрессия, опорные векторы, регрессионные деревья решений, многомерные адаптивные регресси- онные сплайны (англ. Multivariate Adaptive Regression Splines, MARS), мультилинейная интерполяция (англ. Multilinear Interpolation), ради- альные базисные функции (англ. Radial Basis Functions), робастная ре- грессия (англ. Robust Regression), каскадная корреляция (англ. Cascade Correlation) и многие другие способы и подходы. Детали каждого из этих подходов могут быть найдены в специальной литературе. Вместе с тем большинство исследуемых на практике зависимо- стей может быть аппроксимировано стандартными нелинейными математическими функциями, для построения которых широко ис- пользуют метод наименьших квадратов (МНК). Его суть заключа- ется в следующем. Пусть задана модель регрессии – параметрическое семейство функций g(x, α), где α ∈ R p – вектор параметров модели. Определим функционал качества аппроксимации целевой зависимости на вы- борке X ℓ как сумму квадратов ошибок: Q(α, X ℓ ) = ∑ (𝑔(𝑥 𝑖 , α)– 𝑦 𝑖 ) 2 ℓ 𝑖=1 (6.42) Обучение МНК состоит в том, чтобы найти вектор параметров α * , при котором достигается минимум среднего квадрата ошибки на заданной обучающей выборке X ℓ : α ∗ = arg min α∈R P 𝑄(α, 𝑋 ℓ ). (6.43) Стандартный способ решения этой оптимизационной задачи – вос- пользоваться необходимым условием минимума. Если функция g(x, α) достаточное число раз дифференцируема по α, то в точке минимума выполняется система p уравнений относительно p неизвестных: 𝜕𝑄 𝜕α (α, X ℓ ) = 2 ∑ (𝑔(𝑥 𝑖 , α)– 𝑦 𝑖 ) 𝜕𝑔 𝜕α ℓ 𝑖=1 (𝑥 𝑖 , α) = 0. (6.44) Решение системы таких уравнений (методами Гаусса или Кра- мера) позволяет найти необходимые коэффициенты α в уравнении регрессии. |