數(shù)據(jù)挖掘算法介紹

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

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

對于

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

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

數(shù)值型——歐式距離

數(shù)值型+分類型——對數(shù)似然距離第十頁，共五十二頁，編輯于2023年，星期三兩步聚類——預(yù)聚類一個聚類特征CF是一個三元組（N,LS,SS）,N是簇中的點的數(shù)目，LS是N個點的線性和，SS是N個點的平方和。第十一頁，共五十二頁，編輯于2023年，星期三兩步聚類——預(yù)聚類預(yù)聚類過程:建立CF樹

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

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

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

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

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