前言
數(shù)據(jù)挖掘是通過對(duì)大量數(shù)據(jù)的清理及處理以發(fā)現(xiàn)信息，并將這原理應(yīng)用于分類，推薦系統(tǒng)，預(yù)測等方面的過程。本文基于《面向程序員數(shù)據(jù)挖掘指南》的理解，擴(kuò)展學(xué)習(xí)后的總結(jié)。不足之處還請(qǐng)賜教，覺得有幫助請(qǐng)點(diǎn)贊mark下。謝謝！
一、數(shù)據(jù)挖掘過程
1.數(shù)據(jù)選擇
在分析業(yè)務(wù)需求后，需要選擇應(yīng)用于需求業(yè)務(wù)相關(guān)的數(shù)據(jù)。明確業(yè)務(wù)需求并選擇好業(yè)務(wù)針對(duì)性的數(shù)據(jù)是數(shù)據(jù)挖掘的先決條件。
2.數(shù)據(jù)預(yù)處理
選擇好的數(shù)據(jù)會(huì)有噪音，不完整等缺陷，需要對(duì)數(shù)據(jù)進(jìn)行清洗，集成，轉(zhuǎn)換以及歸納。
3.數(shù)據(jù)轉(zhuǎn)換
根據(jù)選擇的算法，對(duì)預(yù)處理好的數(shù)據(jù)轉(zhuǎn)換為特定數(shù)據(jù)挖掘算法的分析模型。
4.數(shù)據(jù)挖掘
使用選擇好的數(shù)據(jù)挖掘算法對(duì)數(shù)據(jù)進(jìn)行處理后得到信息。
5.解釋與評(píng)價(jià)
對(duì)數(shù)據(jù)挖掘后的信息加以分析解釋，并應(yīng)用于實(shí)際的工作領(lǐng)域。
二、數(shù)據(jù)挖掘常用算法簡介
1.關(guān)聯(lián)分析算法
關(guān)聯(lián)規(guī)則在于找出具有最小支持度閾值和最小置信度閾值的不同域的數(shù)據(jù)之間的關(guān)聯(lián)。在關(guān)聯(lián)規(guī)則的分析算法研究中，算法的效率是核心的問題。
經(jīng)典的算法有：Apriori算法，AprioriTid算法，F(xiàn)P-growth算法；
2.分類算法
決策樹算法：以樹形結(jié)構(gòu)表示分類或者決策集合，產(chǎn)生規(guī)則或者發(fā)現(xiàn)規(guī)律。主要有ID3算法，C4.5算法， SLIQ算法， SPRINT算法， RainForest算法；
樸素Bayes分類算法：利用Bayes定理概率統(tǒng)計(jì)的方法，選擇其中概率比較大的類別進(jìn)行分類；
CBA(Classification Based on Association)算法：基于關(guān)聯(lián)規(guī)則的分類算法；
MIND(Mining in Database)算法 ：采用數(shù)據(jù)庫中用戶定義的函數(shù)(user-definedfunction，簡稱UDF)來實(shí)現(xiàn)分類的算法；
神經(jīng)網(wǎng)絡(luò)分類算法：利用訓(xùn)練集對(duì)多個(gè)神經(jīng)的網(wǎng)絡(luò)進(jìn)行訓(xùn)練，并用訓(xùn)練好的模型對(duì)樣本進(jìn)行分類；
粗集理論：粗集理論的特點(diǎn)是不需要預(yù)先給定某些特征或?qū)傩缘臄?shù)量描述，而是直接從給定問題出發(fā)，通過不可分辨關(guān)系和不可分辨類確定問題的近似域,從而找出問題中的內(nèi)在規(guī)律；
遺傳算法：遺傳算法是模擬生物進(jìn)化過程，利用復(fù)制(選擇)、交叉(重組)和變異(突變)3個(gè)基本方法優(yōu)化求解的技術(shù)；
3.聚類算法
聚類分析與分類不同，聚類分析處理的數(shù)據(jù)對(duì)象的類是未知的。聚類分析就是將對(duì)象集合分組為由類似的對(duì)象組成 的多個(gè)簇的過程。分為3類方法：
Ipartitioning method(劃分方法) 給定1個(gè)N個(gè)對(duì)象或者元組的數(shù)據(jù)庫，1個(gè)劃分方法構(gòu)建數(shù)據(jù)的K個(gè)劃分，每1個(gè)劃分表示1個(gè)聚簇，并且K<N。經(jīng)典算法是K-MEAN(K平均值)；
hierarchical method(層次方法)
對(duì)給定數(shù)據(jù)對(duì)象集合進(jìn)行層次的分解，經(jīng)典算法是BIRTH算法；
grid based method(基于網(wǎng)格的方法) 這種方法采用一個(gè)多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)。將空間量化為有限數(shù)目的單元，這些單元形成了網(wǎng)格結(jié)構(gòu)，所有聚類分析都在網(wǎng)格上進(jìn)行。常用的算法有STING，SkWAVECLUSTER和 CLIQUE；
小結(jié)
隨著數(shù)據(jù)量的日益積累以及數(shù)據(jù)庫種類的多樣化，各種數(shù)據(jù)挖掘方法作用范圍有限，都有局限性，因此采用單一方法難以得到?jīng)Q策所需的各種知識(shí)。但它們的有機(jī)組合具有互補(bǔ)性，多方法融合將成為數(shù)據(jù)挖掘算法的發(fā)展趨勢。
三、數(shù)據(jù)挖掘算法實(shí)現(xiàn)
1、相關(guān)知識(shí)
(1)距離度量：在數(shù)據(jù)挖掘中需要明確樣本數(shù)據(jù)相似度，通?？梢杂?jì)算樣本間的距離，如下為常用距離度量的介紹。
樣本數(shù)據(jù)以：
曼哈頓距離： 也稱曼哈頓街區(qū)距離，就如從街區(qū)的一個(gè)十字路口點(diǎn)到另一個(gè)十字路口點(diǎn)的距離，
二維空間（多維空間按同理擴(kuò)展）用公式表示為
歐氏距離：表示為點(diǎn)到點(diǎn)的距離。二維空間（多維空間按同理擴(kuò)展）的公式表示為
閔可夫斯基距離：是一組距離方法的概括，當(dāng) p=1 既是曼哈頓距離，當(dāng) p=2 既是歐氏距離。當(dāng)p越大，單一維度的差值對(duì)整體的影響就越大。
閔可夫斯基距離（包括歐氏距離，曼哈頓距離）的優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：應(yīng)用廣泛。
缺點(diǎn)：無法考慮各分量的單位以及各分量分布（方差，期望）的差異性。（其中個(gè)分量的單位差異可以使用數(shù)據(jù)的標(biāo)準(zhǔn)化來消除，下面會(huì)有介紹。）
余弦相關(guān)系數(shù)：樣本數(shù)據(jù)視為向量，通過兩向量間的夾角余弦值確認(rèn)相關(guān)性，數(shù)值范圍[-1，1]。 -1表示負(fù)相關(guān)，0表示無關(guān)，1表示正相關(guān)。
余弦相關(guān)系數(shù)的優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：余弦相似度與向量的幅值無關(guān)，只與向量的方向相關(guān)，在文檔相似度（TF-IDF）和圖片相似性（histogram）計(jì)算上都有它的身影；
而且在樣本數(shù)值稀疏的時(shí)候仍可以使用。
缺點(diǎn)：余弦相似度受到向量的平移影響，上式如果將 x 平移到 x+1, 余弦值就會(huì)改變。(可以理解為受樣本的起始標(biāo)準(zhǔn)的影響，接下來介紹的皮爾遜相關(guān)系數(shù)可以消除這個(gè)影響)
皮爾遜相關(guān)系數(shù)：計(jì)算出了樣本向量間的相關(guān)性，數(shù)值范圍[-1，1]。
考慮計(jì)算的遍歷的次數(shù)，有一個(gè)替代公式可以近似計(jì)算皮爾遜相關(guān)系數(shù)：
皮爾遜相關(guān)系數(shù)優(yōu)點(diǎn)：可消除每個(gè)分量標(biāo)準(zhǔn)不同（分?jǐn)?shù)膨脹）的影響，具有平移不變性和尺度不變性。
(2)數(shù)據(jù)標(biāo)準(zhǔn)化：
各分量計(jì)算距離而各分量的單位尺度差異很大，可以使用數(shù)據(jù)標(biāo)準(zhǔn)化消除不同分量間單位尺度的影響，常用的方法有三種：
min-max 標(biāo)準(zhǔn)化：將數(shù)值范圍縮放到（0,1）,但沒有改變數(shù)據(jù)分布。max為樣本最大值，min為樣本最小值。
z-score 標(biāo)準(zhǔn)化：將數(shù)值范圍縮放到0附近, 但沒有改變數(shù)據(jù)分布。u是平均值，σ是標(biāo)準(zhǔn)差。
修正的標(biāo)準(zhǔn)z-score：修正后可以減少樣本數(shù)據(jù)異常值的影響。將z-score標(biāo)準(zhǔn)化公式中的均值改為中位數(shù)，將標(biāo)準(zhǔn)差改為絕對(duì)偏差。
其中asd絕對(duì)偏差：u為中位數(shù)，card(x)為樣本個(gè)數(shù)
(3) 算法的效果評(píng)估：
十折交叉驗(yàn)證：將數(shù)據(jù)集隨機(jī)分割成十個(gè)等份，每次用9份數(shù)據(jù)做訓(xùn)練集，1份數(shù)據(jù)做測試集，如此迭代10次。十折交叉驗(yàn)證的關(guān)鍵在于較平均地分為10份。
N折交叉驗(yàn)證又稱為留一法：用幾乎所有的數(shù)據(jù)進(jìn)行訓(xùn)練，然后留一個(gè)數(shù)據(jù)進(jìn)行測試，并迭代每一數(shù)據(jù)測試。留一法的優(yōu)點(diǎn)是：確定性。
2、算法入門——協(xié)同過濾推薦算法
代碼實(shí)現(xiàn)、數(shù)據(jù)集及參考論文 電影推薦——基于用戶、物品的協(xié)同過濾算法
...
示例：
r = Recommendor()
print("items base協(xié)同推薦 slope one")
#items base協(xié)同推薦算法 Slope one
r.slope_one_recommendation('lyy')
print("items base協(xié)同推薦 cos")
#items base協(xié)同推薦算法 修正余弦相似度
r.cos_recommendation('lyy')
print("users base協(xié)同推薦")
#userbase協(xié)同推薦算法
r.user_base_recommendation("lyy")
(1)基于用戶的協(xié)同推薦算法
這個(gè)方法是利用相似用戶的喜好來進(jìn)行推薦：如果要推薦一個(gè)樂隊(duì)給你，會(huì)查找一個(gè)和你類似的用戶，然后將他喜歡的樂隊(duì)推薦給你。
算法的關(guān)鍵在于找到相似的用戶，迭代計(jì)算你與每個(gè)用戶對(duì)相同樂隊(duì)的評(píng)分距離，來確定誰是你最相似的用戶，距離計(jì)算可以用曼哈頓距離，皮爾斯相關(guān)系數(shù)等等。
基于用戶的協(xié)同推薦算法算法的缺點(diǎn)：
擴(kuò)展性：隨著用戶數(shù)量的增加，其計(jì)算量也會(huì)增加。這種算法在只有幾千個(gè)用戶的情況下能夠工作得很好，但達(dá)到一百萬個(gè)用戶時(shí)就會(huì)出現(xiàn)瓶頸。稀疏性：大多數(shù)推薦系統(tǒng)中，物品的數(shù)量要遠(yuǎn)大于用戶的數(shù)量，因此用戶僅僅對(duì)一小部分物品進(jìn)行了評(píng)價(jià)，這就造成了數(shù)據(jù)的稀疏性。比如亞馬遜有上百萬本書，但用戶只評(píng)論了很少一部分，于是就很難找到兩個(gè)相似的用戶了。
(2)基于物品的協(xié)同推薦算法
基于用戶的協(xié)同過濾是通過計(jì)算用戶之間的距離找出最相似的用戶（需要將所有的評(píng)價(jià)數(shù)據(jù)在讀取在內(nèi)存中處理進(jìn)行推薦），并將相似用戶評(píng)價(jià)過的物品推薦給目標(biāo)用戶。而基于物品的協(xié)同過濾則是找出最相似的物品（通過構(gòu)建一個(gè)物品的相似度模型來做推薦），再結(jié)合用戶的評(píng)價(jià)來給出推薦結(jié)果。
基于物品的協(xié)同推薦算法常用有如下兩種：
修正余弦相似度算法：
以物品的評(píng)分作為物品的屬性值，通過對(duì)比物品i,j的工有的用戶相對(duì)評(píng)分的計(jì)算相關(guān)性s(i,j)。與皮爾遜相關(guān)系數(shù)的原理相同，共有用戶對(duì)物品的每一評(píng)分R(u,j)，R(u,i)需要減去該用戶評(píng)分的平均值R(`u)而消除分?jǐn)?shù)膨脹。
修正余弦相似度的優(yōu)點(diǎn)：通過構(gòu)建物品模型的方式，擴(kuò)展性好，占用內(nèi)存??；消除分?jǐn)?shù)膨脹的影響；
修正余弦相似度的缺點(diǎn)：稀疏性，需要基于用戶的評(píng)分?jǐn)?shù)據(jù)；
Slope One推薦算法：
第一步，計(jì)算平均差值：
dev(i,j)為遍歷所有共有物品i，j的共有用戶u的評(píng)分平均差異。
card(Sj,i(X))則表示同時(shí)評(píng)價(jià)過物品j和i的用戶數(shù)。
第二歩，使用加權(quán)的Slope One算法：
PWS1(u)j表示我們將預(yù)測用戶u對(duì)物品j的評(píng)分。
求合集i屬于S(u)-j,用戶u所含的所有物品i（除了j以外）。
dev(i,j)為遍歷所有共有物品i，j的共有用戶u的評(píng)分平均差異。
C(ji)也就是card(Sj,i(X))表示同時(shí)評(píng)價(jià)過物品j和i的用戶數(shù)。
Slope One算法優(yōu)點(diǎn)：算法簡單；擴(kuò)展性好，只需要更新共有屬性的用戶評(píng)價(jià)，而不需要重新載入整個(gè)數(shù)據(jù)集。
Slope One算法的缺點(diǎn)：稀疏性，需要基于用戶的評(píng)分?jǐn)?shù)據(jù)；
3、分類算法
(1)基于物品特征值的KNN分類算法
代碼實(shí)現(xiàn) 鳶尾花KNN分類算法
...
# KNN算法
def knn(self, oj_list):
weight_dict = {"Iris-setosa":0.0, "Iris-versicolor":0.0, "Iris-virginica":0.0}
for atuple in oj_list:
weight_dict[atuple[1]] += (1.0 / atuple[0])
rel_class = [(key, value) for key, value in weight_dict.items()]
#print(sorted(rel_class, key=lambda x:x[1], reverse=True))
rel_class = sorted(rel_class, key=lambda x:x[1], reverse=True)[0][0]
return rel_class
...
前面我們討論的協(xié)同推薦算法需要在用戶產(chǎn)生的各種數(shù)據(jù)上面進(jìn)行分析，因此也稱為社會(huì)化過濾算法，而這種算法通常有數(shù)據(jù)的稀疏性，算法可擴(kuò)展性以及依賴于用戶的數(shù)據(jù)的缺點(diǎn)，而基于物品特征值分類算法可以改善這些問題。算法分為兩步：
第一步、選取特征值
算法的關(guān)鍵在于挑取有代表區(qū)分意義的特征及分值。以Iris花的示例，選取花萼長度， 花萼寬度，花瓣長度，花瓣寬度特征值。
第二歩、計(jì)算距離
比如計(jì)算測試集與訓(xùn)練集特征值之間的曼哈頓距離，得到k個(gè)最近鄰后并通過加權(quán)后的結(jié)果預(yù)測分類。
KNN分類算法的缺點(diǎn)：無法對(duì)分類結(jié)果的置信度進(jìn)行量化；是被動(dòng)學(xué)習(xí)的算法，每次測試需要需要遍歷所有的訓(xùn)練集后才能分類。
(2)貝葉斯分類算法
代碼實(shí)現(xiàn) 區(qū)分新聞?lì)悇e樸素貝葉斯分類算法
...
def train_data(self):
#訓(xùn)練組的條件概率
for word in self.vocabulary:
for category,value in self.prob.items():
if word not in self.prob[category]:
count = 0
else :
count = self.prob[category][word]
#優(yōu)化條件概率公式
self.prob[category][word] = (count + 1) / (self.total[category] + len(self.vocabulary))
...
貝葉斯分類算法是基于概率的分類算法。相比于KNN分類算法，它是主動(dòng)學(xué)習(xí)的算法，它會(huì)根據(jù)訓(xùn)練集建立一個(gè)模型，并用這個(gè)模型對(duì)新樣本進(jìn)行分類，速度也會(huì)快很多。
貝葉斯分類算法的理論基礎(chǔ)是基于條件概率的公式（應(yīng)用于現(xiàn)實(shí)中P(X|Y&Z)不直觀得出，而P(Y|X)*P(Z|X)比較直觀得出），并假設(shè)已存在的子事件(y,z...實(shí)際應(yīng)用中會(huì)有多個(gè))間是相互獨(dú)立的（因此也稱為樸素貝葉斯），當(dāng)y，z事件假設(shè)為獨(dú)立便有：
如下舉例推測買牛奶和有機(jī)食品，再會(huì)買綠茶的概率：
第一步：計(jì)算先驗(yàn)概率及條件概率
先驗(yàn)概率：為單獨(dú)事件發(fā)生的概率，如P(買綠茶)，P(有機(jī)食品)
條件概率（后驗(yàn)概率）：y事件已經(jīng)發(fā)生，觀察y數(shù)據(jù)集后得出x發(fā)生的概率。如P(買有機(jī)食品|買綠茶)，通過以下公式計(jì)算（nc表示y數(shù)據(jù)集下x的發(fā)生頻數(shù)，n為y數(shù)據(jù)集的總數(shù)）：
上式存在一個(gè)缺陷，當(dāng)一個(gè)條件概率 P(y|x)為0時(shí)，整體的預(yù)測結(jié)果P(x) * P(y|x) * P(z|x)只能為0，這樣便不能更全面地預(yù)測。
修正后的條件概率：（公式摘自Tom Mitchell《機(jī)器學(xué)習(xí)》。m是一個(gè)常數(shù)，表示等效樣本大小。決定常數(shù)m的方法有很多，我們這里可以使用預(yù)測結(jié)果的類別來作為m，比如投票有贊成和否決兩種類別，所以m就為2。p則是相應(yīng)的先驗(yàn)概率，比如說贊成概率是0.5，那p(贊成)就是0.5。）：
第二歩：根據(jù)貝葉斯公式做出預(yù)測
由公式計(jì)算比較y&z事件發(fā)生下，不同x事件發(fā)生的概率差異，如得出P（x=喜歡），P（x=不喜歡） 的概率大小，預(yù)測為概率比較大的事件。
因?yàn)镻(y)*p(z)在上式都一樣，因此公式可以簡化為計(jì)算概率最大項(xiàng)而預(yù)測分類：
貝葉斯算法的優(yōu)點(diǎn)：能夠給出分類結(jié)果的置信度；它是一種主動(dòng)學(xué)習(xí)算法，速度更快。
貝葉斯算法的缺點(diǎn)：需要特定格式；數(shù)值型數(shù)據(jù)需要轉(zhuǎn)換為類別計(jì)算概率或用高斯分布計(jì)算概率；
(2)邏輯回歸分類算法
代碼實(shí)現(xiàn) 區(qū)分貓的圖片
注：邏輯回歸分類算法待后續(xù)加入網(wǎng)絡(luò)層，更新為神經(jīng)網(wǎng)絡(luò)分類算法。
...
# cost函數(shù)，計(jì)算梯度
def propagate(w, b, X, Y):
m = X.shape[1]
A = sigmoid(np.dot(w.T, X) + b)
cost = -1 / m * np.sum(Y * np.log(A) + (1 - Y) * np.log(1 - A))
dw = 1 / m * np.dot(X, (A - Y).T)
db = 1 / m * np.sum(A - Y)
...
邏輯回歸分類算法實(shí)現(xiàn)了輸入特征向量X，而輸出Y（范圍0~1）預(yù)測X的分類。
第一步，得到關(guān)于X線性回歸函數(shù)
可以通過線性回歸得到WX + b，其中W是權(quán)重，b是偏差值。但不能用本式表述預(yù)測的值，因?yàn)檩敵鯵的值需要在（0~1）區(qū)間；
第二歩，通過激活函數(shù)轉(zhuǎn)換
激活函數(shù)的特點(diǎn)是可以將線性函數(shù)轉(zhuǎn)換為非線性函數(shù)，并且有輸出值有限，可微分，單調(diào)性的特點(diǎn)。本例使用sigmoid，使輸出為預(yù)測值Y=sigmoid（WX+b）；
第三歩，構(gòu)建Cost函數(shù)
訓(xùn)練W，b更好的預(yù)測真實(shí)的類別需要構(gòu)建Cost代價(jià)函數(shù)，y^為sigmoid(WX+b)的預(yù)測分類值，y為實(shí)際分類值（0或者1）：
其中L(y^,y)稱為損失函數(shù)
訓(xùn)練的目的就是為了讓L(y,y)足夠小，也就是當(dāng)y實(shí)際分類值為1時(shí)，y要盡量偏向1。y實(shí)際分類值為0時(shí)，y^盡量小接近0。
第四步，梯度下降得到Cost函數(shù)的極小值
通過對(duì)W,b兩個(gè)參數(shù)求偏導(dǎo)，不斷迭代往下坡的的位置移動(dòng)（對(duì)w，b值往極小值方向做優(yōu)化，其中α為學(xué)習(xí)率控制下降的幅度），全局最優(yōu)解也就是代價(jià)函數(shù)（成本函數(shù)）J (w,b)這個(gè)凸函數(shù)的極小值點(diǎn)。
第五步、通過訓(xùn)練好的W,b預(yù)測分類。
4、聚類算法
(1)層次聚類
代碼實(shí)現(xiàn) 狗的種類層次聚類
層次聚類將每條數(shù)據(jù)都當(dāng)作是一個(gè)分類，每次迭代的時(shí)候合并距離最近的兩個(gè)分類，直到剩下一個(gè)分類為止。
(2)K-means++聚類
代碼實(shí)現(xiàn) Kmean++聚類
注：Kmean算法與Kmean++區(qū)別在于初始的中心點(diǎn)是直接隨機(jī)選取k各點(diǎn)。
...
#kmean初始化隨機(jī)k個(gè)中心點(diǎn)
#random.seed(1)
#center = [[self.data[i][r] for i in range(1, len((self.data)))]
#for r in random.sample(range(len(self.data)), k)]
# Kmean ++ 初始化基于距離份量隨機(jī)選k個(gè)中心點(diǎn)
# 1.隨機(jī)選擇一個(gè)點(diǎn)
center = []
center.append(random.choice(range(len(self.data[0]))))
# 2.根據(jù)距離的概率選擇其他中心點(diǎn)
for i in range(self.k - 1):
weights = [self.distance_closest(self.data[0][x], center)
for x in range(len(self.data[0])) if x not in center]
dp = [x for x in range(len(self.data[0])) if x not in center]
total = sum(weights)
#基于距離設(shè)定權(quán)重
weights = [weight/total for weight in weights]
num = random.random()
x = -1
i = 0
while i < num :
x += 1
i += weights[x]
center.append(dp[x])
...
k-means++算法可概括為：
（1）基于各點(diǎn)到中心點(diǎn)得距離分量，依次隨機(jī)選取到k個(gè)元素作為中心點(diǎn)：
先隨機(jī)選擇一個(gè)點(diǎn)。重復(fù)以下步驟，直到選完k個(gè)點(diǎn)。
計(jì)算每個(gè)數(shù)據(jù)點(diǎn)dp(n)到各個(gè)中心點(diǎn)的距離（D），選取最小的值D(dp)；
根據(jù)D(dp)距離所占的份量來隨機(jī)選取下一個(gè)點(diǎn)作為中心點(diǎn)。
（2）根據(jù)各點(diǎn)到中心點(diǎn)的距離分類；
（3）計(jì)算各個(gè)分類新的中心點(diǎn)；
重復(fù)(2、3)，直至滿足條件。
