⑴ KNN演算法-4-演算法優化-KD樹
KNN演算法的重要步驟是對所有的實例點進行快速k近鄰搜索。如果採用線性掃描（linear scan），要計算輸入點與每一個點的距離，時間復雜度非常高。因此在查詢操作時，可以使用kd樹對查詢操作進行優化。
Kd-樹是K-dimension tree的縮寫，是對數據點在k維空間（如二維(x，y)，三維(x，y，z)，k維(x1，y，z..)）中劃分的一種數據結構，主要應用於多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。本質上說，Kd-樹就是一種平衡二叉樹。
k-d tree是每個節點均為k維樣本點的二叉樹，其上的每個樣本點代表一個超平面，該超平面垂直於當前劃分維度的坐標軸，並在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹。即若當前節點的劃分維度為d，其左子樹上所有點在d維的坐標值均小於當前值，右子樹上所有點在d維的坐標值均大於等於當前值，本定義對其任意子節點均成立。
必須搞清楚的是，k-d樹是一種空間劃分樹，說白了，就是把整個空間劃分為特定的幾個部分，然後在特定空間的部分內進行相關搜索操作。想像一個三維(多維有點為難你的想像力了)空間，kd樹按照一定的劃分規則把這個三維空間劃分了多個空間，如下圖所示：
首先，邊框為紅色的豎直平面將整個空間劃分為兩部分，此兩部分又分別被邊框為綠色的水平平面劃分為上下兩部分。最後此4個子空間又分別被邊框為藍色的豎直平面分割為兩部分，變為8個子空間，此8個子空間即為葉子節點。
常規的k-d tree的構建過程為：
對於構建過程，有兩個優化點：
例子：採用常規的構建方式，以二維平面點(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 為例結合下圖來說明k-d tree的構建過程：
如上演算法所述，kd樹的構建是一個遞歸過程，我們對左子空間和右子空間內的數據重復根節點的過程就可以得到一級子節點（5,4）和（9,6），同時將空間和數據集進一步細分，如此往復直到空間中只包含一個數據點。
如之前所述，kd樹中，kd代表k-dimension，每個節點即為一個k維的點。每個非葉節點可以想像為一個分割超平面，用垂直於坐標軸的超平面將空間分為兩個部分，這樣遞歸的從根節點不停的劃分，直到沒有實例為止。經典的構造k-d tree的規則如下：
kd樹的檢索是KNN演算法至關重要的一步，給定點p，查詢數據集中與其距離最近點的過程即為最近鄰搜索。
如在構建好的k-d tree上搜索(3,5)的最近鄰時，對二維空間的最近鄰搜索過程作分析。
首先從根節點(7,2)出發，將當前最近鄰設為(7,2)，對該k-d tree作深度優先遍歷。
以(3,5)為圓心，其到(7,2)的距離為半徑畫圓（多維空間為超球面），可以看出(8,1)右側的區域與該圓不相交，所以(8,1)的右子樹全部忽略。
接著走到(7,2)左子樹根節點(5,4)，與原最近鄰對比距離後，更新當前最近鄰為(5,4)。
以(3,5)為圓心，其到(5,4)的距離為半徑畫圓，發現(7,2)右側的區域與該圓不相交，忽略該側所有節點，這樣(7,2)的整個右子樹被標記為已忽略。
遍歷完(5,4)的左右葉子節點，發現與當前最優距離相等，不更新最近鄰。所以(3,5)的最近鄰為(5,4)。
舉例：查詢點（2.1,3.1）
星號表示要查詢的點（2.1,3.1）。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點並不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位於以查詢點為圓心且通過葉子節點的圓域內。為了找到真正的最近鄰，還需要進行相關的『回溯'操作。也就是說，演算法首先沿搜索路徑反向查找是否有距離查詢點更近的數據點。
舉例：查詢點（2，4.5）
一個復雜點了例子如查找點為（2，4.5），具體步驟依次如下：
上述兩次實例表明，當查詢點的鄰域與分割超平面兩側空間交割時，需要查找另一側子空間，導致檢索過程復雜，效率下降。
一般來講，最臨近搜索只需要檢測幾個葉子結點即可，如下圖所示：
但是，如果當實例點的分布比較糟糕時，幾乎要遍歷所有的結點，如下所示：
研究表明N個節點的K維k-d樹搜索過程時間復雜度為： 。
同時，以上為了介紹方便，討論的是二維或三維情形。但在實際的應用中，如SIFT特徵矢量128維，SURF特徵矢量64維，維度都比較大，直接利用k-d樹快速檢索（維數不超過20）的性能急劇下降，幾乎接近貪婪線性掃描。假設數據集的維數為D，一般來說要求數據的規模N滿足N»2D，才能達到高效的搜索。
Sklearn中有KDTree的實現，僅構建了一個二維空間的k-d tree，然後對其作k近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調用方式與此例相差無多。
⑵ 如何用pso演算法優化離散數據
聚類可以理解為根據你劃定的半徑取圈樣本，圈出幾類就是幾類，半徑大類就少，半徑小類就多。中心選擇可以隨機選取，那就是無監督演算法，現在有一種半監督演算法，先用少量標記好的樣本產生一些類別作為聚類中心，指導聚類的過程。可以使用kmeans和SVM結合
⑶ Hive 的Map-Rece Job執行太慢，有什麼辦法可以優化嗎
1.jpg 優化可以從幾個方面著手：1. 好的模型設計事半功倍。2. 解決數據傾斜問題。3. 減少job數。4. 設置旅態茄合理的map rece的task數，能有效提升性能。(比如，10w+級別的計算，用160個rece，那是相當的浪費，1個足夠)。5. 自己動手寫sql解決數據傾斜問題是個不錯的選擇。set hive.groupby.skewindata=true;這是通用的演算法優化，但演算法優化總是漠視業務，習慣性提供通用的解決方法。 Etl開發人員更了解業務，更了解數據，所以通過業務邏輯解決傾斜的方法往往更精確，更有效。6. 對count(distinct)採取漠視的方法，尤其數據大的時候很容易產生傾斜問題，不抱僥幸心理。自己動手，豐衣足食。7. 對小文件進行合並，是行至有效的提高調度效率的方拆察法，假如我們的作業設置合理的文件數，對雲梯的整體調度效率也會產生積極的影響。8. 優化時把握整閉凱體，單個作業最優不如整體最優。
⑷ 數據歸一化會降低數據集大小嗎
數據歸一化方法的本質是一種對數據進行線性轉換的方法，通過構建一種樣本空間之間的線性映射關系來進行數據數值的轉化，這種轉化並不會影響數據分布，即不會影響數據的內在規律，只是對數據的數值進行調整。數據歸一化有很多方法，並且在機器學習領域有諸多用途，不僅是能夠作為梯度下降的優化演算法，同時還能幫助一些數據集避免量綱不一致等問題。
經典機器學習領域的數據歸一化演算法主要有兩種，分別是0-1標准化（Max-Min Normalization）和Z-Score標准化。我們先討論歸一化基本流程，再探討歸一化對機器學習演算法在各方面的影響。
關於歸一化和標准化的概念辨析
一般來說，歸一化和標准化都是指對數據進行數值轉化，根據維基網路的解釋，都是Feature scaling(特徵縮放)的方法，並且都可以稱為normalization。但某些場景下也會有不同的稱呼，例如將0-1標准化稱為normalization，也就是歸一化散沖，而把Z-Score標准化稱為Standardization，即標准化。課上對二者概念不做具體區分。
1.數據歸一化計算公式
1.1 0-1標准化
0-1標准化是最簡單同時也是最常用的標准化方法。該方法通過在輸入特徵中逐列遍歷其中里的每一個數據，將Max和Min的記錄下來，並通過Max-Min作為基數（即Min=0，Max=1）進行數據的歸一化處理，基本公式為：
𝑥𝑛𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑎𝑡𝑖𝑜𝑛=𝑥−𝑀𝑖𝑛𝑀𝑎𝑥−𝑀𝑖𝑛
x
n
o
r
m
a
l
i
z
a
t
i
o
n
=
x
−
M
i
n
M
a
x
−
M
i
n
實際計算過程中需要逐列進行處理，即用每一列中的元素減去當前列的最小值，再除以該列的極差。
1.2 Z-Score標准化
和0-1標准化不同，Z-score標准化利用原始數據的均值（mean）和標准差（standard deviation）進行數據的標准化。同樣是逐列進行操作，每一條數據都減去當前列的均值再除以當前列的標准差，在這種標准化操作下，如果原數據服從正態分布，處理之後的數據服從標准正態分布。Z-Score標准化計算公式如下：
𝑥𝑛𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑎𝑡𝑖𝑜𝑛=𝑥−𝜇𝜎
x
n
o
r
m
a
l
i
z
a
t
i
o
n
=
x
−
μ
σ
其中𝜇
μ
代表均值，𝜎
σ
代表標准差。
和0-1標准化不同，Z-Score標准化並不會將數據放縮在0-1之間，而是均勻地分布在0的兩側。類似這種數據也被稱為Zero-Centered Data，在深度學習領域有重要應用。
一種更加嚴謹的做法，是在分母項、也就是標准差上加上一個非常小的常數𝜇
μ
，從而使得分母恆大於0。
1.3 非線性標准化
除了0-1標准化和Z-Score標准化外，還有一類使用非線性函數進行歸一化操作的方法。其中最具代表性的是Sigmoid標准化。
Sigmoid標准化其實非常好理解，就是利用Sigmoid函數對數據集的每一列進行處理，由於Sigmoid函數特性，處理之後的數據也將被壓縮到0-1之間。
當然，相比Sigmoid標准化，Z-Score標准化實際用途更廣。
2.數據歸一化演算法執行過程
我們以0-1標准化為例，來探討數據歸一化處理對量綱的影響以及在實際建模過程沖伏殲中的計算流程。當然其他標准化也類似。
對於0-1標准化來說，表面上看起來只是將每一列數據都放縮至0-1區間內，但實際上卻有著非常多的用途。一個最簡單的使用場景是，當數據集中不同列的量綱不一致時，通過對每一列的0-1標准化處理，能夠消除因為這種不一致而引發的演算法學習偏差。例如，在鳶尾花數據中，每一列都是以厘米作為單位，整體數據分布相對統一，但如果把其中某一列改為毫米、而其他幾列改為米作為單位，則以毫米為單位的列數值將特別大，而其他幾列數值將特別小，如此一來就會對包括線性方程在內的一系列模型建模造成重大影響，模型將無法「均勻的」從各列中提取信息。
數據的真實規律是第一個特徵其實對標簽的取值起到非常重大的作用，廳中但在實際數據獲取記錄過程中，如果量綱錯配，即給了第一個特徵一個非常大的量綱、第二個特徵一個非常小的量綱，那麼數據情況和實際建模情況就將產生較大誤差。
此時模型為了捕捉第一列相對更加重要的特性，計算所得的第一列特徵取值非常大，甚至是第二列特徵系數的10的5次方倍左右。盡管上述模型結果仍然是可以使用的結果，但特徵系數差異性的增加（由200倍變成20000倍差異）會導致兩個問題，其一是部分系數太小而導致計算精度問題，其二則是在特徵重要性判別上會忽視系數較小的特徵。而為了能夠消除這種量綱差異所帶來的規律挖掘方面的影響，我們就需要採用歸一化方法。
注意，關於標簽是否需要歸一化的問題，一般來說這並不是一個典型的操作，在絕大多數情況下我們也並不會對標簽進行歸一化操作。但此處，由於需要在歸一化後全都為正數的特徵上進行回歸類問題預測，且標簽取值有正有負，因此可以考慮對標簽進行歸一化處理，以方便觀測後續模型參數。不過盡管如此，此處的標簽歸一化也並不是必須的。
當然，如果是劃分訓練集和測試集進行建模並且進行歸一化操作，那麼在遵循「在訓練集上訓練，在測試集上進行測試」的基本原則下，我們首先在訓練集上進行數據歸一化處理並記錄各列的極值，然後當模型訓練完成之後，再藉助訓練集各列的極值來對測試機數據進行歸一化，再帶入模型進行測試。當然，如果這個過程對標簽也進行了歸一化處理，則標簽的歸一化過程和特徵歸一化過程無異，唯一需要注意的是如果是對未知數據進行預測，即需要模型輸出和真實採集到數據類似的結果，則需要在模型輸出的歸一化的標簽基礎上進行逆向歸一化處理。
此外，一般來說如果是Z-Score標准化，則無需對標簽進行標准化處理。
3.數據歸一化演算法評價
此處我們通過量綱不一致問題引出歸一化方法，但歸一化方法卻並不一定、且不僅僅應用於處理量綱不一致問題中。
首先，並非所有模型都受到數據各列的絕對數值大小影響，在通用的模型中，線性模型和距離類模型是兩類典型的會受到各列絕對數值大小影響的模型，例如線性回歸、KNN、K-Means（一種無監督的聚類模型）等，並且邏輯回歸在使用ECOC編碼進行類別判別時也是利用距離來判別樣本最終歸屬，此時，由於各列的絕對數值會影響模型學習的偏重，模型會更加側重於學習那些數值比較大的列，而無法「均勻」的從各列中提取有效信息，因此有時會出現較差的模型結果。但有些模型卻不受此影響，典型的如樹模型。
辯證的看，「均勻」的從各列提取有效信息其實也並不一定是最好的做法，本身對於有監督學習演算法來說，大多數數據集各列的重要性就不是等價的。但是，比起無法「均勻」的從各列提取有效信息，更可怕的是我們會不受控制的「不均勻」的去提取有效信息，這也是歸一化要解決的核心問題。
其次，我們需要知道，一旦對數據進行歸一化處理，數據就將失去可解釋性，也就是失去了量綱。例如對於鳶尾花數據來說，原始數據代表花瓣花萼的長寬測量結果，而如果我們對其進行歸一化處理，則每條數據就無法再給予明確的現實意義，這也是在很多要求可解釋性的情況下我們應該避免使用歸一化方法的原因。
不僅是歸一化方法，其實所有的樣本空間的映射都會改變數據集的可解釋性。
其三，歸一化方法屬於仿射變換的一種特殊形式，而所有的仿射變換其實都不會影響數據集原始分布，也就是並不影響數據集真實規律，只會影響某些演算法挖掘規律的難度（也就是受到特徵絕對數值影響的演算法）。例如對如下數據，我們可以觀察其歸一化前後的數據分布變化情況：
仿射變換指的是樣本空間平移（加減某個數）和放縮（乘除某個數）的變換。0-1標准化過程中，平移就是減去每一列最小值，放縮就是除以某一列的極差。
最後，也是最重要的一點，那就是對於梯度下降演算法來說，歸一化能夠提高收斂速度，例如下圖所示，經過歸一化處理之後的數據，在進行損失函數構造時損失函數的等高線圖將更加均勻，此時梯度下降的收斂速度也將更快，具體理論理解詳見下文論述，而在實際使用過程中，經過歸一化的數據在梯度下降過程中往往收斂更快，這其實是相比消除量綱影響，歸一化方法更加重要應用場景。
在提高收斂速度方面，Z-Score效果要好於0-1標准化。
關於歸一化能夠讓等高線更加均勻從而加快迭代收斂過程的理解：
從理論角度出發，其實梯度下降過程每一步參數點移動的方向是能夠讓梯度最快速下降的方向，也就是圖片上垂直於等高線的方向。但這種所謂的最快速的方向只在開始移動的一瞬間滿足，由於梯度是連續變化的函數，因此當移動了一小步之後「最優方向」其實就可能發生了變化，但參數只能在下次移動時再改變方向，因此中間其實很長一段距離參數並不不一定是沿著最優方向在進行移動。這里需要注意，如果下一次移動的方向和上一次移動方向一致或者類似，那就說明這次移動過程中參數並沒有偏離方向太多，反之則這次移動走了很多彎路。而當損失函數的等高線是均勻分布時，外圈的垂直線也就是內圈的垂直線，此時參數兩次移動過程大概率最優方向一致，也就是說相同的移動能夠更大程度降低損失函數值，而如果類似圖1中的情況，內外圈分布不均勻，則參數兩次迭代過程最優方向將發生偏移，也就是說明上一次迭代過程有很長一段距離沒有沿著最優方向迭代，該次迭代只降低了有限的損失函數計算值。經次過程不斷迭代，由於經過歸一化的損失函數每次迭代效率都更高，因此相比其他損失函數，經過歸一化的數據只需要更少次的迭代就能抵達最小值點，這也就是加快收斂速度的根本原因。
另外需要注意的是，收斂更快往往也意味著能夠收斂至更靠近全局最小值的點。
4.Z-Score標准化演算法評價及橫向對比
從大類上來分，Z-Score的使用場景要遠高於0-1標准化使用場景。當然這也並不是絕對的，要區分二者使用情景，我們首先需要進一步了解二者演算法性能。
生成Zero-Centered Data
一般來說，由於Z-Score標准化生成數據的Zero-Centered特性，使得其在深度學習領域倍受歡迎（是Batch Normalization的一種特殊情況）。而在機器學習領域對於標簽同時存在正負值的回歸類問題，使用Z-Score能夠避免對標簽進行歸一化。
標准正態分布
由於該方法同時也是正態分布轉換為標准正態分布的計算公式，因此如果原始數據滿足正態分布，則經過Z-Score轉化之後就能轉化為標准正態分布，進而可以利用標准正態分布諸多統計性質。
保留極端值分布
還有一點非常實用的功能，就是相比0-1標准化，Z-Score標准化能夠保留極端值的分布。
由於極端值的存在，會將其他數值壓縮在一個非常小的范圍內。而如果此時我們採用Z-Score進行標准化，極端值仍然還是極端值（相對該列其他數值而言），此時我們即可採用極端值處理方法對其進行處理（刪除或者蓋帽（默認凡小於百分之1分位數和大於百分之99分位數的值將會被百分之1分位數和百分之99分位數替代））。
二、梯度下降演算法優化初階
歸一化和學習率調度，是梯度下降演算法優化的基本方法。
1.數據歸一化與梯度下降演算法優化
接下來，我們討論歸一化與梯度下降之間的關系。此前我們通過簡單例子觀察了數據歸一化對梯度下降的影響——即歸一化能夠改變損失函數形態，而這種改變將顯著加快梯度下降的迭代收斂過程，直觀判斷是歸一化之後的損失函數等高線圖更加均勻。本小節我們將從梯度下降演算法優化角度出發，討論數據歸一化和梯度下降之間的關系。
在機器學習模型優化體系中，構建損失函數和損失函數求解是模型優化的兩大核心命題，通過損失函數的構建和求解，就能夠找到模型最優參數。但對於很多復雜模型來說，損失函數構建和求解並非易事，而梯度下降作為損失函數求解的重要方法，如何優化梯度下降求解過程，使其能夠「又快又好」的找到最小值點，就成了決定建模成敗的核心因素。當然，從梯度下降到隨機梯度下降再到小批量梯度下降，我們可以理解其為演算法層面上的優化，但除此以外還有許多圍繞優化梯度下降求解過程的演算法和方法，例如本節介紹的歸一化和學習率調度方法。
當然，優化方法的學習也需要遵循循序漸進的過程，本節我們仍然還是在線性回歸損失函數、也就是凸函數上進行基本優化思路的介紹和基本優化方法的學習，圍繞現線性回歸的凸函數損失函數求解，其實是可以使用最小二乘法一步到位求出數值解的，但也正是因為其最優解明確存在，也就給了我們進行對照實驗的基礎。我們將利用梯度下降演算法，在更加復雜的數據集上，探索如何使用優化方法，來逼近明確存在的全域最小值點，並在這個過程中深化對優化方法的理解，進而能夠在後續更加復雜的損失函數上、甚至是非凸的損失函數上，憑借我們的理解和所掌握的工具，用好最小二乘法這把利器進行更快更好的最優參數的求解。
為何在相同學習率下，在歸一化之後的數據集上進行梯度下降，卻更加接近全域最小值點，這又是什麼原因呢？回顧此前我們所討論的歸一化對損失函數的影響，從等高線圖上來看是等高線變得更加均勻，但實際上是整個損失函數在不同區域對應梯度都更加均勻，從而在靠近最小值點附近的梯度也比歸一化之前的損失函數梯度要大，也就是說，雖然學習率相同，但由於歸一化之後最小值點附近梯度要更大，因此同樣的迭代次，在歸一化之後的損失函數上參數點將移動至更加靠近最小值地附近的點。
我們可以通過不斷嘗試，直到「測出」最佳學習率為止。當然，在Scikit-Learn中其實也提供了這種類似枚舉去找出最佳超參數取值的方法，但如果是面對超大規模數據集的建模，受到計算資源的限制，我們其實是無法反復建模來找到最優學習率的，此時就需要採用一種更加先進的計算流程來解決這個問題。
2.學習率調度
基本概念
其實梯度下降優化的核心目標就是希望「更快更好」的找到最小值點，歸一化是通過修改損失函數來達成這個目標，而所謂學習率調度，則是通過調整學習率來達到這個目標。值得注意的是，此時找到一個確定的最優學習率並不是目標，「更快更好」找到最小值點才是目標，因此我們完全可以考慮在迭代過程動態調整學習率。而所謂學習率調度，也並不是一個尋找最佳學習率的方法，而是一種伴隨迭代進行、不斷調整學習率的策略。
學習率調度方法有很多種，目前流行的也達數十種之多，而其中一種最為通用的學習率調度方法是學習率衰減法，指的是在迭代開始時設置較大學習率，而伴隨著迭代進行不斷減小學習率。通過這樣的學習率設置，能夠讓梯度下降收斂速度更快、效果更好。
實踐過程
例如在上述例子中，我們不妨設置這樣的減速衰減的一個學習調度策略，衰減過程比例由如下函數計算得出：
lr_lambda = lambda epoch: 0.95 ** epoch
即假設初始學習率為0.5，則第一次迭代時實際學習率為0.5*1，第二輪迭代時學習率為0.5*0.95，以此類推。據此，我們可以優化梯度下降迭代過程。
演算法評價
接下來，簡單總結學習率調度的使用場景和注意事項。
首先，在很多海量數據處理場景下，學習率調度的重大價值在於能夠提供對學習率超參數設置更大的容錯空間。在很多情況下，搜索出一個最佳學習率取值進而設置恆定學習率進行梯度下降，難度會遠高於設置一組學習率衰減的參數。並且有的時候，剛開始學習率設置過大其實也可以通過多輪迭代進行調整，其所消耗的算力也遠低於反復訓練模型尋找最佳恆定學習率。
其次，盡管上述例子我們是在梯度下降中使用學習率衰減這一調度策略，但實際上更為一般的情況是學習率調度和小批量梯度下降或者隨機梯度下降來配合使用。一般來說梯度下降的使用場景在於小規模數據集且損失函數較為簡單的情況，此時可利用梯度下降+枚舉找到最佳學習率的策略進行模型訓練，其相關操作的技術門檻相對較低（枚舉法可藉助Scikit-Learn的網格搜索）；而對於更大規模的數據集且損失函數情況更加復雜時，則需要考慮小批量梯度下降+學習率調度方法來進行梯度下降求解損失函數。
當然，除了學習率衰減外還有很多學習率調度策略，甚至有些學習率調度策略會間接性提高和降低學習率，來幫助梯度下降找到最小值點。
3.梯度下降組合優化策略
無論是數據歸一化、學習率調度還是採用小批量梯度下降，這些方法並不互斥，我們完全可以組合進行使用，達到組合優化的目的。
⑸ 梯度下降演算法中的優化途徑
特徵縮放還可以使機器學習演算法工作的更好。
比如在K近鄰演算法中，分類器主要是計算兩點之間的歐幾里得距離，如果一個特徵比其它的特徵有更大的范圍值，那麼距離將會被這個特徵值所主導。
在梯度下降法中，當某個特徵值較顫圓大的時候會出現類似於 圖一 的代價函數輪廓圖：
這樣的情況下，梯度下降的過程中會來回震盪，使得需要更多次的迭代才能到達局部最優點。
而如果對特徵進行縮放（Feature Scaling）那麼，迭代過程就可以像 圖二 一樣，更為快速的收斂。
因此每個特徵應該被歸一化，比如將取值范圍處理為0到1之間。
這種方法是將數據的特徵縮放到[0,1]或[-1,1]之間。縮放到游岩什麼范圍取決於數據的性質。對於這種方法的公式如下：
0均值歸一化方法將原始數據集歸一化為均茄磨塌值為0、方差1的數據集
公式如下：
其中max為樣本數據的最大值，min為樣本數據的最小值。這種方法有個缺陷就是當有新數據加入時，可能導致max和min的變化，需要重新定義。
S = Xmax - Xmin
⑹ 總數一定優化分配用什麼演算法
梯度下降法。
梯度下降法就是實現該「學習」過程的一種最常見的方式，尤其是在深度學習 (神經網路)模型中，BP反向傳播方法的核心就是對每層的權重參數不斷使用梯度下降來進行優化。. 梯度下降法 (gradient descent)是一種常用的一階 (first-order)優化方法，是求解無約束優化問題最簡單、最虧戚經典的方法之一。我們來考慮一個無約束優化問題 , 其中 為連續可微函數，如果我們能夠構造一個序列 ，並能夠滿足。
梯度下降法銷帆陵（英語：Gradient descent）是一個一階最優化演算法。 要使用梯轎滾度下降法找到一個函數的局部極小值，必須向函數上當前點對應梯度（或者是近似梯度）的反方向的規定步長距離點進行迭代搜索。如果相反地向梯度正方向迭代進行搜索，則會接近函數的局部極大值點；這個過程則被稱為梯度上升法。
⑺ 求能夠優化此類計算速度的演算法
左邊數據放在這譽則里：
ListLeft.add(String[A][100],String[B][200]，...)
右邊數據放在這里：
HashMap.put("A","100")
HashMap.put("B","800")
然後遍歷ListLeft,if(HashMap.cantain(String[A]){相加並放入第液斗三個List;HashMap.remove(String[A]);}else{直接放入第三個List},遍歷完後HashMap中剩慶埋棚下的都是ListLeft沒有的，全放入第三個List
只是初步設想，不知道會不會快
⑻ 數據結構和演算法優化
APP的優化是任重而道遠的過程，必須在意每一個環節，否者當你想要優化的時候，發現到處都是坑，已經不知道填補哪裡了，所以我們必須一點一滴的做起。
數據結構和演算法優化
能帶來什麼好處呢？他能使得你程序獲得數據更快，內存佔用更合理。最終體現為響應快內存佔用小。
我們先看常見的數據結構類型特點
數組 ： 一片物理上連續的大小確定的儲存空間 。int[num]
順序表 ：物理上連續、邏輯上連續、大小可以動態增加。ArrayList （查找快，添加刪除慢）
鏈表 ：物理上不連續、邏輯上連續、可以動態增加和刪除節點。LinkedList （查找慢只能輪尋，增加刪除快）
物理上連續：數組或者鏈表在初始化的時候，會申請分配內存空間：只要存儲空間足夠你申請的大小就分配給你初始化（物理不連續）；必須要連續的存儲空間，我才給你分配，否則失敗（物理上連續）
那麼有沒有繼承純虛標和鏈表的2個有點的數據結構呢？HashMap！
HashMap
它是由數組和鏈表結合組成。（HashMap：JDK1.7之前 24 之前： 數組+ 鏈表； HashMap：JDK1.8 之後： 數組+ 鏈表 + 紅黑樹）
下面是HashMap結構圖
它是怎麼操作的呢？為什麼他能同時擁有順序表和鏈表的優點呢？ 搞清它的實現方式，我們就可以知道了， 大致可以分為以下的步驟。
①put方法，傳入object和value，通過hash運算得到一個int類型的hashcode，這里假設為X（後續X為這個hashcode）。
②hashmap內部是有一個table數組+鏈表形成的。我們拿到這個X後，使用X/table.length(hashcode值/table[].length),得到一個小於table.length的值M，該值就是這個value應該放置的數組位置。我們准備把value放入table[M]中。
③我們把hashcode和value打包為一個node節點(為什麼需要這么打包後續會提到),准備存入table[M]中。
④出入table數組的鏈表中有2種方式：
前插方式：不管數組table[M]節點有值與否，都把這個准備插入的node節點作為數組的根節點。可能出現2種情況：
（1）如果table[M]節點沒有值，則node節點作為數組的根節點。
（2）如果table[M]節點已存在數據鏈表，就把這些數據灶含鏈表，鏈到這個准備插入的node節點上，以弄得節點為根節點放入table[M中]。
後插方式：可能會出現的2種情況
碼清 (1) 如果table[M]節點沒有值，則node節點作為數組的根節點。
（2）如果table[M]節點已存在數據鏈表，則把node節點鏈到該數據鏈表的最後一個節點上。
經歷以上4個步驟就完成了hashmap的插入操作，現在解釋一下為什麼要打包為node節點。
舉個栗子，假如hashmap.length=16,我們准備存入ObjectA(OA)和ObjectB(OB),假設OA經過hash運算得到的hashcode是1，OB經過hash運算得到hashcode是17，OA和OB進行求模運算結果都為1，鏈到鏈表上時，我們get方法的時候怎麼取到正確的值呢，因為鏈表上的模運算都是1.這個時候我們就需要通過hashcode來識別這個鏈表上隱模笑的哪個值是OA的value哪個是OB的value，因為我們已經把hashcode和value打包起來了。
補充
hashmap的table數組的大小事是2的次冪（不要問為什麼，源碼定的，他們肯定經過大量的統計或者運算，這是科學）。table數組默認的長度是16，也就是說你new一個空的hashmap長度為16，當然也提供了一個給你設置長度的方法，但是假如你設置17，則長度會為32，這不難理解。
hash碰撞
hash碰撞就是，假如OA、OB...ON經過模運算得到的數組位置相同，那麼他們都會掛在這個數組節點的鏈表上，極端情況想整個hashmap看起來像單鏈表。但這種情況這並不是我們想要的結果。我們可以通過擴容來盡可能的避免hash碰撞。
擴容 ：（意義，在於避免大量的hash碰撞，因為在某些極端情況下，有點像單鏈表）
閾值 ：閾值=table.length* DEFAULT_LOAD_FACTOR （擴容系數，默認為0.75，也可以自己設定，一般不做修改）
hashmap定義：當hashmap中的元素個數超過閾值大小時，我們就需要對table數組進行2倍擴容，如從16→32。
注意：擴容後hashmap會調用resize()，對hashmap內的數據重新計算所有元素的位置 。 。因為假如你之前17/16=1，現在17/32=17，你的位置發生變化了。
缺點 ：
hashMap因為有閾值的擴容機制，所以一定會有空間浪費，比如0.75的時候，一定有25%空間被浪費掉了。空間換時間。
hashmap是線程不安全的。因為可能在一個線程擴容（resize（）方法執行）的情況下,另外一個線程在get，但是拿不到之前的數據了，因為擴容。所以是線程不安全的。或者線程擴容（resize（）方法執行時，多線程進行put的時候導致的多線程數據不一致。
如何線程安全的使用HashMap?使用使用鎖分段技術或者使用HashTable(Hashtable的方法是Synchronize的，而HashMap不是,其實也就是鎖機制起作用)。
SparseArray（Android為了優化內存所提供的api）
特性：key為int,value為object，二分查找的思想，雙數組，刪除的時候節點不刪除，而是把value刪除，避免刪除的時候數組還要移動。
SparseArray比HashMap更省內存，在某些條件下性能更好，主要是因為它避免了對key的自動裝箱（int轉為Integer類型），它內部則是通過兩個數組來進行數據存儲的，一個存儲key，另外一個存儲value，為了優化性能，它內部對數據還採取了壓縮的方式來表示稀疏數組的數據，從而節約內存空間，我們從源碼中可以看到key和value分別是用數組表示。
為什麼是能夠進行二分查找呢？從源碼上看key和value分別是用int類型數組和object數組表示，所以這也是SparseArray的局限性。
private int[] mKeys;
private Object[] mValues;
為什麼說SparseArray比HashMap更省內存，在某些條件下性能更好？
因為SparseArray有以下一個特性，首先它是2個數組，在數據查找的時候無疑會比hashmap快很多，其次在刪除的時候，SparseArray並不會把數組key位置進行刪除，而是把key的索引value置位DELETE標志（這樣就避免了數組delete操作後的array的操作）。當我們下次進行插入的時候，若要插入的位置key的索引value為DELETE標志，則把數據覆蓋給value（只是經歷了set操作，並無其他操作）。否則進行add操作（包含array）。
所以經過以上的情況，我們可以看出，SparseArray相對於HashMap,會越用越快。
缺點
（1）SparseArray僅僅能存儲key為int類型的數據。
（2）插入操作需要復制數組，增刪效率降低 數據量巨大時，復制數組成本巨大，gc()成本也巨大。
（3）數據量巨大時，查詢效率也會明顯下降。
（4）線程不安全問題，類似hashmap
一般我們在滿足下面兩個條件我們可以使用SparseArray代替HashMap：
（1）數據量不大，最好在千級以內
（2）key必須為int類型，這中情況下的HashMap可以用SparseArray代替：
ArrayMap（Android為了優化內存所提供的api）
ArrayMap和SparseArray差不多，不同的是key類型可以是object類型。
ArrayMap的2個數組，一個數組記錄key的hash值，另外一個數組記錄Value值。其他存儲方式和運行思想和SparseArray一致。
線程不安全:hashmap、ArrayMap、SparseArray
⑼ 基於標記數據學習降低誤報率的演算法優化
基於標記數據學習降低誤報率的演算法優化
無論是基於規則匹配的策略，還是基於復雜的安全分析模型，安全設備產生的告警都存在大量誤報，這是一個相當普遍的問題。其中一個碼銀重要的原因是每個客戶的應用場景和數據都多多少少有不同的差異，基於固定判斷規則對有統計漲落的數據進行僵化的判斷，很容易出現誤判。
在沒有持續人工干預和手動優化的情況下，策略和模型的誤報率不會隨著數據的積累而有所改進。也就是說安全分析人員通過對告警打標簽的方式，可以將專業經驗傳授給智能演算法，自動得反饋到策略和模型當中，使之對安全事件做出更精準的判斷。本文介紹利用專家經驗持續優化機器學習的方法，對告警數據進行二次分析和學習，從而顯著地降低安全威脅告警的誤報率。
為了降低誤報率，當前大體上有兩種技術途徑：
根據不同客戶的各種特定情況修正策略和模型，提高策略或者模型的適應能力;
定期(如每月一次)對告警進入二次人工分析，根據分析結果來調整策略和模型的參數配置。
這兩種方法對降低誤報率都有一定的作用。但是第一種沒有自適應能力，是否有效果要看實際情況。第二種效果會好一些，但是非常耗時耗力，而且由於是人工現場干預和調整策略和模型，出錯的概率也非常高。
MIT的研究人員[1] 介紹了一種將安全分析人員標記後的告警日誌作為訓練數據集，令機器學習演算法學習專家經驗，使分析演算法持續得到優化，實現自動識別誤報告警睜模廳，降低誤報率的方法(以下簡稱「標簽傳遞經驗方法」)。這種把安全分析人員的專業悉隱智能轉化成演算法分析能力的過程，會讓分析演算法隨著數據的積累而更加精確。繼而逐漸擺脫人工干預，提高運維效率。如下圖所示：
下面我們通過基於「頻繁訪問安全威脅告警」模擬的場景數據來介紹一下實現機制。
什麼是頻繁訪問模型?邏輯比較簡單：一段時間內(比如1分鍾)，一個攻擊者對系統的訪問次數顯著高於普通訪問者的次數。此告警規則可以用簡單的基於閾值，或者是利用統計分布的離異概率。基於此，我們先模擬一些已經被安全分析人員打過標簽的告警數據。根據實際應用經驗，我們盡量模擬非常接近實際場景的數據。如下圖：
關於模擬數據的介紹：
總共模擬了20天的告警數據，從2017-01-01到2017-01-20。前10天的數據用來訓練模型，後10天的數據用來衡量模型的表現;
每個告警帶有是否誤報的標簽。紅色代表誤報，藍色代表准確告警。
關於模擬數據的假設：
誤報聚集在某個時間段，模擬數據假設的范圍是18:00-19:00。在安全運維實踐中，的確存在某個特定的時間段，由於業務邏輯或者系統原因導致誤報增多的現象。所以上述假設是合理的，告警時間可以作為有效的特徵值。但並不是所有的誤報都聚集在這個時間段，同時並不是這個時間段的所有告警都是誤報;
誤報大多來自於一批不同的IP。所以訪問來源IP也是有用的特徵值;
任何數據都不是完美的，所以在模擬數據中加入了~9%的噪音。也就是說再完美的智能模型，誤報率也不會低於9%。
這些假設在實際的應用場景中也是相對合理的。如果誤報是完全隨機產生的，那麼再智能的模型也不能夠捕捉到誤報的提出信號。所以這些合理的假設幫助我們模擬真實的數據，並且驗證我們的機器學習模型。
簡要模擬數據的代碼實現：
下圖顯示利用PCA降維分析的可視化結果，可以看到明顯的分類情況：
紅色代表誤報，藍色代表正確告警。基於設定特徵值的降維分析可以得到兩個聚集，即誤報和非誤報有明顯的區分的，也就是說誤報的是有一定規律，不是完全隨機的，因此是可以被機器學習捕捉到的。
簡要代碼實現：
基於模擬數據，我們想要達到的目的是通過持續的強化機器學習能夠降低誤報率。所以我們採取的策略是：
訓練一天的數據2017-01-01，測試10天的數據2017-01-11到2017-01-20;
訓練兩天的數據2017-01-01到2017-01-02，測試10天的數據2017-01-11到2017-01-20;
以此類推，來看通過學習越來越多的數據，在測試數據中的誤報率是否能夠得到不斷的改進。
簡要代碼如下：
此安全威脅場景相對簡單，我們不需要太多的特徵值和海量的數據，所以機器學習模型選擇了隨機森林(RandomForest)，我們也嘗試了其他復雜模型，得出的效果區別不大。測試結果如下：
達到我們所預期的效果，當訓練數據越來越多的時候，測試數據當中的誤報率從20%多降低到了10%。通過對告警數據和標簽的不斷自學習，可以剔除很多告警誤報。前面提到，數據當中引入了9%的噪音，所以誤報率不會再持續的降低。
在我們的機器學習模型當中，我們利用了4個主要的特徵值：
srcIP，訪問源IP
timeofday，告警產生的時間
visits，訪問次數
destIP，被訪問IP
下圖顯示了特徵值在模型中的重要性：
和我們的預期也是一致的，訪問源IP(srcIP)和告警發生的時間(timeofday)是區分出誤報告警效果最好的特徵值。
另外，由於隨機森林模型以及大部分機器學習模型都不支持分類變數(categoricalvariable)的學習，所以我們把srcIP和destIP這兩個特徵值做了二值化處理。簡要代碼如下：
總結
本文通過一組模擬實驗數據和隨機森林演算法，從理論上驗證了「標簽傳遞經驗方法」的有效性。即通過安全分析專家對告警日誌進行有效或誤報的標記，把專家的知識技能轉化成機器學習模型的分析能力。和其他方法相比，此方法在完成自動化學習之後就不再需要人工干預，而且會隨著數據的積累對誤報的剔除會更加精確。
⑽ 幾種常用最優化方法
學習和工作中遇到的大多問題都可以建模成一種最優化模型進行求解，比如我們現在學習的機器學習演算法，大部分的機器學習演算法的本質都是建立優化模型，通過最優化方法對目標函數（或損失函數）進行優化，從而訓練出最好的模型。常見的優化方法(optimization)有梯度下降法、牛頓法和擬牛頓法、共軛梯度法等等。
1. 梯度下降法（Gradient Descent）
梯度下降法是最早最簡單，也是最為常用的最優化方法。梯度下降法實現簡單，當目標函數是凸函數時，梯度下降法的解是全局解。一般情況下，其解不保證是全局最優解，梯度下降法的速度也未必是最快的。 梯度下降法的優化思想是用當前位置負梯度方向作為搜索方向，因為該方向為當前位置的最快下降方向，所以也被稱為是」最速下降法「。最速下降法越接近目標值，步長越小，前進越慢。
梯度下降 法的缺點：
（1）靠近極小值時收斂速度減慢;
（2）直線搜索時可能會產生一些問題；
（3）可能會「之字形」地下降。
在機器學習中，基於基本的梯度下降法發展了兩種梯度下降方法，分別為隨機梯度下降法和批量梯度下降法。
比如對一個線性回歸（Linear Logistics）模型，假設下面的h(x)是要擬合的函數，J( )為損失函數， 是參數，要迭代求解的值，求解出來了那最終要擬合的函數h( )就出來了。其中m是訓練集的樣本個數，n是特徵的個數。
1）批量梯度下降法（Batch Gradient Descent，BGD）
（1）將J( )對 求偏導，得到每個theta對應的的梯度：
(2）由於是要最小化風險函數，所以按每個參數 的梯度負方向，來更新每個 ：
（3）從上面公式可以注意到，它得到的是一個全局最優解，但是每迭代一步，都要用到訓練集所有的數據，如果m很大，那麼可想而知這種方法的迭代速度會相當的慢。所以，這就引入了另外一種方法——隨機梯度下降。
對於批量梯度下降法，樣本個數m，x為n維向量，一次迭代需要把m個樣本全部帶入計算，迭代一次計算量為m*n2。
2）隨機梯度下降（Stochastic Gradient Descent，SGD）
（1）上面的風險函數可以寫成如下這種形式，損失函數對應的是訓練集中每個樣本的粒度，而上面批量梯度下降對應的是所有的訓練樣本：
（2）每個樣本的損失函數，對 求偏導得到對應梯度，來更新 ：
（3）隨機梯度下降是通過每個樣本來迭代更新一次，如果樣本量很大的情況（例如幾十萬），那麼可能只用其中幾萬條或者幾千條的樣本，就已經將
迭代到最優解了，對比上面的批量梯度下降，迭代一次需要用到十幾萬訓練樣本，一次迭代不可能最優，如果迭代10次的話就需要遍歷訓練樣本10次。但是，SGD伴隨的一個問題是噪音較BGD要多，使得SGD並不是每次迭代都向著整體最優化方向。
隨機梯度下降每次迭代只使用一個樣本，迭代一次計算量為n2，當樣本個數m很大的時候，隨機梯度下降迭代一次的速度要遠高於批量梯度下降方法。 兩者的關系可以這樣理解：隨機梯度下降方法以損失很小的一部分精確度和增加一定數量的迭代次數為代價，換取了總體的優化效率的提升。增加的迭代次數遠遠小於樣本的數量。
對批量梯度下降法和隨機梯度下降法的總結：
批量梯度下降---最小化所有訓練樣本的損失函數，使得最終求解的是全局的最優解，即求解的參數是使得風險函數最小，但是對於大規模樣本問題效率低下。
隨機梯度下降---最小化每條樣本的損失函數，雖然不是每次迭代得到的損失函數都向著全局最優方向， 但是大的整體的方向是向全局最優解的，最終的結果往往是在全局最優解附近，適用於大規模訓練樣本情況。
2. 牛頓法和擬牛頓法（Newton's method & Quasi-Newton Methods）
1）牛頓法（Newton's method）
牛頓法是一種在實數域和復數域上近似求解方程的方法。方法使用函數 f ( x )的泰勒級數的前面幾項來尋找方程 f ( x ) = 0的根。牛頓法最大的特點就在於它的收斂速度很快。
具體步驟：
首先，選擇一個接近函數 f ( x )零點的x0，計算相應的 f ( x 0)和切線斜率 f ' ( x 0)（這里 f ' 表示函數 f 的導數）。然後我們計算穿過點( x 0, f ( x 0))並且斜率為 f '( x 0)的直線和 x 軸的交點的 x 坐標，也就是求如下方程的解：
我們將新求得的點的 x 坐標命名為 x 1，通常 x 1會比 x 0更接近方程 f ( x ) = 0的解。因此我們現在可以利用 x 1開始下一輪迭代。迭代公式可化簡為如下所示：
已經證明，如果 f '是連續的，並且待求的零點 x 是孤立的，那麼在零點 x 周圍存在一個區域，只要初始值 x 0位於這個鄰近區域內，那麼牛頓法必定收斂。 並且，如果 f ' ( x )不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。下圖為一個牛頓法執行過程的例子。
由於牛頓法是基於當前位置的切線來確定下一次的位置，所以牛頓法又被很形象地稱為是"切線法"。
關於牛頓法和梯度下降法的效率對比：
從本質上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部，梯度下降法每次只從你當前所處位置選一個坡度最大的方向走一步，牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之後，坡度是否會變得更大。所以，可以說牛頓法比梯度下降法看得更遠一點，能更快地走到最底部。（牛頓法目光更加長遠，所以少走彎路；相對而言，梯度下降法只考慮了局部的最優，沒有全局思想。）
根據wiki上的解釋，從幾何上說，牛頓法就是用一個二次曲面去擬合你當前所處位置的局部曲面，而梯度下降法是用一個平面去擬合當前的局部曲面，通常情況下，二次曲面的擬合會比平面更好，所以牛頓法選擇的下降路徑會更符合真實的最優下降路徑。
註：紅色的牛頓法的迭代路徑，綠色的是梯度下降法的迭代路徑。
牛頓法的優缺點總結：
優點：二階收斂，收斂速度快；
缺點：牛頓法是一種迭代演算法，每一步都需要求解目標函數的Hessian矩陣的逆矩陣，計算比較復雜。
2）擬牛頓法（Quasi-Newton Methods）
擬牛頓法是求解非線性優化問題最有效的方法之一，於20世紀50年代由美國Argonne國家實驗室的物理學家W.C.Davidon所提出來。Davidon設計的這種演算法在當時看來是非線性優化領域最具創造性的發明之一。不久R. Fletcher和M. J. D. Powell證實了這種新的演算法遠比其他方法快速和可靠，使得非線性優化這門學科在一夜之間突飛猛進。
擬牛頓法的本質思想是改善牛頓法每次需要求解復雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的復雜度。 擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法更為有效。如今，優化軟體中包含了大量的擬牛頓演算法用來解決無約束，約束，和大規模的優化問題。
具體步驟：
擬牛頓法的基本思想如下。首先構造目標函數在當前迭代xk的二次模型：
這里Bk是一個對稱正定矩陣，於是我們取這個二次模型的最優解作為搜索方向，並且得到新的迭代點：
其中我們要求步長ak 滿足Wolfe條件。這樣的迭代與牛頓法類似，區別就在於用近似的Hesse矩陣Bk 代替真實的Hesse矩陣。所以擬牛頓法最關鍵的地方就是每一步迭代中矩陣Bk的更新。現在假設得到一個新的迭代xk+1，並得到一個新的二次模型：
我們盡可能地利用上一步的信息來選取Bk。具體地，我們要求
從而得到
這個公式被稱為割線方程。常用的擬牛頓法有DFP演算法和BFGS演算法。
原文鏈接： [Math] 常見的幾種最優化方法 - Poll的筆記 - 博客園