Производительность разработки частого набора

Question

Я реализовал алгоритм априорного алгоритма для разработки частых элементов для его выборочных данных, но когда я попытался выполнить его для розничного набора данных, доступного по адресу http://fimi.ua.ac.be/data/retail.dat, который составляет около 3 Мб данных с транзакцией 88 тыс. И 1600 уникальными элементами, занимает около 29 часов. Я искал причину хита производительности и обнаружил, что алгоритм генерации набора элементов-кандидатов занимает много времени. Может ли кто-нибудь помочь мне в том, как улучшить производительность или это нормальное поведение алгоритма.

Answer 1

Какой алгоритм вы используете, и каковы ваши пороги?

Если у вас есть n 1 шт., Которые удовлетворяют вашей минимальной поддержке, Apriori (и многие другие) должны учитывать n*(n-1)/2 2-itemsets. Это, конечно, довольно дорого. В Apriori 2 -множители часто являются самым большим и самым дорогим шагом (в зависимости от ваших настроек, 3-х пунктов могут быть хуже, но обычно вы не добираетесь так далеко)

В зависимости от ваших характеристик данных , Eclat может работать лучше или хуже. FP-рост очень умный, но, похоже, очень сложно реализовать право и эффективно.

Существует также множество вариантов, некоторые из них вероятностны и могут быть значительно быстрее.

Но по существу Реализация и набор данных/параметры параметров имеют значение. Один подход может быть лучше, чем другой, в одном наборе данных; и реализации могут легко иметь 10-кратное различие в производительности. В частности, для APRIORI, где многие люди не полностью понимают используемые приемы обрезки и в конечном итоге делают слишком много работы.

Для вашего примера набора данных (который, к сожалению, совершенно бесполезен без словаря, который объясняет числа), мой APRIORI заканчивается примерно через 1 минуту на низкопроизводительном процессоре Atom с minSupport = 1000.В 4-х наборов найдены были:

32, 38, 39, 48: 1236 
32, 39, 41, 48: 1646 
36, 38, 39, 48: 1080 
38, 39, 41, 48: 1991 
38, 39, 48, 110: 1031 
38, 39, 48, 170: 1193 

, но, как упоминалось ранее, параметры значения в много с априорной. APRIORI хорошо масштабируется по количеству транзакций (что может быть больше, чем соответствует основной памяти), но оно страдает от большого количества кандидатов, поэтому вам нужно установить minSupport достаточно высоко.

С minSupport = 1000:

1-frequentItemsets (56) 
2-frequentItemsets (49) 
3-frequentItemsets (24) 
4-frequentItemsets (6) 
APRIORI runtime: 55401 ms 

С minSupport = 500:

1-frequentItemsets (185) 
2-frequentItemsets (191) 
3-frequentItemsets (79) 
4-frequentItemsets (13) 
5-frequentItemsets (0) 
APRIORI runtime: 136594 ms 

Как вы можете видеть, время работы более чем в два раза. Причина в том, что 1-набор предметов рос, уступив еще много кандидатов из 2-х предметов. В 3-х и 4-х пунктах разница больше не такая большая. Но в целом, 2 минуты исполнения на действительно низкопроизводительном процессоре пока не плох.

Снижение минимальной поддержки 250:

1-frequentItemsets (587) 
2-frequentItemsets (640) 
3-frequentItemsets (273) 
4-frequentItemsets (54) 
5-frequentItemsets (4) 
APRIORI runtime: 954984 ms 

Теперь среда начинает взрываются. Почти 16 минут, чтобы найти 5-наборы элементов:

32, 38, 39, 41, 48: 448 
36, 38, 39, 41, 48: 334 
38, 39, 41, 48, 110: 346 
38, 39, 41, 48, 170: 413 

, как вы можете видеть, 38, 39, 41, 48 4-НИКАКИЕ гарантии играют ключевую роль в этом наборе данных (но мы уже нашли это в первом запуске). Теперь мы можем также доверять 38, 39, 41, 48 -> 32, который будет самым уверенным правилом, включающим 5 предметов: приблизительно 22.5% транзакций, связанных с первыми четырьмя, также включал в себя пункт 32. Но, учитывая, что AFAICT значение номеров для этого набора данных неизвестно, мы не знаем, действительно ли это правило на самом деле интересно или просто игрушка.

Переход к minSupport = 100, среда выполнения дополнительно возрастает:

1-frequentItemsets (1857) 
2-frequentItemsets (2785) 
3-frequentItemsets (1475) 
4-frequentItemsets (306) 
5-frequentItemsets (28) 
6-frequentItemsets (0) 
APRIORI runtime: 8256507 ms 

т.е. более двух часов. Большая часть этого времени расходуется на 2-предметов: есть 1,7 миллиона кандидатов, из которых 2785 были частыми. Для 3-предметов можно приблизительно оценить, что будет только несколько тысяч кандидатов, но не миллионы. У меня есть некоторые планы по дальнейшему совершенствованию реализации путем переключения между двумя кодексами в зависимости от количества кандидатов. ('' 'Update:' '' с более простой модификацией, я еще больше сократил время выполнения в 20 раз. Так что да, '' 'реализация имеет значение' '', он может легко сделать коэффициент от 100 до 1000 или более - когда, например, обрезка APRIORI не выполняется полностью)

Если мне когда-либо найдется время, чтобы прочитать алгоритм Eclat и переопределить его, я могу обновить его с помощью результатов. Я считаю, что здесь будет намного быстрее, и так будет FP-рост.

Answer 2

Существует pretty efficient algorithm proposed by Karp Papadimtrioue Shanke, что нахождение кандидатов в однократном обходе по данным (он был в основном предназначен для обработки потока) для того, чтобы найти элементы, которые имеют частоту по крайней мере theta для любого theta в (0,1).

Алгоритм на высоком уровне:

• Collect элементов в PF, считая их внешности
• Всякий раз, когда 1/& thetas различные элементы встречаются, уменьшить все счетчики на 1 и удалить из PF тех, чьи счетчики равны нулю
• Вывести элементы в ПФ, которые выживают этот процесс

Алгоритм выходы 1/Theta (не более) кандидатов, и это не имеет ложных негативов (не пропустить любого кандидата), но он имеет некоторые ложные срабатывания (некоторые кандидаты не часто бывают).

Для простоты, если 1/Theta является целым числом.

Псевдо Код:

PF = {} //empty dictionary 
for each element e: 
    if PF.contains(e): 
     PF[e] = PF[e] + 1 
    else: 
     PF[e] = 1 
     if PF.size() == 1/Theta: 
      for each element k in PF: 
       PF[k] = PF[k] - 1 
       if PF[k] == 0: 
        remove k from PF 
When done, all elements in PF are your candidates. 

Answer 3

Это зависит от вашей реализации. Существует множество оптимизаций, которые могут быть реализованы при реализации Apriori.

Во-первых, если вы прочитали оригинальную бумагу Apriori от Agrawal & Srikant, вы заметите, что они предлагают использовать специальное дерево хешей для эффективного подсчета поддержки кандидатов. Если вы хотите посмотреть, как работает эта реализация, есть версия Apriori, реализованная с помощью HashTree в библиотеке интеллектуального анализа данных с открытым исходным кодом SPMF. Он называется AprioriHT.

Другая оптимизация, чтобы избежать сканирования базы данных несколько раз, называется AprioriTID.Каждый набор предметов аннотируется с набором идентификаторов транзакции (набора tid), содержащих его. Затем, когда кандидат генерируется путем объединения двух наборов A и B, для подсчета поддержки AUB непосредственно без сканирования базы данных, вы можете выполнить пересечение множеств tid A и B. Для дальнейшей оптимизации вы можете реализовать множество наборов с битных векторов. Эта версия APriori называется AprioriTID.

В алгоритме Паскаль была предложена другая оптимизация. Он должен использовать понятие генераторов для вывода порогов поддержки некоторых наборов элементов без сканирования базы данных, используя концепцию наборов элементов генератора из Formal Concept Analysis.

Другая оптимизация - сортировка ваших наборов предметов для каждого уровня в Apriori по лексикографическому порядку, а также все элементы в каждом наборе предметов по лексикографическому заказу. Затем, при создании кандидатов, вы можете использовать это упорядочение, чтобы не сравнивать все элементы набора друг с другом для создания более крупных кандидатов.

Существуют и другие оптимизации. На веб-сайте FIMI существуют различные реализации с различными оптимизациями.

Если вы хотите посмотреть оптимизированную версию, вы можете взглянуть на мои реализации в SPMF data mining library in Java. Кроме того, на том же сайте вы получите реализацию более быстрых алгоритмов, таких как FPGrowth.