數(shù)據(jù)挖掘常用算法概述

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

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

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

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

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

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

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

8、vs. 數(shù)值型關(guān)聯(lián) (基于 處理數(shù)據(jù)的類型)性別＝“女” ? 職業(yè)＝“ 秘書” [1%, 75%] 布爾型關(guān)聯(lián)規(guī)則 性別＝“女” ? 收入 = 2000 [1%, 75%] 數(shù)值型關(guān)聯(lián)規(guī)則 單維 vs. 多維 關(guān)聯(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. 多層 分析那個(gè)品種牌子的啤酒與那個(gè)牌子的尿布有關(guān)系?各種擴(kuò)展相關(guān)性、因果分析關(guān)聯(lián)并不一定意味著相關(guān)或因果最大模式和閉合相集添加約束如, 哪些“小東西”的銷售促發(fā)了“大家伙”的買賣？,關(guān)聯(lián)規(guī)則挖掘的基本過程,找出所有的頻繁項(xiàng)集 F，其中對于任何的 Z ? F，在交易集合D中至少 s%的事務(wù)包含Z根據(jù)置信度和頻繁項(xiàng)集F, 產(chǎn)生關(guān)聯(lián)規(guī)則。具

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)對種類字段處理時(shí)，缺省是對每個(gè)值作為一個(gè)分割Gain和Gain RatioCHAID在Overfitting前停止樹的生成必須都是分類屬性選擇分割。X2檢驗(yàn),從樹中生成分類規(guī)則,用 IF-THEN 這種形式來表現(xiàn)規(guī)則每個(gè)葉子

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

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

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

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

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

30、,第二步：預(yù)測,流失,,,[20,80] 0.2,,通話次數(shù),<20,>=20,,品牌,,消費(fèi)金額,,神州行,,,,[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:流失用戶數(shù)y:未

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

32、,Input nodes,Hidden nodes,Output vector,Input vector: xi,wij,,計(jì)算實(shí)例,一個(gè)訓(xùn)練樣本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é)點(diǎn)4:-0.4,節(jié)點(diǎn)5:0.2,節(jié)點(diǎn)6:0.1學(xué)習(xí)率設(shè)為0.9節(jié)點(diǎn)4:輸入值:w

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

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

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

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

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

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

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

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

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

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

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

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

45、中心的距離，重新分配到與它最近的簇中； 4.回到第二步，直到不再有新的分配發(fā)生。,K-均值算法圖示,,,K-均值算法例子,Given: {2,4,10,12,3,20,30,11,25}, k=2隨機(jī)指派均值: 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)點(diǎn) 相對高效的: 算法復(fù)雜度O(tkn), 其中n 是數(shù)據(jù)對象的個(gè)數(shù), k 是簇的個(gè)數(shù), t是迭代的次數(shù)，通常k, t << n.算法通常終止于局部最優(yōu)解；缺點(diǎn)只有當(dāng)平均值有意義的情況下才能使用，對于標(biāo)稱字段不適用；必須

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

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

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

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

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

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

53、使用參見補(bǔ)充教材）,休息……,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 個(gè)學(xué)生中3000 喜歡打籃球3750 喜歡吃米飯2000 同時(shí)喜歡打籃球和吃米飯關(guān)聯(lián)規(guī)則：play basketball ? eat cereal [40%, 66.7%] 該規(guī)則具有欺騙性，因?yàn)閺恼麄€(gè)學(xué)生情況來看，有75%的學(xué)生喜歡吃米飯，大大高于 66.7%。關(guān)聯(lián)規(guī)則：play basketbal

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