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

關(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)常會(huì)被一起購買？一般用戶的購買過程中是否存在一定的購買時(shí)間序列？具體應(yīng)用：利潤最大化商品貨架設(shè)計(jì)：更加適合客戶的購物路徑貨存安排：實(shí)現(xiàn)超市的零庫存管理用戶分類：提供個(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)、相關(guān)性、或因果結(jié)構(gòu)。應(yīng)用購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計(jì)、loss-leaderanalysis、聚集、分類等。關(guān)聯(lián)規(guī)則挖掘形式化定義給定:交易數(shù)據(jù)庫每筆交易是：一個(gè)項(xiàng)目列表(消費(fèi)者一次購買活動(dòng)中購買的商品)查找:所有描述一個(gè)項(xiàng)目集合與其他項(xiàng)目集合相關(guān)性的規(guī)則應(yīng)用*護(hù)理用品(商店應(yīng)該怎樣提高護(hù)理用品的銷售？)家用電器

*(其他商品的庫存有什么影響?)在產(chǎn)品直銷中使用附加郵寄其它相關(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ù)間的相關(guān)性可稱為規(guī)則（或模式），對(duì)規(guī)則興趣度的描述采用支持度、置信度概念。支持度（Support）：規(guī)則XY在交易數(shù)據(jù)庫D中的支持度是交易集中包含X和Y的交易數(shù)與所有交易數(shù)之比，記為support(XY)，即support(XY)=|{T:XYT，TD}|/|D|，它是概率P（XY），具體表示為：S=總交易數(shù)同時(shí)包含項(xiàng)目集X和Y的交易數(shù)購買商品Y的交易同時(shí)購買商品X和Y的交易購買商品X的交易關(guān)聯(lián)規(guī)則興趣度的度量值：置信度置信度（Confidence），規(guī)則XY在交易集中的置信度是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比，記為confidence(XY)，即confidence(XY)=|{T:XYT，TD}|/|{T:XT，TD}|，它是概率P（X|Y），具體表示為：最小支持度和最小置信度 用戶（分析員）不關(guān)心可信程度太低的規(guī)則，因而用戶需要輸入兩個(gè)參數(shù)：最小支持度和最小置信度。C=購買商品X的交易數(shù)同時(shí)購買商品X和Y的交易數(shù)購買商品Y的交易同時(shí)購買商品X和Y的交易購買商品X的交易支持度和置信度舉例零售商場銷售分析：數(shù)據(jù)項(xiàng)為商品，記錄集合為交易記錄集合規(guī)則為：“購買商品X的顧客，同時(shí)購買商品Y”，即XY；設(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ī)則挖掘的種類布爾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”)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ì)于任何的ZF，在交易集合D中至少s%的事務(wù)包含Z根據(jù)置信度和頻繁項(xiàng)集F,產(chǎn)生關(guān)聯(lián)規(guī)則。具體方法如下：conf(XY)=supp(X)/supp(XY)如果conf(XY)c成立，則產(chǎn)生XY的規(guī)則,因?yàn)?supp(XY)=supp(XY)s且conf(XY)c因此關(guān)聯(lián)規(guī)則的挖掘可以轉(zhuǎn)換為頻繁項(xiàng)集的挖掘和頻繁項(xiàng)集之間的關(guān)聯(lián)。關(guān)聯(lián)規(guī)則挖掘：一個(gè)例子對(duì)于AC：support=support({A、C})=50%confidence=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ī)則挖掘最為重要的步驟Apriori算法是目前最有影響力的一個(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)集。依此類推。Apriori算法連接:用Lk-1自連接得到Ck剪枝:一個(gè)k-項(xiàng)集，如果它的一個(gè)k-1項(xiàng)集（它的子集）不是頻繁的，那他本身也不可能是頻繁的。偽代碼:Ck:長度為k的候選項(xiàng)集Lk:長度為k的頻繁項(xiàng)集L1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=從Lk生成候選項(xiàng)集;對(duì)于數(shù)據(jù)庫中的任一交易tdo如果t中包含Ck+1中所包含的項(xiàng)集，則計(jì)數(shù)加1Lk+1=Ck+1中超過最小支持度的頻繁項(xiàng)集endreturnkLk;Apriori算法—例子數(shù)據(jù)庫D掃描DC1L1L2C2C2掃描DC3L3掃描DApriori夠快了嗎?—性能瓶頸Apriori算法的核心:用頻繁的(k–1)-項(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é)果顯示(TableForm)關(guān)聯(lián)規(guī)則可視化UsingRuleGraph擴(kuò)展知識(shí)：多層關(guān)聯(lián)規(guī)則項(xiàng)通常具有層次底層的項(xiàng)通常支持度也低某些特定層的規(guī)則可能更有意義交易數(shù)據(jù)庫可以按照維或?qū)泳幋a可以進(jìn)行共享的多維挖掘食品面包牛奶脫脂奶光明統(tǒng)一酸奶白黃擴(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ù)庫buys(X,“milk”)buys(X,“bread”)多維關(guān)聯(lián)規(guī)則：規(guī)則內(nèi)包含2個(gè)以上維/謂詞維間關(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í)例：移動(dòng)通信客戶流失分析系統(tǒng)神經(jīng)網(wǎng)絡(luò)其他分類方法預(yù)測（回歸）建立模型過程歷史數(shù)據(jù)模型建模記錄集合預(yù)測數(shù)學(xué)公式規(guī)則集合分類為一個(gè)事件或?qū)ο筮M(jìn)行歸類預(yù)測分類標(biāo)簽（離散值）基于訓(xùn)練集形成一個(gè)模型，訓(xùn)練集中的類標(biāo)簽是已知的。使用該模型對(duì)新的數(shù)據(jù)進(jìn)行分類分類模型：分類器（分類函數(shù)、分類規(guī)則等）預(yù)測:對(duì)連續(xù)或者有序的值進(jìn)行建模和預(yù)測（回歸方法）典型應(yīng)用客戶/用戶分類信用評(píng)分目標(biāo)營銷醫(yī)療診斷…………分類和預(yù)測分類的相關(guān)概念訓(xùn)練集（TrainingSet）：由一組數(shù)據(jù)庫記錄或者元組構(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ī)則，決策樹，或者數(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)練集分類算法IFrank=‘professor’ORyears>6THENtenured=‘yes’模型分類過程:使用模型模型測試集未知數(shù)據(jù)(Jeff,Professor,4)Tenured?本章內(nèi)容分類與預(yù)測的基本概念決策樹分類實(shí)例：移動(dòng)通信客戶流失分析系統(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)age?student?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40決策樹分類的特點(diǎn)優(yōu)點(diǎn)容易生成可以理解的規(guī)則計(jì)算量相對(duì)來說不大可以處理離散和連續(xù)字段可以清晰顯示哪些字段比較重要缺點(diǎn)對(duì)連續(xù)性的字段難以預(yù)測類別太多的時(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è)葉子節(jié)點(diǎn)訓(xùn)練集ID3算法決策樹結(jié)果：“buys_computer”age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40決策樹算法基本算法（貪心算法）自上而下分而治之的方法開始時(shí)，所有的數(shù)據(jù)都在根節(jié)點(diǎn)屬性都是種類字段(如果是連續(xù)的，將其離散化)所有記錄用所選屬性遞歸的進(jìn)行分割屬性的選擇是基于一個(gè)啟發(fā)式規(guī)則或者一個(gè)統(tǒng)計(jì)的度量(如,informationgain)停止分割的條件一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類別沒有屬性可以再用于對(duì)數(shù)據(jù)進(jìn)行分割幾種經(jīng)典算法介紹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和GainRatioCHAID在Overfitting前停止樹的生成必須都是分類屬性選擇分割。X2檢驗(yàn)從樹中生成分類規(guī)則用IF-THEN這種形式來表現(xiàn)規(guī)則每個(gè)葉子節(jié)點(diǎn)都創(chuàng)建一條規(guī)則每個(gè)分割都成為一個(gè)規(guī)則中的一個(gè)條件葉子節(jié)點(diǎn)中的類別就是Then的內(nèi)容規(guī)則對(duì)于人來說更容易理解例子IFage=“<=30”ANDstudent=“no”THENbuys_computer=“no”IFage=“<=30”ANDstudent=“yes”THENbuys_computer=“yes”IFage=“31…40” THENbuys_computer=“yes”IFage=“>40”ANDcredit_rating=“excellent”THENbuys_computer=“yes”IFage=“<=30”ANDcredit_rating=“fair”THENbuys_computer=“no”本章內(nèi)容分類與預(yù)測的基本概念決策樹分類實(shí)例：移動(dòng)通信客戶流失分析系統(tǒng)神經(jīng)網(wǎng)絡(luò)其他分類方法預(yù)測（回歸）應(yīng)用背景與問題定義背景在移動(dò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)用于移動(dòng)通信領(lǐng)域的客戶流失分析，進(jìn)而為通信企業(yè)的實(shí)際業(yè)務(wù)提供指導(dǎo)是一項(xiàng)具有挑戰(zhàn)性的工作定義客戶流失分析，就是利用數(shù)據(jù)挖掘等分析方法，對(duì)已流失客戶過去一段時(shí)間的通話、繳費(fèi)等信息進(jìn)行分析，提煉出流失客戶的行為特征，利用這些特征預(yù)測在網(wǎng)客戶的流失傾向按真實(shí)比例抽取，可能掩蓋流失用戶的特征解決方法：“樣本放大”數(shù)據(jù)預(yù)處理——抽樣分割抽樣原始數(shù)據(jù)（流失概率3.2%）抽樣采樣后（流失概率25%）合并10,000310,000300,00050%20:15,00015,00020,000流失非流失數(shù)據(jù)預(yù)處理——時(shí)間相關(guān)屬性屬性序列S1用戶標(biāo)識(shí)性別年齡入網(wǎng)品牌…1月份通話時(shí)長2月份通話時(shí)長…6月份通話時(shí)長……1月份話費(fèi)…6月份話費(fèi)…是否流失屬性序列Sn“靜態(tài)”屬性流失標(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è)月份的數(shù)值對(duì)趨勢屬性的影響不同，可以對(duì)各個(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

流失非流失非流失用戶ID通話次數(shù)品牌話費(fèi)金額流失標(biāo)志139****88423全球通23品牌非流失神州行全球通第一步：建立決策樹第二步：預(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.45C[x,y]k%x:流失用戶數(shù)y:未流失用戶數(shù)k:流失概率k=x/(x+y)A決策樹算法——數(shù)據(jù)結(jié)構(gòu)主要內(nèi)容分類與預(yù)測的基本概念決策樹分類實(shí)例：移動(dòng)通信客戶流失分析系統(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)k-f加權(quán)和輸入向量X輸出y激活函數(shù)權(quán)重向量w?w0w1wnx0x1xn多層感知系統(tǒng)OutputnodesInputnodesHiddennodesOutputvectorInputvector:xiwij計(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: 輸入值:w14*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.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)練過度前饋神經(jīng)網(wǎng)絡(luò)前饋網(wǎng)絡(luò)的表達(dá)能力布爾函數(shù)。任何布爾函數(shù)可以被具有兩層單元的網(wǎng)絡(luò)準(zhǔn)確表示，盡管對(duì)于最壞的情況，所需隱藏單元的數(shù)量隨著網(wǎng)絡(luò)輸入數(shù)量的增加指數(shù)級(jí)增長。連續(xù)函數(shù)。任何有界的連續(xù)函數(shù)可以由一個(gè)兩層的網(wǎng)絡(luò)以任意小的誤差逼近。這個(gè)理論適用于隱藏層使用sigmoid單元、輸出層使用（非閾值的）線性單元的網(wǎng)絡(luò)。所需的隱藏單元數(shù)量依賴于要逼近的函數(shù)。任意函數(shù)。任意函數(shù)可以被一個(gè)有三層單元的網(wǎng)絡(luò)以任意精度逼近。與前面相同，輸出層使用線性單元，兩個(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é)果勢必是丟失信息。理論和學(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ò)誤?？扇萑涕L時(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ù)測的基本概念決策樹分類實(shí)例：移動(dòng)通信客戶流失分析系統(tǒng)神經(jīng)網(wǎng)絡(luò)其他分類方法預(yù)測（回歸）其它分類方法貝葉斯（Bayesian）分類k-臨近分類基于案例的推理遺傳算法粗糙集理論模糊集方法分類的準(zhǔn)確性：評(píng)估錯(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個(gè)子樣本作為測試數(shù)據(jù)每一個(gè)數(shù)據(jù)集合具有合適的寬度分類的準(zhǔn)確性：混淆矩陣混淆矩陣（confusionmatrix）用來作為分類規(guī)則特征的表示，它包括了每一類的樣本個(gè)數(shù)，包括正確的和錯(cuò)誤的分類。主對(duì)角線給出了每一類正確分類的樣本的個(gè)數(shù)，非對(duì)角線上的元素則表示未被正確分類的樣本個(gè)數(shù)實(shí)際的類預(yù)測的類A類B類C類總計(jì)A類452350B類1038250C類464050總計(jì)5946451503個(gè)類的混淆矩陣分類的準(zhǔn)確性：收益圖●查全率分析圖：X軸：按離網(wǎng)傾向評(píng)分從大到小排序后的客戶占目標(biāo)客戶人數(shù)的百分比；Y軸：前x%的客戶中被準(zhǔn)確預(yù)測為離網(wǎng)的客戶占目標(biāo)客戶中離網(wǎng)總?cè)藬?shù)的百分比，即查全率。

●Lift分析圖：X軸：按離網(wǎng)傾向評(píng)分從大到小排序后的客戶占目標(biāo)客戶人數(shù)的百分比；Y軸：命中率的提升倍數(shù)。

聚類分析聚類分析什么是聚類分析?劃分方法（PartitioningMethods）分層方法基于密度的方法異常分析什么是聚類分析?簇（Cluster）:一個(gè)數(shù)據(jù)對(duì)象的集合在同一個(gè)簇中，對(duì)象之間具有盡可能大的相似性；不同簇的對(duì)象之間具有盡可能大的相異性。聚類分析把一個(gè)給定的數(shù)據(jù)對(duì)象集合分成不同的簇，即“物以類聚”；聚類是一種無監(jiān)督分類法:沒有預(yù)先指定的類別標(biāo)識(shí)；典型的應(yīng)用作為一個(gè)獨(dú)立的分析工具，用于了解數(shù)據(jù)的分布；作為其它算法的一個(gè)數(shù)據(jù)預(yù)處理步驟；應(yīng)用聚類分析的例子市場銷售:幫助市場人員發(fā)現(xiàn)客戶數(shù)據(jù)庫中不同群體，然后利用這些知識(shí)來開展一個(gè)目標(biāo)明確的市場計(jì)劃；土地使用:在一個(gè)陸地觀察數(shù)據(jù)庫中標(biāo)識(shí)那些土地使用相似的地區(qū)；保險(xiǎn):對(duì)購買了汽車保險(xiǎn)的客戶，標(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)某些還是所有的隱含模式；聚類分析中的數(shù)據(jù)類型如何度量對(duì)象間的距離？歐幾里德距離曼哈頓距離明考斯基距離聚類分析什么是聚類分析?劃分方法（PartitioningMethods）分層方法基于密度的方法異常分析劃分方法:基本概念劃分方法:將一個(gè)包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫組織成k個(gè)劃分（k<=n），其中每個(gè)劃分代表一個(gè)簇（Cluster）。給定一個(gè)k，要構(gòu)造出k個(gè)簇，并滿足采用的劃分準(zhǔn)則：全局最優(yōu):盡可能的列舉所有的劃分；啟發(fā)式方法:k-均值和k-中心點(diǎn)算法k-均值(MacQueen’67):由簇的中心來代表簇；k-中心點(diǎn)或PAM(Partitionaroundmedoids)(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è)簇中心的距離，重新分配到與它最近的簇中；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,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=25K-均值算法優(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)稱字段不適用；必須事先給定要生成的簇的個(gè)數(shù)；對(duì)“噪聲”和異常數(shù)據(jù)敏感；不能發(fā)現(xiàn)非凸面形狀的數(shù)據(jù)。聚類分析什么是聚類分析?劃分方法（PartitioningMethods）分層方法基于密度的方法基于網(wǎng)格的方法異常分析層次方法采用距離作為衡量聚類的標(biāo)準(zhǔn)。該方法不需要指定聚類的個(gè)數(shù)，但用戶可以指定希望得到的簇的數(shù)目作為一個(gè)結(jié)束條件。Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0聚集(AGNES)分裂(DIANA)層次聚類方法討論層次方法的主要缺點(diǎn)：沒有良好的伸縮性:時(shí)間復(fù)雜度至少是O(n2)一旦一個(gè)合并或分裂被執(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)行層次聚類。聚類分析什么是聚類分析?劃分方法（PartitioningMethods）分層方法基于密度的方法異常分析定義兩個(gè)參數(shù)：：鄰域的最大半徑MinPts：數(shù)據(jù)對(duì)象-鄰域內(nèi)最少的數(shù)據(jù)個(gè)數(shù)給定對(duì)象集合D鄰域N(p):對(duì)象p的半徑為內(nèi)的區(qū)域，即{qD|dist(p,q)<=}核心對(duì)象：qD，|N(q)|MinPts從對(duì)象q到對(duì)象p是直接密度可達(dá)的：pN(q)且|N(q)|MinPtspqMinPts=5=1cm定義（續(xù)）從對(duì)象q到對(duì)象p關(guān)于和MinPts是密度可達(dá)的：存在對(duì)象鏈p1，p2，…，pn，并且p1=q，pn=p，piD，從pi到pi+1關(guān)于和MinPts是直接密度可達(dá)的（非對(duì)稱）對(duì)象p和q關(guān)于和MinPts密度相連：存在對(duì)象oD，使得從o到對(duì)象p和q關(guān)于和MinPts密度可達(dá)（對(duì)稱）pqopqp1DBSCAN基本思想簇：基于密度可達(dá)性，密度相連對(duì)象的最大集合噪音：不在任何簇中的對(duì)象邊界對(duì)象：在簇中的非核心對(duì)象，即至少從一個(gè)核心對(duì)象直接可達(dá)核心對(duì)象邊界點(diǎn)噪音=1cmMinPts=5DBSCAN算法1）任意選擇沒有加簇標(biāo)簽的點(diǎn)p2）如果|N(P)|MinPts，則p是核心對(duì)象，找到從p關(guān)于和MinPts密度可達(dá)的所有點(diǎn)。形成一個(gè)新的簇，給簇內(nèi)所有的對(duì)象點(diǎn)加