【正文】 （ 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的改進(jìn)算法 ? 對項目集格空間理論的發(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 !!! 。 算法 319基于距離的劃分 輸入：數(shù)值屬性 A， 區(qū)間的數(shù)目 k。 2020年 10月 5日星期一 71 基于距離的劃分的方法 ? 等寬度劃分的方法和等深度劃分的方法都沒有充分考慮數(shù)據(jù)的分布，單純從幾何和數(shù)學(xué)的角度對數(shù)值屬性進(jìn)行劃分。 輸出：離散后的區(qū)間 。當(dāng)數(shù)據(jù)分布在某個點附近達(dá)到峰值時，等深度劃分這種機械的方法并不能反映出數(shù)據(jù)本身的特點，因此對高偏度的數(shù)據(jù)效果不理想。 ? 等深度劃分一般適用于屬性之間關(guān)聯(lián)度比較低的數(shù)據(jù)集?？梢詫?A的取值區(qū)間分割為一系列不相交的域 Bi=[Xi， Yi]，其中 i=1， 2， …， m且 Xi≤Y i≤X i+1，稱 Bi為 A的一個桶（ Bucket），并稱 Bi中元組個數(shù)為桶的大小，記為 Ui。 （ 3） 形成離散后的區(qū)間 [l1， v1]， [l2， v2]， …[[ln， vn]輸出 ， 其中 li= min（ A） +（ i1） *w， vi= li+w。 輸出：離散后的區(qū)間 。由于該方法比較直觀，比較適合數(shù)值屬性的前期處理，因此通常和聚類等方法結(jié)合，才能取得好的離散化效果。算法只要一次掃描數(shù)據(jù)庫，因此算法效率較高。 ? 較好的離散化方法通常是這兩種策略的結(jié)合，是動態(tài)劃分歸并的過程。 2020年 10月 5日星期一 68 主要的離散化方法 ? 現(xiàn)有的離散化方法主要有兩種策略： ? 歸并方法 ：開始將屬性的每個取值都當(dāng)作是一個離散的值，然后逐個反復(fù)合并相鄰的屬性值，直到滿足某種條件結(jié)束合并。所以具體離散化過程中必須有一種停機條件，當(dāng)區(qū)間合并到一定程度能夠自動停下來。 ? 離散化會帶來區(qū)間的組合爆炸 。 ? 過小支持度問題 ：劃分的區(qū)間數(shù)目過多，則區(qū)間的支持度下降，不能有效的生成期望的頻繁項目集。 ? 4．產(chǎn)生關(guān)聯(lián)規(guī)則： 和前面介紹的方法類似。這樣做的目的是使數(shù)據(jù)歸整以利于挖掘。較典型的數(shù)量關(guān)聯(lián)規(guī)則挖掘的主要步驟有： ? 1．對每個數(shù)值屬性進(jìn)行離散化： 選取或設(shè)計合適的離散化算法，對數(shù)據(jù)庫中的所有數(shù)值屬性進(jìn)行離散化。這和第二類規(guī)則形式恰好相反，但對有些問題，這類規(guī)則非常有意義。這樣的模板很適合用于分類規(guī)則的挖掘。例如， smoke=Yes∩age∈[60 ，80] =heartdesease=Yes。這類規(guī)則較為復(fù)雜，是一般性的數(shù)量關(guān)聯(lián)規(guī)則。 2020年 10月 5日星期一 65 ? 根據(jù)使用的規(guī)則模板，主要技術(shù)有： ? 復(fù)雜的挖掘模板形式： 類似于“ 數(shù)值屬性 ∩ 分類屬性 ?數(shù)值屬性∩ 分類屬性 ”這樣的規(guī)則。離散化的動態(tài)體現(xiàn)在分區(qū)合并等過程中。 ? 基于特定的技術(shù)進(jìn)行離散化： 常用的方法是根據(jù)數(shù)據(jù)的分布，將數(shù)值屬性離散化到“箱（ Bin）”。例如， ine的概念分層可以用于用區(qū)間值“ 0?20K” ，“ 21?30K” ，“ 31?40K” 來替換屬性原來的數(shù)值。 ? 定義 330 給定用戶的最小支持度 minsupport和最小臵信度minconfidence，如果 support（ X?Y） ≥ minsupport且confidence（ X?Y） ≥ minconfidence，則稱數(shù)量關(guān)聯(lián)規(guī)則X?Y為 強規(guī)則 。項目集（ X?Y）的支持度稱為關(guān)聯(lián)規(guī)則 X?Y的支持度，記作support（ X?Y），其中 X?Y的含義是在數(shù)據(jù)庫中同時包含 X和 Y，即 support（ X?Y）＝ support（ X?Y）。若 support（ X）不小于用戶指定的最小支持度，則稱 X為 頻繁項目集 （或大項目集），否則稱 X為非頻繁項目集（或小項目集）。 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中。項目集 X的屬性集合記為attribute（ X），即 attribute（ X） ={Ai|Ai∈A ，Ai， u， v∈X} 。 ? 將連續(xù)屬性的屬性值空間劃分為若干個子區(qū)間并產(chǎn)生項目的過程稱為 連續(xù)屬性的離散化 。 ? 若 Ai為連續(xù)屬性，則 u?v，且 u， v構(gòu)成 Ai的屬性值區(qū)間； ? 若 Ai為分類屬性，則 u= v為分類屬性的一個屬性值，此時項目 Ai， u， v可以簡記為 Ai， u。但是，這類規(guī)則更具有普遍性，具有更好的應(yīng)用價值，因此近年來得到普遍關(guān)注。例如，“年齡（ X， 20~30） ^購買（ X，筆記本電腦） = 購買（ X，打印機）”。這里我們就涉及到三個維：年齡、職業(yè)、購買。例如，有人提出層間關(guān)聯(lián)規(guī)則應(yīng)該根據(jù)較低層次的最小支持度來定。但是，也留下了許多相關(guān)問題需要解決： ? 首先，不同層次間的支持度應(yīng)該有所關(guān)聯(lián)，只有正確地刻畫這種聯(lián)系或找到轉(zhuǎn)換方法，才能使生成的關(guān)聯(lián)規(guī)則相對客觀。較低層次的最小支持度相對較小，而較高層次的最小支持度相對較大。而對于另外的用戶來說，又認(rèn)為支持度太大，有用信息丟失過多。但是弊端也是顯然的： ? 不同層次可能考慮問題的精度不同、面向的用戶群不同。 2020年 10月 5日星期一 56 多層次關(guān)聯(lián)規(guī)則挖掘 ? 多層次關(guān)聯(lián)規(guī)則挖掘的度量方法可以沿用 “ 支持度 可信度 ” 的框架。 2020年 10月 5日星期一 53 約束之間的關(guān)系 Succinctness Antimonotonicity Monotonicity Convertible constraints Inconvertible constraints 2020年 10月 5日星期一 54 第 3章 知識發(fā)現(xiàn)與關(guān)聯(lián)規(guī)則挖掘（ 二 ） 內(nèi)容提要 ? 基本概念與解決方法 ? 經(jīng)典的頻繁項目集生成算法分析 ? Apriori算法的性能瓶頸問題 ? Apriori的改進(jìn)算法 ? 對項目集格空間理論的發(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日星期一 55 多層次關(guān)聯(lián)規(guī)則挖掘 ? 根據(jù)規(guī)則中涉及到的層次，多層次關(guān)聯(lián)規(guī)則可以分為： ? 同層關(guān)聯(lián)規(guī)則： 如果一個關(guān)聯(lián)規(guī)則對應(yīng)的項目是同一個粒度層次，那么它是同層關(guān)聯(lián)規(guī)則。 ? 定義 320 SP?2I 是一個強簡潔集（ Succinct Power Set），如果有一個數(shù)目不變的簡潔集 I1， I2， …，Ik?I， SP 能夠用 I1， I2， …， Ik的并、差運算表示出來。 ? 如果一個約束是簡潔的，那么我們就可以直接使用 SQL查詢來得到滿足條件的集合。如果 S的后綴 S*滿足約束 avg（ S*） ?v，那么 S也滿足 avg（ S） ?v。 ? 定義 318 如果一個約束 C滿足下面的條件，那么稱它是單調(diào)可轉(zhuǎn)變的： ? C（ S）既不是單調(diào)性約束，也不是反單調(diào)性約束； ? 若存在順序 R，使得經(jīng) R排序后的 I滿足：任給 S*∈{suffix_S} ，有C（ S*） =C（ S）。 ? 例如，對于 Avg（ S） ? v，令 I為一組以升序排列數(shù)值的項目集。 ? 這樣的約束可以用來裁減不必要的探索，提高挖掘效率。 2020年 10月 5日星期一 50 反單調(diào)性約束 ? 定義 316 約束 Ca是反單調(diào)的是指對于任意給定的不滿足 Ca的項目集 S，不存在 S的超集能夠滿足 Ca。因為一個項目集滿足這個條件，那么它的超集也一定滿足這個條件。 2020年 10月 5日星期一 49 單調(diào)性約束 ? 定義 315 所謂一個約束 Cm是單調(diào)性的約束是指滿足 Cm的任何項目集 S的超集也能滿足 Cm。 ? 將約束條件用于頻繁集的查詢無非是找出那些滿足 C的頻繁集。約束 C對于一個模式 S的結(jié)果用布爾變量來表示，即 C（ S） =True/False： C（ S） =True表示 S滿足約束條件； C（ S） =False表示 S不滿足約束條件。 2020年 10月 5日星期一 47 約束的類型 ? 一些常用的名詞和符號： ? 定義 312 設(shè)項目集 I={i1， i2， ? ， im}，事務(wù)數(shù)據(jù)庫T=tid， It，模式 S和 S*都是項目集 I的子集，如果S*?S，則稱 S*是 S的 子模式（ Subpattern） ； S是 S*的 超模式（ Superpattern） 。約束數(shù)據(jù)挖掘的思想為系統(tǒng)的增量式擴充提供條件。約束的使用可以幫助我們發(fā)現(xiàn)問題，并及時加以調(diào)整，使知識發(fā)現(xiàn)的各個階段按著正確的方向發(fā)展。約束的使用可以在知識發(fā)現(xiàn)的任何階段進(jìn)行，快速聚焦挖掘任務(wù)，進(jìn)而提高挖掘效率。 ? 這些工作都期望通過引入新的度量機制和重新認(rèn)識關(guān)聯(lián)規(guī)則的系統(tǒng)客觀性來改善挖掘質(zhì)量。 ? 重新考慮關(guān)聯(lián)規(guī)則的客觀度量問題。 2020年 10月 5日星期一 44 系統(tǒng)客觀層面 ? 使用 “ 支持度 可信度 ” 的關(guān)聯(lián)規(guī)則挖掘度量框架，在客觀上也可能出現(xiàn)與事實不相符的結(jié)果。 ? 知識內(nèi)容的約束： 可以通過限定要挖掘的知識的內(nèi)容，如 指定單價大于 10的交易項目 ，減少探索的代價和加快知識的形成過程。 ? 數(shù)據(jù)的約束： 對數(shù)據(jù)的約束可以起到減少數(shù)據(jù)挖掘算法所用的數(shù)據(jù)量、提高數(shù)據(jù)質(zhì)量等作用。 ? 從被約束的對象來看，有下面幾種常用的方法： ? 知識類型的約束： 針對應(yīng)用問題選擇有效的知識表達(dá)模式。 2020年 10月 5日星期一 43 用戶主觀層面 ? 一個規(guī)則的有用與否最終取決于 用戶的感覺 。必須采用 事先預(yù)防、過程控制 以及 事后評估 等多種方法，其中使用合適的機制（如約束），讓用戶主動參與挖掘工作是解決問題的關(guān)鍵。 ? 新穎性：挖掘出的關(guān)聯(lián)規(guī)則可以為用戶提供新的有價值信息。ABCD Answ {（ ABCE， 1），（ BDE， 1） } { ABCD， BCE } 2020年