Data mining(2)

Definition:

• Itemset: 包含一個或多個item的set。包含k個item的itemset被稱為k-itemset。
• Support count(s): 資料庫中某個itemset出現的次數。
• Support: 資料庫中某個itemset出現的佔比。
• Frequent itemset: 某個itemset其support高於minsup即稱為frequent itemset

Association rule則是一個implication expression，以X->Y的形式表達，其中X和Y是itemset。

那麼support即為X和Y同時出現的佔比。

confidence則是Y在有X的transactions中的佔比。(也就是成功預測的佔比)

Association rule mining，即是要從一組transactions中，找出所有support大於minsup和confidence大於minconf的association rule。

同一個itemset可以binary partititon成許多不同rules，但他們的support會是相同的，confidence不同。

因此mining可分成兩個步驟: 先找出frequent itemsets，也就是所有support大於minsup的itemsets，接著再從這些set中找出high confidence rules。找出frequent itemsets仍然需要很多計算時間。

資料庫中有n個item，就可能有2^n個itemset(也就是n的powerset!)。

如果要檢查某個itemset在transactions中出現幾次，是很不切實際的，因為長度為d的itemset其可能的排列順序有2^d個。

Apriori principle: 如果某個itemset為frequent，那麼其subset也必為frequent。

如果找到某個itemset為infrequent，那麼其superset也必為infrequent。

Apriori algorithm?

Apriori algorithm透過每次找出長度為k的frequent itemsets Fk, 來找出更長的frequent itemsets Lk+1，詳細算法請看課本。

由Apriori algorithm產生出的frequent itemsets就能用來找association rule。

我們希望rule A->B的confidence大於minconf，這樣才是合格的rule。而confidence的算法是: support_count(A交集B) / support_count(A)，也就是所有A出現的transaction中，B也出現的機率。
Candidate的generation: 從Fk(長度為k的frequent itemsets)產生出Lk+1(長度為k+1的candidates)。方式是: 如果有兩個itemsets其有相同且長度為k-1的prefix，例如說ABC和ABD，則將他們merge為長度為k的itemset ABCD。

某些因素會影響association rule mining的複雜度:

• Minsup: 較低的minsup會產生更多的frequent itemsets。可能會增加frequent itemsets的max length和candidate的數量。
• Dimensionality: 需要有更多空間去儲存itemset的count。如果frequent itemset的數量增加，那麼計算量和I/O需求的資源都會增加。
• Size of database
• Average transaction width: 可能會增加frequent itemsets的max length。

Redundant itemsets: 某些itemset是多餘的，因為它們和它們的supersets有相同的support。
例如說，如果ABCDE這個資料重複了五次，且其他transaction都沒有出現ABCDE這些items，則只要計算ABCDE這個itemset的support就好，因為其所有的subsets(有2^5個!)都和ABCDE有相同的support。

Maximal frequent itemset: 如果某個frequent itemset的所有supersets都為infrequent，那麼這個itemset就稱為maximal frequent itemset。

Closed itemset: 如果某個itemset沒有任何immediate supersets(應該是指長度差距只有一的superset)和其有相同的support(應該說，均大於supersets的support，因為supersets的support衣錠比較小)，那麼這個itemset稱為closed itemset。

Frequent itemset包含closed frequent itemset，closed frequent itemset包含maximal frequent itemst。

ECLAT演算法: 將每個transactions改為用item出現在哪個TID中的方式來表達，然後再用交集的方式找出itemset的support。詳細算法請看講義。優點是計算support非常的快，但會占用大量的memory。

Frequent pattern growth 或FP-growth。

建置FP-tree

找出frequent itemset L之後，就要找出f使得f -> L - f滿足minimum confidence requirement。
也就是說把L分成兩部分，形成rules，並找出高confidence的rules。
長度為K的L會有2^k - 2個candidate assoication rules(去除掉其中一邊為empty set的情況)。

Rule generation也能應用Apriori algorithm。Confidence of rules generated from the same itemse擁有anti-monotone property。也就是說:
c(ABC ® D) ³ c(AB ® CD) ³ c(A ® BCD)

這應該是因為ABC的support一定比AB和A要來得低或相等。
也就是說，如果c(ABC ® D) 為low confidence rule，那麼在其之下的rules都可以被刪剪(prune)。

透過merging兩個有相同prefix的rule來產生新的candiate rule，例如: join(CD=>AB, BD=>AC)來產生D=>ABC。如果CD=>AB或BD=>AC為low confidence，那麼D=>ABC就可以被刪剪掉。

Minsup會造成的影響: 如果minsup過高，可能會miss某些較少出現的interesting rare items。如果minsup過低，frequent itemset數量可能會過多，計算量過高。
可以設置多個minsup!
給每個item都設置不同的minsup，那麼itemset的minsup即是最小的minsup值。
但這會造成support不再是anti-monotone。連帶的連Apriori algorithm也要修改。