數據挖掘簡介

數據挖掘（英語：Data mining），又譯為資料探勘、數據采礦。它是數據庫知識發現（英語：Knowledge-Discovery in Databases，簡稱：KDD）中的一個步驟。數據挖掘一般是指從大量的數據中通過算法搜索隱藏于其中信息的過程。數據挖掘通常與計算機科學有關，并通過統計、在線分析處理、情報檢索、機器學習、專家系統（依靠過去的經驗法則）和模式識別等諸多方法來實現上述目標。

?

數據挖掘經典算法

1. C4.5：是機器學習算法中的一種分類決策樹算法，其核心算法是ID3算法。

解析

C4.5算法是機器學習算法中的一種分類決策樹算法，其核心算法是ID3 算法。 C4.5算法繼承了ID3算法的長處。并在下面幾方面對ID3算法進行了改進：

1） 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足。

2） 在樹構造過程中進行剪枝；

3） 可以完畢對連續屬性的離散化處理；

4） 可以對不完整數據進行處理。

C4.5算法有例如以下長處：產生的分類規則易于理解，準確率較高。其缺點是：在構造樹的過程中，須要對數據集進行多次的順序掃描和排序，因而導致算法的低效。

1、機器學習中。決策樹是一個預測模型。他代表的是對象屬性與對象值之間的一種映射關系。樹中每一個節點表示某個對象，而每一個分叉路徑則代表的某個可能的屬性值，而每一個葉結點則

相應從根節點到該葉節點所經歷的路徑所表示的對象的值。決策樹僅有單一輸出。若欲有復數輸出，能夠建立獨立的決策樹以處理不同輸出。

2、 從數據產生決策樹的機器學習技術叫做決策樹學習， 通俗說就是決策樹。

3、決策樹學習也是數據挖掘中一個普通的方法。在這里，每一個決策樹都表述了一種樹型結構，他由他的分支來對該類型的對象依靠屬性進行分類。每一個決策樹能夠依靠對源數據庫的切割

進行數據測試。

這個過程能夠遞歸式的對樹進行修剪。

當不能再進行切割或一個單獨的類能夠被應用于某一分支時。遞歸過程就完畢了。

另外。隨機森林分類器將很多決策樹結合起來

以提升分類的正確率。

2. K-means算法：是一種聚類算法。

術語“k-means”最早是由James MacQueen在1967年提出的。這一觀點能夠追溯到1957年 Hugo Steinhaus所提出的想法。1957年。斯圖亞特·勞埃德最先提出這一標準算法，當初是作為一門應用于脈碼調制的技術，直到1982年，這一算法才在貝爾實驗室被正式提出。1965年。 E.W.Forgy發表了一個本質上是同樣的方法。1975年和1979年。Hartigan和Wong分別提出了一個更高效的版本號。

算法描寫敘述

輸入：簇的數目k；包括n個對象的數據集D。

輸出：k個簇的集合。

方法：

從D中隨意選擇k個對象作為初始簇中心；

repeat;

依據簇中對象的均值。將每一個對象指派到最相似的簇；

更新簇均值。即計算每一個簇中對象的均值；

計算準則函數；

until準則函數不再發生變化。

?

3. SVM：一種監督式學習的方法

? ? ? ? 廣泛運用于統計分類以及回歸分析中支持向量機，英文為Support Vector Machine，簡稱SV機（論文中一般簡稱SVM）。它是一

種監督式學習的方法，它廣泛的應用于統計分類以及回歸分析中。

支持向量機屬于一般化線性分類器。他們也可以覺得是提克洛夫規范化（Tikhonov Regularization）方法的一個特例。這族分類器的特點是他們可以同一時候最小化經驗誤差與最大化

幾何邊緣區。因此支持向量機也被稱為最大邊緣區分類器。在統計計算中，最大期望（EM）算法是在概率（probabilistic）模型中尋找參數最大似然預計的算法。當中概率模型依賴于無

法觀測的隱藏變量（Latent Variabl）。

最大期望經經常使用在機器學習和計算機視覺的數據集聚（Data Clustering）領域。

最大期望算法經過兩個步驟交替進行計算：

第一步是計算期望（E），也就是將隱藏變量象可以觀測到的一樣包括在內從而計算最大似然的期望值；

另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值從而計算參數的最大似然預計。

M 步上找到的參數然后用于另外一個 E 步計算，這個過程不斷交替進行。

Vapnik等人在多年研究統計學習理論基礎上對線性分類器提出了還有一種設計最佳準則。其原理也從線性可分說起，然后擴展到線性不可分的情況。

甚至擴展到使用非線性函數中去，這

種分類器被稱為支持向量機（Support Vector Machine，簡稱SVM）。支持向量機的提出有非常深的理論背景。支持向量機方法是在近年來提出的一種新方法。

SVM 的主要思想能夠概括為兩點：

（1） 它是針對線性可分情況進行分析，對于線性不可分的情況，通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉化為高維特征空間使

其線性可分，從而使得高維特征空間採用線性算法對樣本的非線性特征進行線性分析成為可能；

（2） 它基于結構風險最小化理論之上在特征空間中建構最優切割超平面，使得學習器得到全局最優化，而且在整個樣本空間的期望風險以某個概率滿足一定上界。

在學習這樣的方法時，首先要弄清楚這樣的方法考慮問題的特點，這就要從線性可分的最簡單情況討論起，在沒有弄懂其原理之前，不要急于學習線性不可分等較復雜的情況，支持向量機

在設計時。須要用到條件極值問題的求解。因此需用拉格朗日乘子理論。但對多數人來說。曾經學到的或經常使用的是約束條件為等式表示的方式。但在此要用到以不等式作為必須滿足的條件，此時僅僅要了解拉格朗日理論的有關結論即可。

4. Apriori ：是一種最有影響的挖掘布爾關聯規則頻繁項集的算法。

Apriori算法是種最有影響的挖掘布爾關聯規則頻繁項集的算法。它的核心是基于兩階段頻集思想的遞推算法。該關聯規則在分類上屬于單維、單層、布爾關聯規則。

在這里，全部支持度大于最小支持度的項集稱為頻繁項集（簡稱頻集），也常稱為最大項目集。

在Apriori算法中，尋找最大項目集（頻繁項集）的基本思想是：算法須要對數據集進行多步處理。第一步，簡單統計全部含一個元素項目集出現的頻數，并找出那些不小于最小支持度的項目集，即一維最大項目集。從第二步開始循環處理直到再沒有最大項目集生成。循環過程是：第k步中，依據第k-1步生成的（k-1）維最大項目集產生k維侯選項目集。然后對數據庫進行搜索，得到侯選項目集的項集支持度。與最小支持度進行比較，從而找到k維最大項目集。

從算法的執行過程。我們能夠看出該Apriori算法的長處：簡單、易理解、數據要求低。然而我們也能夠看到Apriori算法的缺點：

（1）在每一步產生侯選項目集時循環產生的組合過多，沒有排除不應該參與組合的元素;

（2）每次計算項集的支持度時，都對數據庫D中的所有記錄進行了一遍掃描比較。假設是一個大型的數據庫的話，這樣的掃描比較會大大添加計算機系統的I/O開銷。而這樣的代價是隨著數據庫的記錄的添加呈現出幾何級數的添加。

因此人們開始尋求更好性能的算法。如F-P算法。

5. EM：最大期望值法。

最大期望算法（Expectation-maximization algorithm。又譯期望最大化算法）在統計中被用于尋找，依賴于不可觀察的隱性變量的概率模型中，參數的最大似然預計。

在統計計算中，最大期望（EM）算法是在概率模型中尋找參數最大似然預計或者最大后驗預計的算法。當中概率模型依賴于無法觀測的隱藏變量（Latent Variable）。最大期望經經常使用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。

最大期望算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變量的現有預計值，計算其最大似然預計值；第二步是最大化（M）。最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數預計值被用于下一個 E 步計算中，這個過程不斷交替進行。

M是一個在已知部分相關變量的情況下，預計未知變量的迭代技術。EM的算法流程例如以下：

1. 初始化分布參數

2. 反復直到收斂：

E步驟：預計未知參數的期望值，給出當前的參數預計。

M步驟：又一次預計分布參數，以使得數據的似然性最大，給出未知變量的期望預計。

應用于缺失值

最大期望過程說明

我們用 表示可以觀察到的不完整的變量值，用 表示無法觀察到的變量值，這樣 和 一起組成了完整的數據。

可能是實際測量丟失的數據，也可能是可以簡化問題的隱藏變量，假設它的值可以知道的話。比如，在混合模型（Mixture Model）中，假設“產生”樣本的混合元素成分已知的話最大似然公式將變得更加便利（參見以下的樣例）。

?

6.pagerank：是google算法的重要內容。

PageRank。網頁排名，又稱網頁級別、Google左側排名或佩奇排名，是一種由搜索引擎依據網頁之間相互的超鏈接計算的技術，而作為網頁排名的要素之中的一個，以Google公司創辦人拉里·佩奇（Larry Page）之姓來命名。Google用它來體現網頁的相關性和重要性，在搜索引擎優化操作中是常常被用來評估網頁優化的成效因素之中的一個。Google的創始人拉里·佩奇和謝爾蓋·布林于1998年在斯坦福大學發明了這項技術。

PageRank通過網絡浩瀚的超鏈接關系來確定一個頁面的等級。

Google把從A頁面到B頁面的鏈接解釋為A頁面給B頁面投票。Google依據投票來源（甚至來源的來源，即鏈接到A頁面的頁面）和投票目標的等級來決定新的等級。

簡單的說，一個高等級的頁面能夠使其它低等級頁面的等級提升。

7、Adaboost：是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器然后把弱分類器集合起來，構成一個更強的最終分類器。

AdaBoost。是英文“Adaptive Boosting”（自適應增強）的縮寫，是一種機器學習方法。由Yoav Freund和Robert Schapire提出。

AdaBoost方法的自適應在于：前一個分類器分錯的樣本會被用來訓練下一個分類器。AdaBoost方法對于噪聲數據和異常數據非常敏感。但在一些問題中。AdaBoost方法相對于大多數其他學習算法而言。不會非常easy出現過擬合現象。

AdaBoost方法中使用的分類器可能非常弱（比方出現非常大錯誤率），但僅僅要它的分類效果比隨機好一點（比方兩類問題分類錯誤率略小于0.5），就行改善終于得到的模型。而錯誤率高于隨機分類器的弱分類器也是實用的，由于在終于得到的多個分類器的線性組合中，可以給它們賦予負系數，相同也能提升分類效果。

AdaBoost方法是一種迭代算法。在每一輪中增加一個新的弱分類器，直到達到某個預定的足夠小的錯誤率。每個訓練樣本都被賦予一個權重。表明它被某個分類器選入訓練集的概率。

假設某個樣本點已經被準確地分類，那么在構造下一個訓練集中，它被選中的概率就被減少；

相反。假設某個樣本點沒有被準確地分類，那么它的權重就得到提高。通過這種方式，AdaBoost方法能“聚焦于”那些較難分（更富信息）的樣本上。

在詳細實現上，最初令每一個樣本的權重都相等，對于第k次迭代操作。我們就依據這些權重來選取樣本點，進而訓練分類器Ck。然后就依據這個分類器，來提高被它分錯的的樣本的權重，并減少被正確分類的樣本權重。

然后，權重更新過的樣本集被用于訓練下一個分類器Ck［2］。整個訓練過程如此迭代地進行下去。

8、KNN：是一個理論上比較成熟的的方法，也是最簡單的機器學習方法之一。

1、K近期鄰（k-Nearest Neighbor。KNN）分類算法。是一個理論上比較成熟的方法。也是最簡單的機器學習算法之中的一個。該方法的思路是：假設一個樣本在特征空間中的k個最相似（即特征空

間中最鄰近）的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別。

2、KNN算法中，所選擇的鄰居都是已經正確分類的對象。

該方法在定類決策上僅僅根據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

KNN方法盡管從原理上也依賴于極限定理。但在類別決策時，僅僅與極少量的相鄰樣本有關。因為KNN方法主要靠周圍有限的鄰近的樣本。

而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其它方法更為適合。

3、KNN算法不僅能夠用于分類，還能夠用于回歸。通過找出一個樣本的k個近期鄰居，將這些鄰居的屬性的平均值賦給該樣本，就能夠得到該樣本的屬性。

更實用的方法是將不同距離的

鄰居對該樣本產生的影響給予不同的權值（weight），如權值與距離成正比。

4、該算法在分類時有個基本的不足是，當樣本不平衡時，如一個類的樣本容量非常大，而其它類樣本容量非常小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數。因此能夠採用權值的方法（和該樣本距離小的鄰居權值大）來改進。

該方法不足之處是計算量較大，由于對每個待分類的文本都要計算它到全體已知樣本的距離。才干求得它的K個近期鄰點。

眼下經常使用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自己主動分類，而那些樣本容量較小的類域採用這樣的算法比較easy產生誤分。

算法分類步驟例如以下：

1 首先我們事先定下k值（就是指k近鄰方法的k的大小。代表對于一個待分類的數據點，我們要尋找幾個它的鄰居）。這邊為了說明問題，我們取兩個k值。分別為3和9；

2 依據事先確定的距離度量公式（如：歐氏距離）。得出待分類數據點和全部已知類別的樣本點中。距離近期的k個樣本。

3 統計這k個樣本點中。各個類別的數量。依據k個樣本中，數量最多的樣本是什么類別，我們就把這個數據點定為什么類別。

9、Naive Bayes：在眾多分類方法中，應用最廣泛的有決策樹模型和樸素貝葉斯（Naive Bayes）

貝葉斯分類的基礎是概率推理。就是在各種條件的存在不確定。僅知其出現概率的情況下，怎樣完畢推理和決策任務。概率推理是與確定性推理相相應的。

而樸素貝葉斯分類器是基于獨立如果的，即如果樣本每一個特征與其它特征都不相關。舉個樣例，如果一種水果其具有紅。圓，直徑大概4英寸等特征。該水果能夠被判定為是蘋果。

雖然這些特征相互依賴或者有些特征由其它特征決定。然而樸素貝葉斯分類器覺得這些屬性在判定該水果是否為蘋果的概率分布上獨立的。樸素貝葉斯分類器依靠精確的自然概率模型，在有監督學習的樣本集中能獲取得很好的分類效果。在很多實際應用中。樸素貝葉斯模型參數預計使用最大似然預計方法。換而言之樸素貝葉斯模型能工作并沒實用到貝葉斯概率或者不論什么貝葉斯模型。

雖然是帶著這些樸素思想和過于簡單化的如果，但樸素貝葉斯分類器在非常多復雜的現實情形中仍可以取得相當好的效果。2004年。一篇分析貝葉斯分類器問題的文章揭示了樸素貝葉斯分類器取得看上去不可思議的分類效果的若干理論上的原因。

雖然如此，2006年有一篇文章具體比較了各種分類方法，發現更新的方法（如boosted trees和隨機森林）的性能超過了貝葉斯分類器。

樸素貝葉斯分類器的一個優勢在于僅僅須要依據少量的訓練數據預計出必要的參數（變量的均值和方差）。因為變量獨立如果，僅僅須要預計各個變量的方法。而不須要確定整個協方差矩陣。

?

10、Cart：分類與回歸樹，在分類樹下面有兩個關鍵的思想，第一個是關于遞歸地劃分自變量空間的想法，第二個是用驗證數據進行減枝。

決策樹生長的核心是確定決策樹的分枝準則。

1、 怎樣從眾多的屬性變量中選擇一個當前的最佳分支變量。

也就是選擇能使異質性下降最快的變量。

異質性的度量：GINI、TWOING、least squared deviation。

前兩種主要針對分類型變量，LSD針對連續性變量。

代理劃分、加權劃分、先驗概率

2、 怎樣從分支變量的眾多取值中找到一個當前的最佳切割點（切割閾值）。

（1） 切割閾值：

A、數值型變量——對記錄的值從小到大排序，計算每一個值作為臨界點產生的子節點的異質性統計量。

可以使異質性減小程度最大的臨界值便是最佳的劃分點。

B、分類型變量——列出劃分為兩個子集的全部可能組合。計算每種組合下生成子節點的異質性。相同。找到使異質性減小程度最大的組合作為最佳劃分點。

在決策樹的每個節點上我們能夠按任一個屬性的任一個值進行劃分。按哪種劃分最好呢？有3個標準能夠用來衡量劃分的好壞：GINI指數、雙化指數、有序雙化指數。