本文總結了資料挖掘以及機器學習中常見算法如神經網絡算法、随機森林算法以及決策樹等，希望能對資料挖掘愛好者有一定幫助。
BP神經網絡
BP網絡能學習和存貯大量的輸入-輸出模式映射關系，而無需事前揭示描述這種映射關系的數學方程。它的學習規則是使用最速下降法，通過反向傳播來不斷調整網絡的權值和門檻值，使網絡的誤差平方和最小。BP神經網絡模型拓撲結構包括輸入層（input）、隐層(hidelayer)和輸出層(outputlayer)。BP神經網絡算法是在BP神經網絡現有算法的基礎上提出的，是通過任意標明一組權值，将給定的目标輸出直接作為線性方程的代數和來建立線性方程組，解得待求權，不存在傳統方法的局部極小及收斂速度慢的問題，且更易了解。
其基本思想是：由所給的輸入、輸出模式對通過作用于神經網絡來建立線性方程組，運用高斯消元法解線性方程組來求得未知權值，而未采用傳統BP網絡的非線性函數誤差回報尋優的思想。
對給定的樣本模式對，随機標明一組自由權，作為輸出層和隐含層之間固定權值，通過傳遞函數計算隐層的實際輸出，再将輸出層與隐層間的權值作為待求量，直接将目标輸出作為等式的右邊建立方程組來求解。
決策樹
簡介
項目風險，判斷其可行性的決策分析方法，是直覺運用機率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝幹，故稱決策樹。在機器學習中，決策樹是一個預測模型，他代表的是對象屬性與對象值之間的一種映射關系。Entropy=系統的淩亂程度，使用算法ID3, C4.5和C5.0生成樹算法使用熵。這一度量是基于資訊學理論中熵的概念。
決策樹是一種樹形結構，其中每個内部節點表示一個屬性上的測試，每個分支代表一個測試輸出，每個葉節點代表一種類别。
分類樹（決策樹）是一種十分常用的分類方法。他是一種監管學習，所謂監管學習就是給定一堆樣本，每個樣本都有一組屬性和一個類别，這些類别是事先确定的，那麼通過學習得到一個分類器，這個分類器能夠對新出現的對象給出正确的分類。這樣的機器學習就被稱之為監督學習。
組成
□——決策點，是對幾種可能方案的選擇，即最後選擇的最佳方案。如果決策屬于多級決策，則決策樹的中間可以有多個決策點，以決策樹根部的決策點為最終決策方案。
○——狀态節點，代表備選方案的經濟效果（期望值），通過各狀态節點的經濟效果的對比，按照一定的決策标準就可以選出最佳方案。由狀态節點引出的分支稱為機率枝，機率枝的數目表示可能出現的自然狀态數目每個分枝上要注明該狀态出現的機率。
△——結果節點，将每個方案在各種自然狀态下取得的損益值标注于結果節點的右端。
畫法
機器學習中，決策樹是一個預測模型；他代表的是對象屬性與對象值之間的一種映射關系。樹中每個節點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結點則對應從根節點到該葉節點所經曆的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有複數輸出，可以建立獨立的決策樹以處理不同輸出。資料挖掘中決策樹是一種經常要用到的技術，可以用于分析資料，同樣也可以用來作預測。
從資料産生決策樹的機器學習技術叫做決策樹學習,通俗說就是決策樹。
一個決策樹包含三種類型的節點：
決策節點：通常用矩形框來表示
機會節點：通常用圓圈來表示
終結點：通常用三角形來表示
決策樹學習也是資料探勘中一個普通的方法。在這裡，每個決策樹都表述了一種樹型結構，它由它的分支來對該類型的對象依靠屬性進行分類。每個決策樹可以依靠對源資料庫的分割進行資料測試。這個過程可以遞歸式的對樹進行修剪。當不能再進行分割或一個單獨的類可以被應用于某一分支時，遞歸過程就完成了。另外，随機森林分類器将許多決策樹結合起來以提升分類的正确率。
決策樹同時也可以依靠計算條件機率來構造。
決策樹如果依靠數學的計算方法可以取得更加理想的效果。資料庫已如下所示：
(x,y)=(x1,x2,x3…,xk,y)
相關的變量Y表示我們嘗試去了解，分類或者更一般化的結果。其他的變量x1,x2,x3等則是幫助我們達到目的的變量。
決策樹實際上是将空間用超平面進行劃分的一種方法，每次分割的時候，都将目前的空間一分為二，比如說下面的決策樹：
就是将空間劃分成下面的樣子：
決策樹的剪枝
剪枝是決策樹停止分支的方法之一，剪枝有分預先剪枝和後剪枝兩種。預先剪枝是在樹的生長過程中設定一個名額，當達到該名額時就停止生長，這樣做容易産生“視界局限”，就是一旦停止分支，使得節點N成為葉節點，就斷絕了其後繼節點進行“好”的分支操作的任何可能性。不嚴格的說這些已停止的分支會誤導學習算法，導緻産生的樹不純度降差最大的地方過分靠近根節點。後剪枝中樹首先要充分生長，直到葉節點都有最小的不純度值為止，因而可以克服“視界局限”。然後對所有相鄰的成對葉節點考慮是否消去它們，如果消去能引起令人滿意的不純度增長，那麼執行消去，并令它們的公共父節點成為新的葉節點。這種“合并”葉節點的做法和節點分支的過程恰好相反，經過剪枝後葉節點常常會分布在很寬的層次上，樹也變得非平衡。後剪枝技術的優點是克服了“視界局限”效應，而且無需保留部分樣本用于交叉驗證，是以可以充分利用全部訓練集的資訊。但後剪枝的計算量代價比預剪枝方法大得多，特别是在大樣本集中，不過對于小樣本的情況，後剪枝方法還是優于預剪枝方法的。
決策樹總結
代碼實作
Decisiontree.py
from sklearn import tree
x = [[1,1],[1,1],[1,0],[0,1],[0,1]]
y= [,,,,]
clf=tree.DecisionTreeClassifier()
clf= clf.fit(x,y)
print clf.predict([[1,1]])
随機森林
樹的投票
當你要做預測的時候，新的觀察到的特征随着決策樹自上而下走下來，這樣一組觀察到的特征将會被貼上一個預測值/标簽。一旦森林中的每棵樹都給出了預測值/簽，所有的預測結果将被歸總到一起，所有樹的模式投票被傳回做為最終的預測結果。
簡單來說，99.9%不相關的樹做出的預測結果涵蓋所有的情況，這些預測結果将會彼此抵消。少數優秀的樹的預測結果将會超脫于芸芸“噪音”，做出一個好的預測。
一個映射的例子
随機森林在沒有精心準備的資料映射的情況下也能學習。以方程f(x) = log(x)為例。制造一些假資料，并且加上一點兒噪音。
如果我們建立了一個基本的線性模型通過使用 x 來預測y，我們需要作一條直線，算是平分log (x)函數。而如果我們使用一個随機的森林，它不會更好的逼近 log (x)曲線并能夠使得它更像實際函數。
你也許會說随機森林有點擾亂log(x)函數。不管怎樣我都認為這做了一個很好的說明如何随機森林并未綁定于線性限制 。
變量選擇
随機森林最好的用例之一是特征選擇。嘗試很多決策樹變種的一個副産品就是你可以檢測每棵樹中哪個變量最合适/最糟糕。
當一棵樹使用一個變量，而另一棵不使用這個變量，你就可以從是否包含這個變量來比較價值的減少或增加。優秀的随機森林實作将為你做這些事情，是以你需要做的僅僅是知道去看那個方法或參數。
在下述的例子中，我們嘗試去指出對于将酒分為紅酒或者白酒哪個變量是最重要的。
回歸
随機森林不像其它算法對分類變量或者分類變量和真實變量混合學習的非常好。具有高基數（可能值的#）的分類變量是很棘手的，是以在你的口袋中放點兒這樣的東西将會是非常有用的。
随機森林相當容易使用，而且很強大。對于任何模組化，都要注意過拟合。如果你有興趣用R語言開始使用随機森林，那麼就簽出randomForest包。
代碼實作
RandomForest.py
from sklearn.cross_validation import cross_val_score
from sklearn.datasets import make_blobs
from sklearn.ensemble import RandomForestClassifier
x,y=make_blobs(n_samples=,n_features=,centers=,random_state=)
clf=RandomForestClassifier(n_estimators=,max_depth=None,min_samples_split=,random_state=)
scores = cross_val_score(clf,x,y)
print scores.mean()
PageRank算法
代碼實作
PageRank.py
import networkx as nx
g=nx.DiGraph()
g.add_edge(,)
g.add_edge(,)
g.add_edge(,)
g.add_edge(,)
g.add_edge(,)
g.add_edge(,)
g.add_edge(,)
g.add_edge(,)
pr=nx.pagerank(g,alpha=)
print pr
K-core
代碼實作
Kmeans.py
from numpy import *
import time
import matplotlib.pyplot as plt
# calculate Euclidean distance
def euclDistance(vector1, vector2):
return sqrt(sum(power(vector2 - vector1, )))
# init centroids with random samples
def initCentroids(dataSet, k):
numSamples, dim = dataSet.shape
centroids = zeros((k, dim))
for i in range(k):
index = int(random.uniform(, numSamples))
centroids[i, :] = dataSet[index, :]
return centroids
# k-means cluster
def kmeans(dataSet, k):
numSamples = dataSet.shape[]
# first column stores which cluster this sample belongs to,
# second column stores the error between this sample and its centroid
clusterAssment = mat(zeros((numSamples, )))
clusterChanged = True
## step 1: init centroids
centroids = initCentroids(dataSet, k)
while clusterChanged:
clusterChanged = False
## for each sample
for i in xrange(numSamples):
minDist =
minIndex =
## for each centroid
## step 2: find the centroid who is closest
for j in range(k):
distance = euclDistance(centroids[j, :], dataSet[i, :])
if distance < minDist:
minDist = distance
minIndex = j
## step 3: update its cluster
if clusterAssment[i, ] != minIndex:
clusterChanged = True
clusterAssment[i, :] = minIndex, minDist**
## step 4: update centroids
for j in range(k):
pointsInCluster = dataSet[nonzero(clusterAssment[:, ].A == j)[]]
centroids[j, :] = mean(pointsInCluster, axis = )
print 'Congratulations, cluster complete!'
return centroids, clusterAssment
# show your cluster only available with 2-D data
def showCluster(dataSet, k, centroids, clusterAssment):
numSamples, dim = dataSet.shape
if dim != :
print "Sorry! I can not draw because the dimension of your data is not 2!"
return
mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
if k > len(mark):
print "Sorry! Your k is too large! please contact Zouxy"
return
# draw all samples
for i in xrange(numSamples):
markIndex = int(clusterAssment[i, ])
plt.plot(dataSet[i, ], dataSet[i, ], mark[markIndex])
mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
# draw the centroids
for i in range(k):
plt.plot(centroids[i, ], centroids[i, ], mark[i], markersize = )
plt.show()
print "step 1: load data..."
dataSet = []
fileIn = open('C:/Users/Administrator/test/testSet.txt')
for line in fileIn.readlines():
lineArr = line.strip().split('\t')
dataSet.append([float(lineArr[]), float(lineArr[])])
## step 2: clustering...
print "step 2: clustering..."
dataSet = mat(dataSet)
k =
centroids, clusterAssment = kmeans(dataSet, k)
## step 3: show the result
print "step 3: show the result..."
showCluster(dataSet, k, centroids, clusterAssment)
testSet.txt
1.658985 4.285136
-
4.838138 -1.151539
- -
0.972564 2.924086
-
0.450614 -3.302219
- -
2.668759 1.594842
-
3.165506 -3.999838
- -
4.208187 2.984927
-
0.704199 -0.479481
-. -
2.831667 1.574018
-.
2.943496 -3.357075
- -
2.336445 2.875106
-
2.190101 -1.906020
- -
1.778124 3.880832
-
2.592976 -2.054368
- -
2.257734 3.387564
- .
0.939512 -4.023563
- -
2.046259 2.735279
-
4.372646 -0.822248
- -
1.889034 5.190400
-.
2.836520 -2.658556
- -
2.096701 3.886007
-
3.367037 -3.184789
- -
2.329546 3.179764
-
3.091414 -3.815232
- -
3.542056 2.778832
-
2.127073 -2.983680
- -
3.792121 5.135768
-
2.624081 -3.260715
- -
2.493525 1.963710
-
1.864375 -3.176309
- -
2.894220 2.489128
-
3.491078 -3.947487
- -
3.332948 3.983102
-
2.280615 -2.559444
- -
2.321395 3.154987
-
3.031012 -3.620252
- -
4.196223 1.126677
-
4.668892 -2.562705
- -
2.884105 3.043438
-
4.479332 -1.764772
- -
AdaBoost算法
代碼實作
AdaBoost.py
from sklearn.cross_validation import cross_val_score
from sklearn.datasets import load_iris
from sklearn.ensemble import AdaBoostClassifier
iris = load_iris()
clf= AdaBoostClassifier(n_estimators=)
scores = cross_val_score(clf,iris.data,iris.target)
print scores.mean()