游戲設計中幾種常用機器學習算法合集

當今機器學習算法已經廣泛應用于我們的日常生活之中，每天我們需要處理的數據也在不斷增加。理解數據背后的真實含義，能夠幫助人們認識事物本質，提高生產效率。機器學習算法主要用于分類、回歸和聚類，常用的幾種算法如下所示：

• 監督分類算法

• K-鄰近算法

• 決策樹(ID3算法)

• 樸素葉倍斯分類器

• Logistic回歸

• 支持向量機(SVM)

• AdaBoost元算法

• 回歸預測

• 線性回歸

• 樹回歸

• 無監督聚類

• K-均值聚類

• 關聯分析

• Apriori算法

• FP-growth算法

• 優化技術

• 降維：PCA算法

• 降維：SVD算法

• 大數據：MapReduce

該文作為《機器學習實戰》(Peter Harrington)的讀后感，列舉常用的機器學習算法，單看幾篇文章不可能充分理解機器學習，但可以作為一個索引，知道某種算法適合解決某一類問題，需要時再仔細研究。

K-鄰近算法

一種分類數據最簡單有效的算法，優點是容易實現，缺點在于效率低。原理是選擇與樣本數據中前K個最相似的數據，將k個最相似數據中出現最多的分類，作為新數據的分類。

如下圖所示是幾部電影里的打斗鏡頭與接吻鏡頭所出現次數的數據，現在要計算最后一部電影的類型。

可以算出未知電影與各個電影的距離

若選擇K=3，最近的兩個電影是He's Not Really into Dudes，Beautiful Woman和California Man，這三部電影全是愛情片，因此判斷未知電影也是愛情片。

決策樹ID3算法

決策樹是依照數據的不同特征做分類的方法，輸出結果易于理解，容易看出各個特征的內在聯系，但有可能出現過度匹配的問題。

在構造決策樹時，需要解決的第一個問題是，當前數據集上哪個特征在劃分數據類型時起決定性作用。為了找到決定性特征，我們必須評估每個特征。 ID3算法是一種用來構造決策樹的算法，它以信息熵的下降速度為選取測試屬性的標準。即在每個節點選取還尚未被用來劃分的具有最高信息增益（根據  游戲設計中幾種常用機器學習算法合集 計算）的屬性作為劃分標準，然后繼續這個過程，直到生成的決策樹能完美分類訓練樣例。

如下圖顯示的是動物的幾種特征和是否屬于魚類的數據，先測試以“不浮出水面是否可以生存”和“是否有腳蹼”作為分類后信息熵大小，計算后選取分類后信息熵較大的“不浮出水面是否可以生存”分類，接著再遞歸剩余的特征，直到被完全分類。

樸素葉倍斯分類器

樸素貝葉斯法是基于貝葉斯定理與特征條件獨立假設的分類方法。假設一個數據集由N類組成，如果p(類型c|x,y)?>?p(其他類型|x,y)，那么類別為c。

假如要對留言板的留言分類，屏蔽帶有侮辱性的留言。樣本如下，留言已經去除了標點符號并統一大小寫。

對每個類（帶有侮辱性、不帶侮辱性）計算 （c是分類，w是詞組向量），比較大小即可得出新留言的分類。根據樸素貝葉斯假設，將w展開為一個個獨立特征，那么p(w)=p(w1)*p(w2)*...p(wn)，p(w|ci)= = 。接下來只要統計各個詞在樣本中的出現頻率，就能夠解出上述式子。

Logistic回歸

根據現有數據對分類邊界建立回歸公式，以此進行分類。線性方程 ，即 。只要確定參數w，既可計算出回歸公式，進而分類。

圖：邏輯回歸的思想是用一個超平面將數據集分為兩部分，這兩部分分別位于超平面的兩邊，且屬于兩個不同類別。

梯度上升（下降）算法，是一種計算方程參數的算法。它的思想是：要找到某函數的最大值，最好的方法是沿著該函數的梯度方向搜尋。

由此對 進行多次迭代，即可找出方程參數。

支持向量機(SVM)

支持向量機會將問題當做一個“求兩個類的邊界距離”的最優化問題來解決。

假設你的數據點分為兩類，支持向量機試圖尋找最優的一條線（超平面），使得兩類數據與該線的距離最大。在離邊界較近的點（如下圖Gap內）稱為支持向量，它們對超平面有較大影響，應給予較高權重。

如果數據并非線性可分數據，可以通過核函數將數據映射成高維線性可分的數據，比如徑向核函數 映射數據，如下圖所示：

可以通過迭代計算SMO，其中Platt的SMO算法通過每次只優化兩個alpha值來加快SVM訓練速度。

AdaBoost元算法

元算法也叫集成方法，通過將其他算法進行組合而形成更優的算法，組合方式包括：不同算法的集成，數據集不同部分采用不同算法分類后的集成或者同一算法在不同設置下的集成。

Adaboost的目的就是從訓練數據中學習一系列弱分類器或基本分類器，然后將這些弱分類器組合成一個強分類器。它給每個訓練數據一個權重以達 到優化分類器的目的。每一個訓練樣本最開始時都被賦予相同的權重，接下來，如果某個樣本點已經被準確地分類，那么在構造下一個訓練集中，它被選中的概率就 被降低；相反，如果某個樣本點沒有被準確地分類，那么它的權重就得到提高。

判斷分類器的效果，除了使用錯誤率（正確率） 之外，ROC曲線也是一種分類器的評價方法。比如將“正常郵件分類成垃圾郵件”的后果要比“將垃圾郵件分類成正常郵件”嚴重，由此需要選擇低TN值的模型。

ROC曲線是顯示模型真正率和假正率之間折中的一種圖形化方法。 它引入了真正率、假正率等概念。

• 真正（True Positive , TP）被模型預測為正的正樣本；

• 假負（False Negative , FN）被模型預測為負的正樣本；

• 假正（False Positive , FP）被模型預測為正的負樣本；

• 真負（True Negative , TN）被模型預測為負的負樣本。

線性回歸

線性回歸是中學就學到的知識，一般使用最小二乘法求解，它通過最小化誤差的平方（ ）來尋找y=wx的最佳參數w。如圖是一條擬合直線。

為了達到更好的擬合效果，可以使用局部加權線性回歸。該算法給預測點附近的點賦予較高權重，遠離的點賦予較低權重，常見的權重公式為( )，這時線性方程變成y=w1*w2*x(w1為參數，w2為權重),如下圖為局部加權回歸的效果。

嶺回歸是一種改良的最小二乘估計法，通過放棄最小二乘法的無偏性，以損失部分信息、降低精度為代價獲得回歸系數更為符合實際、更可靠的回歸方法，對病態數據的擬合要強于最小二乘法。

樹回歸

現實生活中很多問題是非線性的，不可能用全局線性模型來擬合數據。一種可行的方法是將數據集切分成很多易建模的數據，然后利用線性回歸技術來進行 擬合。這種切分方式下，樹結構和回歸法就相當有用。分類回歸樹（CART）它使用二元切分來處理連續型變量，回歸樹的策略是：遍歷所有的特征，對每個特 征，遍歷這個特征里所有樣例的取值，計算以這個取值作為切分時，生成的兩個子數據集的平方誤差，我們取子數據集平方誤差最小的切分方式。

K-均值聚類

K-均值聚類算法是采用距離作為相似性的評價指標的無監督聚類算法。兩個對象的距離越近，相似度越大。算法過程如下：

1）隨機選取K個數據作為初始質心

2）測量數據到每個質心的距離，并歸類到最近的質心的類

3）重新計算各個類的質心

4）迭代2～3步直至新的質心小于指定閾值，算法結束

k均值算法的一個缺點是如果初始質心選擇不好，達到局部最優解后，不一定能達到全局最優解。二分k均值算法可以達到全局最優解，主要思想是：首先將所有點作為一個簇，然后將該簇一分為二。之后將簇劃分為兩個簇。以此進行下去，直到簇的數目等于用戶給定的數目k為止。

Apriori算法

關聯分析是一種在大規模數據集中尋找關系的人物，比如要確定商場里同時買啤酒和尿布的人多不多，做優惠的時候是否應該把這兩項捆綁銷售。Apriori 算法是數據挖掘中一種挖掘關聯規則的頻繁項集算法，其核心是基于兩階段頻集思想的遞推算法。

假如有0,1,2,3共4種商品，要找到經常在一起購買的組合。只要掃描所有數據，使用某一組合的總數除以交易總數，就可以得到支持度，支持度大于閥值即認為頻繁購買。但是遍歷2^N次太費時間，因此需要一種算法來減少計算量。

如果某個項是非頻繁的，那么它的子項也是非頻繁的，比如{1,3}不頻繁，那么{1,3,4}一定不頻繁，依據這一原理（Apriori原理）， 可以大大減少計算量。Apriori算法使用一種稱作逐層搜索的迭代方法，首先，找出頻繁1-項集的集合，該集合記作L1。L1用于找頻繁2-項集的集合 L2，而L2用于找L3，如此迭代。

FP-growth算法

Apriori算法在產生頻繁模式完全集前需要對數據進行多次掃描，同時產生大量的候選頻繁集，這就使Apriori算法時間和空間復雜度較大，FP-Growth算法是一種只需遍歷兩次數據的計算頻繁項算法。

FP-Growth算法流程的基本思路是不斷地迭代FP-tree的構造和投影過程。對于每個頻繁項，構造它的條件投影數據庫和投影FP- tree。對每個新構建的FP-tree重復這個過程，直到構造的新FP-tree為空，或者只包含一條路徑。當構造的FP-tree為空時，其前綴即為 頻繁模式；當只包含一條路徑時，通過枚舉所有可能組合并與此樹的前綴連接即可得到頻繁模式。

降維：PCA算法

原始數據很多特征，但這些特征不一定是獨立的，通過某些算法降低數據的特征數，摒棄不重要的特征，可以降低算法開銷。

PCA（Principal Component Analysis)是最常用的線性降維方法，對原始的空間中順序地找一組相互正交的坐標軸，第一個軸是使得方差最大的，第二個軸是在與第一個軸正交的平面 中使得方差最大的，第三個軸是在與第1、2個軸正交的平面中方差最大的，這樣假設在N維空間中，我們可以找到N個這樣的坐標軸，我們取前r個去近似這個空 間，這樣就從一個N維的空間壓縮到r維的空間了，但是我們選擇的r個坐標軸能夠使得空間的壓縮使得數據的損失最小。

降維：SVD

SVD（奇異值分解）是一種強大的降維工具，我們可以利用SVD來逼近矩陣并從中提取重要特征，通過保留矩陣80%-90%的能力，就可以得到重要特征并去除噪聲。

SVD給出一個與原始數據A同大小的對角矩陣S（由Σ的特征值組成），兩個酉矩陣U和V，且滿足= U*S*V'。若A為m×n陣，則U為m×m陣，V為n×n陣。奇異值在S的對角線上，非負且按降序排列。那么對于方陣Σ呢，就有

Σ = USV'

ΣΣ' = USV'*VS'U' = U(ΣΣ')U'

Σ'Σ = VS'U'*USV' = V(Σ'Σ)V'

U是ΣΣ'的特征向量矩陣；

V是Σ'Σ的特征向量矩陣，都是n*n的矩陣

由于方陣的SVD相當于特征值分解，所以事實上U = V, 即Σ = USU', U是特征向量組成的正交矩陣，我們的目的是，從n維降維到k維，也就是選出這n個特征中最重要的k個，也就是選出特征值最大的k個。

大數據：MapReduce

當數據大到無法使用一臺機器計算時，可以使用分布式計算。一個典型的MapReduce分布式作業流程先使用map階段并行處理數據。之后將這些數據在Reduce階段合并。MapReduce處理大數據的過程如下。