非頻繁模式

非頻繁模式，是一個(gè)項(xiàng)集或規(guī)則，其支持度小于閾值minsup.
絕大部分的頻繁模式不是令人感興趣的，但其中有些分析是有用的，特別是涉及到數(shù)據(jù)中的負(fù)相關(guān)時(shí)，如一起購(gòu)買DVD的顧客多半不會(huì)購(gòu)買VCR，反之亦然，這種負(fù)相關(guān)模式有助于識(shí)別競(jìng)爭(zhēng)項(xiàng)(competing item)，即可以相互替代的項(xiàng)。

某些非頻繁模式也可能暗示數(shù)據(jù)中出現(xiàn)了某些罕見(jiàn)事件或例外情況。如，如果{火災(zāi)=yes}是頻繁的，但是{火災(zāi)=yes，警報(bào)=on}是非頻繁的，則后者是有趣的非頻繁模式，因?yàn)榭赡苤赋鰣?bào)警系統(tǒng)出問(wèn)題，為了檢測(cè)這種情況，可以確定模式的期望支持度，當(dāng)模式支持度小于期望支持度時(shí)，表明其實(shí)一個(gè)有趣的非頻繁模式。

挖掘非頻繁模式的主要問(wèn)題是：

如何識(shí)別有趣的非頻繁模式。

如何在大數(shù)據(jù)集中有效地發(fā)現(xiàn)它們。

負(fù)模式

設(shè)???????

是項(xiàng)的集合。負(fù)項(xiàng) ????? 表示項(xiàng) ??? 不在給定事務(wù)中出現(xiàn)。如事務(wù)不包含咖啡，則 咖啡???

是一個(gè)值為1的負(fù)項(xiàng)。

負(fù)項(xiàng)集，負(fù)項(xiàng)集X是一個(gè)具有如下性質(zhì)的項(xiàng)集：（1）???

，其中A是正項(xiàng)的集合，而 ??? 是負(fù)項(xiàng)的集合， ??? ；（2） ?

。

負(fù)關(guān)聯(lián)規(guī)則，（1）規(guī)則是從負(fù)項(xiàng)集中提取的，（2）規(guī)則支持度大于或等于minsup，（3）規(guī)則的置信度大于或等于minconf。

負(fù)項(xiàng)集和負(fù)關(guān)聯(lián)規(guī)則稱為負(fù)模式（negative pattern）。負(fù)關(guān)聯(lián)規(guī)則的一個(gè)例子是茶咖啡???

。

負(fù)相關(guān)模式

用???????

表示k-項(xiàng)集，P(X)表示事務(wù)包含X的概率。在關(guān)聯(lián)分析中，這個(gè)概率通常用項(xiàng)集的支持度s(X)估計(jì)。

負(fù)相關(guān)項(xiàng)集 項(xiàng)集X是負(fù)相關(guān)的，如果

????????????
其中 ??? 是項(xiàng) ???

的支持度。s(X)是給出了X的所有項(xiàng)統(tǒng)計(jì)獨(dú)立的概率估計(jì)。如果它的支持度小于使用統(tǒng)計(jì)獨(dú)立性假設(shè)計(jì)算出的期望支持度。s(X)越小，模式就越負(fù)相關(guān)。

負(fù)相關(guān)關(guān)聯(lián)規(guī)則，規(guī)則?

是負(fù)相關(guān)的，如果
?
其中 ?，這里定義的X和Y中的項(xiàng)的負(fù)相關(guān)部分條件，負(fù)相關(guān)的完全條件為
?????????
其中 ??? 而 ??? 。因?yàn)閄或Y中的項(xiàng)通常是正相關(guān)的，因此使用部分條件而不是完全條件來(lái)定義負(fù)相關(guān)關(guān)聯(lián)規(guī)則更實(shí)際。如規(guī)則
眼鏡，鏡頭清潔劑隱形眼鏡，鹽溶液?

是負(fù)相關(guān)的，但是其中項(xiàng)集內(nèi)的項(xiàng)之間是負(fù)相關(guān)的，眼鏡盒鏡頭清潔劑是負(fù)相關(guān)的，如果使用完全條件，可能就不能發(fā)現(xiàn)該規(guī)則了。

負(fù)相關(guān)條件也可以用正項(xiàng)集和負(fù)項(xiàng)集的支持度表示
(不知道為什么博客園的markdown不支持多行公式？在其他地方都可以的，如果知道怎么做的希望能告知~~)

可以得到負(fù)相關(guān)的條件為

?????????

負(fù)相關(guān)項(xiàng)集和負(fù)相關(guān)關(guān)聯(lián)規(guī)則統(tǒng)稱為負(fù)相關(guān)模式（negatively correlated pattern）

非頻繁模式、負(fù)模式和負(fù)相關(guān)模式比較

根據(jù)上面的定義，我們得到，非頻繁模式與負(fù)相關(guān)模式只涉及包含正項(xiàng)的項(xiàng)集或模式，而負(fù)模式涉及包含正項(xiàng)和負(fù)項(xiàng)的項(xiàng)集或模式。

挖掘有趣的非頻繁模式技術(shù)

非頻繁項(xiàng)集是未被的頻繁項(xiàng)集產(chǎn)生算法如Apriori或FP所提取的有所項(xiàng)集，如下面邊界下的那些項(xiàng)集

非頻繁模式的數(shù)量可能是指數(shù)的，挖掘非頻繁模式主要是為了挖掘那些有趣的非頻繁模式。可以通過(guò)刪除那些不滿足負(fù)相關(guān)條件的非頻繁項(xiàng)集得到。但是與挖掘頻繁項(xiàng)集的支持度度量不同，挖掘負(fù)相關(guān)項(xiàng)集使用的基于相關(guān)性的度量不具有用于指數(shù)搜索空間剪枝的反單調(diào)性，因而計(jì)算量很大。

基于挖掘負(fù)模式的技術(shù)

使用負(fù)項(xiàng)增廣，將事務(wù)數(shù)據(jù)二元化，把原始數(shù)據(jù)變成具有正項(xiàng)和負(fù)項(xiàng)的事務(wù)。對(duì)增廣的事務(wù)使用已有的頻繁項(xiàng)集生成算法。可以導(dǎo)出所有的負(fù)項(xiàng)集。
（下面的右表中B和D兩項(xiàng)標(biāo)好像錯(cuò)了，應(yīng)為???

和 ???

）

如果只有少量變量被視為對(duì)稱的二元變量時(shí)，該方法可行的，但是如果很多項(xiàng)，則會(huì)出現(xiàn)一些問(wèn)題

數(shù)據(jù)集翻倍

引入負(fù)項(xiàng)后，會(huì)出現(xiàn)?

和 ???

，其中必有一個(gè)項(xiàng)的支持度超過(guò)50%，因而導(dǎo)致使用基于支持度剪枝策略算法時(shí)，頻繁項(xiàng)集的數(shù)量將呈指數(shù)增長(zhǎng)。

增加負(fù)項(xiàng)后，事務(wù)的寬度增加，將會(huì)增加候選項(xiàng)集的數(shù)量，很多算法都不能使用。

前面的方法是蠻力計(jì)算方法，代價(jià)很高，因?yàn)槠仁刮覀兇_定大量正模式和負(fù)模式的支持度。另一種方法不是用負(fù)項(xiàng)集增廣數(shù)據(jù)集，而利用正項(xiàng)集來(lái)計(jì)算負(fù)項(xiàng)集的支持度。如

?????
通常項(xiàng)集 ? 的支持度可以
????????

可以用其他的方法來(lái)進(jìn)一步提高算法性能，僅桑y頻繁時(shí)，???

才是有趣的。稀有項(xiàng)易于產(chǎn)生非頻繁項(xiàng)集。

基于支持度期望的技術(shù)。

僅當(dāng)非頻繁模式的支持度顯著小于期望支持度時(shí)，才認(rèn)為是有趣的，期望支持度根據(jù)統(tǒng)計(jì)獨(dú)立性假設(shè)計(jì)算。使用概念分層和基于近鄰的方法，稱作間接關(guān)聯(lián)。

1. 基于概念分層的支持度期望

僅用客觀度量還不足以刪除不感興趣的非頻繁模式。如面包和臺(tái)式機(jī)是不同的產(chǎn)品類，他們的支持度較低，但是他們不是有趣的非頻繁模式，因而需要使用領(lǐng)域知識(shí)裁剪不感興趣的項(xiàng)。

假定{C, G}是頻繁的，用s(.)表示模式的實(shí)際支持度，?

表示期望支持度。則
???????
????
????

2. 基于間接關(guān)聯(lián)的支持度期望
商品(a, b)，如果是不相關(guān)商品，則預(yù)期支持度較低，如果是相關(guān)的商品，預(yù)期支持度較高。上面使用概念分層來(lái)計(jì)算期望支持度，下面使用另外一種方法：通過(guò)考察與這兩個(gè)商品一起購(gòu)買的其他商品。

間接關(guān)聯(lián)，一對(duì)項(xiàng)a，b是通過(guò)中介集間接關(guān)聯(lián)的，如果下列條件成立
（1）???

（項(xiàng)對(duì)支持度條件）
（2） ?

使得

(a) ???

并且 ???

（中介支持度條件）

(b) ?????

，其中d(X, Z)是X和Z之間關(guān)聯(lián)的客觀度量 （中介依賴條件）

中介支持度和依賴條件確保Y中的項(xiàng)形成a和b的近鄰。可以使用興趣因子、余弦或其他依賴度量。

進(jìn)階關(guān)聯(lián)有很多應(yīng)用，如a和b可能是競(jìng)爭(zhēng)商品。文本挖掘中可以識(shí)別同義詞和反義詞。

總結(jié)

以上是生活随笔為你收集整理的数据挖掘之关联分析七（非频繁模式）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。