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

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

2、庫(kù)存管理用戶分類 ：提供個(gè)性化的服務(wù),其他典型應(yīng)用,相關(guān)文獻(xiàn)的收集購(gòu)物籃 = 文檔（Document）項(xiàng) 目 = 單詞（Word）相關(guān)網(wǎng)站的收集購(gòu)物籃 = 詞句（Sentences）項(xiàng) 目 =鏈接文檔（Document）,什么是關(guān)聯(lián)規(guī)則挖掘?,關(guān)聯(lián)規(guī)則挖掘簡(jiǎn)單的說，關(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)用購(gòu)物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計(jì)、 loss-leader analysis、聚集、分類等。,關(guān)聯(lián)規(guī)則挖掘形式化定義,給定:交易數(shù)據(jù)庫(kù) 每筆交易是：一個(gè)項(xiàng)目列表 (消費(fèi)者一次購(gòu)買活動(dòng)中購(gòu)買的商品)查找: 所有描述一個(gè)項(xiàng)目集合與其他項(xiàng)目集合相關(guān)性的規(guī)則應(yīng)用* ? 護(hù)理用品 (商店應(yīng)該怎樣提高護(hù)理用品的銷售？)家用電器 ? * (其他商品的庫(kù)存有什么影響?)在產(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ī)則（或模式），對(duì)規(guī)則興趣度的描述采用支持度、置信度概念。支持度（Support）：規(guī)則X?Y在交易數(shù)據(jù)庫(kù)D中的支持度是交易集中包含X和Y的交易數(shù)與所有交易數(shù)之比，記為support(X?Y)，即support(X?Y)=|{T:X?Y? T，T?D}|/ |D|，它是概率P（ X?Y ），具體表示為：,,,,,,購(gòu)買商品Y的交易,同時(shí)購(gòu)買商品X和Y的交易,購(gòu)買商品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ù)：最小支持度和最小置信度。,支持度和置信度舉例,零售商場(chǎng)銷售分析：數(shù)據(jù)項(xiàng)為商品，記

7、錄集合為交易記錄集合規(guī)則為：“購(gòu)買商品X的顧客，同時(shí)購(gòu)買商品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ù)庫(kù)表分區(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，其中對(duì)于任何的 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è)例子,對(duì)于 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ù)挖掘可以處理變長(zhǎng)的數(shù)據(jù)它的計(jì)算的消耗量是可以預(yù)見的 缺點(diǎn)當(dāng)問題變大時(shí)，計(jì)算量增長(zhǎng)得厲害難以決定正確的數(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: 長(zhǎng)度為k的候選項(xiàng)集Lk :長(zhǎng)度為k的頻繁項(xiàng)集L1 = {frequent items}; for (k = 1; Lk !=?; k++) do begin Ck+1 = 從Lk 生成候選項(xiàng)集; 對(duì)于數(shù)

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

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

16、Form ),關(guān)聯(lián)規(guī)則可視化Using Rule Graph,擴(kuò)展知識(shí)：多層關(guān)聯(lián)規(guī)則,項(xiàng)通常具有層次底層的項(xiàng)通常支持度也低某些特定層的規(guī)則可能更有意義交易數(shù)據(jù)庫(kù)可以按照維或?qū)泳幋a可以進(jìn)行共享的多維挖掘,擴(kuò)展知識(shí)：多維關(guān)聯(lián)規(guī)則,單維關(guān)聯(lián)規(guī)則（維內(nèi)關(guān)聯(lián)規(guī)則）關(guān)聯(lián)規(guī)則中僅包含單個(gè)謂詞（維）通常針對(duì)的是事務(wù)數(shù)據(jù)庫(kù) 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ù)測(cè),本章內(nèi)容,分類與預(yù)測(cè)的基本概念決策樹分類實(shí)例：移動(dòng)通信客戶流失分析系統(tǒng)神經(jīng)網(wǎng)絡(luò)其他分類方法預(yù)測(cè)（回

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

19、ning Set）：由一組數(shù)據(jù)庫(kù)記錄或者元組構(gòu)成，每個(gè)記錄由有關(guān)字段值組成特征向量，這些字段稱為屬性。用于分類的屬性稱為標(biāo)簽屬性。標(biāo)簽屬性也就是訓(xùn)練集的類別標(biāo)記。標(biāo)簽屬性的類型必須是離散的，而且標(biāo)簽屬性的可能值的數(shù)目越少越好。,分類的兩個(gè)步驟,模型創(chuàng)建: 對(duì)一個(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ù)測(cè)未來或者類別未知的記錄估計(jì)模型的準(zhǔn)確率使用創(chuàng)建的模型在一個(gè)測(cè)試集上進(jìn)行預(yù)測(cè)，并將結(jié)果和實(shí)際值進(jìn)行比較準(zhǔn)確率：測(cè)試集和訓(xùn)練集是獨(dú)立的。,分類過程：模型創(chuàng)建（學(xué)習(xí)過程）,訓(xùn)練集,,,分類算法,,IF rank = ‘professor’OR years > 6THEN tenured = ‘yes’,模型,,,,分類過程 : 使用模型,模型,測(cè)試集,,,,,未知數(shù)據(jù),(J

21、eff, Professor, 4),,,,Tenured?,本章內(nèi)容,分類與預(yù)測(cè)的基本概念決策樹分類實(shí)例：移動(dòng)通信客戶流失分析系統(tǒng)神經(jīng)網(wǎng)絡(luò)其他分類方法預(yù)測(cè)（回歸）,使用決策樹進(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ì)算量相對(duì)來說不大可以處理離散和連續(xù)字段可以清晰顯示哪些字段比較重要缺點(diǎn)對(duì)連續(xù)性的字段難以預(yù)測(cè)類別太多的時(shí)候，錯(cuò)誤的可能性會(huì)加大一般情況下，標(biāo)簽屬性的個(gè)數(shù)有限,決策樹的生成與使用,決策樹生成算法分成兩個(gè)步驟樹的生成開始，數(shù)據(jù)都在根節(jié)點(diǎn)遞歸的進(jìn)行數(shù)據(jù)分割樹的修剪去掉一些可能是噪音或者異常的數(shù)據(jù)決策樹使用: 對(duì)未知數(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è)類別沒有屬性可以再用于對(duì)數(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)對(duì)種類字段處理時(shí)，缺省是對(duì)每個(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ī)則對(duì)于人來說更容易理解例子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ù)測(cè)的基本概念決策樹分類實(shí)例：移動(dòng)通信客戶流失分析系統(tǒng)神經(jīng)網(wǎng)絡(luò)其他分類方法預(yù)測(cè)（回歸）,應(yīng)用背景與問題定義,背景在移動(dòng)通信領(lǐng)域，客戶流失成為通信運(yùn)營(yíng)企業(yè)關(guān)注的焦點(diǎn)通信業(yè)務(wù)產(chǎn)生的海量、珍貴數(shù)據(jù)為數(shù)據(jù)挖掘的研究提供了堅(jiān)實(shí)的基礎(chǔ)把數(shù)據(jù)挖掘理論應(yīng)用于移動(dòng)通信領(lǐng)域的客戶流失分析，進(jìn)而為通信企業(yè)的實(shí)際業(yè)務(wù)提供指導(dǎo)是一項(xiàng)具有挑戰(zhàn)性的工作定義客戶流失分析，就是利用數(shù)據(jù)挖掘等分析方法，對(duì)已流失客戶過去一段時(shí)間的通話、繳費(fèi)等信息進(jìn)行分

27、析，提煉出流失客戶的行為特征，利用這些特征預(yù)測(cè)在網(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)志,解決方法：生成匯總屬性（求和、取均值等）生成“趨勢(shì)屬性”，如由屬性序列S1生成屬性“通話時(shí)長(zhǎng)趨勢(shì)”,問題：決策樹算法缺乏處理時(shí)間相關(guān)屬性的能力，致使效率下降,,數(shù)據(jù)預(yù)處理——生成趨勢(shì)屬性,,把每個(gè)月通話時(shí)長(zhǎng)Y視為月份X（取值從1到6）的線性函數(shù)，即Y = α + βX ，系數(shù)β作為屬性“通話時(shí)長(zhǎng)趨勢(shì)”的取值，從而把求趨勢(shì)屬性的問題轉(zhuǎn)化為簡(jiǎn)單的線形回歸問題，,數(shù)據(jù)預(yù)處理——生成趨勢(shì)屬性（續(xù)）,,實(shí)際應(yīng)用中，發(fā)現(xiàn)各個(gè)

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

30、,第二步：預(yù)測(cè),流失,,,[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ù)測(cè)的基本概念決策樹分類實(shí)例：移動(dòng)通信客戶流失分析系統(tǒng)神經(jīng)網(wǎng)絡(luò)其他分類方法預(yù)測(cè)（回歸）,神經(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其他偏置同理,終止條件,對(duì)所有樣本作一次掃描稱為一個(gè)周期終止條件:對(duì)前一周期所有Wij的修改值都小于某個(gè)指定的閾值;或超過預(yù)先指定的周期數(shù).防止訓(xùn)練

35、過度,前饋神經(jīng)網(wǎng)絡(luò),前饋網(wǎng)絡(luò)的表達(dá)能力布爾函數(shù)。任何布爾函數(shù)可以被具有兩層單元的網(wǎng)絡(luò)準(zhǔn)確表示，盡管對(duì)于最壞的情況，所需隱藏單元的數(shù)量隨著網(wǎng)絡(luò)輸入數(shù)量的增加指數(shù)級(jí)增長(zhǎng)。 連續(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ī)則簡(jiǎn)單，便于計(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é)果勢(shì)

37、必是丟失信息。理論和學(xué)習(xí)算法還有待于進(jìn)一步完善和提高。,應(yīng)用,適合神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的問題 實(shí)例是用很多“屬性-值”對(duì)表示的。 目標(biāo)函數(shù)的輸出可能是離散值、實(shí)數(shù)值或者由若干實(shí)數(shù)屬性或離散屬性組成的向量。 訓(xùn)練數(shù)據(jù)可能包含錯(cuò)誤。 可容忍長(zhǎng)時(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ù)測(cè)的基本概念

38、決策樹分類實(shí)例：移動(dòng)通信客戶流失分析系統(tǒng)神經(jīng)網(wǎng)絡(luò)其他分類方法預(yù)測(cè)（回歸）,其它分類方法,貝葉斯（Bayesian）分類k-臨近分類基于案例的推理遺傳算法粗糙集理論模糊集方法,分類的準(zhǔn)確性：評(píng)估錯(cuò)誤率,數(shù)據(jù)分區(qū):訓(xùn)練-測(cè)試數(shù)據(jù)將一個(gè)數(shù)據(jù)集合分成兩個(gè)獨(dú)立的數(shù)據(jù)集。例如：訓(xùn)練數(shù)據(jù) (2/3), 測(cè)試數(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è)子樣本作為測(cè)試數(shù)據(jù)每一個(gè)數(shù)據(jù)集合具有合適的寬度,分類的準(zhǔn)確性：混淆矩陣,混淆矩陣（confusion matrix ）用來作為分類規(guī)則特征的表示，它包括了每一類的樣本個(gè)數(shù)，包括正確的和錯(cuò)誤的分類。主對(duì)角線給出了每一類正確分類的樣本的個(gè)數(shù)，非對(duì)角線上的元素則表示未被正確分類的樣本個(gè)數(shù),3個(gè)類的混淆矩陣,分類的準(zhǔn)確性：收益圖,,,,,●查全率分析圖：X軸：按離網(wǎng)傾向評(píng)分從大到小排序后的客戶占目標(biāo)客戶人數(shù)的百分比；Y軸：前x%的客戶

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

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

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

43、,聚類分析中的數(shù)據(jù)類型,如何度量對(duì)象間的距離？歐幾里德距離 曼哈頓距離 明考斯基距離,聚類分析,什么是聚類分析?劃分方法（Partitioning Methods）分層方法基于密度的方法異常分析,劃分方法: 基本概念,劃分方法: 將一個(gè)包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)組織成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ù)對(duì)象來代表。,K-均值算法,給定k，算法的處理流程如下:1.隨機(jī)的把所有對(duì)象分配到k個(gè)非空的簇中；2.計(jì)算每個(gè)簇的平均值，并用該平均值代表相應(yīng)的簇；3.將每個(gè)對(duì)象根據(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) 相對(duì)高效的: 算法復(fù)雜度O(tkn), 其中n 是數(shù)據(jù)對(duì)象的個(gè)數(shù), k 是簇的個(gè)數(shù), t是迭代的次數(shù)，通常k, t << n.算法通常終止于局部最優(yōu)解；缺點(diǎn)只有當(dāng)平均值有意義的情況下才能使用，對(duì)于標(biāo)稱字段不適用；必須

47、事先給定要生成的簇的個(gè)數(shù)；對(duì)“噪聲”和異常數(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 動(dòng)態(tài)調(diào)整子聚類的質(zhì)量。CURE (1998): 從聚類中選擇分布“好”的數(shù)據(jù)點(diǎn)，并以指定的比例向聚類中心收縮。CHAMELEON (1999): 利用動(dòng)態(tài)建模技術(shù)進(jìn)行層次聚類。,聚類分析,什么是聚類分析?劃分方法（Partitioning Methods）分層方法基于密度的方法異常分析,定義,兩個(gè)參數(shù)：?：鄰域的最大

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

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

51、象，找到從p 關(guān)于? 和MinPts 密度可達(dá)的所有點(diǎn)。形成一個(gè)新的簇，給簇內(nèi)所有的對(duì)象點(diǎn)加簇標(biāo)簽。3）如果p 是邊界點(diǎn), 則處理數(shù)據(jù)庫(kù)的下一點(diǎn)4）重復(fù)上述過程，直到所有的點(diǎn)處理完畢,? = 1cmMinPts = 5,不足和改進(jìn),只能發(fā)現(xiàn)密度相仿的簇對(duì)用戶定義的參數(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ù)對(duì)象一個(gè)人的噪音是另一個(gè)人的信號(hào)信用卡欺詐探測(cè)、收入極高或極低的客戶分區(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