『壹』 三種經典的數據挖掘演算法
演算法，可以說是很多技術的核心，而數據挖掘也是這樣的。數據挖掘中有很多的演算法，正是這些演算法的存在，我們的數據挖掘才能夠解決更多的問題。如果我們掌握了這些演算法，我們就能夠順利地進行數據挖掘工作，在這篇文章我們就給大家簡單介紹一下數據挖掘的經典演算法，希望能夠給大家帶來幫助。
1.KNN演算法
KNN演算法的全名稱叫做k-nearest neighbor classification，也就是K最近鄰，簡稱為KNN演算法，這種分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似，即特徵空間中最鄰近的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。KNN演算法常用於數據挖掘中的分類，起到了至關重要的作用。
2.Naive Bayes演算法
在眾多的分類模型中，應用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型（Naive Bayesian Model，NBC）。樸素貝葉斯模型發源於古典數學理論，有著堅實的數學基礎，以及穩定的分類效率。同時，NBC模型所需估計的參數很少，對缺失數據不太敏感，演算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。但是實際上並非總是如此，這是因為NBC模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬性個數比較多或者屬性之間相關性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關性較小時，NBC模型的性能最為良好。這種演算法在數據挖掘工作使用率還是挺高的，一名優秀的數據挖掘師一定懂得使用這一種演算法。
3.CART演算法
CART, 也就是Classification and Regression Trees。就是我們常見的分類與回歸樹，在分類樹下面有兩個關鍵的思想。第一個是關於遞歸地劃分自變數空間的想法；第二個想法是用驗證數據進行剪枝。這兩個思想也就決定了這種演算法的地位。
在這篇文章中我們給大家介紹了關於KNN演算法、Naive Bayes演算法、CART演算法的相關知識，其實這三種演算法在數據挖掘中占據著很高的地位，所以說如果要從事數據挖掘行業一定不能忽略這些演算法的學習。
『貳』 數據挖掘有哪些典型的應用和演算法
C4.5
C4.5演算法是機器學習演算法中的一種分類決策樹演算法,其核心演算法是ID3演算法. C4.5演算法繼承了ID3演算法的優點，並在以下幾方面對ID3演算法進行了改進：
1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；
2) 在樹構造過程中進行剪枝；
3) 能夠完成對連續屬性的離散化處理；
4) 能夠對不完整數據進行處理。
C4.5演算法有如下優點：產生的分類規則易於理解，准確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致演算法的低效。
2. The k-means algorithm 即K-Means演算法
k-means algorithm演算法是一個聚類演算法，把n的對象根據他們的屬性分為k個分割，k < n。它與處理混合正態分布的最大期望演算法很相似，因為他們都試圖找到數據中自然聚類的中心。它假設對象屬性來自於空間向量，並且目標是使各個群組內部的均 方誤差總和最小。
3. Support vector machines
支持向量機，英文為Support Vector Machine，簡稱SV機（論文中一般簡稱SVM）。它是一種監督式學習的方法，它廣泛的應用於統計分類以及回歸分析中。支持向量機將向量映射到一個更 高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假 定平行超平面間的距離或差距越大，分類器的總誤差越小。一個極好的指南是C.J.C Burges的《模式識別支持向量機指南》。van der Walt 和 Barnard 將支持向量機和其他分類器進行了比較。
4. The Apriori algorithm
Apriori演算法是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法。其核心是基於兩階段頻集思想的遞推演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。在這里，所有支持度大於最小支持度的項集稱為頻繁項集，簡稱頻集。
5. 最大期望(EM)演算法
在統計計算中，最大期望（EM，Expectation–Maximization）演算法是在概率（probabilistic）模型中尋找參數最大似然 估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variabl）。最大期望經常用在機器學習和計算機視覺的數據集聚（Data Clustering）領域。
6. PageRank
PageRank是Google演算法的重要內容。2001年9月被授予美國專利，專利人是Google創始人之一拉里·佩奇（Larry Page）。因此，PageRank里的page不是指網頁，而是指佩奇，即這個等級方法是以佩奇來命名的。
PageRank根據網站的外部鏈接和內部鏈接的數量和質量倆衡量網站的價值。PageRank背後的概念是，每個到頁面的鏈接都是對該頁面的一次投票， 被鏈接的越多，就意味著被其他網站投票越多。這個就是所謂的「鏈接流行度」——衡量多少人願意將他們的網站和你的網站掛鉤。PageRank這個概念引自 學術中一篇論文的被引述的頻度——即被別人引述的次數越多，一般判斷這篇論文的權威性就越高。
7. AdaBoost
Adaboost是一種迭代演算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然後把這些弱分類器集合起來，構成一個更強的最終分類器 (強分類器)。其演算法本身是通過改變數據分布來實現的，它根據每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的准確率，來確定每個樣本的權 值。將修改過權值的新數據集送給下層分類器進行訓練，最後將每次訓練得到的分類器最後融合起來，作為最後的決策分類器。
8. kNN: k-nearest neighbor classification
K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。
9. Naive Bayes
在眾多的分類模型中，應用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型（Naive Bayesian Model，NBC）。樸素貝葉斯模型發源於古典數學理論，有著堅實的數學基礎，以 及穩定的分類效率。同時，NBC模型所需估計的參數很少，對缺失數據不太敏感，演算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。 但是實際上並非總是如此，這是因為NBC模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬 性個數比較多或者屬性之間相關性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關性較小時，NBC模型的性能最為良好。
10. CART: 分類與回歸樹
CART, Classification and Regression Trees。 在分類樹下面有兩個關鍵的思想。第一個是關於遞歸地劃分自變數空間的想法；第二個想法是用驗證數據進行剪枝。
『叄』 數據挖掘十大經典演算法（1）——樸素貝葉斯(Naive Bayes)
在此推出一個演算法系列的科普文章。我們大家在平時埋頭工程類工作之餘，也可以抽身對一些常見演算法進行了解，這不僅可以幫助我們拓寬思路，從另一個維度加深對計算機技術領域的理解，做到觸類旁通，同時也可以讓我們搞清楚一些既熟悉又陌生的領域——比如數據挖掘、大數據、機器學習——的基本原理，揭開它們的神秘面紗，了解到其實很多看似高深的領域，其實背後依據的基礎和原理也並不復雜。而且，掌握各類演算法的特點、優劣和適用場景，是真正從事數據挖掘工作的重中之重。只有熟悉演算法，才可能對紛繁復雜的現實問題合理建模，達到最佳預期效果。
本系列文章的目的是力求用最干練而生動的講述方式，為大家講解由國際權威的學術組織the IEEE International Conference on Data Mining (ICDM) 於2006年12月評選出的數據挖掘領域的十大經典演算法。它們包括：
本文作為本系列的第一篇，在介紹具體演算法之前，先簡單為大家鋪墊幾個數據挖掘領域的常見概念：
在數據挖掘領域，按照演算法本身的行為模式和使用目的，主要可以分為分類(classification)，聚類(clustering)和回歸(regression)幾種，其中：
打幾個不恰當的比方 ：
另外，還有一個經常有人問起的問題，就是 數據挖掘 和 機器學習 這兩個概念的區別，這里一句話闡明我自己的認識：機器學習是基礎，數據挖掘是應用。機器學習研製出各種各樣的演算法，數據挖掘根據應用場景把這些演算法合理運用起來，目的是達到最好的挖掘效果。
當然，以上的簡單總結一定不夠准確和嚴謹，更多的是為了方便大家理解打的比方。如果大家有更精當的理解，歡迎補充和交流。
好了，鋪墊了這么多，現在終於進入正題！
作為本系列入門的第一篇，先為大家介紹一個容易理解又很有趣的演算法—— 樸素貝葉斯 。
先站好隊，樸素貝葉斯是一個典型的 有監督的分類演算法 。
光從名字也可以想到，要想了解樸素貝葉斯，先要從 貝葉斯定理 說起。
貝葉斯定理是我們高中時代學過的一條概率學基礎定理，它描述了條件概率的計算方式。不要怕已經把這些知識還給了體育老師，相信你一看公式就能想起來。
P(A|B)表示事件B已經發生的前提下，事件A發生的概率，叫做事件B發生下事件A的條件概率。其基本求解公式為：
其中，P(AB)表示A和B同時發生的概率，P(B)標識B事件本身的概率。
貝葉斯定理之所以有用，是因為我們在生活中經常遇到這種情況：我們可以很容易直接得出P(A|B)，P(B|A)則很難直接得出，但我們更關心P(B|A)。
而貝葉斯定理就為我們打通從P(A|B)獲得P(B|A)的道路。
下面不加證明地直接給出貝葉斯定理：
有了貝葉斯定理這個基礎，下面來看看樸素貝葉斯演算法的基本思路。
你看，其思想就是這么的樸素。那麼，屬於每個分類的概率該怎麼計算呢？下面我們先祭出形式化語言！
那麼現在的關鍵就是如何計算第3步中的各個條件概率。我們可以這么做：
因為分母對於所有類別為常數，因為我們只要將分子最大化皆可。又因為各特徵屬性是條件獨立的，所以有：
如果你也跟我一樣，對形式化語言有嚴重生理反應，不要怕，直接跳過前面這一坨，我們通過一個鮮活的例子，用人類的語言再解釋一遍這個過程。
某個醫院早上收了六個門診病人，如下表。
現在又來了第七個病人，是一個打噴嚏的建築工人。請問他最有可能患有何種疾病？
本質上，這就是一個典型的分類問題， 症狀 和 職業 是特徵屬性， 疾病種類 是目標類別
根據 貝葉斯定理
可得
假定"打噴嚏"和"建築工人"這兩個特徵是獨立的，因此，上面的等式就變成了
這是可以計算的。
因此，這個打噴嚏的建築工人，有66%的概率是得了感冒。同理，可以計算這個病人患上過敏或腦震盪的概率。比較這幾個概率，就可以知道他最可能得什麼病。
接下來，我們再舉一個樸素貝葉斯演算法在實際中經常被使用的場景的例子—— 文本分類器 ，通常會用來識別垃圾郵件。
首先，我們可以把一封郵件的內容抽象為由若干關鍵片語成的集合，這樣是否包含每種關鍵詞就成了一封郵件的特徵值，而目標類別就是 屬於垃圾郵件 或 不屬於垃圾郵件
假設每個關鍵詞在一封郵件里出現與否的概率相互之間是獨立的，那麼只要我們有若干已經標記為垃圾郵件和非垃圾郵件的樣本作為訓練集，那麼就可以得出，在全部垃圾郵件（記為Trash）出現某個關鍵詞Wi的概率，即 P(Wi|Trash)
而我們最重要回答的問題是，給定一封郵件內容M，它屬於垃圾郵件的概率是多大，即 P(Trash|M)
根據貝葉斯定理，有
我們先來看分子：
P(M|Trash) 可以理解為在垃圾郵件這個范疇中遇見郵件M的概率，而一封郵件M是由若干單詞Wi獨立匯聚組成的，只要我們所掌握的單詞樣本足夠多，因此就可以得到
這些值我們之前已經可以得到了。
再來看分子里的另一部分 P(Trash) ，這個值也就是垃圾郵件的總體概率，這個值顯然很容易得到，用訓練集中垃圾郵件數除以總數即可。
而對於分母來說，我們雖然也可以去計算它，但實際上已經沒有必要了，因為我們要比較的 P(Trash|M) 和 P(non-Trash|M) 的分母都是一樣的，因此只需要比較分子大小即可。
這樣一來，我們就可以通過簡單的計算，比較郵件M屬於垃圾還是非垃圾二者誰的概率更大了。
樸素貝葉斯的英文叫做 Naive Bayes ，直譯過來其實是 天真的貝葉斯 ，那麼他到底天真在哪了呢？
這主要是因為樸素貝葉斯的基本假設是所有特徵值之間都是相互獨立的，這才使得概率直接相乘這種簡單計算方式得以實現。然而在現實生活中，各個特徵值之間往往存在一些關聯，比如上面的例子，一篇文章中不同單詞之間一定是有關聯的，比如有些詞總是容易同時出現。
因此，在經典樸素貝葉斯的基礎上，還有更為靈活的建模方式—— 貝葉斯網路（Bayesian Belief Networks, BBN） ，可以單獨指定特徵值之間的是否獨立。這里就不展開了，有興趣的同學們可以做進一步了解。
最後我們來對這個經典演算法做個點評：
優點：
缺點：
好了，對於 樸素貝葉斯 的介紹就到這里，不知道各位看完之後是否會對數據挖掘這個領域產生了一點興趣了呢？
『肆』 數據挖掘技術在信用卡業務中的應用案例
數據挖掘技術在信用卡業務中的應用案例
信用卡業務具有透支筆數巨大、單筆金額小的特點，這使得數據挖掘技術在信用卡業務中的應用成為必然。國外信用卡發卡機構已經廣泛應用數據挖掘技術促進信用卡業務的發展，實現全面的績效管理。我國自1985年發行第一張信用卡以來，信用卡業務得到了長足的發展，積累了巨量的數據，數據挖掘在信用卡業務中的重要性日益顯現。
一、數據挖掘技術在信用卡業務中的應用數據挖掘技術在信用卡業務中的應用主要有分析型客戶關系管理、風險管理和運營管理。
1.分析型CRM
分析型CRM應用包括市場細分、客戶獲取、交叉銷售和客戶流失。信用卡分析人員搜集和處理大量數據，對這些數據進行分析，發現其數據模式及特徵，分析某個客戶群體的特性、消費習慣、消費傾向和消費需求，進而推斷出相應消費群體下一步的消費行為，然後以此為基礎，對所識別出來的消費群體進行特定產品的主動營銷。這與傳統的不區分消費者對象特徵的大規模營銷手段相比，大大節省了營銷成本，提高了營銷效果，從而能為銀行帶來更多的利潤。對客戶採用何種營銷方式是根據響應模型預測得出的客戶購買概率做出的，對響應概率高的客戶採用更為主動、人性化的營銷方式，如電話營銷、上門營銷；對響應概率較低的客戶可選用成本較低的電子郵件和信件營銷方式。除獲取新客戶外，維護已有優質客戶的忠誠度也很重要，因為留住一個原有客戶的成本要遠遠低於開發一個新客戶的成本。在客戶關系管理中，通過數據挖掘技術，找到流失客戶的特徵，並發現其流失規律，就可以在那些具有相似特徵的持卡人還未流失之前，對其進行有針對性的彌補，使得優質客戶能為銀行持續創造價值。
2.風險管理
數據挖掘在信用卡業務中的另一個重要應用就是風險管理。在風險管理中運用數據挖掘技術可建立各類信用評分模型。模型類型主要有三種：申請信用卡評分卡、行為信用評分卡和催收信用評分卡，分別為信用卡業務提供事前、事中、和事後的信用風險控制。
申請評分模型專門用於對新申請客戶的信用評估，它應用於信用卡徵信審核階段，通過申請人填寫的有關個人信息，即可有效、快速地辨別和劃分客戶質量，決定是否審批通過並對審批通過的申請人核定初始信用額度，幫助發卡行從源頭上控制風險。申請評分模型不依賴於人們的主觀判斷或經驗，有利於發卡行推行統一規范的授信政策。行為評分模型是針對已有持卡人，通過對持卡客戶的行為進行監控和預測，從而評估持卡客戶的信用風險，並根據模型結果，智能化地決定是否調整客戶信用額度，在授權時決定是否授權通過，到期換卡時是否進行續卡操作，對可能出現的使其提前進行預警。催收評分模型是申請評分模型和行為評分模型的補充，是在持卡人產生了逾期或壞賬的情況下建立的。催收評分卡被用於預測和評估對某一筆壞賬所採取措施的有效性，諸如客戶對警告信件反應的可能性。這樣，發卡行就可以根據模型的預測，對不同程度的逾期客戶採取相應措施進行處理。以上三種評分模型在建立時，所利用的數據主要是人口統計學數據和行為數據。人口統計學數據包括年齡、性別、婚姻狀況、教育背景、家庭成員特點、住房情況、職業、職稱、收入狀況等。行為數據包括持卡人在過去使用信用卡的表現信息，如使用頻率、金額、還款情況等。由此可見，數據挖掘技術的使用，可以使銀行有效地建立起事前、事中到事後的信用風險控制體系。
3.運營管理
雖然數據挖掘在信用卡運營管理領域的應用不是最重要的，但它已為國外多家發卡公司在提高生產效率、優化流程、預測資金和服務需求、提供服務次序等問題的分析上取得了較大成績。
二、常用的數據挖掘方法
上述數據挖掘技術在信用卡領域的應用中，有很多工具可用於開發預測和描述模型。有些用統計方法，如線性回歸和邏輯回歸；有些有非統計或混合方法，如神經網路、遺傳演算法、決策樹及回歸樹。這里僅討論幾種常見的典型方法。
1.線性回歸
簡單線性回歸分析是量化兩個連續變數之間關系的一種統計技術。這兩個變數分別是因變數(預測變數)。使用這一方法，可以發現一條穿過數據的線，線上的點使對應數據點的方差最小。為市場營銷、風險和客戶關系管理建立模型時，通常有多個自變數，用多個獨立自變數來預測一個連續變數稱為多元線性回歸，用線性回歸方法建立的模型通常具有魯棒性。
2.邏輯回歸
邏輯回歸是使用最廣泛的建模技術，與線性回歸很相似。兩者的主要區別在於邏輯回歸的因變數(想預測變數)不是連續的，而是離散的或者類型變數。如申請評分模型可運用邏輯回歸方法，選取關鍵變數確定回歸系數。以申請者的關鍵變數x1,x2,…xm為自變數，以y=[1 申請者是壞客戶；0 申請者是好客戶，為因變數，則對於二分類因變數，一般假設客戶變壞的概率為 p(y=1)=eβ0 β1×1 … βmxm/1 eβ0 β1×1 … βmxm式中，β0，β1…，βm是常數，即1n(p/1-p)=β0 β1×1 … βmxm
3.神經網路
神經網路處理和回歸處理大不相同，它不依照任何概率分布，而是模仿人腦功能，可以認為它是從每一次經驗中提取並學習信息。神經網路系統由一系列類似於人腦神經元一樣的節點組成，這些節點通過網路彼此互連。如果有數據輸入，它們便可以進行確定數據模式的工作。神經網路由相互連接的輸入層、中間層(或隱藏層)、輸出層組成。中間層由多個節點組成，完成大部分網路工作。輸出層輸出數據分析的執行結果。
4.遺傳演算法
與神經元網路類似，遺傳演算法也不遵循任何概率分布，是源自「適者生存」的進化過程。它首先將問題的可能解按某種形式進行編碼，編碼後的解稱為染色體。隨機選取n個染色體作為初始種群，再根據預定的評價函數對每個染色體計算適應值，性能較好的染色體有較高的適應值。選擇適應值較高的染色體進行復制，並通過遺傳運算元產生一群新的更適應環境的染色體，形成新的種群，直至最後收斂到一個最適應環境的個體，得到問題的最優化解。
5.決策樹
決策樹的目標是逐步將數據分類到不同的組或分支中，在因變數的值上建立最強劃分。由於分類規則比較直觀，所以易於理解。圖1為客戶響應的決策樹，從中很容易識別出響應率最高的組。
三、實例分析
以下以邏輯回歸方法建立信用卡申請評分模型為例，說明數據挖掘技術在信用卡業務中的應用。申請評分模型設計可分為7個基本步驟。
1.定義好客戶和壞客戶的標准
好客戶和壞客戶的標准根據適合管理的需要定義。按照國外的經驗，建立一個預測客戶好壞的風險模型所需的好、壞樣本至少各要有1000個左右。為了規避風險，同時考慮到信用卡市場初期，銀行的效益來源主要是銷售商的傭金、信用卡利息、手續費收入和資金的運作利差。因此，一般銀行把降低客戶的逾期率作為一個主要的管理目標。比如，將壞客戶定義為出現過逾期60天以上的客戶；將壞客戶定義為出現過逾期60天以上的客戶；將好客戶定義為沒有30天以上逾期且當前沒有逾期的客戶。
一般來講，在同一樣本空間內，好客戶的數量要遠遠大於壞客戶的數量。為了保證模型具有較高的識別壞客戶的能力，取好、壞客戶樣本數比率為1：1。
2.確定樣本空間
樣本空間的確定要考慮樣本是否具有代表性。一個客戶是好客戶，表明持卡人在一段觀察期內用卡表現良好；而一個客戶只要出現過「壞」的記錄，就把他認定為壞客戶。所以，一般好客戶的觀察期要比壞客戶長一些、好、壞客戶可以選擇在不同的時間段，即不同的樣本空間內。比如，好客戶的樣本空間為2003年11月-2003年12月的申請人，壞客戶的樣本空間為2003年11月-2004年5月的申請人，這樣既能保證好客戶的表現期較長，又能保證有足夠數量的壞客戶樣本。當然，抽樣的好、壞客戶都應具有代表性。
3.數據來源
在美國，有統一的信用局對個人信用進行評分，通常被稱為「FICO評分」。美國的銀行、信用卡公司和金融機構在對客戶進行信用風險分析時，可以利用信用局對個人的數據報告。在我國，由於徵信系統還不完善，建模數據主要來自申請表。隨著我國全國性徵信系統的逐步完善，未來建模的一部分數據可以從徵信機構收集到。
4.數據整理
大量取樣的數據要真正最後進入模型，必須經過數據整理。在數據處理時應注意檢查數據的邏輯性、區分「數據缺失」和「0」、根據邏輯推斷某些值、尋找反常數據、評估是否真實。可以通過求最小值、最大值和平均值的方法，初步驗證抽樣數據是否隨機、是否具有代表性。
5.變數選擇
變數選擇要同時具有數學統計的正確性和信用卡實際業務的解釋力。Logistic回歸方法是盡可能准確找到能夠預測因變數的自變數，並給予各自變數一定權重。若自變數數量太少，擬合的效果不好，不能很好地預測因變數的情況；若自變數太多，會形成過分擬合，預測因變數的效果同樣不好。所以應減少一些自變數，如用虛擬變數表示不能量化的變數、用單變數和決策樹分析篩選變數。與因變數相關性差不多的自變數可以歸為一類，如地區對客戶變壞概率的影響，假設廣東和福建兩省對壞客戶的相關性分別為-0.381和-0.380，可將這兩個地區歸為一類，另外，可以根據申請表上的信息構造一些自變數，比如結合申請表上「婚姻狀況」和「撫養子女」，根據經驗和常識結合這兩個欄位，構造新變數「已婚有子女」，進入模型分析這個變數是不真正具有統計預測性。
6.模型建立
藉助SAS9軟體，用逐步回歸法對變數進行篩選。這里設計了一種演算法，分為6個步驟。
步驟1：求得多變數相關矩陣(若是虛擬變數，則＞0.5屬於比較相關；若是一般變數，則＞0.7-0.8屬於比較相關)。
步驟2：旋轉主成分分析(一般變數要求＞0.8屬於比較相關；虛擬變數要求＞0.6-0.7屬於比較相關)。
步驟3：在第一主成分和第二主成分分別找出15個變數，共30個變數。
步驟4：計算所有30個變數對好/壞的相關性，找出相關性大的變數加入步驟3得出的變數。
步驟5：計算VIF。若VIF數值比較大，查看步驟1中的相關矩陣，並分別分析這兩個變數對模型的作用，剔除相關性較小的一個。
步驟6：循環步驟4和步驟5，直到找到所有變數，且達到多變數相關矩陣相關性很而單個變數對模型貢獻作用大。
7.模型驗證
在收集數據時，把所有整理好的數據分為用於建立模型的建模樣本和用於模型驗證的對照樣本。對照樣本用於對模型總體預測性、穩定性進行驗證。申請評分模型的模型檢驗指標包括K-S值、ROC、AR等指標。雖然受到數據不幹凈等客觀因素的影響，本例申請評分模型的K-S值已經超過0.4，達到了可以使用的水平。
四、數據挖掘在國內信用卡市場的發展前景
在國外，信用卡業務信息化程度較高，資料庫中保留了大量的數量資源，運用數據技術建立的各類模型在信用卡業務中的實施非常成功。目前國內信用卡發卡銀行首先利用數據挖掘建立申請評分模型，作為在信用卡業務中應用的第一步，不少發卡銀行已經用自己的歷史數據建立了客戶化的申請評分模型。總體而言，數據挖掘在我國信用卡業務中的應用處於數據質量問題，難於構建業務模型。
隨著國內各家發卡銀行已經建立或著手建立數據倉庫，將不同操作源的數據存放到一個集中的環境中，並且進行適當的清洗和轉換。這為數據挖掘提供了一個很好的操作平台，將給數據挖掘帶來各種便利和功能。人民銀行的個人徵信系統也已上線，在全國范圍內形成了個人信用數據的集中。在內部環境和外部環境不斷改善的基礎上，數據挖掘技術在信用卡業務中將具有越來越廣闊的應用前景。
『伍』 數據挖掘十大演算法-
整理里一晚上的數據挖掘演算法，其中主要引自wiki和一些論壇。發布到上作為知識共享，但是發現Latex的公式轉碼到網頁的時候出現了丟失，暫時沒找到解決方法，有空再回來填坑了。
——編者按
一、 C4.5
C4.5演算法是由Ross Quinlan開發的用於產生決策樹的演算法[1]，該演算法是對Ross Quinlan之前開發的ID3演算法的一個擴展。C4.5演算法主要應用於統計分類中，主要是通過分析數據的信息熵建立和修剪決策樹。
1.1 決策樹的建立規則
在樹的每個節點處，C4.5選擇最有效地方式對樣本集進行分裂，分裂規則是分析所有屬性的歸一化的信息增益率，選擇其中增益率最高的屬性作為分裂依據，然後在各個分裂出的子集上進行遞歸操作。
依據屬性A對數據集D進行分類的信息熵可以定義如下：
劃分前後的信息增益可以表示為：
那麼，歸一化的信息增益率可以表示為：
1.2 決策樹的修剪方法
C4.5採用的剪枝方法是悲觀剪枝法(Pessimistic Error Pruning，PEP)，根據樣本集計運算元樹與葉子的經驗錯誤率，在滿足替換標准時，使用葉子節點替換子樹。
不妨用K表示訓練數據集D中分類到某一個葉子節點的樣本數，其中其中錯誤分類的個數為J，由於用估計該節點的樣本錯誤率存在一定的樣本誤差，因此用表示修正後的樣本錯誤率。那麼，對於決策樹的一個子樹S而言，設其葉子數目為L(S)，則子樹S的錯誤分類數為：
設數據集的樣本總數為Num，則標准錯誤可以表示為：
那麼，用表示新葉子的錯誤分類數，則選擇使用新葉子節點替換子樹S的判據可以表示為：
二、KNN
最近鄰域演算法(k-nearest neighbor classification, KNN)[2]是一種用於分類和回歸的非參數統計方法。KNN演算法採用向量空間模型來分類，主要思路是相同類別的案例彼此之間的相似度高，從而可以藉由計算未知樣本與已知類別案例之間的相似度，來實現分類目標。KNN是一種基於局部近似和的實例的學習方法，是目前最簡單的機器學習演算法之一。
在分類問題中，KNN的輸出是一個分類族群，它的對象的分類是由其鄰居的「多數表決」確定的，k個最近鄰居（k為正整數，通常較小）中最常見的分類決定了賦予該對象的類別。若k = 1，則該對象的類別直接由最近的一個節點賦予。在回歸問題中，KNN的輸出是其周圍k個鄰居的平均值。無論是分類還是回歸，衡量鄰居的權重都非常重要，目標是要使較近鄰居的權重比較遠鄰居的權重大，例如，一種常見的加權方案是給每個鄰居權重賦值為1/d，其中d是到鄰居的距離。這也就自然地導致了KNN演算法對於數據的局部結構過於敏感。
三、Naive Bayes
在機器學習的眾多分類模型中，應用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型(Naive Bayesian Model，NBC)[3]。樸素貝葉斯模型發源於古典數學理論，有著堅實的數學基礎，以及穩定的分類效率。同時，NBC模型所需估計的參數很少，對缺失數據不太敏感，演算法也比較簡單。
在假設各個屬性相互獨立的條件下，NBC模型的分類公式可以簡單地表示為：
但是實際上問題模型的屬性之間往往是非獨立的，這給NBC模型的分類准確度帶來了一定影響。在屬性個數比較多或者屬性之間相關性較大時，NBC模型的分類效率比不上決策樹模型；而在屬性相關性較小時，NBC模型的性能最為良好。
四、CART
CART演算法(Classification And Regression Tree)[4]是一種二分遞歸的決策樹，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子結點都有兩個分支，因此CART演算法生成的決策樹是結構簡潔的二叉樹。由於CART演算法構成的是一個二叉樹，它在每一步的決策時只能是「是」或者「否」，即使一個feature有多個取值，也是把數據分為兩部分。在CART演算法中主要分為兩個步驟：將樣本遞歸劃分進行建樹過程；用驗證數據進行剪枝。
五、K-means
k-平均演算法(k-means clustering)[5]是源於信號處理中的一種向量量化方法，現在則更多地作為一種聚類分析方法流行於數據挖掘領域。k-means的聚類目標是：把n個點（可以是樣本的一次觀察或一個實例）劃分到k個聚類中，使得每個點都屬於離他最近的均值（此即聚類中心）對應的聚類。
5.1 k-means的初始化方法
通常使用的初始化方法有Forgy和隨機劃分(Random Partition)方法。Forgy方法隨機地從數據集中選擇k個觀測作為初始的均值點；而隨機劃分方法則隨機地為每一觀測指定聚類，然後執行「更新」步驟,即計算隨機分配的各聚類的圖心，作為初始的均值點。Forgy方法易於使得初始均值點散開，隨機劃分方法則把均值點都放到靠近數據集中心的地方；隨機劃分方法一般更適用於k-調和均值和模糊k-均值演算法。對於期望-最大化(EM)演算法和標准k-means演算法，Forgy方法作為初始化方法的表現會更好一些。
5.2 k-means的標准演算法
k-means的標准演算法主要包括分配(Assignment)和更新(Update)，在初始化得出k個均值點後，演算法將會在這兩個步驟中交替執行。
分配(Assignment)：將每個觀測分配到聚類中，使得組內平方和達到最小。
更新(Update)：對於上一步得到的每一個聚類，以聚類中觀測值的圖心，作為新的均值點。
六、Apriori
Apriori演算法[6]是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法，其核心是基於兩階段頻集思想的遞推演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。Apriori採用自底向上的處理方法，每次只擴展一個對象加入候選集，並且使用數據集對候選集進行檢驗，當不再產生匹配條件的擴展對象時，演算法終止。
Apriori的缺點在於生成候選集的過程中，演算法總是嘗試掃描整個數據集並盡可能多地添加擴展對象，導致計算效率較低；其本質上採用的是寬度優先的遍歷方式，理論上需要遍歷次才可以確定任意的最大子集S。
七、SVM
支持向量機(Support Vector Machine, SVM)[7]是在分類與回歸分析中分析數據的監督式學習模型與相關的學習演算法。給定一組訓練實例，每個訓練實例被標記為屬於兩個類別中的一個或另一個，SVM訓練演算法創建一個將新的實例分配給兩個類別之一的模型，使其成為非概率二元線性分類器。SVM模型是將實例表示為空間中的點，這樣映射就使得單獨類別的實例被盡可能寬的明顯的間隔分開。然後，將新的實例映射到同一空間，並基於它們落在間隔的哪一側來預測所屬類別。
除了進行線性分類之外，SVM還可以使用所謂的核技巧有效地進行非線性分類，將其輸入隱式映射到高維特徵空間中，即支持向量機在高維或無限維空間中構造超平面或超平面集合，用於分類、回歸或其他任務。直觀來說，分類邊界距離最近的訓練數據點越遠越好，因為這樣可以縮小分類器的泛化誤差。
八、EM
最大期望演算法(Expectation–Maximization Algorithm, EM)[7]是從概率模型中尋找參數最大似然估計的一種演算法。其中概率模型依賴於無法觀測的隱性變數。最大期望演算法經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望(E)，利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化(M)，最大化在E步上求得的最大似然值來計算參數的值。M步上找到的參數估計值被用於下一個E步計算中，這個過程不斷交替進行。
九、PageRank
PageRank演算法設計初衷是根據網站的外部鏈接和內部鏈接的數量和質量對網站的價值進行衡量。PageRank將每個到網頁的鏈接作為對該頁面的一次投票，被鏈接的越多，就意味著被其他網站投票越多。
演算法假設上網者將會不斷點網頁上的鏈接，當遇到了一個沒有任何鏈接出頁面的網頁，這時候上網者會隨機轉到另外的網頁開始瀏覽。設置在任意時刻，用戶到達某頁面後並繼續向後瀏覽的概率，該數值是根據上網者使用瀏覽器書簽的平均頻率估算而得。PageRank值可以表示為：
其中，是被研究的頁面集合，N表示頁面總數，是鏈接入頁面的集合，是從頁面鏈接處的集合。
PageRank演算法的主要缺點是的主要缺點是舊的頁面等級會比新頁面高。因為即使是非常好的新頁面也不會有很多外鏈，除非它是某個站點的子站點。
十、AdaBoost
AdaBoost方法[10]是一種迭代演算法，在每一輪中加入一個新的弱分類器，直到達到某個預定的足夠小的錯誤率。每一個訓練樣本都被賦予一個權重，表明它被某個分類器選入訓練集的概率。如果某個樣本點已經被准確地分類，那麼在構造下一個訓練集中，它被選中的概率就被降低；相反，如果某個樣本點沒有被准確地分類，那麼它的權重就得到提高。通過這樣的方式，AdaBoost方法能「聚焦於」那些較難分的樣本上。在具體實現上，最初令每個樣本的權重都相等，對於第k次迭代操作，我們就根據這些權重來選取樣本點，進而訓練分類器Ck。然後就根據這個分類器，來提高被它分錯的的樣本的權重，並降低被正確分類的樣本權重。然後，權重更新過的樣本集被用於訓練下一個分類器Ck[，並且如此迭代地進行下去。
AdaBoost方法的自適應在於：前一個分類器分錯的樣本會被用來訓練下一個分類器。AdaBoost方法對於雜訊數據和異常數據很敏感。但在一些問題中，AdaBoost方法相對於大多數其它學習演算法而言，不會很容易出現過擬合現象。AdaBoost方法中使用的分類器可能很弱（比如出現很大錯誤率），但只要它的分類效果比隨機好一點（比如兩類問題分類錯誤率略小於0.5），就能夠改善最終得到的模型。而錯誤率高於隨機分類器的弱分類器也是有用的，因為在最終得到的多個分類器的線性組合中，可以給它們賦予負系數，同樣也能提升分類效果。
引用
[1] Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.
[2] Altman, N. S. An introction to kernel and nearest-neighbor nonparametric regression. The American Statistician. 1992, 46 (3): 175–185. doi:10.1080/00031305.1992.10475879
[3] Webb, G. I.; Boughton, J.; Wang, Z. Not So Naive Bayes: Aggregating One-Dependence Estimators. Machine Learning (Springer). 2005, 58 (1): 5–24. doi:10.1007/s10994-005-4258-6
[4] decisiontrees.net Interactive Tutorial
[5] Hamerly, G. and Elkan, C. Alternatives to the k-means algorithm that find better clusterings (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). 2002
[6] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.
[7] Cortes, C.; Vapnik, V. Support-vector networks. Machine Learning. 1995, 20 (3): 273–297. doi:10.1007/BF00994018
[8] Arthur Dempster, Nan Laird, and Donald Rubin. "Maximum likelihood from incomplete data via the EM algorithm". Journal of the Royal Statistical Society, Series B, 39 (1):1–38, 1977
[9] Susan Moskwa. PageRank Distribution Removed From WMT. [October 16, 2009]
[10] Freund, Yoav; Schapire, Robert E. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting. 1995. CiteSeerX: 10.1.1.56.9855
『陸』 數據挖掘-決策樹演算法
決策樹演算法是一種比較簡易的監督學習分類演算法，既然叫做決策樹，那麼首先他是一個樹形結構，簡單寫一下樹形結構（數據結構的時候學過不少了）。
樹狀結構是一個或多個節點的有限集合，在決策樹里，構成比較簡單，有如下幾種元素：
在決策樹中，每個葉子節點都有一個類標簽，非葉子節點包含對屬性的測試條件，用此進行分類。
所以個人理解，決策樹就是 對一些樣本，用樹形結構對樣本的特徵進行分支，分到葉子節點就能得到樣本最終的分類，而其中的非葉子節點和分支就是分類的條件，測試和預測分類就可以照著這些條件來走相應的路徑進行分類。
根據這個邏輯，很明顯決策樹的關鍵就是如何找出決策條件和什麼時候算作葉子節點即決策樹終止。
決策樹的核心是為不同類型的特徵提供表示決策條件和對應輸出的方法，特徵類型和劃分方法包括以下幾個：
注意，這些圖中的第二層都是分支，不是葉子節點。
如何合理的對特徵進行劃分，從而找到最優的決策模型呢？在這里需要引入信息熵的概念。
先來看熵的概念：
在數據集中，參考熵的定義，把信息熵描述為樣本中的不純度，熵越高，不純度越高，數據越混亂（越難區分分類）。
例如：要給（0，1）分類，熵是0，因為能明顯分類，而均衡分布的（0.5，0.5）熵比較高，因為難以劃分。
信息熵的計算公式為：
其中 代表信息熵。 是類的個數， 代表在 類時 發生的概率。
另外有一種Gini系數，也可以用來衡量樣本的不純度：
其中 代表Gini系數，一般用於決策樹的 CART演算法 。
舉個例子：
如果有上述樣本，那麼樣本中可以知道，能被分為0類的有3個，分為1類的也有3個，那麼信息熵為：
Gini系數為：
總共有6個數據，那麼其中0類3個，佔比就是3/6，同理1類。
我們再來計算一個分布比較一下：
信息熵為：
Gini系數為：
很明顯，因為第二個分布中，很明顯這些數偏向了其中一類，所以 純度更高 ，相對的信息熵和Gini系數較低。
有了上述的概念，很明顯如果我們有一組數據要進行分類，最快的建立決策樹的途徑就是讓其在每一層都讓這個樣本純度最大化，那麼就要引入信息增益的概念。
所謂增益，就是做了一次決策之後，樣本的純度提升了多少（不純度降低了多少），也就是比較決策之前的樣本不純度和決策之後的樣本不純度，差越大，效果越好。
讓信息熵降低，每一層降低的越快越好。
度量這個信息熵差的方法如下：
其中 代表的就是信息熵（或者其他可以度量不純度的系數）的差， 是樣本(parent是決策之前， 是決策之後)的信息熵（或者其他可以度量不純度的系數）， 為特徵值的個數， 是原樣本的記錄總數， 是與決策後的樣本相關聯的記錄個數。
當選擇信息熵作為樣本的不純度度量時，Δ就叫做信息增益 。
我們可以遍歷每一個特徵，看就哪個特徵決策時，產生的信息增益最大，就把他作為當前決策節點，之後在下一層繼續這個過程。
舉個例子：
如果我們的目標是判斷什麼情況下，銷量會比較高（受天氣，周末，促銷三個因素影響），根據上述的信息增益求法，我們首先應該找到根據哪個特徵來決策，以信息熵為例：
首先肯定是要求 ，也就是銷量這個特徵的信息熵：
接下來，就分別看三個特徵關於銷量的信息熵，先看天氣，天氣分為好和壞兩種，其中天氣為好的條件下，銷量為高的有11條，低的有6條；天氣壞時，銷量為高的有7條，銷量為低的有10條，並且天氣好的總共17條，天氣壞的總共17條。
分別計算天氣好和天氣壞時的信息熵，天氣好時：
根據公式 ，可以知道，N是34，而天氣特徵有2個值，則k=2，第一個值有17條可以關聯到決策後的節點，第二個值也是17條，則能得出計算：
再計算周末這個特徵，也只有兩個特徵值，一個是，一個否，其中是有14條，否有20條；周末為是的中有11條銷量是高，3條銷量低，以此類推有：
信息增益為：
另外可以得到是否有促銷的信息增益為0.127268。
可以看出，以周末為決策，可以得到最大的信息增益，因此根節點就可以用周末這個特徵進行分支：
注意再接下來一層的原樣本集，不是34個而是周末為「是」和「否」分別計算，為是的是14個，否的是20個。
這樣一層一層往下遞歸，直到判斷節點中的樣本是否都屬於一類，或者都有同一個特徵值，此時就不繼續往下分了，也就生成了葉子節點。
上述模型的決策樹分配如下：
需要注意的是，特徵是否出現需要在分支當中看，並不是整體互斥的，周末生成的兩個分支，一個需要用促銷來決策，一個需要用天氣，並不代表再接下來就沒有特徵可以分了，而是在促銷決策層下面可以再分天氣，另外一遍天氣決策下面可以再分促銷。
決策樹的模型比較容易解釋，看這個樹形圖就能很容易的說出分類的條件。
我們知道屬性有二元屬性、標稱屬性、序數屬性和連續屬性，其中二元、標稱和序數都是類似的，因為是離散的屬性，按照上述方式進行信息增益計算即可，而連續屬性與這三個不同。
對於連續的屬性，為了降低其時間復雜度，我們可以先將屬性內部排序，之後取相鄰節點的均值作為決策值，依次取每兩個相鄰的屬性值的均值，之後比較他們的不純度度量。
需要注意的是，連續屬性可能在決策樹中出現多次，而不是像離散的屬性一樣在一個分支中出現一次就不會再出現了。
用信息熵或者Gini系數等不純度度量有一個缺點，就是會傾向於將多分支的屬性優先分類——而往往這種屬性並不是特徵。
例如上面例子中的第一行序號，有34個不同的值，那麼信息熵一定很高，但是實際上它並沒有任何意義，因此我們需要規避這種情況，如何規避呢，有兩種方式：
公式如下：
其中k為劃分的總數，如果每個屬性值具有相同的記錄數，則 ，劃分信息等於 ，那麼如果某個屬性產生了大量劃分，則劃分信息很大，信息增益率低，就能規避這種情況了。
為了防止過擬合現象，往往會對決策樹做優化，一般是通過剪枝的方式，剪枝又分為預剪枝和後剪枝。
在構建決策樹時，設定各種各樣的條件如葉子節點的樣本數不大於多少就停止分支，樹的最大深度等，讓決策樹的層級變少以防止過擬合。
也就是在生成決策樹之前，設定了決策樹的條件。
後剪枝就是在最大決策樹生成之後，進行剪枝，按照自底向上的方式進行修剪，修剪的規則是，評估葉子節點和其父節點的代價函數，如果父節點的代價函數比較小，則去掉這個葉子節點。
這里引入的代價函數公式是：
其中 代表的是葉子節點中樣本個數， 代表的是該葉子節點上的不純度度量，把每個葉子節點的 加起來，和父節點的 比較，之後進行剪枝即可。
『柒』 數據挖掘十大經典演算法之EM
EM（Expectation-Maximum）演算法也稱期望最大化演算法，它是最常見的隱變數估計方法，在機器學習中有極為廣泛的用途，例如常被用來學習高斯混合模型（Gaussian mixture model，簡稱GMM）的參數；隱式馬爾科夫演算法（HMM）、LDA主題模型的變分推斷等等。
EM演算法是一種迭代優化策略，由於它的計算方法中每一次迭代都分兩步，其中一個為期望步（E步），另一個為極大步（M步），一輪輪迭代更新隱含數據和模型分布參數，直到收斂，即得到我們需要的模型參數。
1. EM演算法推導過程
補充知識：Jensen不等式：
如果f是凸函數，函數的期望 大於等於 期望的函數。當且僅當下式中X是常量時，該式取等號。（應用於凹函數時，不等號方向相反）
2. EM演算法流程
3. EM演算法的其他問題
上面介紹的傳統EM演算法對初始值敏感，聚類結果隨不同的初始值而波動較大。總的來說，EM演算法收斂的優劣很大程度上取決於其初始參數。
EM演算法可以保證收斂到一個穩定點，即EM演算法是一定收斂的。
EM演算法可以保證收斂到一個穩定點，但是卻不能保證收斂到全局的極大值點，因此它是局部最優的演算法，當然，如果我們的優化目標是凸的，則EM演算法可以保證收斂到全局最大值，這點和梯度下降法這樣的迭代演算法相同。
EM演算法的簡單實例： https://zhuanlan.hu.com/p/40991784
參考：
https://zhuanlan.hu.com/p/40991784
https://blog.csdn.net/u011067360/article/details/24368085
『捌』 數據挖掘- 關聯分析演算法
關聯分析，顧名思義就是找出哪幾項之間是有關聯關系的，舉個例子：
以上是五個購物記錄，從中我們可以發現，購買了尿布的人其中有3個購買了啤酒，那麼久我們可以推測，尿布和啤酒之間有較強的關聯關系，盡管他們之間看起來並沒有什麼聯系，也就是能得到規則：
因為購物分析能較好地描述關聯分析，所以又被叫做 購物籃分析 。
為了較好的描述這個分析的各種名詞，我們把上面的表格重新設計一下：
把每一個購物訂單中，涉及到的商品都變成1，沒涉及到的變成0，也就是將各個商品的購買記錄 二元化 。
當然肯定也有多個分類的情況。
那麼麵包，牛奶這些就叫數據集的 項 ，而他們組合起來的子集就叫做 項集 。可以為空，空集是不包含任何項的項集，如果一個項集包含k個子項，就叫做k-項集。
訂單12345叫做 事務 ，某個項集在所有事務中出現多少次，叫做項集的 支持度計數 。
在上面的表格中，項集{啤酒、尿布、牛奶}的支持度計數為2，因為有兩個事務（3、4）包含這一項集。
用 支持度 和 置信度 來衡量，假定存在規則 ，其中X和Y是 不相交 的項集，則支持度為：
其中N是數據集中的事務個數，相當於表示該規則在數據集中出現了多少次。
置信度為：
置信度的意思就是，在出現X的情況下，有多少次同時出現了Y，代表這個關聯規則的頻繁程度。
注意置信度的分母是 ，因此這個評價可能會存在一定的問題。
關聯分析的核心目標就是找出支持度大於等於某個閾值， 同時 置信度大於等於某個閾值的所有規則，這兩個閾值記為 和 。
為了更有效率的完成這個過程，通常把關聯規則演算法分為兩步：
可以看出來，櫻備首先要求得頻繁項集，這步驟的開銷很大，但是只需要考慮支持度就可以了，第二步只考慮置信度就可以了。
下面就可以分兩步來解析演算法：
首先我們可以把項集聯想成一個樹形結構，每層代表著不同的k-項集，依層遞增，非葉子節點來自於他的幾個父節點的並集，如圖：
我們肯定不能通過傳統的方式，遍歷這些節點，算出支持度，然後篩選掉不滿足最小支持度的那些，這樣開銷太大，因此我們引入先驗原理，來輔助剪枝。
這個原理不難想像，假如一個項集{a,b}是非頻繁項集，那麼{a,b,c}肯定也是，因為ab是，在{a,b,c}中與之關聯的c必須在ab出現之後才存在，因此他的支持度肯定不會大於{a,b}。
頻繁的就是支持度大於等於最小支持度的項集，非頻繁就是小於的。
我們可以利用這一定理，把非頻繁項集的超集一並從樹中減去，這樣就能大大的降低計算次數，如圖：
虛線圈上的，就是在{a,b}確定是非頻繁項集之後，剪掉的超集，這些是不用計算的。
根據這個原理，可以說一下Apriori演算法。
根據上面說的先驗原理，Apriori演算法先從項集寬度最低的1開始，遍歷所有的項集支持度，找出頻繁項集（因為第一層在找出支持度之前），之後根據先驗原理，挑選任意兩個頻繁項集組成2-頻繁項集（很簡單，如果挑非頻繁的，那組成的項集就不是頻繁項集了），再用2-項集挑選3-項集，直到挑選不出更高層次的項集為止，把這些項集作為 候選項集 ，如圖：
圖中1-項集中，啤酒，麵包，尿布，牛奶的支持度大於等於3（設 為3），則由他們組成2-項集，繼續篩選滿足支持度不小於3的項集，再由2-項集生成3-項集，這就是 Apriori 演算法篩選頻繁項集的基本步驟。總結如下：
上面提到了用k-1項集生成k-項脊稿毀集，那麼如何才能最有效率的產生k-項集呢，這里用了 的方法，也就是找到一對（k-1）-項集，當他們的前（k-2）項都相同時，進行合並，合並之後的結果就是{ }，因為前k-2項是相同的。
舉個例子：
上面說了如何產生候選項集，接下來就是如何更敬塵有效率的確定支持度計數了，同樣，如果遍歷一個一個查的話效率是很低的，我們可以用枚舉的方法遍歷每個事務包含的項集，以查找3-項集為例，如圖：
因為我們要查3-項集，因此樹狀結構就分到3-項集為止。
因為3-項集的開頭第一個項肯定在1，2，3之間，我們就設定這三個數為三個分支，無論到哪個節點，都嚴格按照這個來分（1在左，2在中，3在右），在下面的層次中如何碰到比123更大的，則再向右分，就可以得到圖中的關於事務t的所有3-項集。
有了所有項集的列表，我們可以用候選項集去匹配這些項集，從而看t中是否包含候選項集，如果包含，則支持度+1。
可以使用Hash樹來進行匹配，從而實現支持度計數。
如下圖，就是一個Hash樹的例子，每個內部節點都使用Hash函數 來確定應當沿著當前節點的哪個分支向下，所以1，4，7就到了同一分支。
我們對於單個事務，可以遍歷Hash樹，設事務為t，則保證所有包含屬於事務t的候選3-項集的葉節點至少訪問一次。
由於我們之前已經通過樹的方式枚舉出了t中所有的3-項集，那麼我們跟這個Hash一走分支，找到對應3-項集的就+1支持度，即可算出每個候選項集的支持度。
提取規則相應的比較簡單，設有 頻繁項集Y ，我們忽略前件為空和後件為空的規則，每個頻繁項集能產生 個關聯規則，提取方法就是將Y劃分為兩個 非空 的子集X和Y-X，使得 滿足 置信度閾值 也就是最小置信度。
同樣的，提取規則也有一個原理：
參考頻繁項集的尋找過程，我們可以利用樹形結構對規則進行剪枝。
樹的每層對應規則後件中的項數，如圖：
假設規則{ } { }不滿足置信度閾值的要求，那麼可以丟棄後件包含{a}的所有規則，如上圖所示。
至此我們經歷了尋找頻繁項集和提取規則的過程，基本Apriori演算法就算完成了，不過還有一些需要考慮的細節。
在實際應用過程中，往往頻繁項集產生的數量可能很大，所以很難表示，我們需要尋找一種方法，找到一些有代表性的頻繁項集，以保證其描述性。
通常有如下兩種方法：
如圖：
這種表示很明顯降低了需要表示項集的個數，我們需要別的候選項集，直接取極大頻繁項集的子集就行，任意一個肯定都是。
但是這么做，表示不出他們子集的支持度，所以就需要再遍歷數據集，確定非極大頻繁項集的支持度，不是很方便。
所以我們還可以用閉頻繁項集來表示。
先來看閉項集的概念：
那麼閉頻繁項集的概念就很好理解了：
如圖，我們假設 是40%。
這種做法可以保證支持度和描述性。
之前舉的例子都是二元分類的，要麼1要麼0，下面看多分類的，我們很容易想到可以用獨熱編碼解決這個問題，把所有分類二元化，但是這樣就存在一個問題，有的屬性值可能會不夠頻繁，沒辦法成為頻繁項集。
所以最好是把多分類的項根據實際情況進行分類化，不要針對每個屬性都設置獨熱編碼。
或者將不太頻繁的屬性值合並為一個稱作其他的類別。
所以面對多分類屬性，我們要做的就是：
獨熱編碼二元化-針對這些值進行一定的合並，或者分類或者並為其他 - 刪除冗餘的項 - 避免包含多個來自同一屬性的項的候選集（例如{ }，被寫到了一個候選集中，但是實際上這種情況不可能發生，由於獨熱編碼進行的二元化而產生了這種情況，需要避免。）
我們也會遇到一些連續屬性，可以通過以下幾種方式處理：
這種做法有一個問題就是分類的效果取決於區間的個數和跨度，如果取不好很難得到理想的結果。
如果要驗證統計出的值是否具有統計意義，可以參考假設檢驗中針對不同比較的不同公式，這里不再舉例。
把mini-Apriori演算法中的支持度代入到Apriori演算法的支持度中即可。
舉個例子：
想要衡量模型的好與壞，肯定要有一個評估指標，我們可以根據業務實際去評價，這是主管評價，叫做 主觀興趣度度量 ，這個顯然要結合業務，所以我們要看看一些客觀指標。
指標的評價往往依賴於相依表，這個相依表有點類似於混淆矩陣：
其中A，B代表在事務中出現，!A,!B代表沒有在事務中出現，空列空行例如 代表A的支持度計數， 表示包含B但是不包含A的事務的個數。
最基本的就是置信度和支持度了，但是這兩種指標都很難做到客觀評價模型，會受到多種因素的影響。
我們可以用 興趣因子 來衡量模型：
首先我們引入 提升度 的概念，它用於計算規則置信度和 規則後件 中項集的支持度之間的比率，
對於二元變數，提升度等價於另一種稱作興趣因子的客觀度量，定義為：
其中N是事務個數。
如果
但是興趣因子有一定局限性，看上圖，{p,q}和{r,s}的興趣因子分別為1.02和4.08，雖然p和q同時出現在88%的文檔中，但是他們的興趣因子接近於1，表明他們相互獨立，另一方面，{r,s}的興趣因子閉{p,q}的高，但是r和s很少出現在一個文檔中，這種情況下，置信度要比興趣因子更可信，置信度表明p和q之間的聯系94.6%遠高於r和s之間。
另外還可以引入 相關系數 ，邏輯類似於向量的相關系數：
相關度的值從-1到1，如果變數相互獨立，則Φ=0。
他的局限性在於在食物中把同時出現和同時不出現視為同等重要，這往往不符合實際規律，同時對於傾斜的變數很難度量。
IS度量 可以用於處理非對稱二元變數，定義如下：
IS數學上等價於二元變數的餘弦度量。
但是IS取決於A和B的支持度，所以存在與置信度度量類似的問題——即使是不相關或者負相關的模式，度量值也可能相當大。
支持度，全置信度，可以應用於較大的項集，興趣因子，IS、PS、Jaccard系數等使用多維相依表中的頻率，可以擴展到多個變數。
針對大多數項具有較低或中等的頻率，但是少數項具有很高頻率的數據集。
交叉支持模式是一個項集 ，他的支持度比率是：
小於用戶指定的閾值 。
需要保證全置信度小於上面的支持度比率，而全置信度是：
其中 .
全置信度能夠確保項集中的項之間是強關聯的，例如，假定一個項集X的全置信度是80%，如果X中的一個項出現在某個事物中，則X中其他的項至少也有80%的幾率屬於同一個事務，這種強關聯模式又稱 超團模式 。
『玖』 數據挖掘演算法與生活中的應用案例
數據挖掘演算法與生活中的應用案例
如何分辨出垃圾郵件」、「如何判斷一筆交易是否屬於欺詐」、「如何判斷紅酒的品質和檔次」、「掃描王是如何做到文字識別的」、「如何判斷佚名的著作是否出自某位名家之手」、「如何判斷一個細胞是否屬於腫瘤細胞」等等，這些問題似乎都很專業，都不太好回答。但是，如果了解一點點數據挖掘的知識，你，或許會有柳暗花明的感覺。
本文，主要想簡單介紹下數據挖掘中的演算法，以及它包含的類型。然後，通過現實中觸手可及的、活生生的案例，去詮釋它的真實存在。 一般來說，數據挖掘的演算法包含四種類型，即分類、預測、聚類、關聯。前兩種屬於有監督學習，後兩種屬於無監督學習，屬於描述性的模式識別和發現。
有監督學習有監督的學習，即存在目標變數，需要探索特徵變數和目標變數之間的關系，在目標變數的監督下學習和優化演算法。例如，信用評分模型就是典型的有監督學習，目標變數為「是否違約」。演算法的目的在於研究特徵變數（人口統計、資產屬性等）和目標變數之間的關系。
分類演算法分類演算法和預測演算法的最大區別在於，前者的目標變數是分類離散型（例如，是否逾期、是否腫瘤細胞、是否垃圾郵件等），後者的目標變數是連續型。一般而言，具體的分類演算法包括，邏輯回歸、決策樹、KNN、貝葉斯判別、SVM、隨機森林、神經網路等。
預測演算法預測類演算法，其目標變數一般是連續型變數。常見的演算法，包括線性回歸、回歸樹、神經網路、SVM等。
無監督學習無監督學習，即不存在目標變數，基於數據本身，去識別變數之間內在的模式和特徵。例如關聯分析，通過數據發現項目A和項目B之間的關聯性。例如聚類分析，通過距離，將所有樣本劃分為幾個穩定可區分的群體。這些都是在沒有目標變數監督下的模式識別和分析。
聚類分析聚類的目的就是實現對樣本的細分，使得同組內的樣本特徵較為相似，不同組的樣本特徵差異較大。常見的聚類演算法包括kmeans、系譜聚類、密度聚類等。
關聯分析關聯分析的目的在於，找出項目（item）之間內在的聯系。常常是指購物籃分析，即消費者常常會同時購買哪些產品（例如游泳褲、防曬霜），從而有助於商家的捆綁銷售。
基於數據挖掘的案例和應用上文所提到的四種演算法類型（分類、預測、聚類、關聯），是比較傳統和常見的。還有其他一些比較有趣的演算法分類和應用場景，例如協同過濾、異常值分析、社會網路、文本分析等。下面，想針對不同的演算法類型，具體的介紹下數據挖掘在日常生活中真實的存在。下面是能想到的、幾個比較有趣的、和生活緊密關聯的例子。
基於分類模型的案例這裡面主要想介紹兩個案例，一個是垃圾郵件的分類和判斷，另外一個是在生物醫葯領域的應用，即腫瘤細胞的判斷和分辨。
垃圾郵件的判別郵箱系統如何分辨一封Email是否屬於垃圾郵件？這應該屬於文本挖掘的范疇，通常會採用樸素貝葉斯的方法進行判別。它的主要原理是，根據郵件正文中的單詞，是否經常出現在垃圾郵件中，進行判斷。例如，如果一份郵件的正文中包含「報銷」、「發票」、「促銷」等詞彙時，該郵件被判定為垃圾郵件的概率將會比較大。
一般來說，判斷郵件是否屬於垃圾郵件，應該包含以下幾個步驟。
第一，把郵件正文拆解成單片語合，假設某篇郵件包含100個單詞。
第二，根據貝葉斯條件概率，計算一封已經出現了這100個單詞的郵件，屬於垃圾郵件的概率和正常郵件的概率。如果結果表明，屬於垃圾郵件的概率大於正常郵件的概率。那麼該郵件就會被劃為垃圾郵件。
醫學上的腫瘤判斷如何判斷細胞是否屬於腫瘤細胞呢？腫瘤細胞和普通細胞，有差別。但是，需要非常有經驗的醫生，通過病理切片才能判斷。如果通過機器學習的方式，使得系統自動識別出腫瘤細胞。此時的效率，將會得到飛速的提升。並且，通過主觀（醫生）+客觀（模型）的方式識別腫瘤細胞，結果交叉驗證，結論可能更加靠譜。
如何操作？通過分類模型識別。簡言之，包含兩個步驟。首先，通過一系列指標刻畫細胞特徵，例如細胞的半徑、質地、周長、面積、光滑度、對稱性、凹凸性等等，構成細胞特徵的數據。其次，在細胞特徵寬表的基礎上，通過搭建分類模型進行腫瘤細胞的判斷。
基於預測模型的案例這裡面主要想介紹兩個案例。即通過化學特性判斷和預測紅酒的品質。另外一個是，通過搜索引擎來預測和判斷股價的波動和趨勢。
紅酒品質的判斷如何評鑒紅酒？有經驗的人會說，紅酒最重要的是口感。而口感的好壞，受很多因素的影響，例如年份、產地、氣候、釀造的工藝等等。但是，統計學家並沒有時間去品嘗各種各樣的紅酒，他們覺得通過一些化學屬性特徵就能夠很好地判斷紅酒的品質了。並且，現在很多釀酒企業其實也都這么幹了，通過監測紅酒中化學成分的含量，從而控制紅酒的品質和口感。
那麼，如何判斷鑒紅酒的品質呢？
第一步，收集很多紅酒樣本，整理檢測他們的化學特性，例如酸性、含糖量、氯化物含量、硫含量、酒精度、PH值、密度等等。
第二步，通過分類回歸樹模型進行預測和判斷紅酒的品質和等級。
搜索引擎的搜索量和股價波動一隻南美洲熱帶雨林中的蝴蝶，偶爾扇動了幾下翅膀，可以在兩周以後，引起美國德克薩斯州的一場龍卷風。你在互聯網上的搜索是否會影響公司股價的波動？
很早之前，就已經有文獻證明，互聯網關鍵詞的搜索量（例如流感）會比疾控中心提前1到2周預測出某地區流感的爆發。
同樣，現在也有些學者發現了這樣一種現象，即公司在互聯網中搜索量的變化，會顯著影響公司股價的波動和趨勢，即所謂的投資者注意力理論。該理論認為，公司在搜索引擎中的搜索量，代表了該股票被投資者關注的程度。因此，當一隻股票的搜索頻數增加時，說明投資者對該股票的關注度提升，從而使得該股票更容易被個人投資者購買，進一步地導致股票價格上升，帶來正向的股票收益。這是已經得到無數論文驗證了的。
基於關聯分析的案例：沃爾瑪的啤酒尿布啤酒尿布是一個非常非常古老陳舊的故事。故事是這樣的，沃爾瑪發現一個非常有趣的現象，即把尿布與啤酒這兩種風馬牛不相及的商品擺在一起，能夠大幅增加兩者的銷量。原因在於，美國的婦女通常在家照顧孩子，所以，她們常常會囑咐丈夫在下班回家的路上為孩子買尿布，而丈夫在買尿布的同時又會順手購買自己愛喝的啤酒。沃爾瑪從數據中發現了這種關聯性，因此，將這兩種商品並置，從而大大提高了關聯銷售。
啤酒尿布主要講的是產品之間的關聯性，如果大量的數據表明，消費者購買A商品的同時，也會順帶著購買B產品。那麼A和B之間存在關聯性。在超市中，常常會看到兩個商品的捆綁銷售，很有可能就是關聯分析的結果。
基於聚類分析的案例：零售客戶細分對客戶的細分，還是比較常見的。細分的功能，在於能夠有效的劃分出客戶群體，使得群體內部成員具有相似性，但是群體之間存在差異性。其目的在於識別不同的客戶群體，然後針對不同的客戶群體，精準地進行產品設計和推送，從而節約營銷成本，提高營銷效率。
例如，針對商業銀行中的零售客戶進行細分，基於零售客戶的特徵變數（人口特徵、資產特徵、負債特徵、結算特徵），計算客戶之間的距離。然後，按照距離的遠近，把相似的客戶聚集為一類，從而有效的細分客戶。將全體客戶劃分為諸如，理財偏好者、基金偏好者、活期偏好者、國債偏好者、風險均衡者、渠道偏好者等。
基於異常值分析的案例：支付中的交易欺詐偵測採用支付寶支付時，或者刷信用卡支付時，系統會實時判斷這筆刷卡行為是否屬於盜刷。通過判斷刷卡的時間、地點、商戶名稱、金額、頻率等要素進行判斷。這裡面基本的原理就是尋找異常值。如果您的刷卡被判定為異常，這筆交易可能會被終止。
異常值的判斷，應該是基於一個欺詐規則庫的。可能包含兩類規則，即事件類規則和模型類規則。第一，事件類規則，例如刷卡的時間是否異常（凌晨刷卡）、刷卡的地點是否異常（非經常所在地刷卡）、刷卡的商戶是否異常（被列入黑名單的套現商戶）、刷卡金額是否異常（是否偏離正常均值的三倍標准差）、刷卡頻次是否異常（高頻密集刷卡）。第二，模型類規則，則是通過演算法判定交易是否屬於欺詐。一般通過支付數據、賣家數據、結算數據，構建模型進行分類問題的判斷。
基於協同過濾的案例：電商猜你喜歡和推薦引擎電商中的猜你喜歡，應該是大家最為熟悉的。在京東商城或者亞馬遜購物，總會有「猜你喜歡」、「根據您的瀏覽歷史記錄精心為您推薦」、「購買此商品的顧客同時也購買了商品」、「瀏覽了該商品的顧客最終購買了商品」，這些都是推薦引擎運算的結果。
這裡面，確實很喜歡亞馬遜的推薦，通過「購買該商品的人同時購買了**商品」，常常會發現一些質量比較高、較為受認可的書。一般來說，電商的「猜你喜歡」（即推薦引擎）都是在協同過濾演算法（Collaborative Filter）的基礎上，搭建一套符合自身特點的規則庫。即該演算法會同時考慮其他顧客的選擇和行為，在此基礎上搭建產品相似性矩陣和用戶相似性矩陣。基於此，找出最相似的顧客或最關聯的產品，從而完成產品的推薦。
基於社會網路分析的案例：電信中的種子客戶種子客戶和社會網路，最早出現在電信領域的研究。即，通過人們的通話記錄，就可以勾勒出人們的關系網路。電信領域的網路，一般會分析客戶的影響力和客戶流失、產品擴散的關系。
基於通話記錄，可以構建客戶影響力指標體系。採用的指標，大概包括如下，一度人脈、二度人脈、三度人脈、平均通話頻次、平均通話量等。基於社會影響力，分析的結果表明，高影響力客戶的流失會導致關聯客戶的流失。其次，在產品的擴散上，選擇高影響力客戶作為傳播的起點，很容易推動新套餐的擴散和滲透。
此外，社會網路在銀行（擔保網路）、保險（團伙欺詐）、互聯網（社交互動）中也都有很多的應用和案例。
基於文本分析的案例這裡面主要想介紹兩個案例。一個是類似「掃描王」的APP，直接把紙質文檔掃描成電子文檔。相信很多人都用過，這里准備簡單介紹下原理。另外一個是，江湖上總是傳言紅樓夢的前八十回和後四十回，好像並非都是出自曹雪芹之手，這裡面准備從統計的角度聊聊。
字元識別：掃描王APP手機拍照時會自動識別人臉，還有一些APP，例如掃描王，可以掃描書本，然後把掃描的內容自動轉化為word。這些屬於圖像識別和字元識別（Optical Character Recognition）。圖像識別比較復雜，字元識別理解起來比較容易些。
查找了一些資料，字元識別的大概原理如下，以字元S為例。
第一，把字元圖像縮小到標准像素尺寸，例如12*16。注意，圖像是由像素構成，字元圖像主要包括黑、白兩種像素。
第二，提取字元的特徵向量。如何提取字元的特徵，採用二維直方圖投影。就是把字元（12*16的像素圖）往水平方向和垂直方向上投影。水平方向有12個維度，垂直方向有16個維度。這樣分別計算水平方向上各個像素行中黑色像素的累計數量、垂直方向各個像素列上的黑色像素的累計數量。從而得到水平方向12個維度的特徵向量取值，垂直方向上16個維度的特徵向量取值。這樣就構成了包含28個維度的字元特徵向量。
第三，基於前面的字元特徵向量，通過神經網路學習，從而識別字元和有效分類。
文學著作與統計：紅樓夢歸屬這是非常著名的一個爭論，懸而未決。對於紅樓夢的作者，通常認為前80回合是曹雪芹所著，後四十回合為高鶚所寫。其實主要問題，就是想確定，前80回合和後40回合是否在遣詞造句方面存在顯著差異。
這事讓一群統計學家比較興奮了。有些學者通過統計名詞、動詞、形容詞、副詞、虛詞出現的頻次，以及不同詞性之間的相關系做判斷。有些學者通過虛詞（例如之、其、或、亦、了、的、不、把、別、好），判斷前後文風的差異。有些學者通過場景（花卉、樹木、飲食、醫葯與詩詞）頻次的差異，來做統計判斷。總而言之，主要通過一些指標量化，然後比較指標之間是否存在顯著差異，藉此進行寫作風格的判斷。
以上是小編為大家分享的關於數據挖掘演算法與生活中的應用案例的相關內容，更多信息可以關注環球青藤分享更多干貨