SAS EM. Лекция 2. Поиск ассоциативных правил (Лекции 2014)

SAS ENTERPRISE MINERПОИСК АССОЦИАТИВНЫХ ПРАВИЛC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .КОНЦЕПЦИЯ SEMMASampleC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ExploreModifyModelAssessТИПОВАЯ ПРИКЛАДНАЯ ЗАДАЧА: АНАЛИЗ«КОРЗИНЫ ПОКУПАТЕЛЯ»АссортиментсупермаркетаИнтересные правила=>=>=>Задача Определить интересные правила в предпочтенияхпокупателей при выборе товараC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .АССОЦИАТИВНЫЙ АНАЛИЗ•Правила с семантикой:•••Основная задача:••в s% случаев ЕСЛИ верно А и B и С, ТО с достоверностью сбудет верно D и EA&B&C=>D&E, где A,B,C,D,E – (различные!) предикаты, s –поддержка (support), с – достоверность (confidence)найти все интересные правила, с заданными ограничениями поs и c (возможно задание дополнительных ограничений напредикаты и сами правила)Основной математический аппарат:•дискретная математика, математическая логика, комбинаторнаяоптимизация (на основе метода «ветвей и границ» - вариацииполного перебора с отсевом подмножеств допустимых решений,заведомо не содержащих оптимальных решений).C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .АССОЦИАТИВНЫЙ АНАЛИЗ•Тип моделей:••Тип обучения:••Как правило, «описательный» (descriptive) Data mining => однаиз задач - наглядное представление правил«без учителя» (unsupervised) => тренировочный набор неразмеченТипы правил:•••••Булевы!!!Числовые – нужна дискретизация, интервалы как булевыпредикатыИерархические – если определена иерархия для значенийатрибутовВременные – как правило, семантика «в s случаях еслипроизошло A и B, то потом случится C и D c вероятностью c»)Пространственные – предикаты определяют пространственныесвязи между объектами, например «рядом», «далеко» и т.п.C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .АССОЦИАТИВНЫЙ АНАЛИЗ• Прикладные••••«Экономические»: анализ корзины, маркетинг«Безопасность» и Web usage mining: моделиповедения пользователяText mining: поиск ключевых слов, характеристик итематикБиоинформатика, медицина• Задачи••••задачи:анализа:Поиск самих правилПоиск исключений (из правил)Выделение признаков (на основе правил)Классификация и прогнозирование (на базе правил)C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .БУЛЕВЫ АССОЦИАТИВНЫЕ ПРАВИЛАОпр Найденные правила называются интересными правилами• Опр Набор атрибутов X  Y называется часто встречаемым еслиsupp(X  Y)>=minsupp•I  {i1 ,i2 ,...,in }  набор атрибутовМножество транзакцийАссоциатив ное правило X  YX  I, Y  I, X  Y  {}support(X  Y)  p(X  Y)p(Y )p(X )p( X  Y )p(X  Y)p(X)Задача : найти все ассоциативные правила сsupport  MinSup и confidence  MinConfconfidence (X  Y)  p(Y | X) Популярные алгоритмы: Apriori, FP-treeC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .ИНТЕРЕСНОСТЬ•Объективная•Субъективная (на основе информации, заданнойэкспертом)•«Полезная» (Actionable)•«Неожиданная» (Unexpected)ПравилаБДC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .АлгоритмИнтересные правилаКРИТИКА ДОСТОВЕРНОСТИ ИПОДДЕРЖКИ•Пример: (Aggarwal & Yu, PODS98)••Среди 5000 студентов:•3000 играют баскетбол, 3750 любят черный хлеб•2000 и то и другоеbasketball  bread [40%, 66.7%] вводит в заблуждение,поскольку процент любителей хлеба 75% выше support 66.7%.•basketball  not bread [20%, 33.3%] более полезное, хотя supportи confidence нижеbreadnot breadsum(col.)C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .basketball not basketball sum(row)20001750375010002501250300020005000КРИТИКА ПОДДЕРЖКИ И ДОСТОВЕРНОСТИ•Пример:X и Y: положительнокоррелированны,• X и Z, отрицательнокоррелированны• support и confidence больше уX=>Z••Нужна мера «зависимости»типаP( A B )P( A) P( B )•P(B|A)/P(B) называется lift для•A => BC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .X 1 1 1 1 0 0 0 0Y 1 1 0 0 0 0 0 0Z 0 1 1 1 1 1 1 1Rule Support ConfidenceX=>Y 25%50%X=>Z 37.50%75%ItemsetSupportInterestX,YX,ZY,Z25%37.50%12.50%20.90.57ОБЪЕКТИВНЫЕ МЕРЫ ИНТЕРЕСНОСТИ1) support(X  Y)  P( X  Y )2) confidence( X  Y )  P (Y | X )3) generality( X  Y )  P(Y)P(X  Y)P(X  Y) P(Y | X) confidence( X  Y )4) lift( X  Y ) PEXP (X  Y) P(X)P(Y)P(Y)P(Y)5) RI( X  Y )  P(Y | X) - P(Y)  confidence( X  Y )  generality( X  Y )P(Y | X )1  P(Y | X )6 ) J(X  Y)  P (Y )[ P (Y | X ) log 2 (1  P(Y | X )) log 2] (J-measure)P(Y )1  P(Y )p( x )D( p( x ), q( x ))   p( x ) log(Kullback, Leibler)p(y)xXC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .АЛГОРИТМ APRIORI•Основной принцип (анти-монотонность):••Формально:•••Любое подмножество часто встречаемого набора является частовстречаемым наборомПоддержка любого набора элементов не может превышатьминимальной поддержки всех его подмножествНеобходимое условие частой встречаемости k-элементного набора –частая встречаемость всех его (k-1)-элементных подмножествЭтапы алгоритма:Генерация множества часто встречаемых наборов (supp >= minsupp):метод «ветвей и границ» - направленный перебор от простых(коротких) наборов к сложным (длинным) с отсечением• Генерация правил по найденным наборам (conf >= minconf)•C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ИДЕЯ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ APRIORInullABCDEABACADAEBCBDBECDCEDEABCABDABEACDACEADEBCDBCEBDECDEРедкийнаборABCDНе рассматриваемC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .ABCEABDEABCDEACDEBCDEПРИМЕР ГЕНЕРАЦИИ КАНДИДАТОВ•L3={abc, abd, acd, ace, bcd}•Объединение: L3*L3••abcd = abc + abd•acde = acd + aceУдаление:••acde удален, т.к. ade не в L3C4={abcd}C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ПРИМЕР ГЕНЕРАЦИИ ЧАСТЫХ НАБОРОВDatabase DTID100200300400Items134235123525C1Scan Ditemset sup.{1}2{2}3{3}3{4}1{5}3L1 itemset sup.{1}{2}{3}{5}C2 itemset supL2itemset{1 3}{2 3}{2 5}{3 5}C3sup2232itemset{2 3 5}C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .{1{1{1{2{2{3Scan D2}3}5}3}5}5}121232L3C2Scan Ditemset sup{2 3 5} 22333itemset{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}ПРИМЕРD=tХлебКефирПивоЧипсы110002110030111401115110061010711118100090010100010C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .Построение L1supp(Хлеб) = 60%supp(Кефир) = 50%supp(Пиво) = 60%supp(Чипсы) = 30%L1 = {{Х}, {К}, {П}, {Ч}}Построение L2{Х, К}, {Х, П}, {Х, Ч}{К, П}, {К, Ч}, {П, Ч}supp({Х, К}) = 30%supp({Х, П}) = 20%supp({Х, Ч}) = 10%supp({К, П}) = 30%supp({К, Ч}) = 30%supp({П, Ч}) = 30%L2={{Х,К}, {К,П}, {К,Ч}, {П,Ч}ПРИМЕРD=tХлебКефирПивоЧипсы110002110030111401115110061010711118100090010100010C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .L2={{Х,К}, {К,П}, {К,Ч}, {П,Ч}}Формируем L3{К, П, Ч}supp({К, П, Ч}) = 30%L3 = {{К, П, Ч}}Результат={{Х}60%,{К}50%,{П}60%,{Ч}30%,{Х,К}30%,{К,П}30%,{К,Ч}30%,{П,Ч}30%,{К, П, Ч}30%}ГЕНЕРАЦИЯ ПРАВИЛ•Критерий:••••Принцип:••Если правило {A} => {B, C} интересно, то и {A, B} => {C}интересноДоказательство:•••••conf(X=>Y) = P(Y|X) = support({X,Y} ) / support(X)conf(X=>Y)>=minconfвсе support известны с 1-го этапаconf({A}=>{B, C}) = supp({A, B, C}) / support({A})>=minconfconf({A, B}=>{C}) = supp({A, B, C}) / support({A, B})support({A, B}) <= supp({A})conf({A, B}=>{ C})>=minconfАлгоритм:•Для каждого часто встречаемого набора проверять правила наинтересность, начиная со случая, когда в правой части правиланаходится один атрибут и постепенно добавлять/убавлятьатрибуты в/из правую/левой часть(и).C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .МЕТОД ВЕТВЕЙ И ГРАНИЦ ДЛЯ ГЕНЕРАЦИИПРАВИЛПравило с низкойдостоверностьюABCD=>{ }BCD=>ACD=>ABBD=>ACD=>ABCИсключенныеправилаC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .ACD=>BBC=>ADC=>ABDABD=>CAD=>BCB=>ACDABC=>DAC=>BDA=>BCDAB=>CDПРИМЕРD=Правила:tХлебКефирПивоЧипсыconf({Х}=>{К})=50%11000conf({К}=>{Х})=60%21100conf({К}=>{П})=60%30111conf({П}=>{К})=50%40111сonf({К}=>{Ч})=60%51100сonf({Ч}=>{К})=100%61010conf({П}=>{Ч})=50%71111conf({Ч}=>{П})=100%81000сonf({К, П}=>{Ч})=100%90010сonf({К}=>{П, Ч})=60%100010сonf({П}=>{К, Ч})=50%Наборы:{Х}60%,{К}50%,{П}60%, {Ч}30%,{Х,К}30%,{К,П}30%,{К,Ч}30%,{П,Ч}30%,{К, П, Ч}30%C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d .сonf({К, Ч}=>{П})=100%сonf({Ч}=>{К, П})=100%сonf({П, Ч}=>{К})=100%НЕДОСТАТКИ APRIORI•Суть алгоритма Apriori:Использовать часто встречаемые наборы размера (k – 1) для генерациикандидатов встречаемых наборов размера k• Использовать db scan и сравнения подмножеств атрибутов для расчетаподдержки кандидатов••Слабое место – генерация кандидатовОгромное число кандидатов: 104 1-элементных наборов приводят к 1072-элементным наборам, если надо найти наборы размера 100 {a1, a2, …,a100}, нужно сгенерировать 2100  1030 кандидатов.• Множественные db scan: (n +1 ) сканирований, где n - длинанаибольшего набора••Пути решения:•••Хэш-деревья для хранения наборов и счетчиков поддержкиУдаление неинформативных транзакций из базыРазбиение базы и sampling - набор будет часто встречаемым, если ончасто встречаемый на каком-то подмножестве транзакций, но:необходима оценка полноты и достоверностиДемонстрация на данных bankC op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c .

A l l r i g h t s r es er v e d ..