數據挖掘常用算法數據挖掘常見類型兩類數據挖掘問題對應的數據挖掘算法業務問題對應的數據挖掘算法舉例決策樹回歸分析聚類分析關聯分析數據挖掘的常見類型對數據挖掘問題進行簡單的劃分，其主要有兩類問題：有目標變量的數據挖掘（有監督的挖掘或預測問題）和無目標變量的數據挖掘（無監督的挖掘）。

有目標變量的數據挖掘，使用目標變量，從數據中發現能解釋目標變量的模式，并且要求歷史數據中包含目標變量所有可能取值的樣本。流失預警是一個典型的有目標變量的數據挖掘問題，歷史數據中同時包含流失客戶和活躍客戶的信息，目標就是發現能解釋流失客戶與活躍客戶差異的原因。根據目標變量的不同類型，預測問題又分為分類預測和數值預測，如預測客戶是否流失屬于分類預測問題，預測收入屬于數值預測問題。無目標變量的數據挖掘，不使用目標變量（或者目標變量不清晰），以發現數據的潛在有用模式為目標，通過人工方式去理解發現的模式及其有用性。如從現有客戶中發現有意義的細分群體的聚類模型，發現哪些產品經常被客戶一起購買的關聯規則模型。兩類數據挖掘問題對應的數據挖掘算法有目標變量無目標變量分類預測數值預測決策樹Logistic回歸模型神經網絡判別分析遺傳算法最近鄰方法多元回歸模型回歸樹神經網絡遺傳算法

聚類模型（細分模型）關聯規則序列模式時間序列其他描述性模型業務問題對應的數據挖掘算法舉例業務問題數據挖掘算法哪些客戶有購買新產品的傾向決策樹/邏輯回歸哪些客戶有終止服務使用的傾向決策樹/邏輯回歸收入未來的變化趨勢多元回歸模型/時間序列客戶未來服務使用量的變化趨勢多元回歸模型/回歸樹哪些客戶存在欺詐行為神經網絡/聚類分析了解客戶存在哪些細分群體聚類分析給客戶推薦手機閱讀的哪類內容關聯規則/最近鄰方法客戶在購買該產品后接下來會購買什么序列模式了解哪些產品經常被客戶一起購買關聯規則客戶的信用度如何描述性模型決策樹——基本概念決策樹(DecisionTree)是一種以實例為基礎的歸納學習算法，是一種從無次序、無規則的訓練樣本集中推理出決策樹表示形式的分類規則的方法，它提供了一種展示類似在什么條件下會得到什么值這類規則的方法。主要應用于分類預測。分類預測的結果有定性和定量兩種。在實際應用中，將定性的分類預測稱為分類，用來確定類別屬性；定量的分類預測成為預測，用來預測具體的數值。決策樹的結構和構造方法屬性選擇噪聲與剪枝子樹復制和碎片問題決策樹——常用算法決策樹的兩大核心問題：一是決策樹的生長，即一棵決策樹是如何長成的，在樣本數據中選擇哪一個屬性作為根節點，然后如何分支，如何選擇內部節點，直到生長出樹葉，即到達葉節點，這一系列過程可稱為決策樹的分枝準則，即具體算法；另一核心問題是決策樹的剪枝，則防止決策樹生長過于茂盛，無法適應實際應用的需要。常用的決策樹算法分為兩類：基于信息論的方法和最小GINI指標的方法。信息論的方法包括：ID系列算法和C4.5、C5.0，而最小GINI指標方法包括：CART、SLIQ和SPRINT算法。決策樹的剪枝方法有預修剪（Pre-Pruning）和后修剪（Post-Pruning）。決策樹——ID3算法ID3算法是以信息論為基礎，運用信息熵理論，采用自頂向下的貪心搜索算法。其核心思想是在決策樹中各級節點上選擇分裂屬性。用信息增益作為屬性選擇的標準，使每個非葉子節點測試時，能獲得關于被測試例子最大的類別信息。使用該屬性將訓練樣本集分成子集后，系統的信息熵值最小。其生成步驟為：①選擇具有最大信息增益的屬性作為決策樹的當前決策節點，并將該屬性從候選屬性中刪除；②根據當前決策節點的不同取值將該樣本數據集劃分成若干個子集；③重復上面步驟①、②，當滿足以下條件之一時，決策樹停止生成新的分支：①給定節點的所有樣本屬于同一類。②沒有剩余屬性可以用來進一步劃分樣本。③分支沒有樣本。決策樹——ID3算法

決策樹——ID3算法

決策樹——C5.0算法

C4.5算法在ID3算法的基礎上進行了改進，增加了對連續屬性的離散型的處理。對于預測變量的缺值處理、剪枝技術、派生規則等方面作了較大改進，既適合于分類問題，又適合于回歸問題。而C5.0則是在C4.5的基礎上改進了執行效率和內存使用，應用于大數據集的分類算法。它采用Boosting方式來提高模型準確率。決策樹是用樣本的屬性作為結點，用屬性的取值作為分枝的樹結構的。屬性的度量標準有很多，如：信息增益率、GINI指標、距離度量等。C5.0采用信息增益率作為屬性的度量標準。步驟如下：首先對所有樣本賦以一個抽樣權重（一般開始的時候權重都一樣即認為均勻分布），在此樣本上訓練一個分類器對樣本分類，這樣可以得到這個分類器的誤差率，我們根據它的誤差率賦以一個權重，大體是誤差越大權重就越小，針對這次分錯的樣本我們增大它的抽樣權重，這樣訓練的下一個分類器就會側重這些分錯的樣本，然后根據它的誤差率計算權重，就這樣依次迭代，最后我們得到的強分類器就是多個弱分類器的加權和。我們可以看出性能好的分類器權重大一些，這就體現了boosting的精髓。決策樹——CART算法CART算法是一種產生二叉決策樹分類模型的技術。它與ID系列算法和C4.5不同的是，它使用的屬性度量標準是Gini指標。Gini指標主要是度量數據劃分或訓練數據集D的不純度為主，系數值的屬性作為測試屬性，Gini值越小，表明樣本的“純凈度”越高。CART算法在滿足下列條件之一，即視為葉節點不再進行分支操作。①所有葉節點的樣本數為1；樣本數小于某個給定的最小值或者樣本都屬于同一類的時候；②決策樹的高度達到用戶設置的閾值，或者分支后的葉節點中的樣本屬性都屬于同一個類的時候；③當訓練數據集中不再有屬性向量作為分支選擇的時候。決策樹——CART算法

決策樹——剪枝技術前剪枝（Forward-Pruning）是提前停止樹的構造而對樹進行剪枝。如果一個結點對樣本的劃分將導致低于預定義閥值的分裂，則給定子集的進一步劃分將停止。選取一個適當的閥值是很困難的，較高的閥值可能導致過分簡化的樹，較低的閥值可能使得樹的簡化太少。由于前剪枝不必生成整棵決策樹，且算法相對簡單，效率很高，適合解決大規模問題，所以這種方法得到了廣泛的應用。后剪枝（Post-Pruning）首先構造完整的決策樹，允許決策樹過度擬合訓練數據，然后對那些置信度不夠的結點的子樹用葉子結點來替代，這個葉子結點所應標記的類別為子樹中大多數實例所屬的類別。ID3算法、C5.0算法和CART算法都是先建樹再剪枝，屬于后剪枝。后剪枝方法現在得到比較廣泛地使用。常用的后剪枝算法有：CCP（CostComplexityPruning）、REP（ReducedErrorPruning）、PEP（PessimisticErrorPruning）、MEP（MinimumErrorPruning）。決策樹——剪枝技術（1）CCP剪枝法。CCP剪枝法是一種基于訓練集的自下而上的剪枝法，也叫做CART剪枝法。剪枝過程包括兩步：①從原始決策樹開始生成一個子樹序列；②從第1步產生的子樹序列中，根據樹的真實誤差估計選擇最佳決策樹。（2）REP剪枝法。REP剪枝法由Quinlan提出，是一種自下而上的簡單實用的剪枝方法。該方法的基本思路是，從訓練集中提取一部分數據作為剪枝集，這部分數據不用來構建決策樹，因此評估錯誤率時有較小的偏置。比較樹Tmax的子樹對剪枝集的分類錯誤率，及將該子樹變為葉子節點后的分類錯誤率。若前者大于后者，則將該子樹剪枝為葉子結點，并以到該結點的多數實例所代表的類來標識。重復以上過程，直到繼續剪枝會增加錯誤率為止。（3）PEP剪枝法。PEP剪枝法由Quinlan提出，是一種自上而下的剪枝法，剪枝基于自由訓練集得到的錯誤估計，因此不需要單獨的剪枝數據。很明顯，訓練集上的錯誤率被樂觀偏置，不能用來生成最優剪枝樹。因此，Quinlan引入了統計學上連續修正的概念來彌補這一缺陷，在子樹的訓練錯誤中添加一個常數，假定每個葉結點都自動對實例的某部分進行錯誤分類，這一部分一般取葉結點所覆蓋的實例總數的1/2。計算標準錯誤率時，連續修正遵循二項式分布。（4）MEP剪枝法。MEP剪枝法也是以一種自下而上的剪枝法，目的是在未知的數據集上產生最小預測分類錯誤率。回歸分析——基本概念

回歸分析——線性回歸模型

回歸分析——Logistic回歸模型

回歸分析——線性回歸模型（3）模型檢驗在一次抽樣中，未知參數的估計值與真實值的差異有多大？是否顯著？需要進行統計檢驗，統計檢驗包括三種：擬合優度檢驗：檢驗樣本的數據點聚集在回歸線周圍的密集程度方程顯著性檢驗：檢驗自變量與因變量的線性關系總體上是否顯著變量顯著性檢驗：檢驗每個自變量與因變量之間的線性關系是否顯著回歸分析——線性回歸模型（4）逐步回歸當輸入變量之間存在較強相關性時，線性回歸模型的參數估計會失真，需要對變量進行篩選，常用的方法是逐步回歸法（Stepwise）。逐步回歸法（Stepwise）的基本思想是將變量逐個引入模型，每引入一個解釋變量后都要進行F檢驗，并對已經選入的解釋變量逐個進行t檢驗，當原來引入的解釋變量由于后面解釋變量的引入變得不再顯著時，則將其刪除。以確保每次引入新的變量之前回歸方程中只包含先主動變量。這是一個反復的過程，直到既沒有顯著的解釋變量選入回歸方程，也沒用不顯著的解釋變量從回歸方程中剔除為止。以保證最后所得到的解釋變量集是最優的。回歸分析——Logistic回歸模型

回歸分析——Logistic回歸模型

回歸分析——Logistic回歸模型

聚類分析——基本概念概括性的定義聚類是將物理或抽象對象的集合分組成為由類似的對象組成的多個類的過程，聚類增強了人們對客觀現實的認識，是概念描述和偏差分析的先決條件。進一步的分析聚類和分類的區別，在分類問題中，訓練樣本的分類屬性的值是已知的，而在聚類問題中，需要根據訓練樣本的值來確定分類屬性值。采用聚類分析技術，可以把無標識的數據樣本自動劃分為不同的類，并且可以不受人的先驗知識的約束和干擾，從而獲取數據集中原本存在的信息。所以說，聚類是一種無指導學習（無監督學習），即從樣本的特征向量出發研究通過某種算法將特征相似的樣本聚集在一起，從而達到區分具有不同特征樣本的目的。分類則是一種有指導學習（有監督學習），它具有先驗知識（分類號），而無監督聚類學習并不具有這種先驗知識。聚類分析——算法分類基于距離的相似度計算：歐幾里德距離（歐氏距離）、曼哈頓距離主要的聚類算法可以劃分為如下幾類：劃分方法(PartitioningMethods)層次的方法(HierarchicalMethods)基于密度的方法(Density-basedMethods)基于網絡的方法(Grid-basedMethods)基于模型的方法(Model-basedMethods)聚類分析——K-Means算法K-means算法的具體流程如下：①從數據集中選擇聚類的K個質心，作為初始的簇中心；②計算每個對象到各質心的距離，把樣本指派給距離最小的簇；③根據每個簇當前所擁有的所有對象更新質心；④根據每個對象與各個簇中心的距離，分配給最近的簇；⑤然后轉③，重新計算每個簇的平均值。這個過程不斷重復直到滿足某個準則函數才停止。注意：利用每個簇的平均值代表新的簇的質心。聚類分析——K-Means算法

聚類分析——兩步聚類算法兩步聚類是一種探索性的聚類方法，是隨著人工智能的發展而發展起來的智能聚類方法中的一種。它最顯著的特點就是它分兩步進行聚類，主要用于處理非常大的數據集，可以處理連續屬性和離散屬性。它只需遍歷數據集一次。兩步聚類的特點包括：同時處理離散變量和連續變量的能力；自動選擇聚類數；通過預先選取樣本中的部分數據構建聚類模型；可以處理超大樣本量的數據。兩步算法的基本原理分為以下兩個步驟：第一步：預聚類。遍歷一次的數據，對記錄進行初始的歸類，用戶自定義最大類別數。通過構建和修改特征樹（CFTREE）來完成；第二步：聚類。對第一步完成的初步聚類進行再聚類并確定最終的聚類方案，使用層次聚類的方法將小的聚類逐漸合并成越來越大的聚類，這一過程不需要再次遍歷數據。層次聚類的好處是不要求提前選擇聚類數。許多層次聚類從單個記錄開始聚類，逐步合并成更大的類群。聚類分析——兩步聚類算法聚類特征(ClusteringFeature,CF)是BIRCH增量聚類算法的核心，CF樹中的節點都是由CF組成，CF是一個三元組，這個三元組就代表了簇的所有信息。給定N個d維的數據點{x1,x2,....,xn}，CF定義如下：CF=（N，LS，SS）。其中，N是子類中節點的數目，LS是N個節點的線性和，SS是N個節點的平方和。CF有個特性，即可以求和，具體說明如下：CF1=（n1,LS1,SS1），CF2=（n2,LS2,SS2），則CF1+CF2=（n1+n2,LS1+LS2,SS1+SS2）。CF樹是在遍歷數據集的過程中不斷添加、更新條目及分裂節點來形成的。根據第一個樣本即可建立根節點以及相應的條目，之后逐個地將后續的樣本根據距離最小的原則指派到CF樹中。一個CF樹有三個參數：B=分支系數，中間節點的最大子節點數量；T=葉節點中的類的半徑或直徑的閾值；L=葉節點的最大CF簇數量。聚類分析——異常檢測基于聚類的異常檢測至少有兩種方法：一種是異常檢測模型利用未標記的數據進行訓練，這些數據包含了正常數據和攻擊數據；另一種是模型僅利用正常數據進行訓練，從而建立正常行為輪廓。模型特征Portnoy等人模型采用數理統計的思想對原始數據包進行標準化，對標準化后的數據采用單鏈接法進行聚類，從而識別攻擊簇Y-means改進經典K-means算法，不依賴k的值，動態地對數據進行聚類MINDS對數據進行聚類，利用基于密度的局部孤立點來檢測入侵三種異常檢測模型的特征表聚類分析——異常檢測現在比較成熟的異常點檢測方法主要有以下幾類：（1）基于統計的方法（2）基于距離的方法（3）基于偏差的方法（4）基于密度的方法（5）高維數據的異常檢測關聯規則——基本概念

關聯規則——基本概念關聯規則依據不同的分類標準，可以有以下的分類：（1）基于規則中處理變量的類型，關聯規則可以分為布爾型和數值型。布爾型考慮的是項集的存在與否，而數值型則是量化的關聯。（2）基于規則中數據的抽象層次，可以分為單層關聯規則和多層關聯規則。（3）基于規則中涉及到的數據維數，可以分為單維關聯規則和多維關聯規則。關聯規則——算法原理關聯規則的挖掘就是在事務數據庫D中找出具有用戶給定的最小支持度（MinimumSupport,minsup）和最小置信度(MinimumConfidence,minconf)的關聯規則。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集或大項集。具體步驟是：Step1根據最小支持度閾值找出數據集D中所有頻繁項目集；Step2根據頻繁項目集和最小置信度閾值產生所有關聯規則。基本算法思想包括：（1）搜索算法。（2）分層算法(寬度優先算法)。（3）深度優先算法。（4）劃分算法。（5）抽樣算法。關聯規則——Apriori算法Apriori算法的基本思路：Apriori算法使用頻繁項集的先驗知識（稱為逐層搜索的迭代方法），k項集用于探索(k+1)項集。首先，通過掃描事務（交易）記錄，找出所有的頻繁1項集，該集合記做L1，然后利用L1找頻繁2項集的集合L2，L2找L3，如此下去，直到不能再找到任何頻繁k項集。最后再在所有的頻繁集中找出強規則，即產生用戶感興趣的關聯規則。Apriori算法的兩大缺點：一是可能產生大量的候選集，二為可能需要重復掃描數據庫。Apriori算法采用連接和剪枝兩種方式來找出所有的頻繁項集。關聯規則——Apriori算法（1）連接步

為找出Lk（所有的頻繁k項集的集合），通過將Lk-1（所有的頻繁k-1項集的集合）與自身連接產生候選k項集的集合。候選集合記作Ck。設l1和l2是Lk-1中的成員。記li[j]表示li中的第j項。假設Apriori算法對事務或項集中的項按字典次序排序，即對于（k-1）項集li，li[1]<li[2]<…<li[k-1]。將Lk-1與自身連接，如果(l1[1]=l2[1])&&(l1[2]=l2[2])&&…&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])