數(shù)據(jù)挖掘算法介紹第一頁，共五十二頁，2022年，8月28日數(shù)據(jù)挖掘十大經(jīng)典算法K-MEANSC4.5SVMEMKnn貝葉斯CARTAdaboostPagerankApriori第二頁，共五十二頁，2022年，8月28日聚類算法層次聚類K-means聚類基于密度的聚類(DBSCAN)模糊聚類（FCM）兩步聚類Kohonen網(wǎng)絡(luò)聚類平衡數(shù)據(jù)——SMOTE算法分類算法KNN算法決策樹（C5.0,CART）人工神經(jīng)網(wǎng)絡(luò)隨機(jī)森林支持向量機(jī)（SVM）

第三頁，共五十二頁，2022年，8月28日基于密度的聚類DBSCAN——基于高密度連通區(qū)域的聚類OPTICS——通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)DENCLUE——基于密度分布函數(shù)的聚類第四頁，共五十二頁，2022年，8月28日DBSCAN聚類DBSCAN聚類認(rèn)為，在整個(gè)樣本空間中，目標(biāo)類簇是由一群稠密樣本點(diǎn)構(gòu)成，這些稠密樣本點(diǎn)被低密度區(qū)域（噪聲）分割，而算法的目的就是要過濾低密度區(qū)域，發(fā)現(xiàn)稠密樣本點(diǎn)。DBSCAN是一種基于高密度聯(lián)通區(qū)域的聚類算法，它將類簇定義為高密度相連點(diǎn)的最大集合。它本身對(duì)噪聲不敏感，并且能發(fā)現(xiàn)任意形狀的類簇。Clusters第五頁，共五十二頁，2022年，8月28日DBSCAN特點(diǎn)發(fā)現(xiàn)任意形狀的聚類處理噪音一遍掃描需要密度參數(shù)作為終止條件第六頁，共五十二頁，2022年，8月28日基本概念（1）E鄰域：給定對(duì)象半徑為E內(nèi)的區(qū)域稱為該對(duì)象的E鄰域（2）核對(duì)象：如果一個(gè)對(duì)象E鄰域內(nèi)的樣本點(diǎn)數(shù)大于等于事先給定的最小樣本點(diǎn)數(shù)MinPts，則稱該對(duì)象為核對(duì)象（3）直接密度可達(dá)：給定一個(gè)對(duì)象集合D，如果p在q的E鄰域內(nèi)，而q是一個(gè)核心對(duì)象，則稱對(duì)象p從對(duì)象q出發(fā)時(shí)是直接密度可達(dá)。第七頁，共五十二頁，2022年，8月28日基本概念（4）密度可達(dá)：如果存在一個(gè)對(duì)象鏈

對(duì)于

是從關(guān)于Eps和MinPts直接密度可達(dá)的，則對(duì)象p是從對(duì)象q關(guān)于Eps和MinPts密度可達(dá)的(density-reachable)。（5）密度相連：如果存在對(duì)象O∈D，使對(duì)象p和q都是從O關(guān)于Eps和MinPts密度可達(dá)的，那么對(duì)象p到q是關(guān)于Eps和MinPts密度相連的第八頁，共五十二頁，2022年，8月28日算法（1）對(duì)數(shù)據(jù)集中的任一點(diǎn)p找到它的所有直接密度可達(dá)，標(biāo)記p為核心點(diǎn)或邊緣點(diǎn)或噪聲點(diǎn)（2）重復(fù)上述步驟，標(biāo)記出所有點(diǎn)。（3）聚類：剔除噪聲點(diǎn)①依據(jù)密度可達(dá)或密度相連，將距離小于eps的核心點(diǎn)連接成一個(gè)類②將所有邊緣點(diǎn)依次分派到相應(yīng)核心點(diǎn)的類中第九頁，共五十二頁，2022年，8月28日兩步聚類兩步聚類：Chiu，2001年在BIRCH（BalancedIterativeReducingandClusteringusingHierarchies）算法基礎(chǔ)上提出的一種改進(jìn)算法。特點(diǎn)：

算法尤其適合于大型數(shù)據(jù)集的聚類研究通過兩步實(shí)現(xiàn)數(shù)據(jù)聚類同時(shí)處理數(shù)值型聚類變量和分類型聚類變量根據(jù)一定準(zhǔn)則確定聚類數(shù)目診斷樣本中的離群點(diǎn)和噪聲數(shù)據(jù)

數(shù)值型——?dú)W式距離

數(shù)值型+分類型——對(duì)數(shù)似然距離第十頁，共五十二頁，2022年，8月28日兩步聚類——預(yù)聚類一個(gè)聚類特征CF是一個(gè)三元組（N,LS,SS）,N是簇中的點(diǎn)的數(shù)目，LS是N個(gè)點(diǎn)的線性和，SS是N個(gè)點(diǎn)的平方和。第十一頁，共五十二頁，2022年，8月28日兩步聚類——預(yù)聚類預(yù)聚類過程:建立CF樹

(1)視所有數(shù)據(jù)為大類，統(tǒng)計(jì)量存在根結(jié)點(diǎn)中(2)讀入一個(gè)樣本點(diǎn)，從CF樹的根結(jié)點(diǎn)開始，利用結(jié)點(diǎn)的統(tǒng)計(jì)量，計(jì)算數(shù)據(jù)與中間結(jié)點(diǎn)的對(duì)數(shù)似然距離。沿對(duì)數(shù)似然距離最小的中間結(jié)點(diǎn)依次向下選擇路徑直到葉結(jié)點(diǎn)(3)計(jì)算與子樹中所有葉結(jié)點(diǎn)（子類）的對(duì)數(shù)似然距離，找到距離最近的葉結(jié)點(diǎn)第十二頁，共五十二頁，2022年，8月28日兩步聚類——預(yù)聚類預(yù)聚類過程(1)如果最近距離小于一定閾值，則該數(shù)據(jù)被相應(yīng)的葉結(jié)點(diǎn)“吸收”；否則，該數(shù)據(jù)將“開辟”一個(gè)新的葉結(jié)點(diǎn)。重新計(jì)算葉結(jié)點(diǎn)和相應(yīng)所有父結(jié)點(diǎn)的匯總統(tǒng)計(jì)量(2)葉結(jié)點(diǎn)足夠大時(shí)應(yīng)再分裂成兩個(gè)葉結(jié)點(diǎn)(3)葉結(jié)點(diǎn)個(gè)數(shù)達(dá)到允許的最大聚類數(shù)目時(shí)，應(yīng)適當(dāng)增加閾值重新建樹，以得到一棵較小的CF樹(4)重復(fù)上述過程，直到所有數(shù)據(jù)均被分配到某個(gè)葉結(jié)點(diǎn)（子類）為止第十三頁，共五十二頁，2022年，8月28日兩步聚類——聚類(1)聚類過程：分析對(duì)象是預(yù)聚類所形成的稠密區(qū)域(2)方法：層次聚類法(3)逐步將較多的小類合并為較少的大類，再將較少的大類合并成更少的更大類，最終將更大類的合并成一個(gè)大類，是一個(gè)類不斷“凝聚”的過程第十四頁，共五十二頁，2022年，8月28日兩步聚類——聚類數(shù)目的確定第一階段：依據(jù)BIC，確定粗略的聚類數(shù)找到R1(J)取最小值（Modeler規(guī)定R1(J)應(yīng)小于0.04）的J為聚類數(shù)目的“粗略”估計(jì)，即BIC減小幅度最小的J第十五頁，共五十二頁，2022年，8月28日兩步聚類——聚類數(shù)目的確定第二階段：對(duì)“粗略”估計(jì)值J的修正2,3,4,…,J中選擇。僅依據(jù)類間對(duì)數(shù)似然距離，不考慮模型復(fù)雜度J類時(shí)的最小對(duì)數(shù)似然距離d(4)d(3)d(2)d(5)計(jì)算R2(J-1)、R2(J-2)到R2(2)，反映J-1類的類內(nèi)差是J類的倍數(shù)。Modeler找到最大值,若最大值是次大值的1.15倍以上，則最大值對(duì)應(yīng)的J為最終聚類數(shù)R2(J)是聚類合并過程中類間差異最小值變化的相對(duì)指標(biāo)第十六頁，共五十二頁，2022年，8月28日模糊聚類——FCMFCM與HCM的主要區(qū)別在于FCM用模糊劃分，使得每個(gè)給定數(shù)據(jù)點(diǎn)用值在0，1間的隸屬度來確定其屬于各個(gè)組的程度。與引入模糊劃分相適應(yīng)，隸屬矩陣U允許有取值在(0,1)間的元素，滿足第十七頁，共五十二頁，2022年，8月28日

目標(biāo)函數(shù)：SSE=

(2)拉格朗日乘數(shù)法這里λj，j=1到n，是(1)式的n個(gè)約束式的拉格朗日乘子。其中，m?[1，+)是一個(gè)加權(quán)指數(shù)，為第I個(gè)聚類中心與第j個(gè)數(shù)據(jù)間的歐幾里德距離。第十八頁，共五十二頁，2022年，8月28日對(duì)所有輸入?yún)⒘壳髮?dǎo)，使式(2)達(dá)到最小。得到解為：（4）（5）其中，m?[1，+)是一個(gè)加權(quán)指數(shù)，為第I個(gè)聚類中心與第j個(gè)數(shù)據(jù)間的歐幾里德距離。模糊質(zhì)心的定義類似于傳統(tǒng)的質(zhì)心定義，不同之處在于所有點(diǎn)都考慮，并且每個(gè)點(diǎn)對(duì)質(zhì)心的貢獻(xiàn)要根據(jù)它的隸屬度加權(quán)。第十九頁，共五十二頁，2022年，8月28日FCM算法實(shí)現(xiàn)step1：初始化聚類中心，用值在0，1間的隨機(jī)數(shù)初始化

隸屬矩陣U，使其滿足式(1)中的約束條件。step2：用式(4)計(jì)算k個(gè)聚類中心ki，i=1,…,k。step3：根據(jù)式(2)計(jì)算目標(biāo)函數(shù)。如果它小于某個(gè)確定的閾值，或它相對(duì)上次目標(biāo)函數(shù)值的改變量小于某個(gè)閾值，則算法停止。step4：用（5）計(jì)算新的U矩陣。返回步驟2。FCM算法需要設(shè)置兩個(gè)參數(shù)：一個(gè)是聚類數(shù)目k，一個(gè)是參數(shù)m。第二十頁，共五十二頁，2022年，8月28日Kohonen網(wǎng)絡(luò)聚類——概述聚類中的主要問題：

如何測(cè)度數(shù)據(jù)點(diǎn)之間的“親疏程度”怎樣的方式實(shí)施聚類Kohonen網(wǎng)絡(luò)的基本策略是：第一：采用歐氏距離作為數(shù)據(jù)“親疏程度”的測(cè)度第二：模擬人腦神經(jīng)細(xì)胞的機(jī)理通過競爭“獲勝”實(shí)現(xiàn)聚類過程第二十一頁，共五十二頁，2022年，8月28日Kohonen網(wǎng)絡(luò)聚類——拓?fù)浣Y(jié)構(gòu)Kohonen網(wǎng)絡(luò)兩層、前饋式、全連接的拓?fù)浣Y(jié)構(gòu)輸入節(jié)點(diǎn)的個(gè)數(shù)取決于聚類變量的個(gè)數(shù)輸出節(jié)點(diǎn)的個(gè)數(shù)即為聚類數(shù)目第二十二頁，共五十二頁，2022年，8月28日Kohonen網(wǎng)絡(luò)聚類——聚類過程(鳶尾花為例)輸入層輸出層歐式距離需提前確定聚類數(shù)目輸入變量個(gè)數(shù)第二十三頁，共五十二頁，2022年，8月28日Kohonen網(wǎng)絡(luò)聚類——聚類過程輸入層輸出層第二十四頁，共五十二頁，2022年，8月28日Kohonen網(wǎng)絡(luò)聚類——聚類過程輸入層輸出層拉動(dòng)多少？第二十五頁，共五十二頁，2022年，8月28日Kohonen網(wǎng)絡(luò)聚類——聚類過程輸入層輸出層將誰推向遠(yuǎn)方？第二十六頁，共五十二頁，2022年，8月28日Kohonen網(wǎng)絡(luò)聚類——聚類過程拉動(dòng)多少？對(duì)獲勝節(jié)點(diǎn)的權(quán)值調(diào)整為：式中，為t時(shí)刻的學(xué)習(xí)率。將誰推向遠(yuǎn)方？——將獲勝節(jié)點(diǎn)的鄰接點(diǎn)推向遠(yuǎn)方鄰接點(diǎn)：與的距離在指定范圍內(nèi)的輸出節(jié)點(diǎn)都視為鄰接點(diǎn)。對(duì)鄰接點(diǎn)的權(quán)值調(diào)整的計(jì)算方法是：式中為核函數(shù)，反映的是t時(shí)刻鄰接節(jié)點(diǎn)與之間距離的側(cè)度。clementine中采用的是切比雪夫距離，即：即以單個(gè)維的距離最大值作為距離的測(cè)度。第二十七頁，共五十二頁，2022年，8月28日平衡數(shù)據(jù)——基于SMOTE算法欠抽樣：通過去除訓(xùn)練數(shù)據(jù)多數(shù)分類中的樣本數(shù)從而達(dá)到平衡數(shù)據(jù)的目的。過抽樣：形成新的少量分類樣本從而達(dá)到平衡數(shù)據(jù)的目的。SMOTE算法主要思想是：通過在一些位置相近的少數(shù)類樣本中插入新樣本以期達(dá)到平衡樣本的目的。SMOTE算法的特點(diǎn)是不按照隨機(jī)過抽樣方法簡單的復(fù)制樣本，而是增加新的并不存在的樣本，因此在一定程度上可以避免過度擬合。第二十八頁，共五十二頁，2022年，8月28日假設(shè)有少數(shù)類樣本，每一個(gè)樣本x，搜索其K個(gè)少數(shù)類最近鄰樣本，在k個(gè)最近鄰樣本中隨機(jī)選擇N個(gè)樣本，記為y1,y2,y3,...yn。在少數(shù)類樣本x與yj之間進(jìn)行隨機(jī)線性插值，構(gòu)造新的少數(shù)類樣本pj。其中，rand(0,1)表示區(qū)間（0，1）內(nèi)的一個(gè)隨機(jī)數(shù)。第二十九頁，共五十二頁，2022年，8月28日KNN算法基本原理：對(duì)一個(gè)待分類的數(shù)據(jù)對(duì)象x，從訓(xùn)練數(shù)據(jù)集中找出與之空間距離（歐式距離）最近的k個(gè)點(diǎn)，取這k個(gè)點(diǎn)的眾數(shù)類作為該數(shù)據(jù)點(diǎn)的類賦給這個(gè)新對(duì)象。問題：（1）如何選取k？k=1?k=n?（2）維度災(zāi)難？第三十頁，共五十二頁，2022年，8月28日k的選取（1）誤差平衡法：選定測(cè)試集，將k由小變大逐漸遞增，計(jì)算測(cè)試誤差，制作k與測(cè)試誤差的曲線圖，從中確定使測(cè)試誤差最小且適中的k值。（2）交叉驗(yàn)證：小數(shù)據(jù)集維度災(zāi)難增加變量的維度，會(huì)使數(shù)據(jù)變得越來越稀疏，這會(huì)導(dǎo)致每一點(diǎn)附近的真實(shí)密度估計(jì)出現(xiàn)較大偏差。所以KNN更適用于低維問題。第三十一頁，共五十二頁，2022年，8月28日決策樹——C5.0根節(jié)點(diǎn)葉節(jié)點(diǎn)中間節(jié)點(diǎn)2叉樹和多叉樹第三十二頁，共五十二頁，2022年，8月28日決策樹——C5.0x1x225854第三十三頁，共五十二頁，2022年，8月28日決策樹——C5.0決策樹生長差異顯著下降：分組樣本中輸出變量取值的差異性是否隨決策樹的生長而顯著減少。第一，如何從眾多的輸入變量中選擇一個(gè)當(dāng)前最佳的分組變量？第二，如何從分組變量的眾多取值中找到一個(gè)最佳的分割點(diǎn)？決策樹剪枝預(yù)修剪：1：預(yù)先指定決策樹生長的最大深度2：預(yù)先指定樣本量的最小值后修剪：允許決策樹充分生長，計(jì)算決策子樹的預(yù)測(cè)誤差，當(dāng)誤差高于某預(yù)定誤差則應(yīng)停止修建，否則可繼續(xù)修剪。第三十四頁，共五十二頁，2022年，8月28日決策樹——C5.0C5.0用于建立多叉的分類樹，要求輸入變量是分類型或數(shù)值型，輸出變量是分類型。以信息增益率為標(biāo)準(zhǔn)確定決策樹分支準(zhǔn)則，尋找最佳分組變量和分割點(diǎn)。CART既可以建立分類數(shù)也可以建立回歸樹，但是CART只能建立二叉樹，采用GINI系數(shù)和方差作為確定最佳分組變量和分割點(diǎn)的依據(jù)。CHAID的輸入變量和輸出變量可以是分類型也可以是數(shù)值型，CHAID能夠建立多叉樹。從統(tǒng)計(jì)顯著性檢驗(yàn)角度確定當(dāng)前最佳分組變量和分割點(diǎn)。QUEST的輸入變量可以是分類型也可以是數(shù)值型，輸出變量為分類型變量，只能建立二叉樹。第三十五頁，共五十二頁，2022年，8月28日C5.0——如何從眾多的輸入變量中選擇一個(gè)當(dāng)前最佳的分組變量？信息熵：信息量的數(shù)學(xué)期望，是信源發(fā)出信息前的平均不確定性，也稱先驗(yàn)熵。后驗(yàn)熵：已知信號(hào)U的概率分布P(U)且收到信號(hào)V=vj，發(fā)出信號(hào)的概率分布為P(U|vj)，信源的平均不確定性：信息增益：信息消除隨機(jī)不確定性的程度信息增益率：P(ui)差別越小，信息熵越大，平均不確定性越大第三十六頁，共五十二頁，2022年，8月28日C5.0——如何從分組變量的眾多取值中找到最佳的分割點(diǎn)？分類型分組變量：有k個(gè)類別，將樣本分成k組，形成樹的k個(gè)分支數(shù)值型分組變量：以MDLP分箱所得的最小組限值為界，將小于組限的樣本劃為一組，大于的劃為另一組，形成兩個(gè)分叉第三十七頁，共五十二頁，2022年，8月28日人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)（ANN）是一種人腦的抽象計(jì)算模型，是一種模擬人腦思維的計(jì)算機(jī)建模方式。與人腦類似，人工神經(jīng)網(wǎng)絡(luò)由相互連接的神經(jīng)元，也稱處理單元組成。如果將人工神經(jīng)網(wǎng)絡(luò)看作一張圖，處理單元成為節(jié)點(diǎn)。節(jié)點(diǎn)之間的連接稱為邊，反映了各節(jié)點(diǎn)之間的關(guān)聯(lián)性，關(guān)聯(lián)性的強(qiáng)弱體現(xiàn)在邊的權(quán)值上。神經(jīng)元連接wi:權(quán)值第三十八頁，共五十二頁，2022年，8月28日人工神經(jīng)網(wǎng)絡(luò)的劃分拓?fù)浣Y(jié)構(gòu)1：兩層神經(jīng)網(wǎng)絡(luò)2：三層神經(jīng)網(wǎng)絡(luò)3：多層神經(jīng)網(wǎng)絡(luò)連接方式1：前饋式神經(jīng)網(wǎng)絡(luò)單向連接，上層節(jié)點(diǎn)的輸出是下層節(jié)點(diǎn)的輸入。2：反饋式神經(jīng)網(wǎng)絡(luò)除單向連接外，輸出節(jié)點(diǎn)的輸出又作為輸入節(jié)點(diǎn)的輸入。第三十九頁，共五十二頁，2022年，8月28日人工神經(jīng)網(wǎng)絡(luò)——節(jié)點(diǎn)第四十頁，共五十二頁，2022年，8月28日加法器：對(duì)自身輸入的線性組合激活函數(shù)：把加法器的結(jié)果映射到一定的取值范圍內(nèi)第四十一頁，共五十二頁，2022年，8月28日人工神經(jīng)網(wǎng)絡(luò)的建模步驟數(shù)據(jù)準(zhǔn)備網(wǎng)絡(luò)結(jié)構(gòu)的確定確定網(wǎng)絡(luò)權(quán)值第四十二頁，共五十二頁，2022年，8月28日數(shù)據(jù)準(zhǔn)備1：數(shù)值型變量的標(biāo)準(zhǔn)化處理[0，1]，極差法2：分類型變量采用啞變量，對(duì)應(yīng)輸入節(jié)點(diǎn)克服啞變量使輸入節(jié)點(diǎn)過多的問題：對(duì)類別的二進(jìn)制編碼例：有4、5、6、7個(gè)類別的分類變量只需3個(gè)變量即可第四十三頁，共五十二頁，2022年，8月28日網(wǎng)絡(luò)結(jié)構(gòu)的確定隱層層數(shù)和各隱層中隱結(jié)點(diǎn)的個(gè)數(shù)決定復(fù)雜度網(wǎng)絡(luò)結(jié)構(gòu)不一定在模型建立之前就完全確定經(jīng)驗(yàn)值法動(dòng)態(tài)調(diào)整法第四十四頁，共五十二頁，2022年，8月28日網(wǎng)絡(luò)權(quán)值的確定步驟初始化網(wǎng)絡(luò)權(quán)值：[-0.5,0.5]計(jì)算各節(jié)點(diǎn)加法器和激活函數(shù)，得到分類預(yù)測(cè)值比較預(yù)測(cè)值與實(shí)際值，根據(jù)誤差值重新調(diào)整各網(wǎng)絡(luò)權(quán)值回第二步，直到預(yù)測(cè)誤差小于指定ε，或達(dá)到指定迭代次數(shù)，或達(dá)到指定的運(yùn)行時(shí)間，或參數(shù)的最大變化值小于指定值第四十五頁，共五十二頁，2022年，8月28日隨機(jī)森林算法思想：每次隨機(jī)選取一些特征，獨(dú)立建立樹，重復(fù)這個(gè)過程，保證每次建立樹時(shí)變量選取的可能性一致，如此建立許多彼此獨(dú)立的樹，最終的分類結(jié)果由產(chǎn)生的這些樹共同決定。誤差：預(yù)測(cè)誤差取決于森林中每