'機器學習&深度學習基礎（tensorflow版本實現的算法概述0）'

tensorflow集成和實現了各種機器學習基礎的算法，可以直接調用。

代碼集：https://github.com/ageron/handson-ml

監督學習

1）決策樹（Decision Tree）和隨機森林

決策樹：

決策樹是一種樹形結構，為人們提供決策依據，決策樹可以用來回答yes和no問題，它通過樹形結構將各種情況組合都表示出來，每個分支表示一次選擇（選擇yes還是no），直到所有選擇都進行完畢，最終給出正確答案。

決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹）。在實際構造決策樹時，通常要進行剪枝，這時為了處理由於數據中的噪聲和離群點導致的過分擬合問題。剪枝有兩種：

先剪枝——在構造過程中，當某個節點滿足剪枝條件，則直接停止此分支的構造。

後剪枝——先構造完成完整的決策樹，再通過某些條件遍歷樹進行剪枝。

決策樹主要是調用sklearn裡面函數，這個裡面包含了DecisionTreeClassifier，不需要我們自己去實現。

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
if __name__ == "__main__":
 n = 500
 x = np.random.rand(n) * 8 - 3
 x.sort()
 y = np.cos(x) + np.sin(x) + np.random.randn(n) * 0.4
 x = x.reshape(-1, 1)
 reg = DecisionTreeRegressor(criterion='mse')
 # reg1 = RandomForestRegressor(criterion='mse')
 dt = reg.fit(x, y)
 # dt1 = reg1.fit(x, y)
 x_test = np.linspace(-3, 5, 100).reshape(-1, 1)
 y_hat = dt.predict(x_test)
 plt.figure(facecolor="w")
 plt.plot(x, y, 'ro', label="actual")
 plt.plot(x_test, y_hat, 'k*', label="predict")
 plt.legend(loc="best")
 plt.title(u'Decision Tree', fontsize=17)
 plt.tight_layout()
 plt.grid()
 plt.show()

隨機森林：

1. Bagging

Bootstrap：一種有放回的抽樣方法。

Bagging（ bootstrap aggregation）的策略：從樣本集中進行有放回地選出n個樣本；在樣本的所有特徵上，對這n個樣本建立分類器；重複上述兩步m次，獲得m個樣本分類器；最後將測試數據都放在這m個樣本分類器上，最終得到m個分類結果，再從這m個分類結果中決定數據屬於哪一類（多數投票制）。

隨機森林採用了Bagging策略，且在其基礎上進行了一些修改，採用了兩個隨機：

1. 從訓練樣本集中使用Bootstrap採樣（隨機有放回）選出n個樣本。
2. 設樣本共有b個特徵，從這b個特徵中只隨機選擇k個特徵來分割樣本，通過計算選擇最優劃分特徵作為節點來劃分樣本集合來建立決策樹。（與Bagging的不同之處：沒有使用全部的特徵，這樣可以避免一些過擬合的特徵，不再對決策樹進行任何剪枝）
3. 重複以上兩步m次，可建立m棵決策樹
4. 這m棵決策樹形成了森林，可通過簡單多數投票法（或其他投票機制）來決定森林的輸出，決定屬於哪一類型。（針對解決迴歸問題，可以採用單棵樹輸出結果總和的平均值）

隨機森林在一定程序上提高了泛化能力，而且可以並行地生成單棵樹。

代碼示例：使用決策樹和隨機森林進行手寫數字（sklearn中的digits數據）的預測：

from sklearn import datasets
from sklearn.model_selection import cross_val_score
import datetime
from sklearn import tree
from sklearn.ensemble import RandomForestClassifier
digits = datasets.load_digits();
X = digits.data\\
 # // 特徵矩陣
y = digits.target \\
 # // 標籤矩陣
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=1/3., random_state=8) \\
 # // 分割訓練集和測試集
estimators = {}
# criterion: 分支的標準(gini/entropy)
estimators['tree'] = tree.DecisionTreeClassifier(criterion='gini',random_state=8) # 決策樹
# n_estimators: 樹的數量
# bootstrap: 是否隨機有放回
# n_jobs: 可並行運行的數量
estimators['forest'] = RandomForestClassifier(n_estimators=20,criterion='gini',bootstrap=True,n_jobs=2,random_state=8) # 隨機森林
for k in estimators.keys():
 start_time = datetime.datetime.now()
 # print '----%s----' % k
 estimators[k] = estimators[k].fit(X_train, y_train)
 pred = estimators[k].predict(X_test)
 # print pred[:10]
 print("%s Score: %0.2f" % (k, estimators[k].score(X_test, y_test)))
 scores = cross_val_score(estimators[k], X_train, y_train,scoring='accuracy' ,cv=10)
 print("%s Cross Avg. Score: %0.2f (+/- %0.2f)" % (k, scores.mean(), scores.std() * 2))
 end_time = datetime.datetime.now()
 time_spend = end_time - start_time
 print("%s Time: %0.2f" % (k, time_spend.total_seconds()))

2）樸素貝葉斯分類器（Naive Bayesian Model，NBM）

樸素貝葉斯分類器基於貝葉斯定理及其假設（即特徵之間是獨立的，是不相互影響的），主要用來解決分類和迴歸問題。

P(A|B) 是後驗概率， P(B|A) 是似然，P(A)為先驗概率，P(B) 為我們要預測的值。

具體應用有：標記一個電子郵件為垃圾郵件或非垃圾郵件；將新聞文章分為技術類、政治類或體育類；檢查一段文字表達積極的情緒，或消極的情緒；用於人臉識別軟件。

學過概率的同學一定都知道貝葉斯定理，這個在250多年前發明的算法，在信息領域內有著無與倫比的地位。貝葉斯分類是一系列分類算法的總稱，這類算法均以貝葉斯定理為基礎，故統稱為貝葉斯分類。樸素貝葉斯算法（Naive Bayesian) 是其中應用最為廣泛的分類算法之一。樸素貝葉斯分類器基於一個簡單的假定：給定目標值時屬性之間相互條件獨立。

通過以上定理和“樸素”的假定，我們知道：

P( Category | Document) = P ( Document | Category ) * P( Category) / P(Document)

舉個例子，給一段文字，返回情感分類，這段文字的態度是positive，還是negative。

為了解決這個問題，可以只看其中的一些單詞。

這段文字，將僅由一些單詞和它們的計數代表。

原始問題是：給你一句話，它屬於哪一類？

通過 bayes rules 變成一個比較簡單容易求得的問題。

問題變成，這一類中這句話出現的概率是多少，當然，別忘了公式裡的另外兩個概率。

例子：單詞love在positive 的情況下出現的概率是0.1，在negative的情況下出現的概率是 0.001。

後面將給大家詳細講解樸素貝葉斯分類算法。

實際應用場景

• 文本分類
• 垃圾郵件過濾
• 病人分類
• 拼寫檢查

樸素貝葉斯模型

樸素貝葉斯常用的三個模型有：

• 高斯模型：處理特徵是連續型變量的情況
• 多項式模型：最常見，要求特徵是離散數據
• 伯努利模型：要求特徵是離散的，且為布爾類型，即true和false，或者1和0

基於多項式模型的樸素貝葉斯算法（在github獲取）

# encoding=utf-8
import pandas as pd
import numpy as np
import cv2
import time
from sklearn.cross_validation import train_test_split
from sklearn.metrics import accuracy_score
# 二值化處理
def binaryzation(img):
 cv_img = img.astype(np.uint8) # 類型轉化成Numpy中的uint8型
 cv2.threshold(cv_img, 50, 1, cv2.THRESH_BINARY_INV, cv_img) # 大於50的值賦值為0,不然賦值為1
 return cv_img
# 訓練，計算出先驗概率和條件概率
def Train(trainset, train_labels):
 prior_probability = np.zeros(class_num) # 先驗概率
 conditional_probability = np.zeros((class_num, feature_len, 2)) # 條件概率
 # 計算
 for i in range(len(train_labels)):
 img = binaryzation(trainset[i]) # 圖片二值化，讓每一個特徵都只有0，1兩種取值
 label = train_labels[i]
 prior_probability[label] += 1
 for j in range(feature_len):
 conditional_probability[label][j][img[j]] += 1
 # 將條件概率歸到[1,10001]
 for i in range(class_num):
 for j in range(feature_len):
 # 經過二值化後圖像只有0，1兩種取值
 pix_0 = conditional_probability[i][j][0]
 pix_1 = conditional_probability[i][j][1]
 # 計算0，1像素點對應的條件概率
 probalility_0 = (float(pix_0)/float(pix_0+pix_1))*10000 + 1
 probalility_1 = (float(pix_1)/float(pix_0+pix_1))*10000 + 1
 conditional_probability[i][j][0] = probalility_0
 conditional_probability[i][j][1] = probalility_1
 return prior_probability, conditional_probability
# 計算概率
def calculate_probability(img, label):
 probability = int(prior_probability[label])
 for j in range(feature_len):
 probability *= int(conditional_probability[label][j][img[j]])
 return probability
# 預測
def Predict(testset, prior_probability, conditional_probability):
 predict = []
 # 對每個輸入的x，將後驗概率最大的類作為x的類輸出
 for img in testset:
 img = binaryzation(img) # 圖像二值化
 max_label = 0
 max_probability = calculate_probability(img, 0)
 for j in range(1, class_num):
 probability = calculate_probability(img, j)
 if max_probability < probability:
 max_label = j
 max_probability = probability
 predict.append(max_label)
 return np.array(predict)
class_num = 10 # MINST數據集有10種labels，分別是“0,1,2,3,4,5,6,7,8,9”
feature_len = 784 # MINST數據集每個image有28*28=784個特徵（pixels）
if __name__ == '__main__':
 print("Start read data")
 time_1 = time.time()
 raw_data = pd.read_csv('../data/train.csv', header=0) # 讀取csv數據
 data = raw_data.values
 features = data[::, 1::]
 labels = data[::, 0]
 # 避免過擬合，採用交叉驗證，隨機選取33%數據作為測試集，剩餘為訓練集
 train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
 time_2 = time.time()
 print('read data cost %f seconds' % (time_2 - time_1))
 print('Start training')
 prior_probability, conditional_probability = Train(train_features, train_labels)
 time_3 = time.time()
 print('training cost %f seconds' % (time_3 - time_2))
 print('Start predicting')
 test_predict = Predict(test_features, prior_probability, conditional_probability)
 time_4 = time.time()
 print('predicting cost %f seconds' % (time_4 - time_3))
 score = accuracy_score(test_labels, test_predict)
 print("The accruacy score is %f" % score)

3）最小二乘法（Least squares）

如果你對統計學有所瞭解，那麼你必定聽說過線性迴歸。最小均方就是用來求線性迴歸的。如下圖所示，平面內會有一系列點，然後我們求取一條線，使得這條線儘可能擬合這些點分佈，這就是線性迴歸。這條線有多種找法，最小二乘法就是其中一種。最小二乘法其原理如下，找到一條線使得平面內的所有點到這條線的歐式距離和最小。這條線就是我們要求取得線。

最小二乘法（又稱最小平方法）是一種數學優化技術。它通過最小化誤差的平方和尋找數據的最佳函數匹配。利用最小二乘法可以簡便地求得未知的數據，並使得這些求得的數據與實際數據之間誤差的平方和為最小。最小二乘法還可用於曲線擬合。其他一些優化問題也可通過最小化能量或最大化熵用最小二乘法來表達。

4）邏輯迴歸（Logistic Regression）

邏輯迴歸模型是一個二分類模型，它選取不同的特徵與權重來對樣本進行概率分類，用一個log函數計算樣本屬於某一類的概率。即一個樣本會有一定的概率屬於一個類，會有一定的概率屬於另一類，概率大的類即為樣本所屬類。用於估計某種事物的可能性。

5）支持向量機（SVM）

支持向量機（support vector machine）是一個二分類算法，它可以在N維空間找到一個(N-1)維的超平面，這個超平面可以將這些點分為兩類。也就是說，平面內如果存在線性可分的兩類點，SVM可以找到一條最優的直線將這些點分開。SVM應用範圍很廣。

要將兩類分開，想要得到一個超平面，最優的超平面是到兩類的margin達到最大，margin就是超平面與離它最近一點的距離，如下圖，Z2>Z1，所以綠色的超平面比較好。

6）K最近鄰算法（KNN，K-NearestNeighbor）

鄰近算法，或者說K最近鄰(KNN，K-NearestNeighbor)分類算法是數據挖掘分類技術中最簡單的方法之一。KNN算法的核心思想是如果一個樣本在特徵空間中的k個最相鄰的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別，並具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

主要應用領域是對未知事物的識別，即判斷未知事物屬於哪一類，判斷思想是，基於歐幾里得定理，判斷未知事物的特徵和哪一類已知事物的的特徵最接近。如上圖，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？如果K=3，由於紅色三角形所佔比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由於藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。由此也說明了KNN算法的結果很大程度取決於K的選擇。

7）集成學習（Ensemble Learning）

集成學習就是將很多分類器集成在一起，每個分類器有不同的權重，將這些分類器的分類結果合併在一起，作為最終的分類結果。最初集成方法為貝葉斯決策。

集成算法用一些相對較弱的學習模型獨立地就同樣的樣本進行訓練，然後把結果整合起來進行整體預測。集成算法的主要難點在於究竟集成哪些獨立的較弱的學習模型以及如何把學習結果整合起來。這是一類非常強大的算法，同時也非常流行。常見的算法包括：Boosting， Bootstrapped Aggregation（Bagging）， AdaBoost，堆疊泛化（Stacked Generalization， Blending），梯度推進機（Gradient Boosting Machine, GBM），隨機森林（Random Forest）。

那麼集成方法是怎樣工作的，為什麼他們會優於單個的模型？

• 他們拉平了輸出偏差：如果你將具有民主黨傾向的民意調查和具有共和黨傾向的民意調查取平均，你將得到一箇中和的沒有傾向一方的結果。
• 它們減小了方差：一堆模型的聚合結果和單一模型的結果相比具有更少的噪聲。在金融領域，這被稱為多元化——多隻股票的混合投資要比一隻股票變化更小。這就是為什麼數據點越多你的模型會越好，而不是數據點越少越好。
• 它們不太可能產生過擬合：如果你有一個單獨的沒有過擬合的模型，你是用一種簡單的方式（平均，加權平均，邏輯迴歸）將這些預測結果結合起來，然後就沒有產生過擬合的空間了。

無監督學習

8）聚類算法

聚類算法就是將一堆數據進行處理，根據它們的相似性對數據進行聚類。

聚類，就像迴歸一樣，有時候人們描述的是一類問題，有時候描述的是一類算法。聚類算法通常按照中心點或者分層的方式對輸入數據進行歸併。所以的聚類算法都試圖找到數據的內在結構，以便按照最大的共同點將數據進行歸類。常見的聚類算法包括 k-Means算法以及期望最大化算法（Expectation Maximization， EM）。

聚類算法有很多種，具體如下：中心聚類、關聯聚類、密度聚類、概率聚類、降維、神經網絡/深度學習。

9)K-均值算法(K-Means)

K-means算法是硬聚類算法，是典型的基於原型的目標函數聚類方法的代表，它是數據點到原型的某種距離作為優化的目標函數，利用函數求極值的方法得到迭代運算的調整規則。K-means算法以歐式距離作為相似度測度，它是求對應某一初始聚類中心向量V最優分類，使得評價指標J最小。算法採用誤差平方和準則函數作為聚類準則函數。K-means算法是很典型的基於距離的聚類算法，採用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。該算法認為簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標。

通常，人們根據樣本間的某種距離或者相似性來定義聚類，即把相似的（或距離近的）樣本聚為同一類，而把不相似的（或距離遠的）樣本歸在其他類。

10)主成分分析（Principal Component Analysis，PCA）

主成分分析是利用正交變換將一些列可能相關數據轉換為線性無關數據，從而找到主成分。PCA方法最著名的應用應該是在人臉識別中特徵提取及數據降維。

PCA主要用於簡單學習與可視化中數據壓縮、簡化。但是PCA有一定的侷限性，它需要你擁有特定領域的相關知識。對噪音比較多的數據並不適用。

11）SVD矩陣分解（Singular Value Decomposition）

也叫奇異值分解（Singular Value Decomposition），是線性代數中一種重要的矩陣分解，是矩陣分析中正規矩陣酉對角化的推廣。在信號處理、統計學等領域有重要應用。SVD矩陣是一個複雜的實復負數矩陣，給定一個m行、n列的矩陣M,那麼M矩陣可以分解為M = UΣV。U和V是酉矩陣，Σ為對角陣。

PCA實際上就是一個簡化版本的SVD分解。在計算機視覺領域，第一個臉部識別算法就是基於PCA與SVD的，用特徵對臉部進行特徵表示，然後降維、最後進行面部匹配。儘管現在面部識別方法複雜，但是基本原理還是類似的。

12）獨立成分分析(ICA)

獨立成分分析（Independent Component Analysis，ICA）是一門統計技術，用於發現存在於隨機變量下的隱性因素。ICA為給觀測數據定義了一個生成模型。在這個模型中，其認為數據變量是由隱性變量，經一個混合系統線性混合而成，這個混合系統未知。並且假設潛在因素屬於非高斯分佈、並且相互獨立，稱之為可觀測數據的獨立成分。

ICA與PCA相關，但它在發現潛在因素方面效果良好。它可以應用在數字圖像、檔文數據庫、經濟指標、心裡測量等。

上圖為基於ICA的人臉識別模型。實際上這些機器學習算法並不是全都像想象中一樣複雜，有些還和高中數學緊密相關。

後面講給大家一一詳細單獨講解這些常用算法。

強化學習

13）Q-Learning算法

Q-learning要解決的是這樣的問題：一個能感知環境的自治agent，怎樣通過學習選擇能達到其目標的最優動作。

強化學習目的是構造一個控制策略，使得Agent行為性能達到最大。Agent從複雜的環境中感知信息，對信息進行處理。Agent通過學習改進自身的性能並選擇行為，從而產生群體行為的選擇，個體行為選擇和群體行為選擇使得Agent作出決策選擇某一動作，進而影響環境。增強學習是指從動物學習、隨機逼近和優化控制等理論發展而來，是一種無導師在線學習技術，從環境狀態到動作映射學習，使得Agent根據最大獎勵值採取最優的策略；Agent感知環境中的狀態信息，搜索策略（哪種策略可以產生最有效的學習）選擇最優的動作，從而引起狀態的改變並得到一個延遲迴報值，更新評估函數，完成一次學習過程後，進入下一輪的學習訓練，重複循環迭代，直到滿足整個學習的條件，終止學習。

Q-Learning是一種無模型的強化學習技術。具體來說，可以使用Q學習來為任何給定的（有限的）馬爾可夫決策過程（MDP）找到最優的動作選擇策略。它通過學習一個動作價值函數，最終給出在給定狀態下采取給定動作的預期效用，然後遵循最優策略。一個策略是代理在選擇動作後遵循的規則。當這種動作值函數被學習時，可以通過簡單地選擇每個狀態中具有最高值的動作來構建最優策略。 Q-learning的優點之一是能夠比較可用操作的預期效用，而不需要環境模型。此外，Q學習可以處理隨機過渡和獎勵的問題，而不需要任何適應。已經證明，對於任何有限的MDP，Q學習最終找到一個最優策略，從總體獎勵的預期值返回到從當前狀態開始的所有連續步驟是最大可實現的意義。