數據挖掘常用算法概述

1、關聯(lián)分析,關聯(lián)規(guī)則挖掘的提出,關聯(lián)規(guī)則挖掘的典型案例：購物籃問題在商場中擁有大量的商品（項目），如：牛奶、面包等，客戶將所購買的商品放入到自己的購物籃中。通過發(fā)現(xiàn)顧客放入購物籃中的不同商品之間的聯(lián)系，分析顧客的購買習慣哪些物品經常被顧客購買？同一次購買中，哪些商品經常會被一起購買？一般用戶的購買過程中是否存在一定的購買時間序列？具體應用：利潤最大化商品貨架設計：更加適合客戶的購物路徑貨存安排 ：實現(xiàn)超市的零

2、庫存管理用戶分類 ：提供個性化的服務,其他典型應用,相關文獻的收集購物籃 = 文檔（Document）項 目 = 單詞（Word）相關網站的收集購物籃 = 詞句（Sentences）項 目 =鏈接文檔（Document）,什么是關聯(lián)規(guī)則挖掘?,關聯(lián)規(guī)則挖掘簡單的說，關聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數據中項集之間有趣的關聯(lián)在交易數據、關系數據或其他信息載體中，查找存在于項目集合或對象集合之間的頻繁模式、關聯(lián)、

3、相關性、或因果結構。應用購物籃分析、交叉銷售、產品目錄設計、 loss-leader analysis、聚集、分類等。,關聯(lián)規(guī)則挖掘形式化定義,給定:交易數據庫 每筆交易是：一個項目列表 (消費者一次購買活動中購買的商品)查找: 所有描述一個項目集合與其他項目集合相關性的規(guī)則應用* ? 護理用品 (商店應該怎樣提高護理用品的銷售？)家用電器 ? * (其他商品的庫存有什么影響?)在產品直銷中使用附加郵寄,其它

4、相關概念,包含k個項目的集合，稱為k-項集項集的出現(xiàn)頻率是包含項集的事務個數，稱為項集的頻率、支持計數或者計數關聯(lián)規(guī)則的基本形式：前提條件 ? 結論 [支持度, 置信度]buys(x, “diapers”) ? buys(x, “beers”) [0.5%, 60%]major(x, “CS”) ^ takes(x, “DB”) ? grade(x, “A”) [1%, 75%],關聯(lián)規(guī)則興趣度的度量值：支持度,推導出的數據間的

5、相關性可稱為規(guī)則（或模式），對規(guī)則興趣度的描述采用支持度、置信度概念。支持度（Support）：規(guī)則X?Y在交易數據庫D中的支持度是交易集中包含X和Y的交易數與所有交易數之比，記為support(X?Y)，即support(X?Y)=|{T:X?Y? T，T?D}|/ |D|，它是概率P（ X?Y ），具體表示為：,,,,,,購買商品Y的交易,同時購買商品X和Y的交易,購買商品X的交易,,關聯(lián)規(guī)則興趣度的度量值：置信度,置信度（Con

6、fidence），規(guī)則X?Y在交易集中的置信度是指包含X和Y的交易數與包含X的交易數之比，記為confidence(X?Y)，即confidence(X?Y)=|{T: X?Y?T，T?D}|/|{T:X?T，T?D}|，它是概率P（ X|Y ），具體表示為：最小支持度和最小置信度用戶（分析員）不關心可信程度太低的規(guī)則，因而用戶需要輸入兩個參數：最小支持度和最小置信度。,支持度和置信度舉例,零售商場銷售分析：數據項為商品，記

7、錄集合為交易記錄集合規(guī)則為：“購買商品X的顧客，同時購買商品Y”，即X ? Y；設最小支持度為0 .3；最小置信度也為0.3。分析結果：,頻繁項集及其基本特征,頻繁項集的定義如果項集滿足最小支持度，則稱之為頻繁項集（高頻項集）頻繁項集的基本特征任何頻繁項集的子集均為頻繁項集。例如：ABC是頻繁項集，則AB、AC、BC均為頻繁項集在數據庫表分區(qū)的情況下，一個項集是頻繁的，則至少在一個分區(qū)內是頻繁的,關聯(lián)規(guī)則挖掘的種類,布爾

8、vs. 數值型關聯(lián) (基于 處理數據的類型)性別＝“女” ? 職業(yè)＝“ 秘書” [1%, 75%] 布爾型關聯(lián)規(guī)則 性別＝“女” ? 收入 = 2000 [1%, 75%] 數值型關聯(lián)規(guī)則 單維 vs. 多維 關聯(lián)age(x, “30..39”) ^ income(x, “42..48K”) ? buys(x, “PC”) [1%, 75%]buys(x, “Book”) ^buys(x, “Pen”)

9、? buys(x, “Ink”) [1%, 75%]單層 vs. 多層 分析那個品種牌子的啤酒與那個牌子的尿布有關系?各種擴展相關性、因果分析關聯(lián)并不一定意味著相關或因果最大模式和閉合相集添加約束如, 哪些“小東西”的銷售促發(fā)了“大家伙”的買賣？,關聯(lián)規(guī)則挖掘的基本過程,找出所有的頻繁項集 F，其中對于任何的 Z ? F，在交易集合D中至少 s%的事務包含Z根據置信度和頻繁項集F, 產生關聯(lián)規(guī)則。具

10、體方法如下：conf(X ? Y) = supp(X)/supp(X ? Y)如果 conf(X ? Y) ? c 成立，則產生 X ? Y 的規(guī)則, 因為:supp(X ? Y) = supp(X ? Y) ? s 且conf(X ? Y) ? c因此關聯(lián)規(guī)則的挖掘可以轉換為頻繁項集的挖掘和頻繁項集之間的關聯(lián)。,關聯(lián)規(guī)則挖掘：一個例子,對于 A ? C：support = support({A 、C}) = 50%co

11、nfidence = support({A 、C})/support({A}) = 66.6%,最小值尺度 50%最小可信度 50%,關聯(lián)規(guī)則挖掘的優(yōu)缺點,優(yōu)點它可以產生清晰有用的結果它支持間接數據挖掘可以處理變長的數據它的計算的消耗量是可以預見的 缺點當問題變大時，計算量增長得厲害難以決定正確的數據容易忽略稀有的數據,查找頻繁項集 — Apriori算法,查找具有最小支持度的頻繁項集是關聯(lián)規(guī)則挖掘最為重要的步驟Ap

12、riori算法是目前最有影響力的一個算法，在1994年，由R.Agrawal, S.Srikant提出該算法基于頻繁項集的特征：如果項集l = {i1,i2,…,in} 是頻繁的，當且僅當項集的所有子集均為頻繁項集.也就是說，如果supp(l)?s，當且僅當 supp(l’ )?s, ?l’ ? l因此，我們可以采用層次順序的方法來實現(xiàn)頻繁項集的挖掘。首先，挖掘一階頻繁項集L1。在此基礎上，形成二階候選項集，挖掘二階頻繁項集。依此類

13、推。,Apriori算法,連接: 用 Lk-1自連接得到Ck剪枝: 一個k-項集，如果它的一個k-1項集（它的子集 ）不是頻繁的，那他本身也不可能是頻繁的。偽代碼:Ck: 長度為k的候選項集Lk :長度為k的頻繁項集L1 = {frequent items}; for (k = 1; Lk !=?; k++) do begin Ck+1 = 從Lk 生成候選項集; 對于數

14、據庫中的任一交易 t do 如果 t 中包含 Ck+1中所包含的項集，則計數加 1 Lk+1 = Ck+1 中超過最小支持度的頻繁項集 end return ?k Lk;,Apriori算法 — 例子,數據庫 D,掃描 D,,C1,L1,L2,C2,C2,,掃描 D,,,C3,L3,掃描 D,,,,Apriori 夠快了嗎? — 性能瓶頸,Apriori算法的核心:用頻繁的(k – 1)

15、-項集生成候選的頻繁 k-項集用數據庫掃描和模式匹配計算候選集的支持度Apriori 的瓶頸: 候選集生成巨大的候選集:104 個頻繁1-項集要生成 107 個候選 2-項集，并且累計和檢查它們的頻繁性要找長度為100的頻繁模式，如 {a1, a2, …, a100}, 你必須先產生2100 ? 1030 個候選集重復掃描數據庫：如果最長的模式是n的話，則需要 (n +1 ) 次數據庫掃描,關聯(lián)規(guī)則結果顯示 (Table

16、Form ),關聯(lián)規(guī)則可視化Using Rule Graph,擴展知識：多層關聯(lián)規(guī)則,項通常具有層次底層的項通常支持度也低某些特定層的規(guī)則可能更有意義交易數據庫可以按照維或層編碼可以進行共享的多維挖掘,擴展知識：多維關聯(lián)規(guī)則,單維關聯(lián)規(guī)則（維內關聯(lián)規(guī)則）關聯(lián)規(guī)則中僅包含單個謂詞（維）通常針對的是事務數據庫 buys(X, “milk”) ? buys(X, “bread”)多維關聯(lián)規(guī)則：規(guī)則內包含2 個

17、以上維/謂詞維間關聯(lián)規(guī)則 (不重復謂詞)age(X,”19-25”) ? occupation(X,“student”) ? buys(X,“coke”)混合維關聯(lián)規(guī)則 (存在重復謂詞) age(X,”19-25”) ? buys(X, “popcorn”) ? buys(X, “coke”),,分類與預測,本章內容,分類與預測的基本概念決策樹分類實例：移動通信客戶流失分析系統(tǒng)神經網絡其他分類方法預測（回

18、歸）,建立模型過程,歷史數據,模型,,建模,,記錄集合,,,,預測,數學公式規(guī)則集合,分類 為一個事件或對象進行歸類預測分類標簽（離散值）基于訓練集形成一個模型，訓練集中的類標簽是已知的。使用該模型對新的數據進行分類分類模型：分類器（分類函數、分類規(guī)則等）預測: 對連續(xù)或者有序的值進行建模和預測（回歸方法） 典型應用客戶/用戶分類信用評分目標營銷醫(yī)療診斷…………,分類和預測,分類的相關概念,訓練集（Trai

19、ning Set）：由一組數據庫記錄或者元組構成，每個記錄由有關字段值組成特征向量，這些字段稱為屬性。用于分類的屬性稱為標簽屬性。標簽屬性也就是訓練集的類別標記。標簽屬性的類型必須是離散的，而且標簽屬性的可能值的數目越少越好。,分類的兩個步驟,模型創(chuàng)建: 對一個已經事先確定的類別創(chuàng)建模型每個元組屬于一個事先確定的類別，使用分類標簽屬性予以確定用于創(chuàng)建模型的數據集叫: 訓練集。單個元組稱為訓練樣本模型可以用分類規(guī)則，決策樹，或者

20、數學方程的形式來表達。模型使用: 用創(chuàng)建的模型預測未來或者類別未知的記錄估計模型的準確率使用創(chuàng)建的模型在一個測試集上進行預測，并將結果和實際值進行比較準確率：測試集和訓練集是獨立的。,分類過程：模型創(chuàng)建（學習過程）,訓練集,,,分類算法,,IF rank = ‘professor’OR years > 6THEN tenured = ‘yes’,模型,,,,分類過程 : 使用模型,模型,測試集,,,,,未知數據,(J

21、eff, Professor, 4),,,,Tenured?,本章內容,分類與預測的基本概念決策樹分類實例：移動通信客戶流失分析系統(tǒng)神經網絡其他分類方法預測（回歸）,使用決策樹進行分類,決策樹 一個樹型的結構內部節(jié)點上選用一個屬性進行分裂 （決策節(jié)點）每個分叉都是分裂的一個部分葉子節(jié)點表示一個分布節(jié)點的子節(jié)點個數跟算法相關,決

22、策樹分類的特點,優(yōu)點容易生成可以理解的規(guī)則計算量相對來說不大可以處理離散和連續(xù)字段可以清晰顯示哪些字段比較重要缺點對連續(xù)性的字段難以預測類別太多的時候，錯誤的可能性會加大一般情況下，標簽屬性的個數有限,決策樹的生成與使用,決策樹生成算法分成兩個步驟樹的生成開始，數據都在根節(jié)點遞歸的進行數據分割樹的修剪去掉一些可能是噪音或者異常的數據決策樹使用: 對未知數據進行分割按照決策樹上采用的分割屬性逐層往下，直到一個

23、葉子節(jié)點,訓練集,ID3算法,決策樹結果： “buys_computer”,決策樹算法,基本算法（貪心算法）自上而下分而治之的方法開始時，所有的數據都在根節(jié)點屬性都是種類字段 (如果是連續(xù)的，將其離散化)所有記錄用所選屬性遞歸的進行分割屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量 (如, information gain)停止分割的條件一個節(jié)點上的數據都是屬于同一個類別沒有屬性可以再用于對數據進行分割,幾種經典算法介

24、紹,CART min(P(c1),P(c2)) 2P(c1)P(c2) [P(c1)logP(c1)]+[P(c2)logP(c2)] C4.5(ID3)C4.5(ID3)對種類字段處理時，缺省是對每個值作為一個分割Gain和Gain RatioCHAID在Overfitting前停止樹的生成必須都是分類屬性選擇分割。X2檢驗,從樹中生成分類規(guī)則,用 IF-THEN 這種形式來表現(xiàn)規(guī)則每個葉子

25、節(jié)點都創(chuàng)建一條規(guī)則每個分割都成為一個規(guī)則中的一個條件葉子節(jié)點中的類別就是Then的內容規(guī)則對于人來說更容易理解例子IF age = “40” AND credit_rating = “excellent” THEN buys_computer = “yes”IF age = “<=30” AND credit_rating = “fair” THEN buys_computer = “no”,本章內容,分類與

26、預測的基本概念決策樹分類實例：移動通信客戶流失分析系統(tǒng)神經網絡其他分類方法預測（回歸）,應用背景與問題定義,背景在移動通信領域，客戶流失成為通信運營企業(yè)關注的焦點通信業(yè)務產生的海量、珍貴數據為數據挖掘的研究提供了堅實的基礎把數據挖掘理論應用于移動通信領域的客戶流失分析，進而為通信企業(yè)的實際業(yè)務提供指導是一項具有挑戰(zhàn)性的工作定義客戶流失分析，就是利用數據挖掘等分析方法，對已流失客戶過去一段時間的通話、繳費等信息進行分

27、析，提煉出流失客戶的行為特征，利用這些特征預測在網客戶的流失傾向,按真實比例抽取，可能掩蓋流失用戶的特征解決方法：“樣本放大”,數據預處理——抽樣,分割,,,抽樣,原始數據（流失概率3.2%）,抽樣,,,采樣后（流失概率25%）,合并,10,000,310,000,300,000,50%,20:1,5,000,15,000,20,000,,流失,,非流失,數據預處理——時間相關屬性,,屬性序列S1,,屬性序列Sn,,“靜態(tài)”

28、屬性,,流失標志,解決方法：生成匯總屬性（求和、取均值等）生成“趨勢屬性”，如由屬性序列S1生成屬性“通話時長趨勢”,問題：決策樹算法缺乏處理時間相關屬性的能力，致使效率下降,,數據預處理——生成趨勢屬性,,把每個月通話時長Y視為月份X（取值從1到6）的線性函數，即Y = α + βX ，系數β作為屬性“通話時長趨勢”的取值，從而把求趨勢屬性的問題轉化為簡單的線形回歸問題，,數據預處理——生成趨勢屬性（續(xù)）,,實際應用中，發(fā)現(xiàn)各個

29、月份的數值對趨勢屬性的影響不同，可以對各個月份指定不同的權重w,,,β作為新生成的趨勢屬性，可以進一步轉換成離散值，如，顯著上升、小幅上升、持平、小幅下降、顯著下降,例如：1到6月份權重分別取1、1、1、2、3、4,決策樹示例,,通話次數,<20,>=20,,品牌,,話費金額,,神州行,,,,,全球通,流失,<25,>=25,,,,流失,,非流失,,非流失,,品牌,,,,非流失,神州行,全球通,第一步：建立決策樹

30、,第二步：預測,流失,,,[20,80] 0.2,,通話次數,<20,>=20,,品牌,,消費金額,,神州行,,,,[10,30] 0.25,[10,50] 0.167,,全球通,[2,23] 0.08,[8,7] 0.53,<25,,>=25,[4,36] 0.1,,品牌,[6,14] 0.3,神州行,,全球通,[1,8] 0.11,[5,6] 0.45,,,,,,C,[x,y] k%x:流失用戶數y:未

31、流失用戶數k:流失概率 k = x/(x+y),A,決策樹算法——數據結構,,,主要內容,分類與預測的基本概念決策樹分類實例：移動通信客戶流失分析系統(tǒng)神經網絡其他分類方法預測（回歸）,神經網絡技術,生物神經系統(tǒng)的計算模擬 (實際上是一個很好的學習系統(tǒng)的例子)海量并行計算技術使得性能大大提高最早的神經網絡算法為 1959由Rosenblatt提出基本結構,神經元結構,,,,,多層感知系統(tǒng),Output nodes

32、,Input nodes,Hidden nodes,Output vector,Input vector: xi,wij,,計算實例,一個訓練樣本X={1,0,1},輸出為1X1=1,x2=0,x3=1,w14=0.2,w15=-0.3,w24=0.4,w25=0.1,w34=-.5,w35=0.2,w46=-0.3,w56=-0.2,偏置值:節(jié)點4:-0.4,節(jié)點5:0.2,節(jié)點6:0.1學習率設為0.9節(jié)點4:輸入值:w

33、14*x1+w24*x2+w34*x3+節(jié)點4的偏置=1*0.2+0.4*0-0.5*1-0.4=-0.7輸出值: 可得0.332同理: 節(jié)點5輸入值0.1,輸出值0.525節(jié)點6: 輸入值:w46*o4+w56*o5+節(jié)點6的偏置=-0.3*0.332-0.2*0.525+0.1=-0.105輸出值:0.474,計算實例,誤差計算,節(jié)點6:0.474*(1-0.474)*(1-0.474)=0.1311節(jié)點5:0

34、.525*(1-0.525)*0.1311*(-0.2)=-0.0065同理節(jié)點4誤差為:-0.0087,更新權值和偏置值,W46:-0.3+(0.9)(0.1311)(0.332)=-0.261其他Wij同理節(jié)點6的偏置:0.1+(0.9)*(0.1311)=0.218其他偏置同理,終止條件,對所有樣本作一次掃描稱為一個周期終止條件:對前一周期所有Wij的修改值都小于某個指定的閾值;或超過預先指定的周期數.防止訓練

35、過度,前饋神經網絡,前饋網絡的表達能力布爾函數。任何布爾函數可以被具有兩層單元的網絡準確表示，盡管對于最壞的情況，所需隱藏單元的數量隨著網絡輸入數量的增加指數級增長。 連續(xù)函數。任何有界的連續(xù)函數可以由一個兩層的網絡以任意小的誤差逼近。這個理論適用于隱藏層使用sigmoid單元、輸出層使用（非閾值的）線性單元的網絡。所需的隱藏單元數量依賴于要逼近的函數。任意函數。任意函數可以被一個有三層單元的網絡以任意精度逼近。與前面相同，輸出層

36、使用線性單元，兩個隱藏層使用sigmoid單元，每一層所需的單元數量一般不確定。,神經網絡特點,優(yōu)點有很強的非線性擬合能力，可映射任意復雜的非線性關系。學習規(guī)則簡單，便于計算機實現(xiàn)。具有很強的魯棒性、記憶能力以及強大的自學習能力。 缺點最嚴重的問題是沒能力來解釋自己的推理過程和推理依據。不能向用戶提出必要的詢問，而且當數據不充分的時候，神經網絡就無法進行工作。 把一切問題的特征都變?yōu)閿底?，把一切推理都變?yōu)閿抵涤嬎?，其結果勢

37、必是丟失信息。理論和學習算法還有待于進一步完善和提高。,應用,適合神經網絡學習的問題 實例是用很多“屬性-值”對表示的。 目標函數的輸出可能是離散值、實數值或者由若干實數屬性或離散屬性組成的向量。 訓練數據可能包含錯誤。 可容忍長時間的訓練。 可能需要快速求出目標函數值。 人類能否理解學到的目標函數是不重要的。,實驗,使用Clementine進行神經網絡分類挖掘（工具使用參見補充教材）,主要內容,分類與預測的基本概念

38、決策樹分類實例：移動通信客戶流失分析系統(tǒng)神經網絡其他分類方法預測（回歸）,其它分類方法,貝葉斯（Bayesian）分類k-臨近分類基于案例的推理遺傳算法粗糙集理論模糊集方法,分類的準確性：評估錯誤率,數據分區(qū):訓練-測試數據將一個數據集合分成兩個獨立的數據集。例如：訓練數據 (2/3), 測試數據(1/3)通常應用于大量數據樣本的數據集交叉驗證將一個數據集合分成若干個子樣本集用k-1個子樣本作為訓練數據，1

39、個子樣本作為測試數據每一個數據集合具有合適的寬度,分類的準確性：混淆矩陣,混淆矩陣（confusion matrix ）用來作為分類規(guī)則特征的表示，它包括了每一類的樣本個數，包括正確的和錯誤的分類。主對角線給出了每一類正確分類的樣本的個數，非對角線上的元素則表示未被正確分類的樣本個數,3個類的混淆矩陣,分類的準確性：收益圖,,,,,●查全率分析圖：X軸：按離網傾向評分從大到小排序后的客戶占目標客戶人數的百分比；Y軸：前x%的客戶

40、中被準確預測為離網的客戶占目標客戶中離網總人數的百分比，即查全率。,●Lift分析圖：X軸：按離網傾向評分從大到小排序后的客戶占目標客戶人數的百分比；Y軸：命中率的提升倍數。,聚類分析,聚類分析,什么是聚類分析?劃分方法（Partitioning Methods）分層方法基于密度的方法異常分析,什么是聚類分析?,簇（Cluster）:一個數據對象的集合在同一個簇中，對象之間具有盡可能大的相似性；不同簇的對象之間具有盡可能

41、大的相異性。聚類分析把一個給定的數據對象集合分成不同的簇，即“ 物以類聚 ”；聚類是一種無監(jiān)督分類法: 沒有預先指定的類別標識；典型的應用作為一個獨立的分析工具，用于了解數據的分布； 作為其它算法的一個數據預處理步驟；,應用聚類分析的例子,市場銷售: 幫助市場人員發(fā)現(xiàn)客戶數據庫中不同群體，然后利用這些知識來開展一個目標明確的市場計劃；土地使用: 在一個陸地觀察數據庫中標識那些土地使用相似的地區(qū)；保險: 對購買了汽車保險的

42、客戶，標識那些有較高平均賠償成本的客戶；城市規(guī)劃: 根據類型、價格、地理位置等來劃分不同類型的住宅；地震研究: 根據地質斷層的特點把已觀察到的地震中心分成不同的類；,如何評價一個好的聚類方法?,一個好的聚類方法要能產生高質量的聚類結果——簇，這些簇具備以下兩個特征：簇內極大相似性簇間極小相似性 聚類結果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實現(xiàn)；聚類方法的好壞還取決與該方法是能發(fā)現(xiàn)某些還是所有的隱含模式；

43、,聚類分析中的數據類型,如何度量對象間的距離？歐幾里德距離 曼哈頓距離 明考斯基距離,聚類分析,什么是聚類分析?劃分方法（Partitioning Methods）分層方法基于密度的方法異常分析,劃分方法: 基本概念,劃分方法: 將一個包含n個數據對象的數據庫組織成k個劃分（k<=n），其中每個劃分代表一個簇（Cluster）。給定一個k，要構造出k個簇，并滿足采用的劃分準則：全局最優(yōu):盡可能的列舉所有的劃分；

44、啟發(fā)式方法: k-均值和k-中心點算法k-均值 (MacQueen’67):由簇的中心來代表簇；k-中心點或 PAM (Partition around medoids) (Kaufman & Rousseeuw’87): 每個簇由簇中的某個數據對象來代表。,K-均值算法,給定k，算法的處理流程如下:1.隨機的把所有對象分配到k個非空的簇中；2.計算每個簇的平均值，并用該平均值代表相應的簇；3.將每個對象根據其與各個簇

45、中心的距離，重新分配到與它最近的簇中； 4.回到第二步，直到不再有新的分配發(fā)生。,K-均值算法圖示,,,K-均值算法例子,Given: {2,4,10,12,3,20,30,11,25}, k=2隨機指派均值: m1=3,m2=4K1={2,3}, K2={4,10,12,20,30,11,25}, m1=2.5,m2=16K1={2,3,4},K2={10,12,20,30,11,25}, m1=3,m2=18K1={2,

46、3,4,10},K2={12,20,30,11,25}, m1=4.75,m2=19.6K1={2,3,4,10,11,12},K2={20,30,25}, m1=7,m2=25,K-均值算法,優(yōu)點 相對高效的: 算法復雜度O(tkn), 其中n 是數據對象的個數, k 是簇的個數, t是迭代的次數，通常k, t << n.算法通常終止于局部最優(yōu)解；缺點只有當平均值有意義的情況下才能使用，對于標稱字段不適用；必須

47、事先給定要生成的簇的個數；對“噪聲”和異常數據敏感；不能發(fā)現(xiàn)非凸面形狀的數據。,聚類分析,什么是聚類分析?劃分方法（Partitioning Methods）分層方法基于密度的方法基于網格的方法異常分析,層次方法,采用距離作為衡量聚類的標準。該方法不需要指定聚類的個數，但用戶可以指定希望得到的簇的數目作為一個結束條件。,層次聚類方法討論,層次方法的主要缺點：沒有良好的伸縮性: 時間復雜度至少是 O(n2)一旦一個合并或

48、分裂被執(zhí)行，就不能修復；綜合層次聚類和其它的聚類技術：BIRCH (1996): 使用 CF-tree 動態(tài)調整子聚類的質量。CURE (1998): 從聚類中選擇分布“好”的數據點，并以指定的比例向聚類中心收縮。CHAMELEON (1999): 利用動態(tài)建模技術進行層次聚類。,聚類分析,什么是聚類分析?劃分方法（Partitioning Methods）分層方法基于密度的方法異常分析,定義,兩個參數：?：鄰域的最大

49、半徑MinPts ：數據對象?-鄰域內最少的數據個數給定對象集合D? 鄰域N?(p): 對象p的半徑為?內的區(qū)域，即{q ? D | dist(p,q) <= ?}核心對象：q ? D，|N?(q)|?MinPts從對象q到對象p是直接密度可達的：p?N?(q)且|N?(q)| ? MinPts,定義（續(xù)）,從對象q到對象p關于?和MinPts是密度可達的：存在對象鏈p1，p2，…，pn，并且p1=q，pn=p，pi?D

50、，從pi到pi+1關于?和MinPts是直接密度可達的（非對稱）對象p和q關于?和MinPts密度相連：存在對象o ?D，使得從o到對象p和q關于?和MinPts密度可達（對稱）,DBSCAN基本思想,簇：基于密度可達性，密度相連對象的最大集合噪音：不在任何簇中的對象 邊界對象：在簇中的非核心對象，即至少從一個核心對象直接可達,DBSCAN算法,1）任意選擇沒有加簇標簽的點 p2）如果|N?(P)|?MinPts，則p 是核心對

51、象，找到從p 關于? 和MinPts 密度可達的所有點。形成一個新的簇，給簇內所有的對象點加簇標簽。3）如果p 是邊界點, 則處理數據庫的下一點4）重復上述過程，直到所有的點處理完畢,? = 1cmMinPts = 5,不足和改進,只能發(fā)現(xiàn)密度相仿的簇對用戶定義的參數 ? 和 MinPts 敏感計算復雜度為O(n2)采用R-樹等空間索引技術，計算復雜度為o(nlogn),圖示,A 和 B被認為是噪音C1和C2兩個簇合并

52、了,聚類分析,什么是聚類分析?劃分方法（Partitioning Methods）分層方法基于密度的方法異常分析,異常分析,孤立點：與數據的其他部分不同的數據對象一個人的噪音是另一個人的信號信用卡欺詐探測、收入極高或極低的客戶分區(qū)、醫(yī)療分析孤立點挖掘在給定的數據集合中定義什么樣的數據為不一致的找到一個有效的方法來挖掘孤立點統(tǒng)計學方法基于距離的方法基于偏移的方法,實驗,使用Clementine進行聚類挖掘（工具

53、使用參見補充教材）,休息……,Knowledge is power.----BaconReal knowledge is to know the extent of one's ignorance. -----Confucius My life is limited, while knowledge is limitless. ----Chuang-tze

54、

55、返回,支持度-置信度方法的不足,Example 1: (Aggarwal & Yu, PODS98)5000 個學生中3000 喜歡打籃球3750 喜歡吃米飯2000 同時喜歡打籃球和吃米飯關聯(lián)規(guī)則：play basketball ? eat cereal [40%, 66.7%] 該規(guī)則具有欺騙性，因為從整個學生情況來看，有75%的學生喜歡吃米飯，大大高于 66.7%。關聯(lián)規(guī)則：play basketbal

56、l ? not eat cereal [20%, 33.3%]該規(guī)則雖然擁有較低的支持度和置信度，但是比較精確。,支持度-置信度方法的不足,Example 2:X and Y：正相關X and Z：負相關需要一個獨立性或者相關性度量P(B|A)/P(B) 稱為規(guī)則 A => B的“提升”,提升：一種興趣度的度量,correlation, liftP(A)和P(B)同時考慮P(A∪B)=P(B)*P(A), A