Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/7783#discussion_r35881077
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/fpm/PrefixSpan.scala
---
@@ -78,81 +97,153 @@ class PrefixSpan private (
* the value of pair is the pattern's count.
*/
def run(sequences: RDD[Array[Int]]): RDD[(Array[Int], Long)] = {
+ val sc = sequences.sparkContext
+
if (sequences.getStorageLevel == StorageLevel.NONE) {
logWarning("Input data is not cached.")
}
- val minCount = getMinCount(sequences)
- val lengthOnePatternsAndCounts =
- getFreqItemAndCounts(minCount, sequences).collect()
- val prefixAndProjectedDatabase = getPrefixAndProjectedDatabase(
- lengthOnePatternsAndCounts.map(_._1), sequences)
- val groupedProjectedDatabase = prefixAndProjectedDatabase
- .map(x => (x._1.toSeq, x._2))
- .groupByKey()
- .map(x => (x._1.toArray, x._2.toArray))
- val nextPatterns = getPatternsInLocal(minCount,
groupedProjectedDatabase)
- val lengthOnePatternsAndCountsRdd =
- sequences.sparkContext.parallelize(
- lengthOnePatternsAndCounts.map(x => (Array(x._1), x._2)))
- val allPatterns = lengthOnePatternsAndCountsRdd ++ nextPatterns
- allPatterns
+
+ // Convert min support to a min number of transactions for this dataset
+ val minCount = if (minSupport == 0) 0L else
math.ceil(sequences.count() * minSupport).toLong
+
+ // (Frequent items -> number of occurrences, all items here satisfy
the `minSupport` threshold
+ val freqItemCounts = sequences
+ .flatMap(seq => seq.distinct.map(item => (item, 1L)))
+ .reduceByKey(_ + _)
+ .filter(_._2 >= minCount)
+ .collect()
+
+ // Pairs of (length 1 prefix, suffix consisting of frequent items)
+ val itemSuffixPairs = {
+ val freqItems = freqItemCounts.map(_._1).toSet
+ sequences.flatMap { seq =>
+ val filteredSeq = seq.filter(freqItems.contains(_))
+ freqItems.flatMap { item =>
+ val candidateSuffix = LocalPrefixSpan.getSuffix(item,
filteredSeq)
+ candidateSuffix match {
+ case suffix if !suffix.isEmpty => Some((List(item), suffix))
+ case _ => None
+ }
+ }
+ }
+ }
+
+ // Accumulator for the computed results to be returned, initialized to
the frequent items (i.e.
+ // frequent length-one prefixes)
+ var resultsAccumulator = freqItemCounts.map(x => (List(x._1), x._2))
+
+ // Remaining work to be locally and distributively processed
respectfully
+ var (pairsForLocal, pairsForDistributed) =
partitionByProjDBSize(itemSuffixPairs)
+
+ // Continue processing until no pairs for distributed processing
remain (i.e. all prefixes have
+ // projected database sizes <= `maxLocalProjDBSize`)
+ while (pairsForDistributed.count() != 0) {
+ val (nextPatternAndCounts, nextPrefixSuffixPairs) =
+ extendPrefixes(minCount, pairsForDistributed)
+ pairsForDistributed.unpersist()
+ val (smallerPairsPart, largerPairsPart) =
partitionByProjDBSize(nextPrefixSuffixPairs)
+ pairsForDistributed = largerPairsPart
+ pairsForDistributed.persist(StorageLevel.MEMORY_AND_DISK)
+ pairsForLocal ++= smallerPairsPart
+ resultsAccumulator ++= nextPatternAndCounts.collect()
--- End diff --
That is the worst case. We should assume that the number of frequent
patterns are small. Having 1 billion frequent patterns doesn't provide any
useful insights. So users should start with a high `minSupport` and collect
just-enough number of frequent patterns.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
