Лекция (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*L3abcd = abc + abdacde = 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:3a:3m-conditional FP-treeAll frequent patternsconcerning mm,fm, cm, am,fcm, fam, cam,fcamПринцип поиска частых наборовСвойство увеличения набораПусть - частый набор в DB, B 's - условный базовыйнабор для и - поднабор в B.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.