首先

这篇文章是Apache Spark Advent Calendar 2015第七天的文章。

从Spark 1.5开始，系列模式挖掘算法之一的PrefixSpan已被实现在mllib中。

我们过去一直对PrefixSpan算法有兴趣，它可以从文档和搜索查询中的关键词序列中提取有用信息。

由于PrefixSpan的实现是在内存中处理数据的，处理大规模数据变得困难。但是，随着使用Spark进行分布式PrefixSpan实现的出现，现在可以对大规模数据进行序列模式抽取了。

为了确认Spark mllib的分布式PrefixSpan实现能在多长时间内处理多大数据量，我们进行了从日本语ngram语料库[2]的1000万个条目中抽取频繁形态素模式的处理。

操作验证、基准测试

确认方式

为了确认在Spark上可以处理多大规模的数据，可以执行从日本语ngram网页语料库中提取频繁形态素序列的处理，从而实现可分布处理的PrefixSpan实施。

使用到的ngram语料库是在[2]上公开发布的。

• 7gram

1000万件

我决定将该数据插入Cassandra，并通过Spark访问它，使用PrefixSpan算法提取频繁的形态素模式。

gm | partition | content                               | freq
----+-----------+---------------------------------------+------
  7 |         0 |           ( は ち おうじ みなみ の え |   18
  7 |         0 |            ) から 桓武 天皇 の 時代 ( |   26
  7 |         0 | ) について 】 当 キャンペーン 終了 後 |   15
  7 |         0 |                  ( まゆ ) の 間 を 、 |   11
  7 |         0 |          3 分 ブン の 2 以上 イジョウ |   11
  7 |         0 |    ( PDF ファイル ) ( ダウンロード し |   46
  7 |         0 |          ( 偶然 かも しれ ない けど ) |   38
  7 |         0 |              1 ) 予定 価格 調書 案 の |   20
  7 |         0 |                  1 号 店 3 階 の 販売 |   11
  7 |         0 |        22 日 、 東京 地裁 八王子 支部 |   32

集群配置

我們所使用的 Spark 集群配置如下。

这次使用的聚类是用于评估测试的，无法测量处理时间性能的绝对能力。
仅仅是为了评估能够处理多少数据。

• Spark master 1台, Spark worker 7台構成

cassandra server 3台

所有机器的规格几乎完全一样。

• CPU: 4コア

mem: 32GB

我使用了那台机器。

Spark的配置是什么？

• standalone mode

• worker memory: 4GB

driver memory: 10GB

努力了。 le.)

处理时间

PrefixSpan的参数

• minSupportを 0.1〜 0.0001まで3段階に変化

maxPatternLength = 3に固定

進行了該步驟。

在将数据从cassandra作为RDD读取后，我们将其进行缓存，以尽量减少对cassandra的访问开销。

处理时间是通过linux的time命令测量总处理时间。

结果

如果minsup变小，频繁项集的不同数量会增加，相应地预计处理时间将呈指数增长，并且实际测量结果也确实如此。我们成功地在一亿条大规模数据中，在30分钟内无OOM地提取出计数大于等于1000的频繁模式，从而验证了分散PrefixSpan实现的有效性。

Spark MLlib的PrefixSpan实现概述

mllib PrefixSpan实现
https://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/mllib/fpm/PrefixSpan.scala

以下是处理流程的概述。

提取并标识频繁出现的项目

使用PrefixSpan算法方法来

• 頻出itemの抽出

• minCount以上の頻出itemのid化

系列パターンの内部表現化

在PrefixSpan.scala的代码中，为了找到具有给定前缀的频繁序列，可以使用该方法。

正在附近举行。

频繁出现的项目提取与单词计数相同，结果被收集到驱动程序中。

PrefixSpan的本体处理 = 获得频繁模式

以下是原始的句子：
1) がhttps://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/mllib/fpm/PrefixSpan.scala#L179
2) https://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/mllib/fpm/PrefixSpan.scala#L236

以下是中文翻译：
1) 这是https://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/mllib/fpm/PrefixSpan.scala#L179
2) 这是https://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/mllib/fpm/PrefixSpan.scala#L236

成为。

在这个方法中，实现了分散的PrefixSpan算法。

根据物品进行投影

正在使用↑进行执行。

在这个链接的代码中（https://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/mllib/fpm/PrefixSpan.scala#L271），通过使用两个flatMap将前缀和后缀进行连接，并计算频繁前缀及其频率。最后，结果也被收集到了driver节点上。

我认为这就像分散PrefixSpan算法的核心一样。

在这个过程中，尺寸较小的射影数据库将被保存为smallPrefixes，并通过下一个localPrefixSpan对象进行递归处理。

在每个worker上执行localPrefixSpan.run

正在执行中。

抽取出的最终常见模式结果

最终将驱动程序保存的经常出现的模式与每个工作节点上由localPrefixSpan对象提取的频繁模式作为RDD联合起来并返回。

最后

我对之前非常有兴趣的分散PrefixSpan的Spark mllib实现，进行了1000个大规模数据的操作确认。在进行操作确认之前，我对能否真正处理实际问题感到不安，但是当最小支持度超过一定阈值时，我确认它可以以足够高的速度进行处理。

如果要使用PrefixSpan从大规模语料库和搜索查询中提取频繁关键字模式和词素序列模式。

在应用PrefixSpan算法处理大规模数据时面临的困难：提取无意义的频繁模式；提取存在信息重复或包含关系的频繁模式。

有三个缺点。

可以使用Spark mllib的PrefixSpan实现来解决这个问题。对于2，3，通常需要通过处理大规模数据的前处理和后处理来解决，但是希望通过PrefixSpan的扩展算法来解决第2点和第3点。例如，

• itemへの重要度ウェイトを付与して、そのウェイトにより抽出するパターンを制御する。

PrefixSpanをClosed系列パターンマイニングにまで拡張する。

我正在考虑将这些应用于Spark mllib的PrefixSpan算法。

请参阅提供的信息。

[1] PrefixSpan: http://chasen.org/~taku/software/prefixspan/
前缀序列模式挖掘算法：http://chasen.org/~taku/software/prefixspan/

[2] 日本语网络语料库2010年版：http://s-yata.jp/corpus/nwc2010/