Лекция (2) (1185742), страница 2
Текст из файла (страница 2)
Тогда есть частыйнабор в DB тогда и только тогда, когда - частый набор вB.“abcdef ” - частый набор тогда и только тогда, когда“abcde ” - частый набор“f ” - частый элемент для множества транзакций,содержащих “abcde ”Преимущества FP-tree перед AprioriЭкспериментально:FP-tree значительно (на некоторых задачах - на порядок)быстрее AprioriПричинаНет генерации и проверки кандидатовИспользуется компактная структура для поиска частыхнаборов и расчета поддержкиНет повторяющихся сканирований БДОсновные операции – суммирование и построение дереваКритика Support и ConfidenceПример: (Aggarwal & Yu, PODS98)Среди 5000 студентов 3000 играют баскетбол 3750 любят черный хлеб 2000 и то и другоеbasketball bread [40%, 66.7%] вводит в заблуждение,поскольку процент любителей хлеба 75% выше support 66.7%.basketball not bread [20%, 33.3%] более полезное, хотяsupport and confidence нижеbreadnot breadsum(col.)basketball not basketball sum(row)20001750375010002501250300020005000Критика Support и ConfidenceПример:X и Y: положительнокоррелированны, X и Z, отрицательнокоррелированны support и confidence больше уX=>ZНужна мера зависимости:corrA,BP( Aand B)P( A) P( B)P(B|A)/P(B)A => BX 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 )xXИнтересность[Tuzhilin, 1996] Объективная Субъективная (на основе информации, заданнойэкспертом)«Полезная» (Actionable) «Неожиданная» (Unexpected)ПравилаБДАлгоритмИнтересные правилаИспользование ограниченийПроблема итеративного анализа больших объемов данных:невозможно без использования ограниченийТипы ограничений:стандартные: на support и confidenceна меры объективной интересностина выборку «горизонтально» - подмножества транзакцийна выборку «вертикально» - подмножества атрибутовна значения отдельных атрибутов (с точки зрения алгоритмааналогично «вертикальному»)шаблоны правил для поиска – метаправила (задаются экспертом,учитываются методом «ветвей и границ» при генерации наборов иправил из них, сокращается перебор)шаблоны «неинтересных» правил (поиск «неожиданных» правил,нарушающих шаблон) – для оценки субъективной интересностиНастройки метаданых дляпостроения ассоциативных правилРоль таблицы “Transaction”Роли переменных:Id (для идентификатора)Target (для элемента транзакции)Sequence (опционально, для временной метки)Интерфейс SAS Enterprise Miner дляработы с Ассоциативными правиламиОсновные результаты:Таблица правилГраф зависимостейПоиск последовательностейПравила вида А1 => А2 => … => АkС семантикой «После события Аi следует Аj»Требует признак с ролью sequenceЕсть дополнительные параметры на временные окнаНельзя корректно рассчитать liftПоддержка задается отдельноМожно использовать в рекомендательных системахАлгоритм поиска последовательностей:Сначала поиск частых эпизодов (без учета времени) Потом из частых эпизодов выделяются многоместные правила«следования» с учетом времени Возможны правила вида A=>AПоиск последовательностей и анализграфа связейДля узлов (событий) можнорассчитать разные полезныехарактеристики, например,число связей (входящих,исходящих, всего)Коэфициент кластеризации(реальное число связейближайших соседей деленноена максимально возможноечисло связей между ними)показывает находится ли узелвнутри плотной группыПоиск последовательностей и анализграфа связейБлизость – усредненноезначение кратчайших путейдо всех узлов в графеВнутренность – показываеткак часто этот узелвстречается в кратчайшихпутях между другими узламиПоиск последовательностей и анализграфа связейХабы – узлы, из которыхмного ссылок на важныеузлы (авторитеты)Авторитеты – важные узлы,на которые ссылается многохабовПоиск последовательностей и анализграфа связейХабы – узлы, из которыхмного ссылок на важныеузлы (авторитеты)Авторитеты – важные узлы,на которые ссылается многохабов.