Лекция (2) (1185742)

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

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

Лекция 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.

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

Тип файла PDF

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

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

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