Лекция (2)

Лекция 2:Поиск ассоциативныхправилТиповая прикладная задача: анализ«корзины покупателя»АссортиментсупермаркетаИнтересные правила=>=>=>Задача Определить интересные правила в предпочтенияхпокупателей при выборе товараАссоциативный анализПравила с семантикой:в s% случаях ЕСЛИ верно А1, А2 , …, Аk, ТО с достоверностью сбудет верно B1, B2, …, BmА1  А2  …  Аk =>B1  B2  …  Bmгде А1, А2 , …, Аk, B1, B2, …, Bm – (различные!) предикаты,s – поддержка (support), с – достоверность (confidence)Основная задача:найти все интересные правила, с заданными ограничениями по s иc (возможно задание дополнительных ограничений на предикаты исами правила)Основной математический аппарат:дискретная математика, математическая логика, комбинаторнаяоптимизация (на основе метода «ветвей и границ» - вариацииполного перебора с отсевом подмножеств допустимых решений,заведомо не содержащих оптимальных решений).Ассоциативный анализТип моделей:Тип обучения:Как правило, «описательный» (descriptive) Data mining => одна иззадач - наглядное представление правил«без учителя» (unsupervised) => тренировочный набор не размеченТипы правил:Булевы!!!Числовые – нужна дискретизация, интервалы как булевыпредикатыИерархические – если определена иерархия для значенийатрибутовВременные – как правило, семантика «в s случаях если произошлоA и B, то потом случится C и D c вероятностью c»)Пространственные – предикаты определяют пространственныесвязи между объектами, например «рядом», «далеко» и т.п.Ассоциативный анализПрикладные задачи:«Экономические»: анализ корзины, маркетинг«Безопасность» и Web usage mining: модели поведенияпользователяText mining: поиск ключевых слов, характеристик и тематикБиоинформатика, медицинаЗадачи анализа:Поиск самих правилПоиск исключений (из правил)Выделение признаков (на основе правил)Классификация и прогнозирование (на базе правил)Булевы ассоциативные правилаI = {item1, item2, …, itemn} – множество атрибутовD – множество транзакций T  D, каждая транзакция T – набор элементов из I,Каждая транзакция T – бинарный вектор длины n: (t1,t2, …, tn)tk=1, если элемент itemk присутствует в T, иначе tk=0Опр Транзакция T содержит (поддерживает) X – набор атрибутов из I, еслиX TОпр Ассоциативным правилом называется импликация X=>Y, где X,Y  I иX  Y=ØОпр Правило X=>Y имеет поддержку (support) s, если s% транзакций из Dсодержат X и YОпр Правило X=>Y имеет достоверность (confidence) c, если с%транзакций из D, содержащих X, также содержат Y.ПримерD=tХлебКефирПивоЧипсы110002110030111401115110061010711118100090010100010I={Хлеб, Кефир, Пиво, Чипсы}supp(Хлеб) = 60%supp(Кефир) = 50%supp(Пиво) = 60%supp(Чипсы) = 30%Пример правила: Пиво=>Чипсыsupp(П=>Ч) = 30%conf(П=>Ч) = 50%Задача: Найти правила спараметрами:minsupp = 30%,minconf = 60%Булевы ассоциативные правилаОпр Найденные правила называются интересными правиламиОпр Набор атрибутов X and Y называется часто встречаемым еслиsupp(X and Y)>=minsuppI  {i1 ,i2 ,...,in }  набор атрибутовАссоциативное правило X  YX  I,Y  I, X  Y  {}support(X  Y)  p(X and Y)p(X and Y)confidence(X  Y)  p(Y | X) p(X)Задача : найти все ассоциативные правила сsupport  MinSup и confidence  MinConfМножество транзакцийYXX and YПопулярные алгоритмы: Apriori, FP-treeАлгоритм AprioriОсновной принцип (анти-монотонность):Формально:Любое подмножество часто встречаемого набора является частовстречаемым наборомПоддержка любого набора элементов не может превышатьминимальной поддержки всех его подмножествНеобходимое условие частой встречаемости k-элементного набора– частая встречаемость всех его (k-1)-элементных подмножествВ примере: supp({Хлеб, Кефир, Чипсы}) <= supp({Хлеб, Кефир}),supp({Хлеб, Чипсы}),supp({Кефир, Чипсы}), supp({Кефир}),supp({Чипсы}),supp({Хлеб})Этапы алгоритма:Генерация множества часто встречаемых наборов (supp >=minsupp): метод «ветвей и границ» - направленный перебор отпростых (коротких) наборов к сложным (длинным) с отсечением Генерация правил по найденным наборам (conf >= minconf)Идея метода ветвей и границ для ApriorinullABCDEABACADAEBCBDBECDCEDEABCABDABEACDACEADEBCDBCEBDECDEРедкийнаборABCDНе рассматриваемABCEABDEABCDEACDEBCDEГенерация множества частовстречаемых наборов атрибутовL1 = {часто встречаемые 1-элементные наборы}for (k = 2; Lk-1 != {}; k++) {Ck = apriori-gen(Lk-1); // Генерация k-элементных кандидатовforall transactions t  D {Ct = subset(Ck, t); // Кандидаты, которые содержатся в транзакции tforall candidates c  Ctc.count++;}Lk = {c  Ck | c.count >= minsupp }}Answer = k LkГенерация кандидатов apriori-genCk = apriori-gen(Lk-1)Шаг JOININSERT INTO CkSELECT p.item1, p.item2, …, p.itemk-1, q.itemk-1FROM Lk-1 p, Lk-1 qWHERE p.item1 = q.item1, …, p.itemk-2 = q.itemk-2,p.itemk-1 < q.itemk-1;Шаг PRUNEforall itemsets c  Ckforall (k-1)-subsets s of cif (s  Lk-1) delete c from Ck;Пример генерации кандидатовL3={abc, abd, acd, ace, bcd}Join: L3*L3abcd = abc + abdacde = acd + acePruning:acde удален, т.к.

ade не в L3C4={abcd}ПримерD=tХлебКефирПивоЧипсы110002110030111401115110061010711118100090010100010Построение 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ХлебКефирПивоЧипсы110002110030111401115110061010711118100090010100010L2={{Х,К}, {К,П}, {К,Ч}, {П,Ч}}Формируем L3{К, П, Ч}supp({К, П, Ч}) = 30%L3 = {{К, П, Ч}}Результат={{Х}60%,{К}50%,{П}60%,{Ч}30%,{Х,К}30%,{К,П}30%,{К,Ч}30%,{П,Ч}30%,{К, П, Ч}30%}Генерация правилКритерий:conf(X=>Y) = P(Y|X) = support({X,Y} ) / support(X) conf(X=>Y)>=minconf все support известны с 1-го этапаПринцип:Если правило {A} => {B, C} интересно, то и {A, B} => {C} интересноДоказательство:conf({A}=>{B, C}) = supp({A, B, C}) / support({A})>=minconf conf({A, B}=>{C}) = supp({A, B, C}) / support({A, B}) support({A, B}) <= supp({A}) conf({A, B}=>{ C})>=minconfАлгоритм:Для каждого часто встречаемого набора проверять правила наинтересность, начиная со случая, когда в правой части правиланаходится один атрибут и постепенно добавлять/убавлятьатрибуты в/из правую/левой часть(и).Метод ветвей и границ для генерации правилПравило с низкойдостоверностьюABCD=>{ }BCD=>ACD=>ABBD=>ACD=>ABCИсключенныеправилаACD=>BBC=>ADC=>ABDABD=>CAD=>BCB=>ACDABC=>DAC=>BDA=>BCDAB=>CDПримерD=tХлебКефирПивоЧипсы110002110030111401115110061010711118100090010100010Наборы:{Х}60%,{К}50%,{П}60%, {Ч}30%,{Х,К}30%,{К,П}30%,{К,Ч}30%,{П,Ч}30%,{К, П, Ч}30%Правила:conf({Х}=>{К})=50%conf({К}=>{Х})=60%conf({К}=>{П})=60%conf({П}=>{К})=50%сonf({К}=>{Ч})=60%сonf({Ч}=>{К})=100%conf({П}=>{Ч})=50%conf({Ч}=>{П})=100%сonf({К, П}=>{Ч})=100%сonf({К}=>{П, Ч})=60%сonf({П}=>{К, Ч})=50%сonf({К, Ч}=>{П})=100%сonf({Ч}=>{К, П})=100%сonf({П, Ч}=>{К})=100%Недостатки AprioriСуть алгоритма Apriori:Использовать часто встречаемые наборы размера (k – 1) длягенерации кандидатов часто встречаемых наборов размера k Использовать dbscan и сравнения подмножеств атрибутов длярасчета поддержки кандидатовСлабое место – генерация кандидатовОгромное число кандидатов: 104 1-элементных наборов приводят к107 2-элементным наборам, если надо найти наборы размера 100{a1, a2, …, a100}, нужно сгенерировать 2100  1030 кандидатов. Множественные dbscan: (n +1 ) сканирований, где n - длинанаибольшего набораПути решения:Хэш-деревья для хранения наборов и счетчиков поддержки Удаление неинформативных транзакций из базы Разбиение базы и sampling - набор будет часто встречаемым, еслион часто встречаемый на каком-то подмножестве транзакций, но:необходима оценка полноты и достоверностиПоиск частых наборов без кандидатовОсновная задача, решаемая методом Frequent-Pattern tree (FP-tree):«сжать» информацию о транзакциях и представить в «компактном» видес быстрым поиском частых наборов (FP-tree)уйти от частых сканирований БД, не генерировать кандидатов, а искатьих динамически по структуре FP-treeстратегия «разделяй и властвуй»: декомпозиция задачи поиска на болеемелкие подзадачи – рекурсивное построение «пути» частых наборов вFP-tree деревеСвойства и требования к структуре:«сжатая» информация для поиска наборов должна быть полнойразмер вспомогательных структур не должен превосходить размер БД,не должно быть несодержательной информации, например, о редкихнаборах при поиске обратная упорядоченность по частоте наборов и атрибутов– более часто встречаемые атрибуты с большой вероятностьюявляются частью частых наборовПостроение FP-treeTID100200300400500Items{f, a, c, d, g, i, m, p}{a, b, c, f, l, m, o}{b, f, h, j, o}{b, c, k, s, p}{a, f, c, e, l, p, m, n}Шаги:1.

Первое сканирование БДи построение частых 1наборов2. Обратная сортировка почастоте3. Второе сканирование ипостроение FP-treefrequent items{f, c, a, m, p}{f, c, a, b, m}{f, b}{c, b, p}{f, c, a, m, p}min_support = 0.5{}Header TableItem frequency headf4c4a3b3m3p3f:4c:3c:1b:1a:3b:1p:1m:2b:1p:2m:1Поиск частых наборов с FP-treeМетод:Для каждого элемента найти его условный базовый наборНа базе условного базового набора построить новоеусловное FP-tree поддерево для каждого элемента,рассматривая каждый путь как отдельную транзакциюПовторить процесс для элементов каждого вновь созданногоусловного FP-tree поддереваДо тех пор пока результирующее FP-tree не будет пусто илине будет содержать единственный путьЕдинственный путь генерирует все комбинации подпутей,каждый из которых есть частый наборШаг 1: От FP-tree к условному базовомунаборуДля каждого элемента проход FP-tree «вверх» по дугам сзапоминанием «условного» пути и его поддержкиВ результате с каждым элементом связан условный базовый набор(набор возможных путей к вершине с поддержкой)Header TableItem frequency headf4c4a3b3m3p3{}Conditional pattern basesf:4c:3c:1b:1a:3b:1p:1itemcond.

pattern basecf:3afc:3bfca:1, f:1, c:1m:2b:1mfca:2, fcab:1p:2m:1pfcam:2, cb:1Свойства условного FP-treeСвойство «узел-связь»: Длякаждого частого элемента ai, все возможныечастые наборы, содержащие ai , могут бытьполучены обходом по пути «узел-связь» от ai‘-гозаголовочного элемента к заголовку FP-treeСвойство префикса: Дляпоиска частых наборов для узла ai в пути P,необходимо рассматривать только префикс подпути от ai в P, его поддержка должна быть равнаподдержке узла ai.Шаг 2: Построение условного FP-treeДля каждого условного базового набора Построитьусловное FP-tree, содержащее толькопути из базового набораHeader TableItem frequency headf4c4a3b3m3p3{}f:4c:3c:1b:1a:3b:1p:1m-conditional patternbase:fca:2, fcab:1{}f:3 m:2b:1c:3p:2m:1a:3All frequent patternsconcerning mm,fm, cm, am,fcm, fam, cam,fcamm-conditional FP-treeПоиск частых наборов по условнымбазовым наборамItemУсловный базовый наборУсловное FP-treep{(fcam:2), (cb:1)}{(c:3)}|pm{(fca:2), (fcab:1)}{(f:3, c:3, a:3)}|mb{(fca:1), (f:1), (c:1)}Emptya{(fc:3)}{(f:3, c:3)}|ac{(f:3)}{(f:3)}|cfEmptyEmptyШаг 3: Рекурсивная обработкаусловного FP-tree{}{}Условный базовый набор для “am”: (fc:3)f:3c:3f:3am-conditional FP-treec:3Условный базовый набор для“cm”: (f:3)a:3{}f:3m-conditional FP-treecm-conditional FP-tree{}Условный базовый набор для“cam”: (f:3)f:3cam-conditional FP-treeЕдинственный путь в FP-treeПредположим в FP-tree T есть единственный путь PПолное множество частых наборов из T могут бытьполучены перебором всех возможных комбинацийподпутей из P{}f:3c:3a:3m-conditional FP-treeAll frequent patternsconcerning mm,fm, cm, am,fcm, fam, cam,fcamПринцип поиска частых наборовСвойство увеличения набораПусть  - частый набор в DB, B 's - условный базовыйнабор для  и  - поднабор в B.