數(shù)據(jù)挖掘?qū)д摰?章-資料下載頁
2025-04-30 23:56本頁面
【正文】 的負項。 ? 定義 負項集 – 負項集 X是一個具有如下性質(zhì)的項集：（ 1） X=A∪ B，其中 A是正項的集合，而 B是負項的集合， |B|≥1。 （ 2）s(X) ≥ minsup。 ? 定義 負關(guān)聯(lián)規(guī)則 – 負關(guān)聯(lián)規(guī)則是一個具有如下性質(zhì)的關(guān)聯(lián)規(guī)則：（ 1）規(guī)則是從一個負項集提取的，（ 2）規(guī)則的支持度大于或等于 minsup，（ 3）規(guī)則的置信度大于或等于 minconf ? 本章中，負項集和負關(guān)聯(lián)規(guī)則統(tǒng)稱負模式 負相關(guān)模式 ? 定義 負相關(guān)項集 – 項集 X={x1,x2,…,xk} 是負相關(guān)的，如果 ? 定義 負相關(guān)關(guān)聯(lián)規(guī)則 – 關(guān)聯(lián)規(guī)則 X ?Y是負相關(guān)的，如果 s(X∪ Y)s(X)s(Y)，其中， X和 Y是不相交的項集，即 X ∩Y=162。 – 負相關(guān)的完全條件可以表述如下： )(...)()()()( 211 kkjj xsxsxsxsXs ????? ??????jjii ysxsYXs )()()(? 負相關(guān)條件也可以用正項集和負項集的支持度表示。設(shè) 和 分別表示 X和 Y的對應(yīng)負項集，由于 ? 負相關(guān)條件可以表述如下： ? 負相關(guān)項集和負相關(guān)關(guān)聯(lián)規(guī)則統(tǒng)稱負相關(guān)模式（ negatively correlated pattern） Y( ) ( ) ( )( ) [ ( ) ( ) ] [ ( ) ( ) ]( ) [ 1 ( ) ( ) ( ) ] ( ) ( )( ) ( ) ( ) ( )s X Y s X s Ys X Y s X Y s X Y s X Y s X Ys X Y s X Y s X Y s X Y s X Y s X Ys X Y s X Y s X Y s X Y??? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?? ? ? ? ? ?X)()()()( YXsYXsYXsYXs ?????非頻繁模式、負模式和負相關(guān)模式比較 ? 非頻繁模式、負模式和負相關(guān)模式是三個密切相關(guān)的概念。 ? 盡管非頻繁模式和負相關(guān)模式只涉及包含正項的項集或模式，而負模式涉及包含正項和負項的項集或模式，但是這三個概念之間存在一定的共性，如圖722所示 ? 首先，許多非頻繁模式有對應(yīng)的負模式。 ? 如果 x ∪ y是非頻繁的，則除非 minsup太高，否則它很可能有對應(yīng)的負項集。 ? 例如：假定 minsup，如果 x ∪ y是非頻繁的，則表中的其它幾種組合至少有一種是頻繁的。 y y x S(x∪ y) S(x∪ y) S(x) x S(x∪ y) S(x∪ y) S(x) S(y) S(y) 1 挖掘有趣的非頻繁模式的技術(shù) ? 原則上講，非頻繁項集是未被標(biāo)準的頻繁項集產(chǎn)生算法（如 Apriori和FP增長）提取的所有項集。這些項集對應(yīng)于圖 723所示的頻繁項集邊界之下的那些項集。 ? 由于非頻繁模式的數(shù)量可能是指數(shù)級的，特別是對于稀疏的、高維的數(shù)據(jù)。 ? 因此，為挖掘非頻繁模式而開發(fā)的技術(shù)著力于發(fā)現(xiàn)有趣的非頻繁模式。 ? 例如：負相關(guān)模式 基于挖掘負模式的技術(shù) ? 一種方法是將每個項看作對稱的二元變量。通過用負項增廣，將事務(wù)數(shù)據(jù)二元化。然后使用 Apriori算法等，可以導(dǎo)出所有的負項集。 ? 僅當(dāng)只有少量變量被視為對稱的二元變量時，該方法才是可行的。如果每個項都必須視為對稱的二元變量，則可能導(dǎo)致計算復(fù)雜度增加。 – (1)當(dāng)每個項都用對應(yīng)的負項增廣時，項的個數(shù)就加倍。待探測的項集格比 2d大得多。 – (2)當(dāng)增加進負項后，基于支持度的剪枝不再有效。對于每個變量 x， x或 的支持度大于等于 50%.因此，即使支持度閾值達到 50%，仍有一半的項是頻繁的。 – (3)當(dāng)增加進負項后，每個事務(wù)的寬度增加。當(dāng)包含負項后，事務(wù)的寬度增加到 d。 x? 另一種方法不是用負項增廣數(shù)據(jù)，而是根據(jù)對應(yīng)的正項集計算負項集的支持度。例如， 的支持度可以用如下方法計算： ? },{ rqp}),({}),({}),({})({}),({ rqpsrpsqpspsrqps ????? ???????????niiZYZi ZXsXsXs1||,)}()1{()()Y( YX 到：的支持度可以用下式得更一般地，項集基于支持度期望的技術(shù) ? 該方法要求僅當(dāng)非頻繁模式的支持度顯著小于期望支持度時，才認為它是有趣的。 ? 本節(jié)介紹兩種計算期望支持度的方法。 – 基于概念分層的支持度期望 – 基于間接關(guān)聯(lián)的支持度期望 ? 計算期望支持度的一種方法是利用概念分層來推導(dǎo) ? 例如：由于火腿和熏肉屬于相同的產(chǎn)品族，我們預(yù)期火腿和薄片食物之間的關(guān)聯(lián)與熏肉和薄片食物之間的關(guān)聯(lián)類似。 ? 如果任何一對的真實支持度小于期望支持度，則非頻繁模式是有趣的。 計算期望支持度的公式 ? 假定項集 {C， G}是頻繁的。用 s(． )表示模式的實際支持度，而表示 ε (.)期望支持度。 C和 G的子女或兄弟的期望支持度可以用如下公式計算： )()(),()),(()()(),()),(()()()()(),()),((GsHsGCsHCsGsJsGCsJCsGsJsCsEsGCsJEs??????????? 節(jié)食碳酸飲料和薄片食物的期望支持度可以使用公式（ 78）計算。因為這兩項分別是碳酸飲料和點心的子女。 ? 如果節(jié)食碳酸飲料薄片食物的實際支持度明顯低于它們的期望值，則節(jié)食碳酸飲料和薄片食物形成一個有趣的非頻繁模式。 基于間接關(guān)聯(lián)的支持度期望 ? 本節(jié)提供一種確定商品對期望支持度的方法：考察通常與這兩個商品一起購買的其他商品。 ? 假定節(jié)食和普通碳酸飲料都經(jīng)常與薄片食品和點心一起購買。這兩種商品可望是相關(guān)的，并且它們的支持度應(yīng)當(dāng)較高。 ? 因為他們的實際支持度低，節(jié)食和普通碳酸飲料形成了一個有趣的非頻繁模式。這樣的模式稱作間接關(guān)聯(lián)（ indirect association）模式。 ? 間接關(guān)聯(lián)的一個高層解釋見圖 727。項 a和 b對應(yīng)于節(jié)食和普通碳酸飲料，而 Y稱作中介集（mediator set），包含諸如薄片食物和點心等商品。間接關(guān)聯(lián)形式定義在下面給出。 ? 定義 間接關(guān)聯(lián) – 一對項 a， b是通過中介集 Y間接關(guān)聯(lián)的，如果下列條件成立： – (1)s({a,b})ts（項對支持度條件） – ? 中介支持度和依賴條件用來確保 Y中的項形成 a和 b的近鄰?？梢允褂?、余弦或 IS、 Jaccard和其他依賴度量。 中介依賴條件）之間關(guān)聯(lián)的客觀度量和是其中）（（中介支持度條件）并且）（使得：(ZX),(,)},({,)},({b )}({)}({a )2(ZXdtYbdtYadtYbstYasYddff???????? ?? 間接關(guān)聯(lián)可以用如下方法產(chǎn)生。首先，使用諸如Apriori和 FP增長等標(biāo)準算法產(chǎn)生頻繁項集。然后，合并每對頻繁 k項集得到候選間接關(guān)聯(lián) (a,b,Y)，其中 a和 b是一對項，而 Y是它們的公共中介。 ? 例如， {p,q,r}和 {p,q,s}是頻繁 3項集，則通過合并這對頻繁項集得到候選間接關(guān)聯(lián) (r,s,{p,q})。 ? 一旦產(chǎn)生候選，就要驗證它是否滿足定義 項對支持度和中介依賴條件。 ? 中介支持度條件不必驗證，因為候選間接關(guān)聯(lián)是通過合并一對頻繁項集得到的。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1