Интеллектуальный анализ данных учебное пособие. ИАД Лекции Замятин 20. Интеллектуальный анализ данных
 Скачать 2.95 Mb.
|
|
6.6. Ассоциация Еще одним методом, который выделяют в Data Mining, является ассоциация – выявление закономерностей между связанными собы- тиями. Следует отметить, что в Data Mining методы ассоциаций, поиска ассоциативных правил (англ. association rule induction) принято выделять в отдельный класс, хотя по сути они являются ча- стью более общих методов неконтролируемой классификации [72]. Примером ассоциативной закономерности (ассоциативного пра- вила) служит правило, указывающее, что из события X следует собы- тие Y. Впервые эта задача апробирована в торговой отрасли при нахож- дении типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее называют анализом рыночной корзины (англ. market basket analysis). Ассоциативные правила помогают выявлять группы товаров, как правило, приобретаемые совместно. Знание этих правил позволяет соответствующим образом размещать то- вары на прилавках, стимулируя интенсивность их продаж. Задача поиска ассоциативных правил актуальна и в сфере обслуживания, где интерес представляет то, какими услугами клиенты предпочи- тают пользоваться в совокупности. В медицине интересной пред- ставляется возможность выявлять наиболее сочетаемые болезни и симптомы, требующиеся для определения диагноза. Наиболее известным и широко используемым (в ритейле и кон- салтинговых компаниях) примером практической реализации по- иска ассоциативных правил является алгоритм Априори (англ. Apri- ori, A priori) [3]. Продемонстрируем работу алгоритма Априори на примере задачи анализа рыночной корзины, оперируя привычными на практике табличными записями. Одним из наиболее распространенных типов данных в этой задаче являются транзакционные данные (англ. transaction data), отражающие в таблице базы данных взаи- модействие клиентов и магазина (табл. 7). В примере представлено 20 записей, полученных при продаже семи видов товаров. В большом супермаркете аналогичные реальные 6. Основные методы анализа и интерпретации данных 93 данные могут быть представлены миллионами записей в месяц, а число групп товаров может достигать тысячи и более. Т а б л и ц а 7 Пример транзакционных данных клиентов и магазина ID Яблоки Пиво Сыр Финики Яйца Рыба Конфеты Условное обозначение a b c d e f g 1 1 1 1 1 2 1 1 1 3 1 1 1 4 1 1 5 1 1 6 1 7 1 1 8 1 9 1 1 10 1 1 11 1 1 12 1 13 1 1 14 1 1 15 16 1 17 1 1 18 1 1 1 1 19 1 1 1 1 20 1 При анализе рыночной корзины оперируют утверждениями типа: «Если корзина содержит Х и Y, то она также содержит и Z». (6.45) Подобное правило сопровождается двумя метриками: 1. Достоверность или точность (англ. confidence или accuracy). Отражает, как часто при справедливости выражения в части «если», оно также справедливо в части «то». 2. Покрытие или поддержка (англ. coverage или support). Отра- жает долю выражений в части «если» в базе данных. Интеллектуальный анализ данных 94 Для утверждения (6.45) в случае X =пиво, Y =сыр, Z =рыба в рассматриваемом примере достоверность составляет 1/2 = 50%, а поддержка 2/20 = 10%. Какие же утверждения конструкции «если / то» следует признать интересными и достойными внимания? Логично к таким утвержде- ниям отнести такие, которые справедливы чаще, чем случайно. Например, статистический анализ потребительской корзины по- казывает, что 10% в ней занимает хлеб, а 4% – стиральный порошок. Это означает, что вероятность встретить в такой корзине хлеб P(хлеб) = 0,1, а порошок – P(порошок) = 0,04. Какова же вероят- ность встретить эти товары в корзине совместно? Очевидно, P(хлеб | порошок) = P(хлеб) × P(порошок) = 0,1×0,04 = 0,004. На практике, анализируя, например, тысячу таких потребительских корзин, лишь в четырех из них ожидается увидеть хлеб и порошок. Поэтому, если в действительности такую комбинацию удастся обнаружить в 20 или 30 случаях из тысячи, это будет сюрпризом, достойным внимательного анализа (между товарами в магазине или торговой сети есть какая-то неочевидная связь). Каким же образом в базе данных можно найти наиболее интерес- ные для анализа правила (ассоциации)? Очевидно, такие правила не только будут отличаться более высокой точностью, но и должны иметь значительную поддержку (обеспечивая воспроизво- димость найденного правила на данном наборе данных). Однако, задача поиска таких ассоциативных правил на практике осложня- ется высокой вычислительной сложностью. Можно оперировать 500 000 000 возможными правилами типа (6.45), и если база данных состоит из 20 000 000 записей, то число возможных вычислитель- ных операций может доходить до 10 16 . Проверка уровней точности и поддержки в таком массиве – нетривиальная задача. Поэтому для решения подобных задач был предложен неслож- ный, вычислительно эффективный алгоритм Априори, позволяю- щий находить интересные ассоциативные связи в данных. Алго- ритм оперирует не собственно ассоциативными правилами типа (6.45), а множествами (англ. itemsets), элементы которых опреде- ленным образом ассоциированы между собой. 6. Основные методы анализа и интерпретации данных 95 6.6.1. Описание алгоритма Рассмотрим описание алгоритма Априори, основываясь на утвер- ждении, что любое множество, содержащееся в некотором часто встречающемся множестве (ЧВМ), является ЧВМ. Другими сло- вами, если Y ⊆ X и P(X) ≥ c, то P(Y) ≥ c. (6.46) При этом k-множеством будем называть множество, состоящее из k элементов. Обозначим через L k множество всех часто встречающихся k-множеств. Объединение L k по всем k дает все искомое множество ЧВМ. Построение L k выполняется по шагам. Сначала находится L 1 (множество одноэлементных ЧВМ). Затем для каждого фиксированного k ≥ 2, используя найденное множество L k−1 , определяется L k . Процесс завершается, как только k станет больше максимального количества элементов. Определение L k при известном L k − 1 выполняется в два шага: 1) генерируются множества-кандидаты C k ; 2) затем из этого множества исключаются лишние элементы. Полученное таким образом множество и будет равно L k Генерация множества кандидатов. Множество кандидатов C k составляется путем слияний всех допустимых пар l 1 , l 2 ∈ L k−1 Сокращение. Множество кандидатов C k содержит все множе- ства из L k , но содержит дополнительно и лишние множества, не яв- ляющиеся ЧВМ. Чтобы получить L k , необходимо лишь исключить такие множества. Для этого необходимо для каждого набора из C k посчитать количество его повторений в базе данных и исключить это множество, если число повторений меньше заданного порога (уровня поддержки). Но такой подсчет – довольно трудоемкая про- цедура, так как C k может иметь очень большой размер. Поэтому рекомендуется сначала произвести его предварительную очистку следующим образом. Пусть l – некоторое множество из C k (следовательно, он состоит из k элементов). Если l – ЧВМ, то в соответствии с утверждением (6.46) все подмножества l, состоящие из k − 1 элементов, должны Интеллектуальный анализ данных 96 быть также ЧВМ, т.е. принадлежать множеству L k−1 . Поэтому если хотя бы одно множество, полученное из l удалением одного эле- мента, не принадлежит L k−1 , то l не может являться ЧВМ и должно быть исключено из C k Допустимая пара и их слияние. Пусть l 1 , l 2 ∈ L k−1 – два множе- ства из множества L k−1 . Обозначим через l i [j] j-й элемент в множе- стве l i . Например, l 1 [k − 2] – это предпоследний элемент в l 1 . Пред- полагается, что на исходном множестве элементов задано некото- рое отношение порядка ‘<’ (например, по номерам элементов), и в наборе l i элементы отсортированы в соответствии с данным отно- шением порядка. Пара l 1 , l 2 – допустимая для слияния, если: (l 1 [1] = l 2 [1]) ∧ (l 1 [2] = l 2 [2]) ∧ … ∧ (l 1 [k − 2] = = l 2 [k − 2]) ∧ (l 1 [k − 1] < l 2 [k − 1]). (6.47) Условие (l 1 [k − 1] < l 2 [k − 1]) гарантирует, что дубликатов в мно- жестве C k не будет. Слиянием u(l 1 , l 2 ) допустимых наборов l 1 , l 2 будет множество, состоящее из элементов l 1 [1], l 1 [2], . . . , l 1 [k − 1], l 2 [k − 1]. 6.6.2. Пример исполнения алгоритма Для демонстрации работы алгоритма Априори приведем его краткое пошаговое описание. Шаг 1. Найти все одноэлементные ЧВМ множества. Шаг 2. For (k = 2; while L k–1 <> ‘ ‘; k++) { Шаг 3. C k = apriori_gen(L k-1 ) Шаг 4. Для каждого c в C k , c.count = 0 Шаг 5. Для всех записей r в БД { Шаг 6. C r = subset(C k , r); For each c in C r , c.count++ } Шаг 7. Set L k := all c in C k whose count >= minsup Шаг 8. Вывод k L k } // возвращаем все множества L k Обозначим с помощью minsup – параметр минимального уровня поддержки. Пусть minsup = 4 (т.е. 20%). 6. Основные методы анализа и интерпретации данных 97 Шаг 1. Находим все одноэлементные ЧВМ с заданным minsup (т.е. записи, представленные в БД минимум 4 раза): Результат шага: L 1 = {{a}, {b}, {c}, {d}, {e}, {f}, {g}}. Шаг 2, 3. Задаем k = 2 и запускаем процедуру apriori_gen для формирования из L 1 множества кандидатов C 2 , отсортированных по алфавиту. Результат: C 2 = {{a, b}, {a, c}, {a, d}, {a, e}, {a, f}, {a, g}, {b, c}, {b, d}, {b, e}, {b, f}, {b, g}, {c, d}, {c, e}, {c, f}, {c, g}, {d, e}, {d, f}, {d, g}, {e, f}, {e, g}, {f, g}}. Шаг 4. Инициализируем счетчик с.count нулевым значением. Шаг 5, 6. Перебираем все записи БД и находим те, которые со- держатся в C 2 Первая запись r1= {a, b, d, g}. Элементами C 2 , содержащими элементы из r1будут: C r1 = {{a, b}, {a, d}, {a, g}, {a, d}, {a, g}, {b, d}, {b, g}, {d, g}}. Также для каждого из C r для этих множеств призна- ков инкрементируем счетчик c.count++ . Вторая запись r2 = {c, d, e}, а C r2 = {{c, d}, {c, e}, {d, e}}. И так далее, для всех записей из БД. После анализа 20 записей БД проверяем, для каких множеств-кандидатов значения счетчика c.count не ниже заданного уровня поддержки – т.е. ≥ minsup (4): {a, b}{a, c}{a, d}{c, d}{c, e}{c, f}. Результат: L 2 = {{a, b}{a, c}{a, d}{c, d}{c, e}{c, f}} Затем осуществляется переход к шагу 2 алгоритма, k = 3 и вы- полняется процедура apriori_gen по данным L 2 . Формируются сле- дующие пары значений: {a, b}:{a, c} {a, c}:{a, d} {c, d}:{c, e} {c, d}:{c, f} {c, e}:{c, f}. Множества из 3 элементов будут выглядеть следующим образом: {a, b, c}, {a, c, d}, {c, d, e}, {c, d, f}, {c, e, f}. – {a, b, c} исключается из рассмотрения, так как {b, c} не в L 2 ; – {c, d, e} исключается из рассмотрения, так как {d, e} не в L 2 ; – {c, d, f}исключается из рассмотрения, так как {d, f}не в L 2 ; – {c, e, f}исключается из рассмотрения, так как {e, f} не в L 2 Интеллектуальный анализ данных 98 Таким образом, остается C 3 = {a, c, d}. Выполняются шаги 5–7 с подсчетом количества появлений C 3 в исходной БД. Их число со- ставляет 4, поэтому L 3 = {a, c, d}. Затем осуществляется очередной переход к шагу 2, k = 4 и вы- полняется процедура apriori_gen по данным L 3 . В данном случае L 4 = {}, выполнение алгоритма завершается, возвращая все полу- ченные непустые множества. Результат: Ls = {{a}, {b}, {c}, {d}, {e}, {f}, {g}, {a, c}, {a, d}, {c, d}, {c, e}, {c, f}, {a, c, d}}. Каждый из 13 элементов множества данных Ls может представ- лять бизнес-интерес, интерпретируя эти элементы можно составить несложные, но практически полезные ассоциативные правила. 6.7. Последовательная ассоциация При анализе ассоциаций, которым посвящен разд. 6.6, может быть полезной не только найденная в совокупности транзакций базы данных связь между переменными, но и последовательность появления таких транзакций в базе данных во времени. В таком случае появляются анализ последовательности (англ. sequence) и поиск последовательных ассоциаций (англ. sequential association), которые могут содержать интересную информацию. Фактически ассоциация является частным случаем последовательной ассоциа- ции с временным лагом, равным нулю. При наличии закономерностей в таких последовательностях воз- можно с некоторой долей вероятности предсказывать появление со- бытий в будущем и принимать на основе этого более обоснованные решения. Такую разновидность поиска ассоциативных правил назы- вают сиквенциальным анализом (англ. Sequential Pattern Mining, SPM), отличающимся учетом отношения порядка между исследуе- мыми наборами. Данное отношение может быть определено раз- ными способами. При анализе последовательности событий, проис- ходящих во времени, объектами таких наборов являются события, а отношение порядка соответствует хронологии их появления. В этом случае примером закономерности (шаблоном, паттерном) служит 6. Основные методы анализа и интерпретации данных 99 правило, указывающее, что из события X спустя время t последует событие Y. Сиквенциальный анализ широко используется, например, в те- лекоммуникационных компаниях для анализа данных об авариях на различных узлах сети [118]. Информация о последовательности совершения аварий может помочь в обнаружении неполадок и пре- дупреждении новых аварий. Например, если известна типичная по- следовательность сбоев некоторой телекоммуникационной среды: e 5 , e 2 , e 7 , e 13 , e 6 , e 1 , ..., где e i – сбой с кодом i, то на основании факта появления сбоя e 2 можно сделать вывод о скором появлении сбоя e 7 . Это позволяет априори предпринять профилактические меры, устраняющие причины возникновения сбоя. Кроме того, если дополнительно обладать и знаниями о времени между сбоями, то можно предсказать не только факт его появления, но и время. При анализе поведения пользователей интернет-сайтов полез- ным может быть определение профиля пользователя по закономер- ностям в последовательности навигации по тем или иным разделам (web-страницам) сайта. В биоинформатике такие ассоциации могут быть информативны при поиске каркасов белковых последователь- ностей. В маркетинге и менеджменте при управлении циклом работы с клиентом (англ. Customer Lifecycle Management) эти подходы крайне востребованы, они позволяют предугадать связь приобрете- ния одного товара / услуги с вероятностью приобретения других товаров / услуг позднее. Например, после покупки квартиры боль- шинство людей в течение двух недель приобретают холодильник, а в течение двух месяцев – телевизор. Или может существовать по- следовательная связь между покупкой кровати и постельных при- надлежностей для нее. 6.7.1. Алгоритмы семейства «Априори» Первыми алгоритмами, разработанными для решения задач сиквенциального анализа, были алгоритмы, построенные на базе алгоритма Априори (см. разд. 6.6), но отличающиеся учетом допол- Интеллектуальный анализ данных 100 нительного параметра – времени совершения транзакции (напри- мер, AprioriAll, AprioriSome, DynamicSome) [1, 118]. Эти алгоритмы используют подход генерации и отбора кандидатов часто встречаю- щихся последовательностей, а также свойство, заключающееся в том, что каждая подпоследовательность ЧВП должна также быть ЧВП. Опишем кратко суть этих алгоритмов сиквенциального анализа. Пусть имеется база данных, в которой каждая запись представ- ляет собой клиентскую транзакцию – идентификатор клиента, дата / время транзакции, набор приобретенных товаров. При этом есть условие – клиент не может иметь две и более транзакций, со- вершенных в один момент времени. Введем несколько основных понятий, требуемых для описания сути алгоритмов. Предметное множество (англ. itemset)– непустой набор пред- метов (товаров), появившихся в одной транзакции, т.е. приобретен- ных одновременно. Для обозначения используем фигурные скобки: I = {i1, i2, ..., im},где ij – предмет. Последовательность – упорядоченное предметное множество. Для обозначения используем треугольные скобки: S = I1, I2, ..., Im, где Ii – предметное множество. Длиной последовательности будем называть количество предметов в этой последовательности, а k-последовательностью – последовательность длины k. Последовательность S1 содержится в последовательности S2, если все предметные множества S1содержатся в предметных множествах S2, при этом порядок надмножеств из S2соответствует порядку пред- метных множеств S1. Например, последовательность {3}, {4,5}, {8} содержится в последовательности {7}, {3,8}, {9}, {4,5,6}, {8}, по- скольку {3} содержится в {3,8}, {4,5} содержится в {4,5,6} и {8} – в {8}. Однако {3}, {5} не содержится в {3,5} (и наоборот), по- скольку в первой последовательности предметы 3 и 5 приобретены один за другим, а во второй – совместно. Все транзакции одного клиента могут быть показаны в виде последовательности, в которой они упорядочены по дате, времени или номеру визита. Такие последовательности будем называть 6. Основные методы анализа и интерпретации данных 101 клиентскими. Формально это записывается следующим образом. Пусть клиент совершил несколько упорядоченных во времени тран- закций T1, T2, ..., Tk. Тогда каждый предметный набор в транзакции Ti обозначим I(Ti), а каждую клиентскую последовательность для данного клиента запишем как I(T1), I(T2), ..., I(Tk). Последовательность S называется поддерживаемой клиентом, если она содержится в клиентской последовательности данного клиента. Тогда поддержка последовательности определяется как число клиентов, поддерживающих данную последовательность (аналогично поддержке при ассоциативном анализе в разд. 6.6). Для базы данных клиентских транзакций задача поиска шабло- нов заключается в обнаружении последовательностей, имеющих поддержку выше заданного порогового значения. Каждая такая последовательность является шаблоном (паттерном) последова- тельных событий. Последовательность, удовлетворяющую ограни- чению минимальной поддержки, будем называть ЧВП. Последовательность S называется максимальной, если она не со- держится в какой-либо другой последовательности. Упомянутые выше алгоритмы сиквенционального анализа ре- шают задачу поиска последовательных шаблонов и состоят в общем виде из следующих этапов. |