Алгоритм априори: Наличие частых (k-1) -поднаборов подразумевает частоту?

Question

Я смотрю на следующую строку в книге, описывающую алгоритм Apriori для майнинга часто встречающихся наборов, и я не могу понять его

Обратите внимание, что с учетом кандидата k-itemset мынужно только проверить, часты ли его (k-1) -подмножества, так как алгоритм Apriori использует стратегию поиска по уровням.

В приведенном выше слове кандидат означает наличие потенциального частого набора k-элементов.

Ясно, что (k-1) -подмножества часто встречающихся k-элементов часто встречаются, но я не вижу другого следствия, даже если все (k-1) -подмножества встречаются часто.Но, возможно, я неправильно читаю?

Answer 1

"Ясно, что (k-1) -подмножества частых k-элементов являются частыми, но я не вижу других последствий, даже если бы все (k-1) -подмножества были частыми."

Вы правы, другое утверждение неверно. Подмножества (k-1) используются для генерации наборов k-элементов, которые необходимо проверить на частоту или поддержку (как это называется в оригинальной статье). Вам необходимо проверить поддержку k-элементных наборов, сгенерированных из (k-1) -подмножеств.

Оригинальная статья вполне читабельна и доступна здесь . В столбце 1 приведен пример, который дает ясную идею.

Answer 2

Другое значение неверно. Но если одно подмножество встречается не часто, то оно не будет частым. Алгоритм APriori выполняет проверку подмножества, чтобы исключить некоторые нечастые наборы предметов. Но после этого все равно нужно проверять поддержку каждого кандидата. Для этого алгоритм Apriori будет сканировать базу данных.

Если вы хотите получить лучшее описание Apriori, я предлагаю проверить эту главу книги:

http://www -users.cs.umn.edu / ~ Кумар / dmbook / ch6.pdf

Это объясняет Apriori, FPGrowth и майнинг правил ассоциации в очень простых терминах. Это легче читать, чем оригинальная статья Apriori.