1、第七章 敘述性採掘7.1 特徵與比較敘述7.2 關聯規則採掘 7.3 群集分析習題,特色與比較描述是概念描述的兩個方面。概念描述通常是指資料的匯總描述。當概念描述涉及物件類時，概念描述也稱為類描述。關聯規則可以分為許多種類。根據規則涉及的值類型，可以分為布爾關聯規則與量化關聯規則；根據規則涉及的資料維，可以分為單維關聯規則與多維關聯規則。,7.1 特色與比較敘述7.1.1 特色與比較描述概述,概念描述就是對其類物件的特色進行概括。概念描述分為特色描述和比較描述，前者描述某類物件的共同特色，後者描述某類物件與其他物件相區別的特性，所以比較描述也稱為區分性描述。,例如，如果該學校想了解研究生與大學
2、生、博士班研究生的相區分的特色，那麼它可以在學生資料表中針對研究生、本科生、博士班研究生進行比較描述。 特色描述中，進行特色描述的資料物件集合稱為目標類。,7.1.2 屬性歸納,屬性歸納導向是關聯式資料庫的。面向屬性歸納的基本思想是:首先，進行屬性刪除；然後，進行屬性一般化，即根據屬性概念分層，運用閥值控制，將屬性的低層屬性值用相應高層概念替換；最後，合併由此得到的相同記錄，並統計重複記錄數目。,例7.2、例7.1的“年齡”、“專業”、“綜合測評”屬性的概念階層樹分別如圖7.1、7.2、7.3所示 (注：“15-”表示包括小於15； “45+”表示包括大於45)。,概念分層 (或者概念階層樹)
3、一般由系統客戶、領域專家(Domain Expert)提供，但是這是叫常耗時、乏味的工作，在6.4.6節中，我們簡單介紹了概念階層樹的自動生成。,給定關聯式資料集S，m個屬性A1,Am的概念階層樹h1,hm和屬性閥值k1,km，屬性一般化的一般程序如下： 根據hi，將S在上的屬性值轉換為相應葉概念 。 統計S在Ai上出現的不同葉概念個數，如果不同葉概念個數大於ki，再根據hi將葉概念轉換為上一層相應概念，如此重複，直至S在Ai上出現的不同概念個數小於等於 。 當所有屬性都停止向上歸納時，結束屬性一般化程序。,例7.3：假設屬性閥值均為2，寫出例義7.17.2的屬性一般化程序。 “年齡”屬性 因
4、為在其上出現的不同葉概念有“2529”、“3034”、“3539”共3個，大於其屬性閥值2，所以向上歸納一層。此時，在其上出現的不同概念有“2534”、“3545+”共2個，等於其屬性閥值2，停止向上歸納。,“專業”屬性 因為在其上出現了所有葉概念，共5個，大於其屬性閥值2，所以向上歸納一層。此時，在其上出現的不同概念有“通訊”、“電腦”共2個，等於其屬性閥值2，停止向上歸納。 “綜合測評”屬性 因為在其上出現的不同葉概念有“7079”、“8089”共2個，等於其屬性閥值2，所以停止向上歸納。,例7.4 例子7.17.3的一般化關聯式如表7.2所示，其中“count”表示重複記錄數目。,在合併
5、相同記錄時，有兩種有效方法： 將每個一般化記錄插入到一般化關聯式中。如果一般化記錄己經存在，則累計重複記錄數目或計算其他聚集值；否則增加一條一般化記錄，並初始化重複記錄數目或其他聚集值。 由於在一般化關聯式中，在各個屬性上出現的不同概念個數很少，小於等於各個屬性的屬性閥值，即在一般化關聯式中，不同記錄數目n為,例7.6 表6.3所示的一般化關聯式可以用圖7.4所示的共有3x1=3個元素的2維陣列表示。,下面給出面向屬性歸納演算法的描述。演算法：屬性歸納導向演演算法(S， h1,hm，K1,Km)輸入：關聯式資料集S、屬性h1,hm的概念階層樹h1,hm和屬性閥值K1,Km輸出：一般化關聯式步驟
6、：,(1) for S中的每個記錄s (1.1) for 每個 (1.1.1) if 為空 then (1.1.1.1) if sAi 是新屬性值 then (1.1.2) else (1.1.2.1) 根據將sAi轉換為相應葉概念sAi (1.1.1.2) if sAi是新葉概念 then,(2) for 每個Ai (2.1) if 為空並且 then刪除 (2.2) if 不為空 then 確定Ai向上歸納的階層及S 在Ai上最終出現的不同概念個數 (3) for S中的每個記錄s (3.1) 經過屬性刪除、屬性一般化，將s轉換為相 應一般化記錄s (3.2) 將引插入到一般化關聯式或陣列
7、(共有無 個元素的m維陣列)中並累計重複記錄數目或 計算其他聚集值。,7.1.3 特色與比較規則,對於特色描述，有關目標類的關聯式資料集的一般化關聯式就是目標類的特色匯總；而對於比較描述，有關目標類與對比類肘關聯式資料集的一般化關聯式就是目標類與對比類相區分的特色匯總。,特色規則 特色描述的規則表示稱為特色規則。通常，特色規則採用t-權作為興趣度度量，帶有t-加權的特色規則稱為量化特色規則，形如下式：,一般化關聯式中第i個一般化記錄(或者特色規則中第i個析取項)的t-加權&定義為式(7.1),例7.7假設目標類研究生的一般化關聯式如表7.2所示，寫出量化特色規則。 研究生資料集,比較規則 比較
8、描述的規則表示稱為比較規則。通常，比較規則採用d-權作為興趣度度量，帶有d-權的比較規則稱為量化比較規則，形如下式：,第j個一般化記錄關於目標類的d-加權dj定義為：,第j個一般化紀錄關於第i個對比類的d-加權dji定義為,例7.8 假設目標類研究生的一般化關係如表7.2所示，而對比非研究生的一般化關係如表7.3所示，寫出量化對比規則。,7.2 關聯規則採掘7.2.1 關聯規則的基本概念,關聯規則採掘的一個典型應用是購物籃分析。所謂購物籃分析就是在某商店的銷售事務資料中分析該商店的“大部分顧客會在一次購物中同時購買什麼商品？”，以便對商品促銷、佈局等提供幫助。,購物籃分析只是關聯規則採掘的一種
9、形式與應用。事實上，關聯規則可以分為許多種類。 根據規則涉及的值類型，可以分為布林關聯規則與量化關聯規則。布林關聯規則中考慮的是項的在與不在。根據規則涉及的資料維度(或謂詞)，可以分為單維關聯規則與多維關聯規則。單維關聯規則中的項涉及一個維度。,根據規則涉及的抽象層，可以分為單層關聯規則與多層關聯規則。單層關聯規則中的項涉及一個抽象層，多層關聯規則中的項涉及多個抽象層。,假設min_sup是最小支援度閥值；min_conf是最小信賴度閥值。如果交易集合T中的關聯規則A B同時滿足：則A B稱為T中的強關聯規則。,設n是交易集合T中的交易數，即 。如果T中某k-項目集Ik的支援計數滿足：sup_
10、count (Ik) nmin_sup即support (Ik) min_sup,在交易集合庫中採掘強關聯規則主要包括兩個步驟：找出所有頻繁項目集例7.9 如果項目集 是頻繁3-項目集，即 support (a,b,c) P(a,b,c) min_sup那,產生強關聯規則產生強關聯規則就是在所有支援度大於等於最小支援度閥值的關聯規則中，找出所有信賴度大於等於最小信賴度閥值的關聯規則。,7.2.2 Apriori演算法,核心演算法定理7.1如果某k-項目集Ik不是頻繁k-項目集，則包含Ik的(k+1)-項目集也不是頻繁(k+1)-項目集。該性質稱為Apriori性質。,證明：因為 ，所以 所以,
11、Apriori演算法找出所有頻繁項目集的關鍵步驟 基於頻繁k-項目集集合Lk，產生所有可能頻繁的 (k+1)-項目集，即候選(k+1)-項目集集合Ck+1設 。如果表示li的第j項，則lu、lv稱為可連接的。設且是可連接的。lu、lv的連接運算定義為：,掃描一次交易集合，頻繁k-項目集集合Lk與候選(k+1)-項目集集合Ck+1，找出頻繁(k+l)-項目集集合Lk+1。,例7.10 假設交易集合T如表7.4所示，最小支援度閥值min_sup為20%。寫出搜索所有頻繁項目集的程序。因為：min_sup=20% n=9 n*min_sup=9*20%=1.8所以：支援計數大於或等於1.8的項目集是
12、頻繁項目集。 掃描一次交易集合，對T中的所有項進行支援計數計算，找出頻繁1-項目集集合L1，如表7.5所示。 對L1中的所有可連接的頻繁1-項目集進行連接運算，產生候選2-項目集集合C2，如表7.6所示。, 掃描一次交易集合，對C2中的所有2-項目集進行支援計數計算，找出頻繁2-項目集集合L2如表7.7所示。, 對L2中的所有可連接的頻繁2-項目集進行連接運 算，產生候選3-項目集集合C3如表7.8所示。例如， 與 是可連接的， = 與 是可連接的， = 與 是不可連接的。,根據Aprior性質，可以利用L2事先刪除C3中不可能是頻率3-項目集的項目集，得到如表7.9所示的結果。例如，因為 ，
13、所以 。所以可以從C3中刪除 。, 掃描-次交易集合，對C3中的所有3-項目集進行支援計數計算，3-項目集集合助，如表7.10所示。, 對L3中的所有可連接的頻繁3-項目集進行連接運算，產生候選本項目集集合C4。因為L3中只有一個頻繁3-項目集，所以,Apriori演算法產生強關聯規則的步驟 對於每個頻繁項目集l，產生l的所有非空白真子 集。 對於l的每個非空白真子集lu，如果的支援計數除 以lu的支援計數大於等於最小信賴度閥值min_conf，則輸出規則lu=(l-lu)。,下面給出Apriori演算法的描述。演算法：Apriori演算法(T,min_sup,min_conf)輸入：交易集合
14、T最小支援度閥值min_sup，最小信 賴度閥值min_conf輸出：強關聯規則集合R_S 步驟： for T中的每個交易t (1.1) for t中的每個項i (1.1.1) i.sup_count=i.sup_count+1, for每個項i (2.1) if /找出頻繁1-項目集 for (k=2； ；k+) /找出頻繁k-項目集 (3.1) for 中的每個項目集lu (3.1.1) for 中的每個項目集lv (3.1.1.1) if then (3.1.1.1.1) C = (3.1.1.1.2) (3.1.1.1.3) for c中的每個(k-1)-項目集 (3.1.1.1.3.
15、1) if then /事先剪枝,(3.2) for T中的每個交易t (3.2.1) for t中的每個k-項子集s(3.2.1.1) if then s.sup_count=s.sup_count+1(3.3) for 中的每一個項目集c (3.3.1) /找出頻繁k-項目集(3.4), for L 中的每個頻繁項目集l (4.1) for l中的每個非空白真子集lu (4.1.1) if then (4.1.1.1) R_S = R_S lu=(l-lu) /得到強關 聯規則集合,Apriori演算法的幾種優化方法劃分導向的方式這個演算法先把資料庫從邏輯上分成兒個互不相交的塊，每次單獨考
16、慮一個分塊並對它生成所有的頻集，然後把產生的頻集合並，用來生成所有可能的頻集，最後計算這些項目集的支援度。,Hash導向的方式一個高效地產生頻集的雜湊(Hash)的演算法由Park等提出來。運用實驗可以發現尋找頻集主要的計算是在生成頻繁2-項目集上，Park等就是利用了這個性質引入雜草技術來改進產生頻繁兒項目集的方法。,採樣導向的方式Mannila等先考慮了這一點，他們認為採樣是發現規則的一個有效途徑。隨後又由Toivonen進一步發展了這個思想，先使用從資料庫中抽取出來的採樣得到一些在整個資料庫中可能成立的規則，然後對資料庫的剩餘部分驗證這個結果。,減少交易的個數減少用於未來掃描的交易集的大
17、小。一個基本的原理就是當一個交易不包含長度為k的頻繁項目集，則必然不包含長度為k+1的頻繁項目集。,7.2.3 PF-growth演算法,Apriori方法一些固有的缺陷還是無法克服。如：可能產生大量的候選集。 FP-growth演算法恰克服了Apriori演算法的上述不足。 FP-growth演算法的基本思想是：掃描一次交易集合，找出頻繁1-項目集L；基於L，再掃描一次交易集合，構造表示交易集合中項目集關聯的FP樹。,FP-growth演算法找出所有頻繁項目集的關鍵步驟主要有以下兩個：掃描交易集合，找出頻繁I-項目集L，基於L，構造表示交易集合項目集關聯的FP樹。FP-growth演算法規定
18、頻繁1-項目集合L中的項按支援計數降序排序。表示交易集合項目集關聯的PF樹的建構方式如下：,創建FP樹的根節點，用“null”標記。掃描一次交易集合，對每個交易找出其中的頻繁項並按L中的順序排序，為每個交易創建一個分支。為方便追蹤FP樹，為FP樹創建一個項表，項表中每一行表示一個頻繁項，並有一個指針標向它在FP樹中的節點。,例7.12 假設交易集合T如表7.4所示，最小支援度閥值min_sup為20%。寫出構造FP樹的程序。首先，掃描一次交易集合，找出頻繁項(1-項目集)的集合L=其次，以L為基礎，再掃描一次交易集合，建構FP樹。對交易t1，其頻繁項及排序為 ，其分支創建之後的FP樹如圖7.5
19、所示。,對交易t2，其頻繁項及排序為 ，其分支創建之後的FP樹如圖7.6所示。,創建所有交易分支之後的FP樹如圖7.7所示。,在FP樹上遞迴地找出所有頻繁項目集。在FP樹上遞迴地找出所有頻繁項目集的方法如下： 賦與之後序模式a初始值為mull，即 null，在FP樹上遞迴地搜索頻繁項目集。 在條件FP樹上採用相同方法遞迴地搜索頻繁項目集(後序模式 此時為 ，即 。,例7.14 考慮例子7.12。寫出在FP樹上遞迴地找出所有頻繁項目集的程序。第一層遞迴巳( null)：因為FP樹有多個分支，所以進入第二層遞迴。第二層遞迴：因為的條件FP樹只有一個分支，所以直接產生頻繁項目集，如表7.12所示。因
20、為的條件FP樹有兩個分支，所以進入第三層遞迴。,第三層遞迴：因為 、 的條件FP樹只有一個分支，所以直接產生頻繁項目集，如表7.13所示。,下面給出FP-growth演算法的描述。演算法：FP-growth演算法()輸入：交易集合T，最小支援度閥值，最小信賴度閥 值。輸出：強關聯規則集合R_S步驟：(1) 掃描T找出頻繁1-項目集合L(2) L中的項目按支援計數降序排序,(3) 創建FP樹的根節點null /創建FP樹 (4) for T中的每個交易t (4.1) 找出t中的頻繁1-項目集合Lt (4.2) Lt中的項目按L中的順序排序 (4.3) Insert-FP (Lt，null) /創
21、建交易分支 (5) L_S=Search-FP(Lt，null) /找出所有頻繁項目集 (6) 在L_S中產生強關聯規則集合R_S,算法：Insert-FP演算法(Li，Tr)輸入：已排序頻繁項目集合Li，FP (子)樹的根節點 Tr 輸出：FP樹步驟：(1) If Li 不空 then (1.1)取出Li中的第1個項i (1.2) if Tr 的某個子節點N是i then (1.2.1) N.count = N.count+1,(1.3) else (1.3.1) 創建Tr的子節點N為i (1.3.2) N.coun=1 (1.3.3) 將N加入項表鏈中(1.4) lnsert-FP(Li-
22、I,N),算法：Search-FP演算法 (T, )輸入：(條件)FP樹T後序模式 輸出：頻繁項目集集合L_S步驟：(1) if T中只有一個分支P then (1.1) for P上的節點的每個組合 BETA (1.1.1) /產生一個頻繁項目集 (1.1.2),(2) else (2.1) for T中的每個頻繁項i (2.1.1) /後序模式增長 (2.1.2) 構造 的條件模式基及其條件FP樹 (2.1.3) if then Search-FP( , ),7.3 群集分析7.3.1 群集分析的基本概念,什麼是群集分析群集分析就是根據資料物件的屬性資訊或物件間的關聯式，將資料物件分組成為
23、類別(cluster)，使在同一個群集中的物件之間具有較高的相似度，而不同簇中的物件彼此差別較大。,群集分析中的資料類型資料矩陣(data matrix )：物件在多維空間中通常表示為點(向量)，其每一維表示為不同屬性，這些屬性描述出物件。,相異度矩陣(dissimilarity matrix)：群集分析有時使用最初的資料矩陣，但大部分時候群集應用經計算的相異度矩陣。,相異度圖形(dissimilarity graph)：由相異度矩陣可以定義一個帶有權重的圖，在圖中，節點表示要進行群集的物件，節點間帶加權的邊表示兩節點的相異度。,相異度的計算對圖7.9所示的二維平面中的點進行群集分析。直觀地，
24、點可以分為兩個類，較靠近的點在同一類中。,設d(i,j)為資料物件i與資料物件j的距離。由於現實資料物件的描述屬性的類型多樣、複雜，不同類型屬性的距離含義不同，因此不同類型屬性的距離應該分別定義，但是它們都應該使d(i,j)滿足如下條件：非負性 (Non-Negative)對稱性 (Symmetric)三角不等式 (Triangular Inequality),下面我們分別介紹不同類型屬性的距離定義。在下面的介紹中，我們首先介紹資料物件的描述屬性的類型都相同的情況；然後再介紹資料物件的描述屬性的類型不相同的情況。,資料物件的描述屬性都是連續屬性連續屬性可以分為區間標度屬性與比例標度屬性。區間標
25、度屬性的值是一個線性標度的連續度量。 比例標度屬性的值是一個非線性標度的取正度量。,資料物件的描述屬性都是離散屬性離散屬性可以分為標稱屬性與序數屬性。標稱屬性的域由多個無先後次序的狀態值構成。 序數屬性的域由多個有先後次序的狀態值構成。,在此，我們也僅僅介紹當資料物件的描述屬性都是標稱屬性時，資料物件的距離 (或者相異度)定義。資料物件的描述屬性都是對稱二元屬性。如果採用1、0分別表示對稱二元屬性的兩個狀態值，可以得到如表7.14所示的可能性表。,資料物件的描述屬性都是對稱標稱屬性。對於描述屬性都是對稱標稱屬性的資料物件，它們的相異度定義可以運用擴展上述簡單匹配係數方法得到。,對於描述屬性都是
26、不對稱二元屬性的資料物件，它們的相異度定義通常採用Jaccard係數方法。,資料物件的描述屬性都是不對稱標稱屬性。對於不對稱標稱屬性，可以首先將不對稱標稱屬性轉換為不對稱二元屬性，然後作為不對稱二元屬性處理。,資料物件的描述屬性是混合的 一般，資料物件的描述屬性可以包括以上介紹的幾種類型，這時，通常採用如式(7.13)的距離定義。,群集準則常用的群集準則有如下兩種：設置相異性閥值T常用的類的相異性度量方法有如下幾種：最短距離方法：,最長距離方法：重心方法：,類平均方法,定義群集準則函數f一般採用的群集準則函數f如下：,7.3.2 劃分導向的群集演算法,劃分的群集演算法的主要思想是將資料庫中由們個屬性描述的門個資料物件的集合S劃分為k個集合(或者類)C1,C2,Ck。演算法通常從一個起始劃分開始，然後應用迭代控制策略優化群集準則函數，直到函數收斂。,下面給出k-平均演算法的描述。演算法:k-平均演算法 (S,K)輸入:資料物件集合S，類數目K輸出:幾個類步驟:從S中隨機選取 K個不同的資料物件作為K個類C1，C2，.，Ck的代表P1，P2.Pk,7.4 結語,本章介紹了描述性採掘中的特色與比較描述、關聯規則採掘、群集分析。在特色與比較描述中，著重介紹了屬性歸納導向方法以及帶有t-加權的量化特徵規則、帶有d-加權的量化比較規則。,
