愛(ài)華網(wǎng)第六章，F(xiàn)requentPattern，挖掘頻繁模式
（1）主要問(wèn)題是，尋找經(jīng)常在一起出現(xiàn)的itemset。有多經(jīng)常？使用約束指標(biāo)：支持度（support），置信度(confidence)。一些有意思的特性：如果一個(gè)itemset是frequent的，那么它的subset也是frequent的。由于subset實(shí)在太多了，我們引入closedfrequentitemset概念。
（2）算法Frequentpatternmining的算法：Apriori算法：先算size為1的頻繁itemsetL1，然后由L1構(gòu)建L2，再逐次往上構(gòu)建。其中，構(gòu)建Lk只需要L（k-1）就可以了。源于這么一個(gè)性質(zhì)：如果一個(gè)集合不能通過(guò)測(cè)試（足夠frequent），則它的所有超集也不能通過(guò)測(cè)試。這屬于一種反單調(diào)性（antimonotone）。這個(gè)算法看起來(lái)還是很直接很暴力的，但是它work而且makesense。原始的算法效率低，可以通過(guò)諸多方法優(yōu)化。一個(gè)性能更好的算法FrequentPatternGrowth（FPGrowth）。構(gòu)建頻繁模式樹(shù)，使用最不頻繁的項(xiàng)作后綴，降低搜索開(kāi)銷。
Apriori和FPGrowth都是使用水平數(shù)據(jù)集操作的，{Transaction_ID:itemset}。數(shù)據(jù)可以用另一種方向來(lái)表示：{item:Transaction_ID_Set}，右邊是所有包含這個(gè)item的transactions，稱為垂直數(shù)據(jù)格式，verticaldataformat。使用垂直數(shù)據(jù)格式也可以進(jìn)行frequentpatternmining，其中主要是進(jìn)行集合取交的運(yùn)算，為了提高效率，可使用差集的表示技術(shù)。
（3）模式評(píng)估只使用support和condifence會(huì)有誤導(dǎo)性。書(shū)中提出了更多的相關(guān)性度量：卡方，提升度，全置信度，最大置信度，Kluc，余弦。我們需要注意零事務(wù)（null-transaction），是不包含任何考察項(xiàng)的事務(wù)。有的度量指標(biāo)受零事務(wù)影響很大，不是null-invariant零不變量，全置信度，最大置信度，Kluc，余弦是null-invariant，卡方和提升度則不是。書(shū)中還引入了不平衡比。總之，由于大型數(shù)據(jù)集常有大量的null-transaction，所以我們要考慮零不變性，以上各種度量中，推薦Kluc和不平衡比配合使用。
愛(ài)華網(wǎng)本文地址 » http://www.klfzs.com/a/25101014/217175.html
