Алгоритмы поиска ассоциативных правил

На сегодняшний день изучено огромное количество алгоритмов поиска ассоциативных правил (АП). Основные из них это - AIS, SETM и Apriori.

AIS – алгоритм поиска АП, был разработан сотрудниками исследовательского центра IBM Almaden в 1993 году. С этой работы начался интерес к ассоциативным правилам; на середину 90-х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появляется несколько новых алгоритмов. В алгоритме AIS кандидаты множества наборов генерируются и подсчитываются "на лету", во время сканирования базы данных. [1]

SETM – алгоритм поиска АП, был создан в качестве реализации идеи использования языка SQL для вычисления часто встречающихся наборов товаров. Алгоритм SETM формирует кандидатов "на лету", основываясь на преобразованиях базы данных, данная методика практиковалась и в AIS. SETM отделяет формирование кандидата от их подсчета для того, чтобы использовать операцию объединения языка SQL при формировании кандидата. [3]

Недостаток алгоритмов AIS и SETM - излишняя генерация и осуществление проверок множества кандидатов, которые в конечном этапе оказывается не часто встречающимися.

Apriori – стал основным алгоритмом, который применяется для получения АП. Он был предложен для улучшения работы алгоритмов AIS и SETM. Его автором является Ракеш Агравал (Rakesh Agrawal) в настоящее время работающий в Microsoft Research. [2]

Алгоритм Apriori предназначен для поиска всех частых множеств признаков. Он является поуровневым, использует стратегию поиска в ширину и осуществляет его снизу-вверх. С момента своего создания,

Apriori уже был несколько раз модифицирован. Работы по улучшению скорости работы ведутся и по сей день.

Формирование           Подсчет

2-элементных         2-элементных              Часто встречающиеся кандидатов            кандидатов               2-элементные наборы

	Itemset		Itemset	Support		Itemset	Support
	ab		ah	3		ab	3
	Ас		ас	3		ac	3
	ad		ad	2		bd	3
	Вс		be	2
	Bd		bd	3
	Cd		cd	2

Формирование 3-элементных кандидатов

	Itemset
	abc abd	--►
	bed
	acd

Подсчет 3-элементных кандидатов

Itemset	Support	Min_sup=3
abc	3
abd	2
bed	2
acd	2

Часто встречающиеся 3-элементные наборы

Itemset	Support
abc	3

Часто встречающиеся 3-элементныс наборы

Формирование 3-элементных кандидатов

Часто встречающиеся наборы

Min_sup=3 Itemset Support abc

Рис.1. Алгоритм Apriori

Впервые метод поиска АП был предложен для разработки шаблонов покупок, совершаемых в магазинах, в связи с этим её стали называть анализом рыночной корзины, т.е. набора товаров, приобретённых покупателем в рамках одной отдельно взятой транзакции. [1]

В настоящее время данный метод применяется в самых разных областях:

• •    предоставление рекомендаций при совершении покупок;

• •    поиск ошибок в базах данных;

• •    медицинская диагностика;

• •    анализ белковых последовательностей;

• •    анализ погодных явлений и т.д. [4]

Одной из основных задач исследований на тему АП является улучшение алгоритмов поиска ассоциативных правил. Благодаря алгоритму поиска АП можно легко угадать какой товар на «рынке» будет востребован больше всего, изучив транзакции магазина или проведя социологический опрос населения, вычислить какая погода будет в тот или иной период времени, проанализировав температурные скачки за последние 5, 10 или 20 лет. Данный метод очень необходим в нашей жизни, качество работы алгоритма необходимо улучшать!