分歧演算法原理圖

Ⅰ DES演算法實現

完成一個DES 演算法的 詳細設計 ,內容包括：

DES（Data Encryption Standard）是一種用於電子數據加密的對稱密鑰塊加密演算法 .它以64位為分組長度，64位一組的明文作為演算法的輸入，通過一系列復雜的操作，輸出同樣64位長度的密文。DES 同樣採用64位密鑰，但由於每8位中的最後1位用於奇偶校驗，實際有效密鑰長度為56位。密鑰可以是任意的56位的數，且可隨時改變。

DES 使用加密密鑰定義變換過程，因此演算法認為只有持有加密所用的密鑰的用戶才能解密密文。DES的兩個重要的安全特性是混淆和擴散。其中 混淆 是指通過密碼演算法使明文和密文以及密鑰的關系非常復雜，無法從數學上描述或者統計。 擴散 是指明文和密鑰中的每一位信息的變動，都會影響到密文中許多位信息的變動，從而隱藏統計上的特性，增加密碼的安全。

DES演算法的基本過程是換位和置換。如圖，有16個相同的處理階段，稱為輪。還有一個初始和最終的排列，稱為 IP 和 FP，它們是反向的 (IP 取消 FP 的作用，反之亦然)。

在主輪之前，塊被分成兩個32位的一半和交替處理；這種縱橫交錯的方案被稱為Feistel 方法。Feistel 結構確保了解密和加密是非常相似的過程——唯一的區別是在解密時子鍵的應用順序是相反的。其餘的演算法是相同的。這大大簡化了實現，特別是在硬體中，因為不需要單獨的加密和解密演算法。

符號表示異或（XOR）操作。Feistel 函數將半塊和一些鍵合在一起。然後，將Feistel 函數的輸出與塊的另一半組合在一起，在下一輪之前交換這一半。在最後一輪之後，兩隊交換了位置；這是 Feistel 結構的一個特性，使加密和解密過程類似。

IP 置換表指定64位塊上的輸入排列。其含義如下：輸出的第一個比特來自輸入的第58位;第二個位來自第50位，以此類推，最後一個位來自第7位輸入。

最後的排列是初始排列的倒數。

展開函數被解釋為初始排列和最終排列。注意，輸入的一些位在輸出時是重復的;輸入的第5位在輸出的第6位和第8位中都是重復的。因此，32位半塊被擴展到48位。

P排列打亂了32位半塊的位元。

表的「左」和「右」部分顯示了來自輸入鍵的哪些位構成了鍵調度狀態的左和右部分。輸入的64位中只有56位被選中；剩下的8（8、16、24、32、40、48、56、64）被指定作為奇偶校驗位使用。

這個排列從56位鍵調度狀態為每輪選擇48位的子鍵。

這個表列出了DES中使用的8個S-box，每個S-box用4位的輸出替換6位的輸入。給定一個6位輸入，通過使用外部的兩個位選擇行，以及使用內部的四個位選擇列，就可以找到4位輸出。例如，一個輸入「011011」有外部位「01」和內部位「1101」。第一行為「00」，第一列為「0000」，S-box S5對應的輸出為「1001」(=9)，即第二行第14列的值。

DES演算法的基本流程圖如下：

DES演算法是典型的對稱加密演算法，在輸入64比特明文數據後，通過輸入64比特密鑰和演算法的一系列加密步驟後，可以得到同樣為64比特的密文數據。反之，我們通過已知的密鑰，可以將密文數據轉換回明文。 我們將演算法分為了三大塊：IP置換、16次T迭代和IP逆置換 ，加密和解密過程分別如下：

實驗的設計模式是自頂向下的結構，用C語言去分別是先各個函數的功能，最後通過主函數將所有函數進行整合，讓演算法更加清晰客觀。

通過IP置換表，根據表中所示下標，找到相應位置進行置換。

對於16次 迭代，我們先將傳入的經過 IP 混淆過的64位明文的左右兩部分，分別為32位的 和32位的 。之後我們將 和 進行交換，得到作為IP逆置換的輸入：

，

子密鑰的生成，經歷下面一系列步驟：首先對於64位密鑰，進行置換選擇，因為將用戶輸入的64 位經歷壓縮變成了56位，所以我們將左面和右面的各28位進行循環位移。左右兩部分分別按下列規則做循環移位：當 ，循環左移1位；其餘情況循環左移2位。最後將得到的新的左右兩部分進行連接得到56位密鑰。

對半塊的 Feistel 操作分為以下五步：

如上二圖表明，在給出正確的密碼後，可以得到對應的明文。

若密碼錯誤，將解碼出錯誤答案。

【1】 Data Encryption Standard

【2】 DES演算法的詳細設計（簡單實現）

【3】 深入理解並實現DES演算法

【4】 DES演算法原理完整版

【5】 安全體系（一）—— DES演算法詳解

Ⅱ DBSCAN原理是怎麼樣的

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚類演算法，它是一種基於高密度連通區域的、基於密度的聚類演算法，能夠將具有足夠高密度的區域劃分為簇，並在具有雜訊的數據中發現任意形狀的簇。我們總結一下DBSCAN聚類演算法原理的基本要點：
DBSCAN演算法需要選擇一種距離度量，對於待聚類的數據集中，任意兩個點之間的距離，反映了點之間的密度，說明了點與點是否能夠聚到同一類中。由於DBSCAN演算法對高維數據定義密度很困難，所以對於二維空間中的點，可以使用歐幾里德距離來進行度量。
DBSCAN演算法需要用戶輸入2個參數：一個參數是半徑（Eps），表示以給定點P為中心的圓形鄰域的范圍；另一個參數是以點P為中心的鄰域內最少點的數量（MinPts）。如果滿足：以點P為中心、半徑為Eps的鄰域內的點的個數不少於MinPts，則稱點P為核心點。
DBSCAN聚類使用到一個k-距離的概念，k-距離是指：給定數據集P={p(i); i=0,1,…n}，對於任意點P(i)，計算點P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有點之間的距離，距離按照從小到大的順序排序，假設排序後的距離集合為D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}，則d(k)就被稱為k-距離。也就是說，k-距離是點p(i)到所有點（除了p(i)點）之間距離第k近的距離。對待聚類集合中每個點p(i)都計算k-距離，最後得到所有點的k-距離集合E={e(1), e(2), …, e(n)}。
根據經驗計算半徑Eps：根據得到的所有點的k-距離集合E，對集合E進行升序排序後得到k-距離集合E』，需要擬合一條排序後的E』集合中k-距離的變化曲線圖，然後繪出曲線，通過觀察，將急劇發生變化的位置所對應的k-距離的值，確定為半徑Eps的值。
根據經驗計算最少點的數量MinPts：確定MinPts的大小，實際上也是確定k-距離中k的值，DBSCAN演算法取k=4，則MinPts=4。
另外，如果覺得經驗值聚類的結果不滿意，可以適當調整Eps和MinPts的值，經過多次迭代計算對比，選擇最合適的參數值。可以看出，如果MinPts不變，Eps取得值過大，會導致大多數點都聚到同一個簇中，Eps過小，會導致已一個簇的分裂；如果Eps不變，MinPts的值取得過大，會導致同一個簇中點被標記為雜訊點，MinPts過小，會導致發現大量的核心點。
DBSCAN演算法，需要輸入2個參數，這兩個參數的計算都來自經驗知識。半徑Eps的計算依賴於計算k-距離，DBSCAN取k=4，也就是設置MinPts=4，然後需要根據k-距離曲線，根據經驗觀察找到合適的半徑Eps的值，下面的演算法實現過程中，我們會詳細說明。對於演算法的實現，首先我們概要地描述一下實現的過程：
1）解析樣本數據文件。
2）計算每個點與其他所有點之間的歐幾里德距離。
3）計算每個點的k-距離值，並對所有點的k-距離集合進行升序排序，輸出的排序後的k-距離值。
4）將所有點的k-距離值，在Excel中用散點圖顯示k-距離變化趨勢。
5）根據散點圖確定半徑Eps的值。）根據給定MinPts=4，以及半徑Eps的值，計算所有核心點，並建立核心點與到核心點距離小於半徑Eps的點的映射。
6）根據得到的核心點集合，以及半徑Eps的值，計算能夠連通的核心點，得到雜訊點。
7）將能夠連通的每一組核心點，以及到核心點距離小於半徑Eps的點，都放到一起，形成一個簇。
8）選擇不同的半徑Eps，使用DBSCAN演算法聚類得到的一組簇及其雜訊點，使用散點圖對比聚類效果。

Ⅲ 線性回歸演算法原理（越詳細越好）

線性回歸是利用數理統計中的回歸分析，來確定兩種或兩種以上變數間相互依賴的定量關系的一種統計分析方法之一，運用十分廣泛。

分析按照自變數和因變數之間的關系類型，可分為線性回歸分析和非線性回歸分析。

如果在回歸分析中，只包括一個自變數和一個因變數，且二者的關系可用一條直線近似表示，這種回歸分析稱為一元線性回歸分析。如果回歸分析中包括兩個或兩個以上的自變數，且因變數和自變數之間是線性關系，則稱為多元線性回歸分析。

我們以一簡單數據組來說明什麼是線性回歸。假設有一組數據型態為y=y(x)，其中

x={0,1,2,3,4,5},y={0,20,60,68,77,110}

如果我們要以一個最簡單的方程式來近似這組數據，則非一階的線性方程式莫屬。先將這組數據繪圖如下

圖中的斜線是我們隨意假設一階線性方程式y=20x，用以代表這些數據的一個方程式。以下將上述繪圖的MATLAB指令列出，並計算這個線性方程式的y值與原數據y值間誤差平方的總合。

>>x=[012345];

>>y=[020606877110];

>>y1=20*x;%一階線性方程式的y1值

>>sum_sq=sum(y-y1).^2);%誤差平方總合為573

>>axis([-1,6,-20,120])

>>plot(x,y1,x,y,'o'),title('Linearestimate'),grid

如此任意的假設一個線性方程式並無根據，如果換成其它人來設定就可能採用不同的線性方程式；所以我們須要有比較精確方式決定理想的線性方程式。我們可以要求誤差平方的總合為最小，做為決定理想的線性方程式的准則，這樣的方法就稱為最小平方誤差(leastsquareserror)或是線性回歸。MATLAB的polyfit函數提供了從一階到高階多項式的回歸法，其語法為polyfit(x,y,n)，其中x,y為輸入數據組n為多項式的階數，n=1就是一階的線性回歸法。polyfit函數所建立的多項式可以寫成

從polyfit函數得到的輸出值就是上述的各項系數，以一階線性回歸為例n=1，所以只有二個輸出值。如果指令為coef=polyfit(x,y,n)，則coef(1)=,coef(2)=,...,coef(n+1)=。注意上式對n階的多項式會有n+1項的系數。我們來看以下的線性回歸的示範：

>>x=[012345];

>>y=[020606877110];

>>coef=polyfit(x,y,1);%coef代表線性回歸的二個輸出值

>>a0=coef(1);a1=coef(2);

>>ybest=a0*x+a1;%由線性回歸產生的一階方程式

>>sum_sq=sum(y-ybest).^2);%誤差平方總合為356.82

>>axis([-1,6,-20,120])

>>plot(x,ybest,x,y,'o'),title('Linearregressionestimate'),grid

[編輯本段]線性回歸擬合方程

一般來說，線性回歸都可以通過最小二乘法求出其方程，可以計算出對於y=bx+a的直線，其經驗擬合方程如下：

Ⅳ 常見密碼演算法原理

PBKDF2(Password-Based Key Derivation Function)是一個用來導出密鑰的函數，用來生成加密的密碼，增加破解的難度，類似bcrypt/scrypt等，可以用來進行密碼或者口令的加密存儲。主要是鹽值+pwd，經過多輪HMAC演算法的計算，產生的密文。
PBKDF2函數的定義
DK = PBKDF2(PRF, Password, Salt, c, dkLen)
• PRF是一個偽隨機函數，例如HASH_HMAC函數，它會輸出長度為hLen的結果。
• Password是用來生成密鑰的原文密碼。
• Salt是一個加密用的鹽值。
• c是進行重復計算的次數。
• dkLen是期望得到的密鑰的長度。
• DK是最後產生的密鑰。
https://segmentfault.com/a/1190000004261009

下面我們以Alice和Bob為例敘述Diffie-Hellman密鑰交換的原理。
1,Diffie-Hellman交換過程中涉及到的所有參與者定義一個組，在這個組中定義一個大質數p，底數g。
2,Diffie-Hellman密鑰交換是一個兩部分的過程，Alice和Bob都需要一個私有的數字a，b。
下面是DH交換的過程圖：
本圖片來自wiki
下面我們進行一個實例
1.愛麗絲與鮑伯協定使用p=23以及g=5.
2.愛麗絲選擇一個秘密整數a=6, 計算A = g^a mod p並發送給鮑伯。
A = 5^6 mod 23 = 8.
3.鮑伯選擇一個秘密整數b=15, 計算B = g^b mod p並發送給愛麗絲。
B = 5^15 mod 23 = 19.
4.愛麗絲計算s = B a mod p
19^6 mod 23 = 2.
5.鮑伯計算s = A b mod p
8^15 mod 23 = 2.

ECDH:
ECC演算法和DH結合使用，用於密鑰磋商，這個密鑰交換演算法稱為ECDH。交換雙方可以在不共享任何秘密的情況下協商出一個密鑰。ECC是建立在基於橢圓曲線的離散對數問題上的密碼體制，給定橢圓曲線上的一個點P，一個整數k，求解Q=kP很容易；給定一個點P、Q，知道Q=kP，求整數k確是一個難題。ECDH即建立在此數學難題之上。密鑰磋商過程：
假設密鑰交換雙方為Alice、Bob，其有共享曲線參數（橢圓曲線E、階N、基點G）。

來自 http://www.cnblogs.com/fishou/p/4206451.html

https://zh.wikipedia.org/wiki/SHA%E5%AE%B6%E6%97%8F

exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
-----END RSA PRIVATE KEY-----
while a RSA public key contains only the following data:
-----BEGIN RSA PUBLIC KEY-----
RSAPublicKey ::= SEQUENCE {
molus INTEGER, -- n
publicExponent INTEGER -- e
}
-----END RSA PUBLIC KEY-----
and this explains why the private key block is larger.
Note that a more standard format for non-RSA public keys is
-----BEGIN PUBLIC KEY-----
PublicKeyInfo ::= SEQUENCE {
algorithm AlgorithmIdentifier,
PublicKey BIT STRING
}
AlgorithmIdentifier ::= SEQUENCE {
algorithm OBJECT IDENTIFIER,
parameters ANY DEFINED BY algorithm OPTIONAL
}
-----END PUBLIC KEY-----
More info here.
BTW, since you just posted a screenshot of the private key I strongly hope it was just for tests :)

密鑰的長度
C:\herong>java RsaKeyGenerator 128
p: 17902136406704537069
q: 17902136406704537077
m:
Molus:
Key size: 128
Public key:
Private key:
C:\herong>java RsaKeyGenerator 256
p:
q:
m: ...
Molus: ...
Key size: 256
Public key: ...
Private key: ...

https://security.stackexchange.com/questions/90169/rsa-public-key-and-private-key-lengths
https://stackoverflow.com/questions/2921508/trying-to-understand-java-rsa-key-size >

http://www.herongyang.com/Cryptography/RSA-BigInteger-Keys-Generated-by-RsaKeyGenerator-java.html

update() adds data to the Cipher』s internal buffer, then returns all currently completely encoded blocks. If there are any encoded blocks left over, they remain in the Cipher』s buffer until the next call, or a call to doFinal(). This means that if you call update() with a four byte array to encrypt, and the buffer size is eight bytes, you will not receive encoded data on the return (you』ll get a null instead). If your next call to update() passes five bytes of data in, you will get an 8 byte (the block size) array back, containing the four bytes passed in on the previous call, the first four bytes from the current call – the remaining byte from the current call is left in the Cipher』s buffer.
doFinal() on the other hand is much simpler: it encrypts the passed data, pads it out to the necessary length, and then returns it. The Cipher is essentially stateless.

來自 https://segmentfault.com/a/1190000006931511

DH演算法的中間人攻擊
在最初的描述中，迪菲－赫爾曼密鑰交換本身並沒有提供通訊雙方的身份驗證服務，因此它很容易受到中間人攻擊。 一個中間人在信道的中央進行兩次迪菲－赫爾曼密鑰交換，一次和Alice另一次和Bob，就能夠成功的向Alice假裝自己是Bob，反之亦然。而攻擊者可以解密（讀取和存儲）任何一個人的信息並重新加密信息，然後傳遞給另一個人。因此通常都需要一個能夠驗證通訊雙方身份的機制來防止這類攻擊。

優缺點：
1、 僅當需要時才生成密鑰，減小了將密鑰存儲很長一段時間而致使遭受攻擊的機會。
2、 除對全局參數的約定外，密鑰交換不需要事先存在的基礎結構。
然而，該技術也存在許多不足：
1、 沒有提供雙方身份的任何信息。
2、 它是計算密集性的，因此容易遭受阻塞性攻擊，即對手請求大量的密鑰。受攻擊者花費了相對多的計算資源來求解無用的冪系數而不是在做真正的工作。
3、 沒辦法防止重演攻擊。
4、 容易遭受中間人的攻擊。第三方C在和A通信時扮演B；和B通信時扮演A。A和B都與C協商了一個密鑰，然後C就可以監聽和傳遞通信量。中間人的攻擊按如下進行：
（1） B在給A的報文中發送他的公開密鑰。
（2） C截獲並解析該報文。C將B的公開密鑰保存下來並給A發送報文，該報文具有B的用戶ID但使用C的公開密鑰YC，仍按照好像是來自B的樣子被發送出去。A收到C的報文後，將YC和B的用戶ID存儲在一塊。類似地，C使用YC向B發送好像來自A的報文。
（3） B基於私有密鑰XB和YC計算秘密密鑰K1。A基於私有密鑰XA和YC計算秘密密鑰K2。C使用私有密鑰XC和YB計算K1，並使用XC和YA計算K2。
（4） 從現在開始，C就可以轉發A發給B的報文或轉發B發給A的報文，在途中根據需要修改它們的密文。使得A和B都不知道他們在和C共享通信。

Ⅳ 決策樹演算法-原理篇

關於決策樹演算法，我打算分兩篇來講，一篇講思想原理，另一篇直接擼碼來分析演算法。本篇為原理篇。
通過閱讀這篇文章，你可以學到：
1、決策樹的本質
2、決策樹的構造過程
3、決策樹的優化方向

決策樹根據使用目的分為：分類樹和回歸樹，其本質上是一樣的。本文只講分類樹。

決策樹，根據名字來解釋就是，使用樹型結構來模擬決策。
用圖形表示就是下面這樣。

其中橢圓形代表：特徵或屬性。長方形代表：類別結果。
面對一堆數據（含有特徵和類別），決策樹就是根據這些特徵（橢圓形）來給數據歸類（長方形）
例如，信用貸款問題，我根據《神奇動物在哪裡》的劇情給銀行造了個決策樹模型，如下圖：

然而，決定是否貸款可以根據很多特徵，然麻雞銀行選擇了：（1）是否房產價值>100w；（2）是否有其他值錢的抵押物；（3）月收入>10k；（4）是否結婚；這四個特徵，來決定是否給予貸款。
先不管是否合理，但可以肯定的是，決策樹做了特徵選擇工作，即選擇出類別區分度高的特徵。

由此可見， 決策樹其實是一種特徵選擇方法。 （特徵選擇有多種，決策樹屬於嵌入型特徵選擇，以後或許會講到，先給個圖）即選擇區分度高的特徵子集。

那麼， 從特徵選擇角度來看決策樹，決策樹就是嵌入型特徵選擇技術

同時，決策樹也是機器學習中經典分類器演算法，通過決策路徑，最終能確定實例屬於哪一類別。
那麼， 從分類器角度來看決策樹，決策樹就是樹型結構的分類模型

從人工智慧知識表示法角度來看，決策樹類似於if-then的產生式表示法。
那麼， 從知識表示角度來看決策樹，決策樹就是if-then規則的集合

由上面的例子可知，麻雞銀行通過決策樹模型來決定給哪些人貸款，這樣決定貸款的流程就是固定的，而不由人的主觀情感來決定。
那麼， 從使用者角度來看決策樹，決策樹就是規范流程的方法

最後我們再來看看決策樹的本質是什麼已經不重要了。
決策樹好像是一種思想，而通過應用在分類任務中從而成就了「決策樹演算法」。

下面內容還是繼續講解用於分類的「決策樹演算法」。

前面講了決策樹是一種 特徵選擇技術 。

既然決策樹就是一種特徵選擇的方法，那麼經典決策樹演算法其實就是使用了不同的特徵選擇方案。
如：
（1）ID3：使用信息增益作為特徵選擇
（2）C4.5：使用信息增益率作為特徵選擇
（3）CART：使用GINI系數作為特徵選擇
具體選擇的方法網上一大把，在這里我提供幾個鏈接，不細講。

但，不僅僅如此。
決策樹作為嵌入型特徵選擇技術結合了特徵選擇和分類演算法，根據特徵選擇如何生成分類模型也是決策樹的一部分。
其生成過程基本如下：

根據這三個步驟，可以確定決策樹由：（1）特徵選擇；（2）生成方法；（3）剪枝，組成。
決策樹中學習演算法與特徵選擇的關系如下圖所示：

原始特徵集合T：就是包含收集到的原始數據所有的特徵，例如：麻瓜銀行收集到與是否具有償還能力的所有特徵，如：是否結婚、是否擁有100w的房產、是否擁有汽車、是否有小孩、月收入是否>10k等等。
中間的虛線框就是特徵選擇過程，例如：ID3使用信息增益、C4.5使用信息增益率、CART使用GINI系數。
其中評價指標（如：信息增益）就是對特徵的要求，特徵需要滿足這種條件（一般是某個閾值），才能被選擇，而這一選擇過程嵌入在學習演算法中，最終被選擇的特徵子集也歸到學習演算法中去。
這就是抽象的決策樹生成過程，不論哪種演算法都是將這一抽象過程的具體化。
其具體演算法我將留在下一篇文章來講解。

而決策樹的剪枝，其實用得不是很多，因為很多情況下隨機森林能解決決策樹帶來的過擬合問題，因此在這里也不講了。

決策樹的優化主要也是圍繞決策樹生成過程的三個步驟來進行優化的。
樹型結構，可想而知，演算法效率決定於樹的深度，優化這方面主要從特徵選擇方向上優化。
提高分類性能是最重要的優化目標，其主要也是特徵選擇。
面對過擬合問題，一般使用剪枝來優化，如：李國和基於決策樹生成及剪枝的數據集優化及其應用。
同時，決策樹有很多不足，如：多值偏向、計算效率低下、對數據空缺較為敏感等，這方面的優化也有很多，大部分也是特徵選擇方向，如：陳沛玲使用粗糙集進行特徵降維。
由此，決策樹的優化方向大多都是特徵選擇方向，像ID3、C4.5、CART都是基於特徵選擇進行優化。

參考文獻
統計學習方法-李航
特徵選擇方法綜述-李郅琴
決策樹分類演算法優化研究_陳沛玲
基於決策樹生成及剪枝的數據集優化及其應用-李國和

Ⅵ 大數據演算法：分類演算法

KNN演算法，即K近鄰（K Nearest Neighbour）演算法，是一種基本的分類演算法。其主要原理是：對於一個需要分類的數據，將其和一組已經分類標注好的樣本集合進行比較，得到距離最近的K個樣本，K個樣本最多歸屬的類別，就是這個需要分類數據的類別。下面我給你畫了一個KNN演算法的原理圖。

圖中，紅藍綠三種顏色的點為樣本數據，分屬三種類別 、 、 。對於待分類點 ，計算和它距離最近的5個點（即K為5），這5個點最多歸屬的類別為 （4個點歸屬 ，1個點歸屬 ），那麼 的類別被分類為 。

KNN的演算法流程也非常簡單，請看下面的流程圖。

KNN演算法是一種非常簡單實用的分類演算法，可用於各種分類的場景，比如新聞分類、商品分類等，甚至可用於簡單的文字識別。對於新聞分類，可以提前對若干新聞進行人工標注，標好新聞類別，計算好特徵向量。對於一篇未分類的新聞，計算其特徵向量後，跟所有已標注新聞進行距離計算，然後進一步利用KNN演算法進行自動分類。

讀到這你肯定會問，如何計算數據的距離呢？如何獲得新聞的特徵向量呢？

KNN演算法的關鍵是要比較需要分類的數據與樣本數據之間的距離，這在機器學習中通常的做法是：提取數據的特徵值，根據特徵值組成一個n維實數向量空間（這個空間也被稱作特徵空間），然後計算向量之間的空間距離。空間之間的距離計算方法有很多種，常用的有歐氏距離、餘弦距離等。

對於數據 和 ，若其特徵空間為n維實數向量空間 ，即 ， ，則其歐氏距離計算公式為

這個歐式距離公式其實我們在初中的時候就學過，平面幾何和立體幾何里兩個點之間的距離，也是用這個公式計算出來的，只是平面幾何（二維幾何）里的n=2，立體幾何（三維幾何）里的n=3，而機器學習需要面對的每個數據都可能有n維的維度，即每個數據有n個特徵值。但是不管特徵值n是多少，兩個數據之間的空間距離的計算公式還是這個歐氏計算公式。大多數機器學習演算法都需要計算數據之間的距離，因此掌握數據的距離計算公式是掌握機器學習演算法的基礎。

歐氏距離是最常用的數據計算公式，但是在文本數據以及用戶評價數據的機器學習中，更常用的距離計算方法是餘弦相似度。

餘弦相似度的值越接近1表示其越相似，越接近0表示其差異越大，使用餘弦相似度可以消除數據的某些冗餘信息，某些情況下更貼近數據的本質。我舉個簡單的例子，比如兩篇文章的特徵值都是：「大數據」「機器學習」和「極客時間」，A文章的特徵向量為（3, 3, 3），即這三個詞出現次數都是3；B文章的特徵向量為（6, 6, 6），即這三個詞出現次數都是6。如果光看特徵向量，這兩個向量差別很大，如果用歐氏距離計算確實也很大，但是這兩篇文章其實非常相似，只是篇幅不同而已，它們的餘弦相似度為1，表示非常相似。

餘弦相似度其實是計算向量的夾角，而歐氏距離公式是計算空間距離。餘弦相似度更關注數據的相似性，比如兩個用戶給兩件商品的打分分別是（3, 3）和（4, 4），那麼兩個用戶對兩件商品的喜好是相似的，這種情況下，餘弦相似度比歐氏距離更合理。

我們知道了機器學習的演算法需要計算距離，而計算距離需要還知道數據的特徵向量，因此提取數據的特徵向量是機器學習工程師們的重要工作，有時候甚至是最重要的工作。不同的數據以及不同的應用場景需要提取不同的特徵值，我們以比較常見的文本數據為例，看看如何提取文本特徵向量。

文本數據的特徵值就是提取文本關鍵詞，TF-IDF演算法是比較常用且直觀的一種文本關鍵詞提取演算法。這種演算法是由TF和IDF兩部分構成。

TF是詞頻（Term Frequency），表示某個單詞在文檔中出現的頻率，一個單詞在一個文檔中出現的越頻繁，TF值越高。

詞頻：

IDF是逆文檔頻率（Inverse Document Frequency），表示這個單詞在所有文檔中的稀缺程度，越少文檔出現這個詞，IDF值越高。

逆文檔頻率：

TF與IDF的乘積就是TF-IDF。

所以如果一個詞在某一個文檔中頻繁出現，但在所有文檔中卻很少出現，那麼這個詞很可能就是這個文檔的關鍵詞。比如一篇關於原子能的技術文章，「核裂變」「放射性」「半衰期」等詞彙會在這篇文檔中頻繁出現，即TF很高；但是在所有文檔中出現的頻率卻比較低，即IDF也比較高。因此這幾個詞的TF-IDF值就會很高，就可能是這篇文檔的關鍵詞。如果這是一篇關於中國原子能的文章，也許「中國」這個詞也會頻繁出現，即TF也很高，但是「中國」也在很多文檔中出現，那麼IDF就會比較低，最後「中國」這個詞的TF-IDF就很低，不會成為這個文檔的關鍵詞。

提取出關鍵詞以後，就可以利用關鍵詞的詞頻構造特徵向量，比如上面例子關於原子能的文章，「核裂變」「放射性」「半衰期」這三個詞是特徵值，分別出現次數為12、9、4。那麼這篇文章的特徵向量就是（12, 9, 4），再利用前面提到的空間距離計算公式計算與其他文檔的距離，結合KNN演算法就可以實現文檔的自動分類。

貝葉斯公式是一種基於條件概率的分類演算法，如果我們已經知道A和B的發生概率，並且知道了B發生情況下A發生的概率，可以用貝葉斯公式計算A發生的情況下B發生的概率。事實上，我們可以根據A的情況，即輸入數據，判斷B的概率，即B的可能性，進而進行分類。

舉個例子：假設一所學校里男生佔60%，女生佔40%。男生總是穿長褲，女生則一半穿長褲一半穿裙子。假設你走在校園中，迎面走來一個穿長褲的學生，你能夠推斷出這個穿長褲學生是男生的概率是多少嗎？

答案是75%，具體演算法是：

這個演算法就利用了貝葉斯公式，貝葉斯公式的寫法是：

意思是A發生的條件下B發生的概率，等於B發生的條件下A發生的概率，乘以B發生的概率，除以A發生的概率。還是上面這個例子，如果我問你迎面走來穿裙子的學生是女生的概率是多少。同樣帶入貝葉斯公式，可以計算出是女生的概率為100%。其實這個結果我們根據常識也能推斷出來，但是很多時候，常識受各種因素的干擾，會出現偏差。比如有人看到一篇博士生給初中學歷老闆打工的新聞，就感嘆讀書無用。事實上，只是少見多怪，樣本量太少而已。而大量數據的統計規律則能准確反映事物的分類概率。

貝葉斯分類的一個典型的應用場合是垃圾郵件分類，通過對樣本郵件的統計，我們知道每個詞在郵件中出現的概率 ，我們也知道正常郵件概率 和垃圾郵件的概率 ，還可以統計出垃圾郵件中各個詞的出現概率 ，那麼現在一封新郵件到來，我們就可以根據郵件中出現的詞，計算 ，即得到這些詞出現情況下，郵件為垃圾郵件的概率，進而判斷郵件是否為垃圾郵件。

現實中，貝葉斯公式等號右邊的概率，我們可以通過對大數據的統計獲得，當有新的數據到來的時候，我們就可以帶入上面的貝葉斯公式計算其概率。而如果我們設定概率超過某個值就認為其會發生，那麼我們就對這個數據進行了分類和預測，具體過程如下圖所示。

訓練樣本就是我們的原始數據，有時候原始數據並不包含我們想要計算的維度數據，比如我們想用貝葉斯公式自動分類垃圾郵件，那麼首先要對原始郵件進行標注，需要標注哪些郵件是正常郵件、哪些郵件是垃圾郵件。這一類需要對數據進行標注才能進行的機器學習訓練也叫作有監督的機器學習。

Ⅶ 計算機視覺——典型的目標檢測演算法(OverFeat演算法)（二）

【嵌牛導讀】目標檢測在現實中的應用很廣泛，我們需要檢測數字圖像中的物體位置以及類別，它需要我們構建一個模型，模型的輸入一張圖片，模型的輸出需要圈出圖片中所有物體的位置以及物體所屬的類別。在深度學習浪潮到來之前，目標檢測精度的進步十分緩慢，靠傳統依靠手工特徵的方法來提高精度已是相當困難的事。而ImageNet分類大賽出現的卷積神經網路（CNN）——AlexNet所展現的強大性能，吸引著學者們將CNN遷移到了其他的任務，這也包括著目標檢測任務，近年來，出現了很多目標檢測演算法。

【嵌牛鼻子】計算機視覺

【嵌牛提問】如何理解目標檢測演算法——OverFeat

【嵌牛正文】

一、深度學習的典型目標檢測演算法

深度學習目標檢測演算法主要分為 雙階段檢測演算法 和 單階段檢測演算法 ，如圖1所示。

雙階段目標檢測演算法先對圖像提取候選框，然後基於候選區域做二次修正得到檢測結果，檢測精度較高，但檢測速度較慢;單階段目標驗測演算法直接對圖像進行計算生成檢測結果，檢測速度快,但檢測精度低。

1、雙階段目標檢測演算法

雙階段目標檢測方法主要通過選擇性搜索（Selective Search）或者Edge Boxes等演算法對輸入圖像選取可能包含檢測目標的候選區域（Region Proposal），再對候選區域進行分類和位置回歸以得到檢測結果。

1.1 OverFeat 演算法

《OverFeat: Integrated Recognition, Localization and Detection using Convolutional Networks》

Sermanet 等改進AlexNet 提出 OverFeat 演算法。該演算法結合AlexNet通過多尺度滑動窗口實現特徵提取功能，並且共享特徵提取層，應用於圖像分類、定位和目標檢測等任務。

關鍵技術：

1、FCN（ 全卷積神經網路 ）

對於一個各層參數結構都設計好的網路模型，要求輸入圖片的尺寸是固定的（例如，Alexnet要求輸入圖片的尺寸為227px*227px）。如果輸入一張500*500的圖片，希望模型仍然可以一直前向傳導，即一個已經設計完畢的網路，可以輸入任意大小的圖片，這就是FCN。

FCN的思想在於：

1、從卷積層到全連接層，看成是對一整張圖片的卷積層運算。

2、從全連接層到全連接層，看成是採用1*1大小的卷積核，進行卷積層運算。

如上圖所示，綠色部分代表卷積核大小。假設一個CNN模型，其輸入圖片大小是14*14，通過第一層卷積後得到10*10大小的圖片，然後接著通過池化得到了5*5大小的圖片。像但是對於像素值為5*5的圖片到像素值為1*1的圖片的過程中：

（1）傳統的CNN：如果從以前的角度進行理解的話，那麼這個過程就是全連接層，我們會把這個5*5大小的圖片，展平成為一維向量進行計算。

（2）FCN：FCN並不是把5*5的圖片展平成一維向量再進行計算，而是直接採用5*5的卷積核，對一整張圖片進行卷積運算。

二者本質上是相同的，只是角度不同，FCN把這個過程當成了對一整張特徵圖進行卷積，同樣，後面的全連接層也是把它當做是以1*1大小的卷積核進行卷積運算。

當輸入一張任意大小的圖片，就需要利用以上所述的網路，例如輸入一張像素為16*16的圖片：

根據上圖，該網路最後的輸出是一張2*2的圖片。可見採用FCN網路可以輸入任意大小的圖片。同時需要注意的是網路最後輸出的圖片大小不在是一個1*1大小的圖片，而是一個與輸入圖片大小息息相關的一張圖片。

Overfeat就是把採用FCN的思想把全連接層看成了卷積層，在網路測試階段可以輸入任意大小的圖片。

2、offset max-pooling

簡單起見，不用二維的圖像作為例子，而是採用一維作為示例：

如上圖所示，在X軸上有20個神經元，並且選擇池化size=3的非重疊池化，那麼根據之前所學的方法應該是：對上面的20個神經元，從1位置開始進行分組，每3個連續的神經元為一組，然後計算每組的最大值(最大池化)，19、20號神經元將被丟棄，如下圖所示：

或者可以在20號神經元後面，添加一個數值為0的神經元編號21，與19、20成為一組，這樣可以分成7組:[1,2,3]，[4,5,6]……,

[16,17,18],[19,20,21]，最後計算每組的最大值。

如果只分6組，除了以1作為初始位置進行連續組合之外，也可以從位置2或者3開始進行組合。也就是說其實有3種池化組合方法：

A、△=0分組:[1,2,3]，[4,5,6]……,[16,17,18]；

B、△=1分組:[2,3,4]，[5,6,7]……,[17,18,19]；

C、△=2分組:[3,4,5]，[6,7,8]……,[18,19,20]；

對應圖片如下：

以往的CNN中，一般只用△=0的情況，得到池化結果後，就送入了下一層。但是該文獻的方法是，把上面的△=0、△=1、△=2的三種組合方式的池化結果，分別送入網路的下一層。這樣的話，網路在最後輸出的時候，就會出現3種預測結果了。

前面所述是一維的情況，如果是2維圖片的話，那麼(△x,△y)就會有9種取值情況(3*3)；如果我們在做圖片分類的時候，在網路的某一個池化層加入了這種offset 池化方法，然後把這9種池化結果，分別送入後面的網路層，最後的圖片分類輸出結果就可以得到9個預測結果(每個類別都可以得到9種概率值，然後我們對每個類別的9種概率，取其最大值，做為此類別的預測概率值)。

演算法原理：

文獻中的演算法，就是把這兩種思想結合起來，形成了文獻最後測試階段的演算法。

1、論文的網路架構與訓練階段

(1)網路架構

對於網路的結構，文獻給出了兩個版本——快速版、精確版，一個精度比較高但速度慢；另外一個精度雖然低但是速度快。下面是高精度版本的網路結構表相關參數：

表格參數說明：

網路輸入：圖片大小為221px*221px；

網路結構方面基本上和AlexNet相同，使用了ReLU激活，最大池化。不同之處在於：(a)作者沒有使用局部響應歸一化層；(b)然後也沒有採用重疊池化的方法；(c)在第一層卷積層，stride作者是選擇了2，這個與AlexNet不同（AlexNet選擇的跨步是4，在網路中，如果stride選擇比較大得話，雖然可以減少網路層數，提高速度，但是卻會降低精度）。

需要注意的是把f7這一層，看成是卷積核大小為5*5的卷積層，總之就是需要把網路看成前面所述的FCN模型，去除了全連接層的概念，因為在測試階段可不是僅僅輸入221*221這樣大小的圖片，在測試階段要輸入各種大小的圖片，具體請看後面測試階段的講解。

(2)網路訓練

訓練輸入：對於每張原圖片為256*256，然後進行隨機裁剪為221*221的大小作為CNN輸入，進行訓練。

優化求解參數設置：訓練的min-batchs選擇128，權重初始化選擇高斯分布的隨機初始化：

然後採用隨機梯度下降法，進行優化更新，動量項參數大小選擇0.6，L2權重衰減系數大小選擇10-5次方。學習率初始化值為0.05，根據迭代次數的增加，每隔幾十次的迭代後，就把學習率的大小減小一半。

然後就是DropOut，這個只有在最後的兩個全連接層，才採用dropout，dropout比率選擇0.5。

2、網路測試階段

在Alexnet的文獻中，預測方法是輸入一張圖片256*256，然後進行multi-view裁剪，也就是從圖片的四個角進行裁剪，還有就是一圖片的中心進行裁剪，這樣可以裁剪到5張224*224的圖片。然後把原圖片水平翻轉一下，再用同樣的方式進行裁剪，又可以裁剪到5張圖片。把這10張圖片作為輸入，分別進行預測分類，在後在softmax的最後一層，求取個各類的總概率，求取平均值。

然而Alexnet這種預測方法存在兩個問題：

一方面這樣的裁剪方式，把圖片的很多區域都給忽略了，這樣的裁剪方式，剛好把圖片物體的一部分給裁剪掉了；

另一方面，裁剪窗口重疊存在很多冗餘的計算，像上面要分別把10張圖片送入網路，可見測試階段的計算量還是較大的。

Overfeat演算法：

訓練完上面所說的網路之後，在測試階段不再是用一張221*221大小的圖片了作為網路的輸入，而是用了6張大小都不相同的圖片，也就是所謂的多尺度輸入預測，如下表格所示：

當網路前向傳導到layer 5的時候，就利用了前面所述的FCN、offset pooling這兩種思想的相結合。現以輸入一張圖片為例(6張圖片的計算方法都相同)，講解layer 5後面的整體過程，具體流程示意圖如下：

步驟一：

對於某個尺度的圖片，經過前五層的卷積後得到特徵圖。上圖中特徵圖的解析度是20x23，256個通道。

步驟二：

對於該特徵圖，重復多次使用非重疊的池化，每次池化的偏置不同，有行偏置和列偏置。上圖中偏置池化3次，偏置分別為為(0,1,2)。這就是offset pooling，也被稱為fine stride。offset pooling得到的特徵圖的維度為6x7x3x3xD，其中6x7是特徵圖的解析度，3x3是偏置池化的次數，D是通道數。上圖中是以1維顯示的。

步驟三：

池化後得到的特徵圖將被送入分類器。

步驟四：

分類器的輸入是的5x5xD，輸出是C(類別數)維向量。但是offset pooling後得到的特徵圖並不是5x5xD，比如上圖中的特徵圖大小為6x7xD，因此分類器以滑動窗口的方式應用在特徵圖上，每個滑動窗口經過分類器輸出一個C維向量。比如上圖中輸入的6x7xD的特徵圖最終得到2x3xC的輸出，其中2x3是滑動窗口的個數。

步驟五：

而2x3xC只是一組偏置池化的輸出，總的輸出為2x3x3x3xC，將輸出的張量reshape，得到6x9xC輸出張量。最終輸出分類張量為3d張量，即兩個解析度維度 x C維。

然後需要在後面把它們拉成一維向量，這樣在一個尺度上，可以得到一個C*N個預測值矩陣，每一列就表示圖片屬於某一類別的概率值，並且求取每一列的最大值，作為本尺度的每個類別的概率值。

最後一共用了6種不同尺度(文獻使用了12張，另外6張是水平翻轉的圖片)進行做預測，然後把這六種尺度結果再做一個平均，作為最最後的結果。

從上面過程可以看到整個網路分成兩部分：layer 1~5這五層稱之為特徵提取層；layer 6~output稱之為分類層。

六、定位任務

用於定位任務的時候，就把分類層(上面的layer 6~output)給重新設計一下，把分類改成回歸問題，然後在各種不同尺度上訓練預測物體的bounding box。

Ⅷ 常見加密演算法原理及概念

在安全領域，利用密鑰加密演算法來對通信的過程進行加密是一種常見的安全手段。利用該手段能夠保障數據安全通信的三個目標：

而常見的密鑰加密演算法類型大體可以分為三類：對稱加密、非對稱加密、單向加密。下面我們來了解下相關的演算法原理及其常見的演算法。

對稱加密演算法採用單密鑰加密，在通信過程中，數據發送方將原始數據分割成固定大小的塊，經過密鑰和加密演算法逐個加密後，發送給接收方；接收方收到加密後的報文後，結合密鑰和解密演算法解密組合後得出原始數據。由於加解密演算法是公開的，因此在這過程中，密鑰的安全傳遞就成為了至關重要的事了。而密鑰通常來說是通過雙方協商，以物理的方式傳遞給對方，或者利用第三方平台傳遞給對方，一旦這過程出現了密鑰泄露，不懷好意的人就能結合相應的演算法攔截解密出其加密傳輸的內容。

對稱加密演算法擁有著演算法公開、計算量小、加密速度和效率高得特定，但是也有著密鑰單一、密鑰管理困難等缺點。

常見的對稱加密演算法有：
DES：分組式加密演算法，以64位為分組對數據加密，加解密使用同一個演算法。
3DES：三重數據加密演算法，對每個數據塊應用三次DES加密演算法。
AES：高級加密標准演算法，是美國聯邦政府採用的一種區塊加密標准，用於替代原先的DES，目前已被廣泛應用。
Blowfish：Blowfish演算法是一個64位分組及可變密鑰長度的對稱密鑰分組密碼演算法，可用來加密64比特長度的字元串。

非對稱加密演算法採用公鑰和私鑰兩種不同的密碼來進行加解密。公鑰和私鑰是成對存在，公鑰是從私鑰中提取產生公開給所有人的，如果使用公鑰對數據進行加密，那麼只有對應的私鑰才能解密，反之亦然。
下圖為簡單非對稱加密演算法的常見流程：

發送方Bob從接收方Alice獲取其對應的公鑰，並結合相應的非對稱演算法將明文加密後發送給Alice；Alice接收到加密的密文後，結合自己的私鑰和非對稱演算法解密得到明文。這種簡單的非對稱加密演算法的應用其安全性比對稱加密演算法來說要高，但是其不足之處在於無法確認公鑰的來源合法性以及數據的完整性。
非對稱加密演算法具有安全性高、演算法強度負復雜的優點，其缺點為加解密耗時長、速度慢，只適合對少量數據進行加密，其常見演算法包括：
RSA ：RSA演算法基於一個十分簡單的數論事實：將兩個大素數相乘十分容易，但那時想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰，可用於加密，也能用於簽名。
DSA ：數字簽名演算法，僅能用於簽名，不能用於加解密。
DSS ：數字簽名標准，技能用於簽名，也可以用於加解密。
ELGamal ：利用離散對數的原理對數據進行加解密或數據簽名，其速度是最慢的。

單向加密演算法常用於提取數據指紋，驗證數據的完整性。發送者將明文通過單向加密演算法加密生成定長的密文串，然後傳遞給接收方。接收方在收到加密的報文後進行解密，將解密獲取到的明文使用相同的單向加密演算法進行加密，得出加密後的密文串。隨後將之與發送者發送過來的密文串進行對比，若發送前和發送後的密文串相一致，則說明傳輸過程中數據沒有損壞；若不一致，說明傳輸過程中數據丟失了。單向加密演算法只能用於對數據的加密，無法被解密，其特點為定長輸出、雪崩效應。常見的演算法包括：MD5、sha1、sha224等等，其常見用途包括：數字摘要、數字簽名等等。

密鑰交換IKE（Internet Key Exchange）通常是指雙方通過交換密鑰來實現數據加密和解密，常見的密鑰交換方式有下面兩種：
1、公鑰加密，將公鑰加密後通過網路傳輸到對方進行解密，這種方式缺點在於具有很大的可能性被攔截破解，因此不常用；
2、Diffie-Hellman，DH演算法是一種密鑰交換演算法，其既不用於加密，也不產生數字簽名。DH演算法的巧妙在於需要安全通信的雙方可以用這個方法確定對稱密鑰。然後可以用這個密鑰進行加密和解密。但是注意，這個密鑰交換協議/演算法只能用於密鑰的交換，而不能進行消息的加密和解密。雙方確定要用的密鑰後，要使用其他對稱密鑰操作加密演算法實際加密和解密消息。DH演算法通過雙方共有的參數、私有參數和演算法信息來進行加密，然後雙方將計算後的結果進行交換，交換完成後再和屬於自己私有的參數進行特殊演算法，經過雙方計算後的結果是相同的，此結果即為密鑰。
如：

在整個過程中，第三方人員只能獲取p、g兩個值，AB雙方交換的是計算後的結果，因此這種方式是很安全的。

公鑰基礎設施是一個包括硬體、軟體、人員、策略和規程的集合，用於實現基於公鑰密碼機制的密鑰和證書的生成、管理、存儲、分發和撤銷的功能，其組成包括：簽證機構CA、注冊機構RA、證書吊銷列表CRL和證書存取庫CB。
PKI採用證書管理公鑰，通過第三方可信任CA中心，把用戶的公鑰和其他用戶信息組生成證書，用於驗證用戶的身份。
公鑰證書是以數字簽名的方式聲明，它將公鑰的值綁定到持有對應私鑰的個人、設備或服務身份。公鑰證書的生成遵循X.509協議的規定，其內容包括：證書名稱、證書版本、序列號、演算法標識、頒發者、有效期、有效起始日期、有效終止日期、公鑰 、證書簽名等等的內容。

CA證書認證的流程如下圖，Bob為了向Alice證明自己是Bob和某個公鑰是自己的，她便向一個Bob和Alice都信任的CA機構申請證書，Bob先自己生成了一對密鑰對（私鑰和公鑰），把自己的私鑰保存在自己電腦上，然後把公鑰給CA申請證書，CA接受申請於是給Bob頒發了一個數字證書，證書中包含了Bob的那個公鑰以及其它身份信息，當然，CA會計算這些信息的消息摘要並用自己的私鑰加密消息摘要（數字簽名）一並附在Bob的證書上，以此來證明這個證書就是CA自己頒發的。Alice得到Bob的證書後用CA的證書（自簽署的）中的公鑰來解密消息摘要，隨後將摘要和Bob的公鑰發送到CA伺服器上進行核對。CA在接收到Alice的核對請求後，會根據Alice提供的信息核對Bob的證書是否合法，如果確認合法則回復Alice證書合法。Alice收到CA的確認回復後，再去使用從證書中獲取的Bob的公鑰加密郵件然後發送給Bob，Bob接收後再以自己的私鑰進行解密。