При создании современных рекомендательных систем одной из задач является поиск ассоциативных правил, позволяющих при анализе корзин покупок рекомендовать очередные, вероятно необходимые покупателю, товары. Аналогично, при анализе последовательностей изученных курсов или запрошенных компьютерной программой массивов данных можно рекомендовать очередные курсы или массивы данных для обработки или анализа.
Для поиска подобных ассоциативных правил необходимо сначала находить последовательные шаблоны (Sequential Pattern Mining) – цепочки купленных товаров или запрошенных файлов, и затем исследуя их строить устойчивые ассоциации.
К настоящему времени для решения этой задачи разработано несколько алгоритмов, с разной степенью эффективности анализи-рующих различные типы последо-вательности товаров и услуг.
Одним из наиболее эффективных алгоритмов поиска ассоциативных правил является алгоритм FP-growth (https://basegroup.ru/community/articles/fpg). Его название можно перевести как «выращивание популярных (часто встречающихся) предметных наборов». Этот алгоритм позволяет не только избежать затратной процедуры генерации кандидатов, но и уменьшить необходимое число проходов по базе данных предметных наборов до двух.
В основе метода лежит предобработка базы транзакций, путем преобразования ее в компактную древовидную структуру, называемую Frequent-Pattern Tree – дерево популярных предметных наборов (откуда и название алгоритма). В дальнейшем для краткости будем называть эту структуру FP-дерево. К основным преимуществам данного метода относятся:
- Сжатие БД транзакций в компактную структуру, что обеспечивает очень эффективное и полное извлечение частых предметных наборов;
- При построении FP-дерева используется технология разделения и захвата (divide & conquer), которая позволяет выполнить декомпозицию одной сложной задачи на множество более простых;
- Позволяет избежать затратной процедуры генерации кандидатов, характерной, например, для алгоритма «a priori».
Идея алгоритма PrefixSpan
(http://ijaiem.org/Volume2Issue2/IJAIEM-2013-02-20-024.pdf)
заключается в том, чтобы найти в заданной базе предметных наборов все часто встречающиеся предметы и добавить их к текущему шаблону, получая новые частые последовательности. После этого можно искать частые последовательности большей длины на основе проецированных баз данных. Создание проецированных баз может сильно ухудшить производительность при работе с большими объемами данных, поэтому вместо физического создания проекций, используется псевдопроецирование (pseudoprojection).
При рекурсивном вызове метода PrefixSpan вместо созданной проекции ему передаются указатели на минимальные позиции возможных вхождений предметов в клиентские последовательности после текущего шаблона. В качестве указателя рассматривается набор, состоящий из идентификатора клиента, номера транзакции в клиентской последовательности и позиции в транзакции. Благодаря псевдопроекции, скорость работы алгоритма значительно повышается. Кроме того, для работы алгоритма требуется значительно меньше памяти.
Работа с алгоритмами FP—growth и PrefixSpan
Действия:
А) Скачиваем предоставленные тестовые файлы с указанного диска.
Немного о выборках:
Имеем шесть выборок с разными параметрами (см. рис. 4.2):
— среднее число транзакций (T) для неоднородных баз или точное число транзакций для однородных баз (С) в клиентских последовательностях,
— среднее число предметов в транзакциях (I),
— количество клиентских последовательностей (D).
Копируем файлы с выборками в hadoop. Делаем так же, как уже делали в лабораторной работе № 2 (пункт 2.2.-> Создание таблиц):
hadoop fs -copyFromLocal /home/cloudera/Desktop/название_документа_с_выборкой /user/cloudera/
получаем:
Рис. 4.3. Результат копирования файлов с выборками.
Б) Тестируем алгоритм FP-growth
Запускаем Apache Spark командой spark–shell (в разных версиях Spark разные команды, ещё одна из них: spark2–shell) в терминале системы и ждём пока появится строка scala> (в нижней части экрана на рис. 4.4)
Рис. 4.4. Результат запуска Spark.
Вводим в терминал системы код заранее написанной программы:
import org.apache.spark.mllib.fpm.FPGrowth
import org.apache.spark.rdd.RDD //импортируем библиотеки
val data =
sc.textFile(«/user/cloudera/название_документа_с_выборкой «)//загружаем датасеты
val transactions: RDD[Array[String]] = data.map(s => s.trim.split(‘ ‘))/ /преобразовываем датасеты в нужный формат
val fpg = new FPGrowth()//заводим переменную, отвечающую за работу алгоритма
.setMinSupport(0.2) //Изменяемое значение параметра MinSupp
.setNumPartitions(10) FP-growth где указываем MinSupp и NumPartitions
val model = fpg.run(transactions)//запускаем алгоритм FP-growh с указанными выше параметрами
model.freqItemsets.collect().foreach { itemset =>
println(itemset.items.mkString(«[«, «,», «]») + «, » + itemset.freq)
}
//Печатаем найденные последовательности
val minConfidence = 0.8 //задаём MinConf
model.generateAssociationRules(minConfidence).collect().foreach { rule =>
println(
rule.antecedent.mkString(«[«, «,», «]»)
+ » => » + rule.consequent .mkString(«[«, «,», «]»)
+ «, » + rule.confidence)
}//Для полученных последовательностей ищем ассоциативные правила и выводим их.
Так же можно создать файл. В него скопировать текст программы и запустить его командой (лучший вариант запуска, так как в дальнейшем нужно будет редактировать код)
:load /home/cloudera/Desktop/название_файла_с_программой
Код этой программы без комментариев, чтобы просто “копипастнуть”.
import org.apache.spark.mllib.fpm.FPGrowth
import org.apache.spark.rdd.RDD
val data = sc.textFile(«/user/cloudera/c10d1k «)
val transactions: RDD[Array[String]] = data.map(s => s.trim.split(‘ ‘))
val fpg = new FPGrowth().setMinSupport(0.05)
val model = fpg.run(transactions)
model.freqItemsets.collect().foreach { itemset =>
println(itemset.items.mkString(«[«, «,», «]») + «, » + itemset.freq)
}
val minConfidence = 0.5
model.generateAssociationRules(minConfidence).collect().foreach { rule =>
println(
rule.antecedent.mkString(«[«, «,», «]»)
+ » => » + rule.consequent .mkString(«[«, «,», «]»)
+ «, » + rule.confidence)
}
В результате выполнения получаем (рис. 4.5).
Оцениваем результат. Создаём файл на рабочем столе, куда копируем результаты выполнения программы. Аналогично делаем для разных выборок, измеряя время работы программы с помощью функции: System.currentTimeMillis()). Для этого в самое начало выполнения программы пишем команду:
val t0 = System.currentTimeMillis()и получаем время, которое было на момент запуска программы. Далее в конце программы (до вывода результатов) выполняем команду: println(System.currentTimeMillis() – t0). Результаты заносим в заранее созданную для этого Excel–таблицу (рис. 4.6).
Рис. 4.5. Результат запуска программы с алгоритмом FPGrowth. Рис. 4.6. Время работы алгоритма FPGrowth.Если еще осталось время, можно, изменяя минимальные поддержку (MinSupp) и достоверность (MinConf), получить результаты для разных случаев.
В) Тестируем алгоритм PrefixSpan
Вводим код программы в терминал системы:
import org.apache.spark.mllib.fpm.PrefixSpan //импортируем библиотеки
val sequences = sc.parallelize(Seq(
Array(Array(1, 2), Array(3)),
Array(Array(1), Array(3, 2), Array(1, 2)),
Array(Array(1, 2), Array(5)),
Array(Array(6))
), 2).cache() //задаём последовательности
val prefixSpan = new PrefixSpan()
.setMinSupport(0.5) //Изменяемое значение параметра MinSupp
.setMaxPatternLength(5)
//заводим переменную, отвечающую за работу алгоритма PrefixSpan, где указываем MinSupp и MaxPatternLength
val model = prefixSpan.run(sequences) )//запускаем алгоритм PrefixSpan с указанными выше параметрами
model.freqSequences.collect().foreach { freqSequence =>
println(
freqSequence.sequence.map(_.mkString("[", ", ", "]")).mkString("[", ", ", "]") +
", " + freqSequence.freq)
}//Печатаем найденные последовательности
Выборки приходится вставлять непосредственно в код (3-я строчка) после команды: val sequences = sc.parallelize (Seq(.
Чтобы не работать руками, пишем на любом языке программирования парсер для стандартных форматов. Если есть трудности с написанием, то пишем этот парсер в любом текстовом редакторе, например, NotePad++.
Можно распарсить выборку и самостоятельно Формат входных данных для алгоритма JavaRDD<List<List<Integer>>>Пример. Есть выборка:
1 2 3
4 5 6
7 8 9
Открываем файл с выборкой в Notepad++. Открываем замену символов. Заменяем пробелы на запятые. Заменяем начало строки на — Array(Array(. Конец строки заменяем на — )), Копируем полученное в код программы и запускаем.
Результаты так же заносим в excel-таблицу и файл.
Здесь можно также изменять минимальную поддержку (MinSupp).
4.3. Сравнение алгоритмов
Сравниваем время работы алгоритмов на одних и тех же выборках. Находим отличия.
