Лекция (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,BP( 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 )xXИнтересность[Tuzhilin, 1996] Объективная Субъективная (на основе информации, заданнойэкспертом)«Полезная» (Actionable) «Неожиданная» (Unexpected)ПравилаБДАлгоритмИнтересные правилаИспользование ограниченийПроблема итеративного анализа больших объемов данных:невозможно без использования ограниченийТипы ограничений:стандартные: на support и confidenceна меры объективной интересностина выборку «горизонтально» - подмножества транзакцийна выборку «вертикально» - подмножества атрибутовна значения отдельных атрибутов (с точки зрения алгоритмааналогично «вертикальному»)шаблоны правил для поиска – метаправила (задаются экспертом,учитываются методом «ветвей и границ» при генерации наборов иправил из них, сокращается перебор)шаблоны «неинтересных» правил (поиск «неожиданных» правил,нарушающих шаблон) – для оценки субъективной интересностиНастройки метаданых дляпостроения ассоциативных правилРоль таблицы “Transaction”Роли переменных:Id (для идентификатора)Target (для элемента транзакции)Sequence (опционально, для временной метки)Интерфейс SAS Enterprise Miner дляработы с Ассоциативными правиламиОсновные результаты:Таблица правилГраф зависимостейПоиск последовательностейПравила вида А1 => А2 => … => АkС семантикой «После события Аi следует Аj»Требует признак с ролью sequenceЕсть дополнительные параметры на временные окнаНельзя корректно рассчитать liftПоддержка задается отдельноМожно использовать в рекомендательных системахАлгоритм поиска последовательностей:Сначала поиск частых эпизодов (без учета времени) Потом из частых эпизодов выделяются многоместные правила«следования» с учетом времени Возможны правила вида A=>AПоиск последовательностей и анализграфа связейДля узлов (событий) можнорассчитать разные полезныехарактеристики, например,число связей (входящих,исходящих, всего)Коэфициент кластеризации(реальное число связейближайших соседей деленноена максимально возможноечисло связей между ними)показывает находится ли узелвнутри плотной группыПоиск последовательностей и анализграфа связейБлизость – усредненноезначение кратчайших путейдо всех узлов в графеВнутренность – показываеткак часто этот узелвстречается в кратчайшихпутях между другими узламиПоиск последовательностей и анализграфа связейХабы – узлы, из которыхмного ссылок на важныеузлы (авторитеты)Авторитеты – важные узлы,на которые ссылается многохабовПоиск последовательностей и анализграфа связейХабы – узлы, из которыхмного ссылок на важныеузлы (авторитеты)Авторитеты – важные узлы,на которые ссылается многохабов.

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

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