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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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 ..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций