3.31 lcm : LCM over ZDD

書式

$obj$ .lcm( $type,transaction,minsup[,order,ub]$ ) $\rightarrow$ $zdd$

$transaction$ : string

$type$ : string

$minsup$ : integer

$order$ : string

$ub$ : integer

説明

$transaction$ で指定されたトランザクションファイルから、LCM over zdd アルゴリズムを利用し、指定された最小サポート $minsup$ 以上の頻出パターンを列挙しそのZDDオブジェクト $zdd$ を返す。 $order$ でZDDのアイテムオーダファイルを指定し、 $ub$ で列挙するアイテム集合のサイズの上限を与える。

列挙する頻出パターンの種別は $type$ で与え、"F"(頻出アイテム集合) ,"M"(極大アイテム集合),"C"(飽和アイテム集合)の三種類が指定できる。また"FQ"のように、"Q"を付けると、列挙された各頻出アイテム集合に頻度を重みとして出力する。 "Q"をつけなければ、最小サポート条件を満たす頻出アイテム集合のみ出力され、頻度情報は省かれる。

トランザクションファイルは、以下に示すようなテキストファイルで、一つの行が一つのトランザクションに対応しており、アイテムは1から始まる連番で指定し、アイテムの区切りには半角スペースを用いる。アイテムとしてアルファベットを利用することはできない。

$order$ ファイルは、ZDDのアイテムオーダ表に登録するアイテムの順序を示したテキストファイルである。通常は、以下のように、トランザクションデータに含まれる全アイテムを番号順に並べて与える。またトランザクションのアイテム番号に欠番があった場合でも、その欠番を含めて指定する必要があることに注意する。

1 2 3 4 5 6

$order$ ファイルは省略する(もしくはnilを指定する)ことができるが、その場合、効率性のためにアイテムオーダはLCMの内部アルゴリズムによって決まる。しかし、この方法を利用すると、そのオーダに応じてアイテム番号が再び採番されるため、出力されるZDDの頻出アイテム集合におけるアイテム番号は、元のトランザクションの番号とは異なったものとなる。アイテムの内容に関係のない解析をするのであれば、 $order$ を省略することで計算効率は高まるが、逆に、アイテムの内容についての意味を解析する目的があるのであれば、上記に示した連番としてのオーダファイルを指定する。

$ub$ には列挙される頻出アイテム集合のサイズの上限を指定する。指定を省略するか、nilを与えると上限なしに列挙する。

例

例1: 基本例

> require 'zdd'
# tra.txtの内容
# 1 2 3 6
# 4 5 6
# 1 2 4 6
# 2 4 6
# 1 2 4 5
# order.txtの内容
# 1 2 3 4 5 6
> p1=ZDD::lcm("FQ","tra.txt",3,"order.txt")
> p1.show
 3 x6 x4 + 3 x6 x2 + 4 x6 + 3 x4 x2 + 4 x4 + 3 x2 x1 + 4 x2 + 3 x1 + 5

# オーダファイルを省略した場合、得られる頻出アイテム集合は同じであるが
# そのアイテム番号がトランザクションファイルのアイテム番号と異なったものとなることに注意する。
> p2=ZDD::lcm("FQ","tra.txt",3)
> p2.show
 3 x4 x1 + 3 x4 + 3 x3 x2 + 3 x3 x1 + 4 x3 + 3 x2 x1 + 4 x2 + 4 x1 + 5

3.31 lcm : LCM over ZDD

書式

説明

例

例1: 基本例

関連