Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Алгоритм apriori




Читайте также:
  1. A) Словесный, графический, формально - словесный, алгоритмический язык
  2. Алгоритм
  3. Алгоритм
  4. Алгоритм 2.
  5. АЛГОРИТМ АНАЛИЗА ПЕДАГОГИЧЕСКОЙ СИТУАЦИИ
  6. Алгоритм БПФ.
  7. Алгоритм визначення/зміни ключового поля
  8. Алгоритм визначення/зміни ключового поля
  9. Алгоритм выбора лиц, принимающих решения

Рассмотрим набор клиентов, включающий заданные характеристики. Выразим этот набор с помощью переменных. Обозначим множество характеристик за I – {A, B, C, D..P}

Алгоритм Apriori определяет часто встречающиеся наборы за несколько этапов.
На i-ом этапе определяются все часто встречающиеся i-элементные наборы. Каждый этап состоит из двух шагов:

1. формирование кандидатов (candidate generation);

2. подсчет поддержки кандидатов (candidate counting).

Рассмотрим i-ый этап. На шаге формирования кандидатов алгоритм создает множество кандидатов из i-элементных наборов,
чья поддержка пока не вычисляется. На шаге подсчета кандидатов алгоритм сканирует множество клиентов, вычисляя поддержку наборов-кандидатов. После сканирования отбрасываются кандидаты, поддержка которых меньше определенного пользователем минимума, и сохраняются только часто встречающиеся i-элементные наборы. Во время первого этапа выбранное множество наборов-кандидатов содержит все одно-элементные частые наборы.

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

1. L1 = {часто встречающиеся 1-элементные наборы}

2. для (k=2; Lk-1 <> ; k++) {

3. Ck = Apriorigen(Lk-1) // генерация кандидатов

4. для всех клиентов t T {

5. Ct = subset(Ck, t) // удаление избыточных правил

6. для всех кандидатов c Ct

7. c.count ++

8. }

9. Lk = { c Ck | c.count >= minsupport} // отбор кандидатов

10. }

11. Результат

Обозначения, используемые в алгоритме:

· Lk - множество k-элементных наборов, чья поддержка не меньше заданной. Каждый член множества имеет набор упорядоченных (ij < ip если j < p) элементов F и значение поддержки набора SuppF> Suppmin:

Lk = {(F1,Supp1),(F2,Supp2),...,(Fq,Suppq)},
где Fj = {i1,i2,...,ik};

· Ck - множество кандидатов k-элементных наборов потенциально частых. Каждый член множества имеет набор упорядоченных (ij < ip если j < p) элементов F и значение поддержки набора Supp.

Опишем данный алгоритм по шагам.
Шаг 1. Присвоить k = 1 и выполнить отбор всех 1-элементных наборов, у которых поддержка больше минимально заданной. Suppmin.
Шаг 2. k = k + 1.
Шаг 3. Если не удается создавать k-элементные наборы, то завершить алгоритм, иначе выполнить следующий шаг.
Шаг 4. Создать множество k-элементных наборов кандидатов из частых наборов. Для этого необходимо объединить в k-элементные кандидаты (k-1)-элементные частые наборы. Каждый кандидат будет формироваться путём добавления к (k-1)-элементному частому набору - p элемента из другого (k-1)-элементного частого набора - q. Причем добавляется последний элемент набора q, который по порядку выше, чем последний элемент набора p (p.itemk − 1 < q.itemk − 1).
При этом все k-2 элемента обоих наборов одинаковы (p.item1 = q.item1,p.item2 =q.item2,...,p.itemk − 2 = q.itemk − 2).



Шаг 5. Для каждого клиента T из множества D выбрать кандидатов Ct из множества Ck, присутствующих в наборе характеристик клиента T. Для каждого набора из построенного множества Ck удалить набор, если хотя бы одно из его (k-1) подмножеств не является часто встречающимся т.е. отсутствует во множестве Lk− 1. Это можно записать в виде следующего псевдокода:

Для всех наборов выполнить для всех (k-1)-поднаборов s из c выполнить если ( ), то удалить его из Ck



Шаг 6. Для каждого кандидата из Ck увеличить значение поддержки на единицу.
Шаг 7. Выбрать только кандидатов Lk из множества Ck, у которых значение поддержки больше заданной пользователем Suppmin. Вернуться к шагу 2.
Результатом работы алгоритма является объединение всех множеств Lk для всех k.

 

 

Таблица 4.1. Схематическое изображение работы алгоритма apriori


Дата добавления: 2015-08-05; просмотров: 22; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты