數據挖掘算法介紹

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

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

對于

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

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

數值型——歐式距離

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

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

目標函數：SSE=

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

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

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