Top-K HUIsアルゴリズムの比較分析
はじめに
項目効用は、内部効用と追加効用に分けられます［］。しかし、新たな問題が生じました。それは、以前のFIMモデルの特徴である下方終結は、項目セットモデルの効率的な使用には適用できないということです。なぜなら、数量と利益の変化に伴って、個々の財の効用値は不規則な変化を示すからです。そこで、反単調性の考え方を利用する他の方法はないでしょうか？その後、Transaction Weighted Utilisation (TWU) という新しい概念が提案されました[]。
しかし、アイテムセットを用いた効率的なパターンマイニングには大きな欠点があります。この現象はWu-guided TKUアルゴリズムの文献で以下のように分析されていることが論文で述べられています：
ここまでくると、アイテム集合を使った効率的なパターン・マイニングを行うためには、妥当な閾値を設定することが大きな課題となります[]。
これに続いたのが、Top-Kマイニングモデルを考案した学者たちです[]。
最後に、本論文の目的を紹介します：トップk高有用度アイテムセットマイニングの現在のトレンドと将来の方向性を探ることです。
背景知識と問題の説明
このセクションでは、用語とは何か、トランザクション用語とは何か、なぜTWU< />なのかといった定義や特性に焦点を当てます。
トップK高効用マイニングに向けて
この部分が焦点で、実際、HUI関連のアルゴリズムを学習する過程でも理解することができ、最初の発展はHUI-Minerのような2ステップのアルゴリズムから、EFIMのような後の1ステップのアルゴリズムまで、top-kの発展は実際同じで、文献も主にこの観点からです：
Two-Phase
TKU、REPTなどのアルゴリズムに代表されます。
TKU
このアルゴリズムは非常に早い時期に提案され、その文献は2012年にCheng Wei Wu, Bai-En Shie, Philip S. Yu, Vincent S. Tsengという偉大な頭脳によって発表されました。プロセスの最初のステップでは、アルゴリズムはUP-Tree構造を構築し、潜在的にk個の高ユーティリティアイテムのセットを生成します。PKHUIは、トップkのHUIを選択するために、5つの異なる閾値自己増加戦略が提案されています。
PE戦略：
主に閾値の自己増殖を構築するための事前評価行列を介して、戦略は、UP-Treeの構築の前に選択され、その目的は、計算プロセスの構築を開始する閾値として0にUP-Treeを避けるために、水平方向と垂直方向に行列から構築されたバイナリアイテムセットに値を割り当てることです。そして、ブースティング後にk番目に大きい値を閾値として選択します[]：
NUの戦略：
UP-Treeに少なくともk個のノードが存在し、k番目のノードの効用値が現在設定されている閾値よりも大きい場合、このペアはk番目のノードの効用値を新しい閾値に設定します。
MD戦略：
UP-Treeを構築した後、ルートノードの下にある異なる子ノードを結合し、それらのmiu(X)値を求め、これらの下界値の中からk番目の値を選び、それが現在の閾値より大きければ閾値を更新し、そうでなければ何も行いません。
MC戦略：
k番目のアイテムセットの最小値が現在のしきい値より大きいかどうかを比較し、大きくない場合はスキップします。
SE戦略：
第2ステップでは、ヒープ構造が候補アイテムセットを格納するために利用され、設定されたしきい値を取るために大きな効用値を持つアイテムセットに優先権が与えられます。
上記はあまり詳細ではなく、UP-Treeの主な構造を理解することに集中する必要があります。また、UP-Growthの文献に記載されていない、他の4つの刈り込み戦略が設計されています。
REPT
このアルゴリズムは2015年にHeungmo Ryang, Unil Yunによって発表されたもので、TKUアルゴリズムと非常によく似ており、PMUDを用いて、二項集合の最初の項が外部効用の値が最大となる取引集合の項となるように選択される点と、4つの自己増加戦略がある点が異なります。
PUD戦略
バイナリアイテムセットの下界値はPMUD行列を用いて構築され、PMUD行列に少なくともk個のアイテムセットが存在する場合、k番目に大きい効用値の置換が閾値に対して実行されます。目的はPE戦略と同じで、UP-Treeの構築効率を向上させることです。
RIU
RSD戦略
バイナリアイテムセットの正確な効用情報を格納するために使用され、この行列は各アイテムのサポートに基づいて、N/2の最も高いサポートとN/2の最も低いサポートが選択され、置換の考え方はPUD戦略と同じです。
SEP戦略
はSE戦略のPLUSバージョンで、予測値ではなく正確な値を使って閾値を引き上げます。
元記事では、REPTアルゴリズムの計算思想も簡単に説明していますが、元のREPTアルゴリズムへのリンクはです。データセットの最初のスキャンでは、TKUのように予測値を使用するのではなく、実ユーティリティを使用して閾値を自己増加させます。同時に木構造を構築する2回目のスキャンでは、TKUと非常によく似たRSD戦略を使用して閾値を自己増加させます；次の図は、REPTアルゴリズムとTKUアルゴリズムが実際の運用で採用する戦略の違いを示しています：
One-Phase
TKO、KHMCなどのアルゴリズムに代表されます。
TKO
TKOアルゴリズムとTKUアルゴリズムは同じ論文で提案されました。HUI-Minerアルゴリズム以来、アイテムのソートは非常に重要な部分となっています。TKOアルゴリズムもHUI-Minerアルゴリズムの設計思想を借用しており、候補集合の代わりにユーティリティリスト構造を使用しています。
このアルゴリズムはまた、データセットの最初のスキャンの間に閾値を自己増加させるためにPE行列構造を使用し、2回目のスキャンは単項目のリストを構築するために開始され、その間に、DGU刈り込み戦略で導入された特性を使用して、低ユーティリティ項目がフィルタリングされ、各トランザクション内の項目が事前にランク付けされます。その後、単項目のリストに対して2対2の マージ 操作を行うことで、アイテムセットのバイナリリストが構築されます。2回目のスキャン処理では、k個の実用性の高いアイテムセットを格納する小さなルートヒープが構築され、閾値が変化する度にヒープの先頭要素が取られ、ヒープの調整によりヒープノードが追加・削除されます。閾値の自己追加戦略と検索空間を刈り込むために、3つの新しい戦略が用いられます。
RUC戦略
TopK-CI-Listヒープ構造を使用して、閾値はヒープの先頭の値と直接比較され、もしそれが小さければ置き換えられます。
RUZ戦略
NZEU(X)は、項目集合XのすべてのNZ要素のiutilsの和と定義されます。NZEU(X) + RU(X) < minUtil のとき、項目集合Xのすべての上位集合はトップk HUIでないと判断できます。
EPB戦略
この戦略の目的は、効率的に使用される候補の集合を優先的に生成することです。なぜなら、期待効用値が最大の項を最初に展開することで、効率的に使用される値が得られる可能性が高くなるため、minUtilを早期に増加させることができ、その結果、探索空間をより多く刈り込むことができるからです。
KHMC
2016年にQuang-Huy Duongらはこのアルゴリズムを発表しました。データセットの最初のスキャンでは、各アイテムの効用値とTWUが計算され、次にRIU戦略を用いて閾値が引き上げられます。データセットの2回目のスキャンでは、EUCST、CUDM、Utility-Listなどのデータ構造がそれぞれ構築されます。EUCSTはアイテムセットのTWU値を格納するために使用されるハッシュマップデータ構造であり、CUDMはアイテムセットのユーティリティ値を格納します。
CUD戦略
データセットの2回目のスキャンが終わると、minUtilが引き上げられ、再びCUDMに保存されているk番目の効用値を使用して、現在の閾値と比較されます。
COV戦略
項目xの拡張セットが項目yの拡張セットのサブセットである場合、項目yは項目xのオーバーレイとして使用することができます。このメソッドは、その拡張バイナリ項目セットの効用値を推定するためにモナド項目に焦点を当て、同様に、この効用値は、現在のしきい値を上げるために使用することができます。
RIU
RUC
Top-Kアルゴリズム間の比較
次の図は、現在のtop-kアルゴリズムの自己追加戦略をまとめたものです：
次の図は、現在のtop-kアルゴリズムの刈り込み戦略をまとめたものです：
元論文では、異なるデータセットの場合、TKOとKHMCアルゴリズムの違いも検証しています。
- Srikumar Krishnamoorthy: A comparative study of top-k high utility itemset mining methods-
- Cheng Wei Wu, et al(1)閾値引き上げと刈り込み戦略を用いたトップK高効用アイテムセットのマイニング(2)Quang-Huy Duong, et al.
- Heungmo Ryang, Unil Yun閾値引き上げ戦略を用いたTop-k高効用パターンマイニング- Quang-Huy Duong, et al.
- Quang-Huy Duong, et alをマイニングするための効率的なアルゴリズム。, using novel threshold raising and pruning strategies-
