【導(dǎo)讀】基本概念與解決方法。Apriori算法的性能瓶頸問題。對項目集格空間理論的發(fā)展。基于項目序列集操作的關(guān)聯(lián)規(guī)則挖掘算法。改善關(guān)聯(lián)規(guī)則挖掘質(zhì)量問題。在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項目集合或。對象集合之間的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計、聚集、分類等。護理用品(商店應(yīng)該怎樣提高護理用品的銷售？在產(chǎn)品直銷中使用附加郵寄。支持度,s,一次交易中包含{X、可信度,c,包含{X、Y}的交。關(guān)聯(lián)并不一定意味著相關(guān)或因果。至今仍活躍的研究方法之一。最早是由Agrawal等人提出的。最初提出的動機是針對購物。關(guān)聯(lián)規(guī)則的挖掘工作成果頗豐。，tn}是由一系列具有唯一標(biāo)識。在頻繁項目集中挑選出所有不被其他元素包。I2，并且它的可信度或信任度或臵信度。繁項目集中，尋找關(guān)聯(lián)規(guī)則。第1個子問題是近年來關(guān)聯(lián)規(guī)則挖掘算法研究的重。Agrawal等人建立了用于事務(wù)數(shù)據(jù)庫挖掘的項目集格空

　　

【正文】 屬性值區(qū)間； ? 若 Ai為分類屬性，則 u= v為分類屬性的一個屬性值，此時項目 Ai， u， v可以簡記為 Ai， u。 2020年 10月 5日星期一 60 ? 對數(shù)據(jù)集 D中的連續(xù)屬性 Ai，若其屬性值空間 [ui，vi]被劃分成為 n個子區(qū)間 [u1， v1]、 [u2， v2]、 …、[un， vn]，則屬性 Ai將產(chǎn)生 n個項目 Ai， u1， vAi， u2， v2]、 …、 Ai， un， vn。 ? 將連續(xù)屬性的屬性值空間劃分為若干個子區(qū)間并產(chǎn)生項目的過程稱為 連續(xù)屬性的離散化 。 2020年 10月 5日星期一 61 項目集的泛化與特化 ? 定義 326 設(shè) X?I是一個項目集，若 |X|=k則稱項目集為 k項目集 。項目集 X的屬性集合記為attribute（ X），即 attribute（ X） ={Ai|Ai∈A ，Ai， u， v∈X} 。 ? 對項目集 X和 X?，若 attribute（ X） = attribute（ X?），且對于任意 Ai∈attribute （ X），都有 { Ai ， u， v∈ X}∩{Ai， u? ， v? ∈ X?}≠Φ? u?uv v?， 則稱項目集 X?為 X的 泛化（ Generalization） ， X為 X?的 特化（ Specialization） 。 2020年 10月 5日星期一 62 項目集的支持度 ?定義 327 對 K項目集 X={A1， u1， v1， A2， u2，v2， …， Ak， uk， vk}和數(shù)據(jù)集 D中的記錄 T， T的 A1，A2， …， Ak屬性的屬性值為 TA1， TA2， …， TAk，若對所有的 i=1， 2， …， k，有 ui?TAi?vi，則稱記錄 T包含 在 K項目集 X中。 ?定義 328 數(shù)據(jù)集 D中包含在項目集 X的記錄數(shù)稱為項目集 X的支持?jǐn)?shù)，記為 ?x，項目集 X的 支持度 記作support（ X），并滿足關(guān)系： support（ X） = ?x/|D|?100%， 其中 |D|是數(shù)據(jù)集 D的記錄數(shù)。若 support（ X）不小于用戶指定的最小支持度，則稱 X為 頻繁項目集 （或大項目集），否則稱 X為非頻繁項目集（或小項目集）。 2020年 10月 5日星期一 63 關(guān)聯(lián)規(guī)則的置信度 ? 定義 329 若 X， Y為項目集，且 X∩Y= ?，蘊涵式 X?Y稱為數(shù)量關(guān)聯(lián)規(guī)則， X和 Y分別稱為 X?Y的前提和結(jié)論。項目集（ X?Y）的支持度稱為關(guān)聯(lián)規(guī)則 X?Y的支持度，記作support（ X?Y），其中 X?Y的含義是在數(shù)據(jù)庫中同時包含 X和 Y，即 support（ X?Y）＝ support（ X?Y）。數(shù)值關(guān)聯(lián)規(guī)則 X?Y的 臵信度 記作 confidence（ X?Y）：confidence（ X?Y） = support（ X?Y） /support（ X）?100%。 ? 定義 330 給定用戶的最小支持度 minsupport和最小臵信度minconfidence，如果 support（ X?Y） ≥ minsupport且confidence（ X?Y） ≥ minconfidence，則稱數(shù)量關(guān)聯(lián)規(guī)則X?Y為 強規(guī)則 。 2020年 10月 5日星期一 64 數(shù)量關(guān)聯(lián)數(shù)規(guī)則的分類 ? 根據(jù)數(shù)值屬性的處理方式，主要技術(shù)有： ? 數(shù)值屬性的靜態(tài)離散化： 數(shù)值屬性使用預(yù)定義的概念分層，在挖掘之前進行離散化，數(shù)值屬性的值用相應(yīng)的區(qū)間來替代。例如， ine的概念分層可以用于用區(qū)間值“ 0?20K” ，“ 21?30K” ，“ 31?40K” 來替換屬性原來的數(shù)值。 ? 數(shù)值屬性的動態(tài)離散化： 動態(tài)離散化過程需要考慮數(shù)據(jù)的關(guān)聯(lián)和程度，使用相應(yīng)的度量手段，如數(shù)據(jù)點之間的距離，來跟蹤數(shù)據(jù)的語意。 ? 基于特定的技術(shù)進行離散化： 常用的方法是根據(jù)數(shù)據(jù)的分布，將數(shù)值屬性離散化到“箱（ Bin）”。由于這些箱可能在挖掘過程中進一步組合，因此有動態(tài)的特征。離散化的動態(tài)體現(xiàn)在分區(qū)合并等過程中。三種常用的分箱策略是 等寬分箱、等深分箱和基于同質(zhì)的分箱 。 2020年 10月 5日星期一 65 ? 根據(jù)使用的規(guī)則模板，主要技術(shù)有： ? 復(fù)雜的挖掘模板形式： 類似于“ 數(shù)值屬性 ∩ 分類屬性 ?數(shù)值屬性∩ 分類屬性 ”這樣的規(guī)則。例如， sex=‘female’∩age∈[20 ，30] =wages∈[$5 ， $10]。這類規(guī)則較為復(fù)雜，是一般性的數(shù)量關(guān)聯(lián)規(guī)則。 ? 分類規(guī)則的挖掘模板： 簡單的挖掘模板形式類似于“ 數(shù)值屬性 ∩分類屬性 ?分類屬性 ”這樣的規(guī)則。例如， smoke=Yes∩age∈[60 ，80] =heartdesease=Yes。此類規(guī)則的左端通常表示的是數(shù)據(jù)庫的的幾個連續(xù)或分類屬性，右端則是一個預(yù)定義的類。這樣的模板很適合用于分類規(guī)則的挖掘。 ? 其他挖掘模板： 例如，挖掘模板形式類似于“分類屬性 ?數(shù)值屬性 ∩ 分類屬性”這樣的規(guī)則。這和第二類規(guī)則形式恰好相反，但對有些問題，這類規(guī)則非常有意義。 2020年 10月 5日星期一 66 數(shù)量關(guān)聯(lián)規(guī)則挖掘的一般步驟 ? 以 Boolean關(guān)聯(lián)規(guī)則算法及其理論為基礎(chǔ)，是解決數(shù)量關(guān)聯(lián)規(guī)則的挖掘問題的最有效途徑之一。較典型的數(shù)量關(guān)聯(lián)規(guī)則挖掘的主要步驟有： ? 1．對每個數(shù)值屬性進行離散化： 選取或設(shè)計合適的離散化算法，對數(shù)據(jù)庫中的所有數(shù)值屬性進行離散化。 ? 2．離散區(qū)間整數(shù)化： 對分類屬性或數(shù)值屬性的離散區(qū)間，將其值映射成連續(xù)的整數(shù)標(biāo)識。這樣做的目的是使數(shù)據(jù)歸整以利于挖掘。 ? 3．在離散化的數(shù)據(jù)集上生成頻繁項目集： 此步和前面介紹的生成頻繁項目集的步驟類似。 ? 4．產(chǎn)生關(guān)聯(lián)規(guī)則： 和前面介紹的方法類似。 ? 5．確定感興趣的 （ Interesting）關(guān)聯(lián)規(guī)則作為輸出 2020年 10月 5日星期一 67 數(shù)值屬性離散化問題 ? 數(shù)值屬性離散化是關(guān)鍵問題，處理不當(dāng)會帶來如下問題： ? 過小置信度問題 ：若區(qū)間的數(shù)目過少，則支持區(qū)間的元組數(shù)目增加，包含區(qū)間的強項目集的支持度上升，但在強項目集的子集支持度不變的情況下，將導(dǎo)致右端包含該子集的規(guī)則置信度下降，若不能達(dá)到置信度閾值，就會造成信息丟失。 ? 過小支持度問題 ：劃分的區(qū)間數(shù)目過多，則區(qū)間的支持度下降，不能有效的生成期望的頻繁項目集。 ? 離散化可能會把本來很緊密的數(shù)據(jù)分割開來，結(jié)果就會生成大量沒有意義的無用規(guī)則。 ? 離散化會帶來區(qū)間的組合爆炸 。假設(shè)某數(shù)值屬性劃分成 n個基區(qū)間，由于相鄰的兩個連續(xù)屬性又可以合并生成更大的區(qū)間，這樣反反復(fù)復(fù)的合并，最終的區(qū)間數(shù)目就有 O（ nn）個。所以具體離散化過程中必須有一種停機條件，當(dāng)區(qū)間合并到一定程度能夠自動停下來。離散區(qū)間的組合爆炸帶來的直接后果是算法效率低下，而且生成成千上萬條規(guī)則，用戶很難從中找到有趣的規(guī)則。 2020年 10月 5日星期一 68 主要的離散化方法 ? 現(xiàn)有的離散化方法主要有兩種策略： ? 歸并方法 ：開始將屬性的每個取值都當(dāng)作是一個離散的值，然后逐個反復(fù)合并相鄰的屬性值，直到滿足某種條件結(jié)束合并。 ? 劃分方法 ：將屬性的整個取值區(qū)間作為一個離散屬性，然后對該區(qū)間反復(fù)劃分成更小的區(qū)間，直到滿足某種條件結(jié)束劃分。 ? 較好的離散化方法通常是這兩種策略的結(jié)合，是動態(tài)劃分歸并的過程。 ? 目前最典型的數(shù)值屬性離散化方法主要有： ? 等寬度劃分 ? 等深度劃分 ? 基于距離的劃分 2020年 10月 5日星期一 69 等寬度劃分的方法 ? 等寬度劃分的方法是最簡單的離散化方法，一般適用分布比較均勻的數(shù)據(jù)。算法只要一次掃描數(shù)據(jù)庫，因此算法效率較高。等寬度劃分的方法單純從數(shù)學(xué)角度對數(shù)值屬性進行劃分，不考慮數(shù)據(jù)分布的特點。由于該方法比較直觀，比較適合數(shù)值屬性的前期處理，因此通常和聚類等方法結(jié)合，才能取得好的離散化效果。 算法 317 等寬度劃分算法描述 輸入：數(shù)值屬性 A， 區(qū)間數(shù) n。 輸出：離散后的區(qū)間 。 （ 1） 掃描數(shù)據(jù)庫 ， 得到 A的最大值 max（ A） 和最小值 min（ A） ； （ 2） 求區(qū)間的寬度 w， w=（ max（ A） min（ A）） /n。 （ 3） 形成離散后的區(qū)間 [l1， v1]， [l2， v2]， …[[ln， vn]輸出 ， 其中 li= min（ A） +（ i1） *w， vi= li+w。 2020年 10月 5日星期一 70 等深度劃分方法 ? 定義 331 若 A的取值區(qū)間在 [Xl， Ym]?？梢詫?A的取值區(qū)間分割為一系列不相交的域 Bi=[Xi， Yi]，其中 i=1， 2， …， m且 Xi≤Y i≤X i+1，稱 Bi為 A的一個桶（ Bucket），并稱 Bi中元組個數(shù)為桶的大小，記為 Ui。若兩個桶的大小相等，則稱它們?yōu)榈壬钔啊? ? 等深度劃分一般適用于屬性之間關(guān)聯(lián)度比較低的數(shù)據(jù)集。等深度劃分的方法趨向于把具有共性的、支持度很高的相鄰值劃分到不同的區(qū)間去。當(dāng)數(shù)據(jù)分布在某個點附近達(dá)到峰值時，等深度劃分這種機械的方法并不能反映出數(shù)據(jù)本身的特點，因此對高偏度的數(shù)據(jù)效果不理想。 算法 318 等深度劃分描述 輸入：數(shù)值屬性 A， 區(qū)間數(shù) （ 桶數(shù) ） n。 輸出：離散后的區(qū)間 。 （ 1） 數(shù)值屬性 A從小到大或從大到小排序； （ 2） 掃描數(shù)據(jù)庫 ， 統(tǒng)計數(shù)據(jù)庫的記錄數(shù) N； （ 3） 求桶的深度： h=N/n； （ 4） 逐個掃描排序后的 A值 ， 形成離散后的區(qū)間 [li， vi]（ i=1， 2， … n） ， 每個區(qū)間包含h個值 。 2020年 10月 5日星期一 71 基于距離的劃分的方法 ? 等寬度劃分的方法和等深度劃分的方法都沒有充分考慮數(shù)據(jù)的分布，單純從幾何和數(shù)學(xué)的角度對數(shù)值屬性進行劃分?；诰嚯x的離散化方法通過數(shù)據(jù)聚類方法形成數(shù)據(jù)區(qū)間。 算法 319基于距離的劃分 輸入：數(shù)值屬性 A， 區(qū)間的數(shù)目 k。 輸出：離散后的區(qū)間 [u1， v1]， [u2， v2]， … ， [uk， vk]。 （ 1） 從數(shù)值屬性 A任意選擇 k個不同的值作為初始的簇的中心； （ 2） REPEAT （ 3） 根據(jù)簇中 A的平均值 ， 將每個 A值 （ 重新 ） 賦給最類似的簇 （ 4） 更新簇的平均值 ， 即計算每個簇中 A值的平均值 （ 5） INTIL 不再發(fā)生變化 . 2020年 10月 5日星期一 72 第 3章 知識發(fā)現(xiàn)與關(guān)聯(lián)規(guī)則挖掘（ 二 ） 內(nèi)容提要 ? 基本概念與解決方法 ? 經(jīng)典的頻繁項目集生成算法分析 ? Apriori算法的性能瓶頸問題 ? Apriori的改進算法 ? 對項目集格空間理論的發(fā)展 ? 基于項目序列集操作的關(guān)聯(lián)規(guī)則挖掘算法 ? 改善關(guān)聯(lián)規(guī)則挖掘質(zhì)量問題 ? 約束數(shù)據(jù)挖掘問題 ? 關(guān)聯(lián)規(guī)則挖掘中的一些更深入的問題 ? 數(shù)量關(guān)聯(lián)規(guī)則挖掘方法 2020年 10月 5日星期一 73 Thank you !!!