酔っぱらいながらアプリオリアルゴリズムを書いてみた

 
Aprioriアルゴリズム:ここでは頻出アイテム集合だけを発見する.「アプリオリアルゴリズム」で検索して上に出てきた2つのページをリンクします.
~アプリオリアルゴリズム・極大頻出アイテム集合~
データマイニング
酔っ払ってるし,よく分からん型作ってるね.あとItemMax決め打ちかよ.
 

object Main {
  def main(args: Array[String]): Unit = {
    val set = Mining.apriori("database.txt", 3)		
    println(set)
  }
}

object Mining {
  import scala.io.Source
  type LDB = List[Set[Int]]
  type SDB = Set[Set[Int]]
  val ItemMax = 9
  def apriori(filename: String, th: Int): SDB = {
    val lines = Source.fromFile(filename).getLines.toList
    val database = lines.map{_.split(" ").toList.map(_.toInt).toSet}

    // Calculate all occurrences of 
    val size1 = (1 to ItemMax).toList.
    map(Set(_)).filter( i => count(database, i) >= th)

    // Generate candidates of length k+1 from those of length k
    def growth(k: Int, Sk: LDB): (LDB, LDB) = {
      val candidates = collection.mutable.ListBuffer[Set[Int]]()
      for (S1 < - Sk) {
        for (S2 <- Sk if S1 != S2
             && (S1 ++ S2).size == k+1
             && !candidates.contains(S1 ++ S2)) {
              candidates.append(S1 ++ S2)
        }
      }
      val frequentCandidates = candidates.filter( count(database, _) >= th)
      (candidates.toList, frequentCandidates.toList)
    }

    def _apriori(k: Int, C: LDB, S: LDB): LDB = {
      if (C.isEmpty) return S
      else {
        val (nC, nS) = growth(k, S)
        return S ++ _apriori(k+1, nC, nS)
      }
    }

    // Calculate until no such candidates are generated
    val frequentItemsets = _apriori(1, size1, size1)
    frequentItemsets.toSet
  }

  def count(db: List[Set[Int]], itemset: Set[Int]): Int = {
    db.filter( itemset.subsetOf(_) ).length
  }
}

database.txtの中身は以下のとおり.
1 2 5 6 7 9
2 3 4 5
1 2 7 8 9
1 7 9
2 3 7 9

たぶん動いた気がする(震え声)

1件のコメント

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です