演算法簡介

『壹』 推薦演算法簡介

在這個時代，無論是信息消費者還是信息生產者都遇到了很大的挑戰:作為信息消費者，如何從大量信息中找到自己感興趣的信息是一件非常困難的事情;作為信息生產者， 如何讓自己生產的信息脫穎而出，受到廣大用戶的關注，也是一件非常困難的事情。推薦系統就是解決這一矛盾的重要工具。推薦系統的任務就是聯系用戶和信息，一方面幫助用戶發現對自己有價值的信息，另一方面讓信息能夠展現在對它感興趣的用戶面前，從而實現信息消費者和信息 生產者的雙贏。和搜索引擎不同的是，推薦系統不需要用戶提供明確的需求，而是通過分析用戶的歷史行為給用 戶的興趣建模，從而主動給用戶推薦能夠滿足他們興趣和需求的信息 個性化推薦的成功需要兩個條件。第一是存在 信息過載 ，因為如果用戶可以很容易地從所有物品中找到喜歡的物品，就不需要個性化推薦。第二用 戶大部分時候沒有特別明確的需求 ，因為用戶沒有明確的需求，可以直接通過搜索引擎找到感興趣的物品。

一個完整的推薦系統一般存在3個參與方：用戶、物品提供者和提供推薦系統的網站。以圖書推薦為例， 首先，推薦系統需要滿足用戶的需求，給用戶推薦那些令他們感興趣的圖書。其次，推薦系統要讓各出版社的書都能夠被推薦給對其感興趣的用戶，而不是只推薦幾個大型出版社的書。最後， 好的推薦系統設計，能夠讓推薦系統本身收集到高質量的用戶反饋，不斷完善推薦的質量，增加 用戶和網站的交互，提高網站的收入。因此在評測一個推薦演算法時，需要同時考慮三方的利益， 一個好的推薦系統是能夠令三方共贏的系統。

推薦系統中，主要有3種評測推薦效果的實驗方法，即離線實驗(offline experiment)、用戶調查(user study)和在線實驗(online experiment)。

2.1 離線實驗

離線實驗的方法一般由如下幾個步驟構成: (1) 通過日誌系統獲得用戶行為數據，並按照一定格式生成一個標準的數據集; (2) 將數據集按照一定的規則分成訓練集和測試集; (3) 在訓練集上訓練用戶興趣模型，在測試集上進行預測; (4) 通過事先定義的離線指標評測演算法在測試集上的預測結果。

從上面的步驟可以看到，推薦系統的離線實驗都是在數據集上完成的，也就是說它不需要一個實際的系統來供它實驗，而只要有一個從實際系統日誌中提取的數據集即可。這種實驗方法的 好處是不需要真實用戶參與，可以直接快速地計算出來，從而方便、快速地測試大量不同的演算法。它的主要缺點是無法獲得很多商業上關注的指標，如點擊率、轉化率等，而找到和商業指標非常相關的離線指標也是很困難的事情

2.2 用戶調查

3.3 在線實驗

在完成離線實驗和必要的用戶調查後，可以將推薦系統上線做 AB測試 ，將它和舊的演算法進行比較。 AB測試 是一種很常用的在線評測演算法的實驗方法。它通過一定的規則將用戶隨機分成幾組，並對不同組用戶採取不同的演算法，然後通過統計不同組用戶的各種不同的評測指標比較不同演算法的好壞。 AB測試的優點是可以公平獲得不同演算法實際在線時的性能指標，包括商業上關注的指標。 AB測試的缺點主要是周期比較長，必須進行長期的實驗才能得到可靠的結果。因此一般不會用 AB測試測試所有的演算法，而只是用它測試那些在離線實驗和用戶調查中表現很好的演算法。其次， 一個大型網站的AB測試系統的設計也是一項復雜的工程。

一般來說，一個新的推薦演算法最終上線，需要完成上面所說的3個實驗。 1）首先，需要通過離線實驗證明它在很多離線指標上優於現有的演算法。 2）然後，需要通過用戶調查確定它的用戶滿意度不低於現有的演算法。 3）最後，通過在線的AB測試確定它在我們關心的指標上。

本節將介紹各種推薦系統的評測指標。這些評測指標可用於評價推薦系統各方面的性能。這 些指標有些可以定量計算，有些只能定性描述，有些可以通過離線實驗計算，有些需要通過用戶 調查獲得，還有些只能在線評測。

(1) 用戶滿意度

用戶作為推薦系統的重要參與者，其滿意度是評測推薦系統的最重要指標。但是，用戶滿意度沒有辦法離線計算，只能通過用戶調查或者在線實驗獲得。

在在線系統中，用戶滿意度主要通過一些 對用戶行為的統計得到 。比如在電子商務網站中，用戶如果購買了推薦的商品，就表示他們在一定程度上滿意。因此，我們可以 利用購買率度量用 戶的滿意度 。此外，有些網站會通過設計一些用戶 反饋界面收集用戶滿意度 。比如在視頻網站中，都有對推薦結果滿意或者不滿意的 反饋按鈕 ，通過統計兩種按鈕的單擊情況就可以度量系統的用戶滿意度。更一般的情況下，我們可以用 點擊率、用戶停留時間和轉化率等指標度量 用戶的滿意度。

(2) 預測准確度

預測准確度度量一個推薦系統或者推薦演算法預測用戶行為的能力。這個指標是最重要的推薦系統離線評測指標

在計算該指標時需要有一個離線的數據集，該數據集包含用戶的歷史行為記錄。然後，將該數據集通過時間分成訓練集和測試集。最後，通過在訓練集上建立用戶的行為和興趣模型預測用戶在測試集上的行為，並計算預測行為和測試集上實際行為的重合度作為預測准確度。 預測准確度指標有分為以下幾種：

評分預測：

預測用戶對物品評分的行為成為評分預測，在評分預測中，預測准確度一般通過均方根誤差RMSE和平均絕對誤差MAE計算，對於測試集中的一個用戶u和物品i,令[圖片上傳失敗...(image-62a797-1560412790460)] 是用戶u對物品i的實際評分，而[圖片上傳失敗...(image-28cfbc-1560412790460)] 是推薦演算法給出的預測評分，那麼RMSE定義為：

其中T為樣本個數

MAE採用絕對值計算預測誤差，它的定義為:

TopN推薦

網站在提供推薦服務時，一般是給用戶一個個性化的推薦列表，這種推薦叫做TopN推薦。TopN推薦的預測准確率一般通過准確率(precision)/召回率(recall)度量。 令R(u)是根據用戶在訓練集上的行為給用戶作出的推薦列表，而T(u)是用戶在測試集上的行為列表。那麼，推薦結果的召回率定義為:

推薦結果准確率定義：

(3) 覆蓋率

覆蓋率（coverage）描述一個推薦系統對物品長尾的發掘能力。覆蓋率有不同的定義方法，最簡單的定義為推薦系統能夠推薦出來的物品占總物品集合的比例。假設系統的用戶集合U，推薦系統給每個用戶推薦一個長度為N的物品集合R（u）。那麼推薦系統的覆蓋率可以通過下面的公式計算：

I為總物品數

此外，從上面的定義也可以看到，熱門排行榜的推薦覆蓋率是很低的，它只會 推薦那些熱門的物品，這些物品在總物品中占的比例很小。一個好的推薦系統不僅需要有比較高的用戶滿意度，也要有較高的覆蓋率。

但是上面的定義過於粗略。覆蓋率為100%的系統可以有無數的物品流行度分布。為了更細致地描述推薦系統發掘長尾的能力，需要統計推薦列表中不同物品出現次數的分布。如果所有的 物品都出現在推薦列表中，且出現的次數差不多，那麼推薦系統發掘長尾的能力就很好。因此， 可以通過研究物品在推薦列表中出現次數的分布描述推薦系統挖掘長尾的能力。如果這個分布比 較平，那麼說明推薦系統的覆蓋率較高，而如果這個分布較陡峭，說明推薦系統的覆蓋率較低。 在資訊理論和經濟學中有兩個著名的指標可以用來定義覆蓋率。第一個是信息熵:

其中：n代表推薦列表中物品類別個數，p(i)代表每個類別的所佔的比率

第二個指標是基尼系數：

(4) 多樣性

為了滿足用戶廣泛的興趣，推薦列表需要能夠覆蓋用戶不同的興趣領域，即推薦結果需要具有多樣性。多樣性推薦列表的好處用一句俗話表示就是（不在一棵樹上弔死）。盡管用戶的興趣在較長的時間跨度中是一樣的。但具體到用戶訪問推薦系統的某一時刻，其興趣往往是單一的，那麼如果推薦列表只能覆蓋用戶的一個興趣點，而這個興趣點不是用戶這個時刻的興趣點，推薦結果就不會讓用戶滿意。反之如果推薦列表表較多樣，覆蓋用戶絕大多數的興趣點，那麼久會增加用戶找到感興趣物品的概率。因此給用戶的推薦列表也需要滿足用戶廣泛的興趣，即具有多樣性。

多樣性描述了推薦列表中物品兩兩之間的不相似性，因此，多樣性和相似性是對應的。假設s(i, j) ∈Î[0,1] 定義了物品i和j之間的相似度，那麼用戶u的推薦列表R(u)的多樣性定義如下：

而推薦系統的整體多樣性可以定義為所有用戶推薦列表多樣性的平均值：

(5) 新穎性

新穎的推薦是指給用戶推薦那些他們以前沒有聽說過的物品。在一個網站中 實現新穎性 的最簡單辦法是，把那些用戶之前在網站中對其有過行為的物品從推薦列表中過濾掉。比如在一個視 頻網站中，新穎的推薦不應該給用戶推薦那些他們已經看過、打過分或者瀏覽過的視頻。 評測新穎度的最簡單方法是利用推薦結果的平均流行度，因為越不熱門的物品越 可能讓用戶覺得新穎。因此，如果推薦結果中物品的平均熱門程度較低，那麼推薦結果就可能有比較高的新穎性。

(6) 驚喜度

驚喜度(serendipity)是最近這幾年推薦系統領域最熱門的話題。如果推薦結果和用戶的歷史興趣不相似，但卻讓用戶覺得滿意，那麼就可以說推薦結果的驚喜度很高，而推薦的新穎性僅僅取決於用戶是否聽說過這個推薦結果。提高推薦驚喜度需要提高推薦結果的用戶滿意度，同時降低推薦結果和用戶歷史興趣的相似度。

(7) 信任度

度量推薦系統的信任度只能通過問卷調查的方式，詢問用戶是否信任推薦系統的推薦結果。 提高推薦系統的信任度主要有兩種方法。首先需要增加推薦系統的透明度(transparency)， 而增加推薦系統透明度的主要辦法是提供推薦解釋。只有讓用戶了解推薦系統的運行機制，讓用 戶認同推薦系統的運行機制，才會提高用戶對推薦系統的信任度。其次是考慮用戶的社交網路 信息，利用用戶的好友信息給用戶做推薦，並且用好友進行推薦解釋。這是因為用戶對他們的 好友一般都比較信任，因此如果推薦的商品是好友購買過的，那麼他們對推薦結果就會相對比較信任

(8) 實時性

在很多網站中，因為物品(新聞、微博等)具有很強的時效性，所以需要在物品還具有時效 性時就將它們推薦給用戶。 推薦系統的實時性包括兩個方面。首先，推薦系統需要實時地更新推薦列表來滿足用戶新的 行為變化。實時性的第二個方面是推薦系統需要能夠將新加入系統的物品推薦給用戶。這主要考驗了推 薦系統處理物品冷啟動的能力。

(9) 健壯性

健壯性(即robust,魯棒 性)指標衡量了一個推薦系統抗擊作弊的能力。演算法健壯性的評測主要利用模擬攻擊。首先，給定一個數據集和一個演算法，可以用這個演算法 給這個數據集中的用戶生成推薦列表。然後，用常用的攻擊方法向數據集中注入雜訊數據，然後 利用演算法在注入雜訊後的數據集上再次給用戶生成推薦列表。最後，通過比較攻擊前後推薦列表 的相似度評測演算法的健壯性。如果攻擊後的推薦列表相對於攻擊前沒有發生大的變化，就說明算 法比較健壯

(10) 商業目標

很多時候，網站評測推薦系統更加註重網站的商業目標是否達成，而商業目標和網站的盈利模式是息息相關的

(11) 總結

上一節介紹了很多評測指標，但是在評測系統中還需要考慮評測維度，比如一個推薦演算法， 雖然整體性能不好，但可能在某種情況下性能比較好，而增加評測維度的目的就是知道一個演算法 在什麼情況下性能最好。這樣可以為融合不同推薦演算法取得最好的整體性能帶來參考。

一般來說，評測維度分為如下3種。 1） 用戶維度 ：主要包括用戶的人口統計學信息、活躍度以及是不是新用戶等。 2） 物品維度 ：包括物品的屬性信息、流行度、平均分以及是不是新加入的物品等。 3） 時間維度 ：包括季節，是工作日還是周末，是白天還是晚上等。 如果能夠在推薦系統評測報告中包含不同維度下的系統評測指標，就能幫我們全面地了解推 薦系統性能，找到一個看上去比較弱的演算法的優勢，發現一個看上去比較強的演算法的缺點。

『貳』 幾種常用的演算法簡介

1、窮舉法窮舉法是最基本的演算法設計策略，其思想是列舉出問題所有的可能解，逐一進行判別，找出滿足條件的解。
窮舉法的運用關鍵在於解決兩個問題：
在運用窮舉法時，容易出現的問題是可能解過多，導致演算法效率很低，這就需要對列舉可能解的方法進行優化。
以題1041--純素數問題為例，從1000到9999都可以看作是可能解，可以通過對所有這些可能解逐一進行判別，找出其中的純素數，但只要稍作分析，就會發現其實可以大幅度地降低可能解的范圍。根據題意易知，個位只可能是3、5、7，再根據題意可知，可以在3、5、7的基礎上，先找出所有的二位純素數，再在二位純素數基礎上找出三位純素數，最後在三位純素數的基礎上找出所有的四位純素數。
2、分治法分治法也是應用非常廣泛的一種演算法設計策略，其思想是將問題分解為若乾子問題，從而可以遞歸地求解各子問題，再綜合出問題的解。
分治法的運用關鍵在於解決三個問題：
我們熟知的如漢諾塔問題、折半查找演算法、快速排序演算法等都是分治法運用的典型案例。
以題1045--Square
Coins為例，先對題意進行分析，可設一個函數f(m,
n)等於用面值不超過n2的貨幣構成總值為m的方案數，則容易推導出：
f(m,
n)
=
f(m-0*n*n,
n-1)+f(m-1*n*n,
n-1)+f(m-2*n*n,
n-1)+...+f(m-k*n*n,
n-1)
這里的k是幣值為n2的貨幣最多可以用多少枚，即k=m/(n*n)。
也很容易分析出，f(m,
1)
=
f(1,
n)
=
1
對於這樣的題目，一旦分析出了遞推公式，程序就非常好寫了。所以在動手開始寫程序之前，分析工作做得越徹底，邏輯描述越准確、簡潔，寫起程序來就會越容易。
3、動態規劃法
動態規劃法多用來計算最優問題，動態規劃法與分治法的基本思想是一致的，但處理的手法不同。動態規劃法在運用時，要先對問題的分治規律進行分析，找出終結子問題，以及子問題向父問題歸納的規則，而演算法則直接從終結子問題開始求解，逐層向上歸納，直到歸納出原問題的解。
動態規劃法多用於在分治過程中，子問題可能重復出現的情況，在這種情況下，如果按照常規的分治法，自上向下分治求解，則重復出現的子問題就會被重復地求解，從而增大了冗餘計算量，降低了求解效率。而採用動態規劃法，自底向上求解，每個子問題只計算一次，就可以避免這種重復的求解了。
動態規劃法還有另外一種實現形式，即備忘錄法。備忘錄的基本思想是設立一個稱為備忘錄的容器，記錄已經求得解的子問題及其解。仍然採用與分治法相同的自上向下分治求解的策略，只是對每一個分解出的子問題，先在備忘錄中查找該子問題，如果備忘錄中已經存在該子問題，則不須再求解，可以從備忘錄中直接得到解，否則，對子問題遞歸求解，且每求得一個子問題的解，都將子問題及解存入備忘錄中。
例如，在題1045--Square
Coins中，可以採用分治法求解，也可以採用動態規劃法求解，即從f(m,
1)和f(1,
n)出發，逐層向上計算，直到求得f(m,
n)。
在競賽中，動態規劃和備忘錄的思想還可以有另一種用法。有些題目中的可能問題數是有限的，而在一次運行中可能需要計算多個測試用例，可以採用備忘錄的方法，預先將所有的問題的解記錄下來，然後輸入一個測試用例，就查備忘錄，直接找到答案輸出。這在各問題之間存在父子關系的情況下，會更有效。例如，在題1045--Square
Coins中，題目中已經指出了最大的目標幣值不超過300，也就是說問題數只有300個，而且各問題的計算中存在重疊的子問題，可以採用動態規劃法，將所有問題的解先全部計算出來，再依次輸入測試用例數據，並直接輸出答案。
4、回溯法回溯法是基於問題狀態樹搜索的求解法，其可適用范圍很廣。從某種角度上說，可以把回溯法看作是優化了的窮舉法。回溯法的基本思想是逐步構造問題的可能解，一邊構造，一邊用約束條件進行判別，一旦發現已經不可能構造出滿足條件的解了，則退回上一步構造過程，重新進行構造。這個退回的過程，就稱之為回溯。
回溯法在運用時，要解決的關鍵問題在於：
回溯法的經典案例也很多，例如全排列問題、N後問題等。
5、貪心法貪心法也是求解最優問題的常用演算法策略，利用貪心法策略所設計的演算法，通常效率較高，演算法簡單。貪心法的基本思想是對問題做出目前看來最好的選擇，即貪心選擇，並使問題轉化為規模更小的子問題。如此迭代，直到子問題可以直接求解。
基於貪心法的經典演算法例如：哈夫曼演算法、最小生成樹演算法、最短路徑演算法等。

『叄』 推薦演算法簡介

寫在最前面：本文內容主要來自於書籍《推薦系統實踐》和《推薦系統與深度學習》。

推薦系統是目前互聯網世界最常見的智能產品形式。從電子商務、音樂視頻網站，到作為互聯網經濟支柱的在線廣告和新穎的在線應用推薦，到處都有推薦系統的身影。推薦演算法是推薦系統的核心，其本質是通過一定的方式將用戶和物品聯系起來，而不同的推薦系統利用了不同的方式。

推薦系統的主要功能是以個性化的方式幫助用戶從極大的搜索空間中快速找到感興趣的對象。因此，目前所用的推薦系統多為個性化推薦系統。個性化推薦的成功應用需要兩個條件：

在推薦系統的眾多演算法中，基於協同的推薦和基於內容的推薦在實踐中得到了最廣泛的應用。本文也將從這兩種演算法開始，結合時間、地點上下文環境以及社交環境，對常見的推薦演算法做一個簡單的介紹。

基於內容的演算法的本質是對物品內容進行分析，從中提取特徵，然後基於用戶對何種特徵感興趣來推薦含有用戶感興趣特徵的物品。因此，基於內容的推薦演算法有兩個最基本的要求：

下面我們以一個簡單的電影推薦來介紹基於內容的推薦演算法。

現在有兩個用戶A、B和他們看過的電影以及打分情況如下：

其中問好（?）表示用戶未看過。用戶A對《銀河護衛隊 》《變形金剛》《星際迷航》三部科幻電影都有評分，平均分為 4 .7 分 （ (5+4+5 ) / 3=4.7 ）；對《三生三世》《美人魚》《北京遇上西雅圖》三部愛情電影評分平均分為 2.3 分 （ ( 3十2+2 ) /3=2.3 ）。現在需要給A推薦電影，很明顯A更傾向於科幻電影，因此推薦系統會給A推薦獨立日。而對於用戶B，通過簡單的計算我們可以知道更喜歡愛情電影，因此給其推薦《三生三世》。當然，在實際推薦系統中，預測打分比這更加復雜些，但是其原理是一樣的。

現在，我們可以將基於內容的推薦歸納為以下四個步驟：

通過上面四步就能快速構建一個簡單的推薦系統。基於內容的推薦系統通常簡單有效，可解釋性好，沒有物品冷啟動問題。但他也有兩個明顯的缺點：

最後，順便提一下特徵提取方法：對於某些特徵較為明確的物品，一般可以直接對其打標簽，如電影類別。而對於文本類別的特徵，則主要是其主題情感等，則些可以通過tf-idf或LDA等方法得到。

基於協同的演算法在很多地方也叫基於鄰域的演算法，主要可分為兩種：基於用戶的協同演算法和基於物品的協同演算法。

啤酒和尿布的故事在數據挖掘領域十分有名，該故事講述了美國沃爾瑪超市統計發現啤酒和尿布一起被購買的次數非常多，因此將啤酒和尿布擺在了一起，最後啤酒和尿布的銷量雙雙增加了。這便是一個典型的物品協同過濾的例子。

基於物品的協同過濾指基於物品的行為相似度（如啤酒尿布被同時購買）來進行物品推薦。該演算法認為，物品A和物品B具有很大相似度是因為喜歡物品A的用戶大都也喜歡物品B。

基於物品的協同過濾演算法主要分為兩步：

基於物品的協同過濾演算法中計算物品相似度的方法有以下幾種：
（1）基於共同喜歡物品的用戶列表計算。

此外，John S. Breese再其論文中還提及了IUF（Inverse User Frequence，逆用戶活躍度）的參數，其認為活躍用戶對物品相似度的貢獻應該小於不活躍的用戶，應該增加IUF參數來修正物品相似度的公式：

上面的公式只是對活躍用戶做了一種軟性的懲罰， 但對於很多過於活躍的用戶， 比如某位買了當當網80%圖書的用戶， 為了避免相似度矩陣過於稠密， 我們在實際計算中一般直接忽略他的興趣列表， 而不將其納入到相似度計算的數據集中。

（2）基於餘弦相似度計算。

（3）熱門物品的懲罰。
從上面（1）的相似度計算公式中，我們可以發現當物品 i 被更多人購買時，分子中的 N(i) ∩ N(j) 和分母中的 N(i) 都會增長。對於熱門物品，分子 N(i) ∩ N(j) 的增長速度往往高於 N(i)，這就會使得物品 i 和很多其他的物品相似度都偏高，這就是 ItemCF 中的物品熱門問題。推薦結果過於熱門，會使得個性化感知下降。以歌曲相似度為例，大部分用戶都會收藏《小蘋果》這些熱門歌曲，從而導致《小蘋果》出現在很多的相似歌曲中。為了解決這個問題，我們對於物品 i 進行懲罰，例如下式， 當α∈(0, 0.5) 時，N(i) 越小，懲罰得越厲害，從而使熱門物品相關性分數下降（ 博主註：這部分未充分理解 ）：

此外，Kary pis在研究中發現如果將ItemCF的相似度矩陣按最大值歸一化， 可以提高推薦的准確率。 其研究表明， 如果已經得到了物品相似度矩陣w， 那麼可以用如下公式得到歸一化之後的相似度矩陣w'：

歸一化的好處不僅僅在於增加推薦的准確度，它還可以提高推薦的覆蓋率和多樣性。一般來說，物品總是屬於很多不同的類，每一類中的物品聯系比較緊密。假設物品分為兩類——A和B， A類物品之間的相似度為0.5， B類物品之間的相似度為0.6， 而A類物品和B類物品之間的相似度是0.2。 在這種情況下， 如果一個用戶喜歡了5個A類物品和5個B類物品， 用ItemCF給他進行推薦， 推薦的就都是B類物品， 因為B類物品之間的相似度大。 但如果歸一化之後， A類物品之間的相似度變成了1， B類物品之間的相似度也是1， 那麼這種情況下， 用戶如果喜歡5個A類物品和5個B類物品， 那麼他的推薦列表中A類物品和B類物品的數目也應該是大致相等的。 從這個例子可以看出， 相似度的歸一化可以提高推薦的多樣性。

那麼，對於兩個不同的類，什麼樣的類其類內物品之間的相似度高，什麼樣的類其類內物品相似度低呢？一般來說，熱門的類其類內物品相似度一般比較大。如果不進行歸一化，就會推薦比較熱門的類裡面的物品，而這些物品也是比較熱門的。因此，推薦的覆蓋率就比較低。相反，如果進行相似度的歸一化，則可以提高推薦系統的覆蓋率。

最後，利用物品相似度矩陣和用戶打過分的物品記錄就可以對一個用戶進行推薦評分：

基於用戶的協同演算法與基於物品的協同演算法原理類似，只不過基於物品的協同是用戶U購買了A物品，會計算經常有哪些物品與A一起購買（也即相似度），然後推薦給用戶U這些與A相似的物品。而基於用戶的協同則是先計算用戶的相似性（通過計算這些用戶購買過的相同的物品），然後將這些相似用戶購買過的物品推薦給用戶U。

基於用戶的協同過濾演算法主要包括兩個步驟：

步驟（1）的關鍵是計算用戶的興趣相似度，主要是利用用戶的行為相似度計算用戶相似度。給定用戶 u 和 v，N(u) 表示用戶u曾經有過正反饋（譬如購買）的物品集合，N(v) 表示用戶 v 曾經有過正反饋的物品集合。那麼我們可以通過如下的 Jaccard 公式簡單的計算 u 和 v 的相似度：

或通過餘弦相似度：

得到用戶之間的相似度之後，UserCF演算法會給用戶推薦和他興趣最相似的K個用戶喜歡的物品。如下的公式度量了UserCF演算法中用戶 u 對物品 i 的感興趣程度：

首先回顧一下UserCF演算法和ItemCF演算法的推薦原理：UserCF給用戶推薦那些和他有共同興趣愛好的用戶喜歡的物品， 而ItemCF給用戶推薦那些和他之前喜歡的物品具有類似行為的物品。

（1）從推薦場景考慮
首先從場景來看，如果用戶數量遠遠超過物品數量，如購物網站淘寶，那麼可以考慮ItemCF，因為維護一個非常大的用戶關系網是不容易的。其次，物品數據一般較為穩定，因此物品相似度矩陣不必頻繁更新，維護代價較小。

UserCF的推薦結果著重於反應和用戶興趣相似的小群體的熱點，而ItemCF的推薦結果著重於維系用戶的歷史興趣。換句話說，UserCF的推薦更社會化，反應了用戶所在小型興趣群體中物品的熱門程度，而ItemCF的推薦更加個性化，反應了用戶自己的個性傳承。因此UserCF更適合新聞、微博或微內容的推薦，而且新聞內容更新頻率非常高，想要維護這樣一個非常大而且更新頻繁的表無疑是非常難的。

在新聞類網站中，用戶的興趣愛好往往比較粗粒度，很少會有用戶說只看某個話題的新聞，而且往往某個話題也不是每天都會有新聞。 個性化新聞推薦更強調新聞熱點，熱門程度和時效性是個性化新聞推薦的重點，個性化是補充，所以 UserCF 給用戶推薦和他有相同興趣愛好的人關注的新聞，這樣在保證了熱點和時效性的同時，兼顧了個性化。

（2）從系統多樣性（也稱覆蓋率，指一個推薦系統能否給用戶提供多種選擇）方面來看，ItemCF的多樣性要遠遠好於UserCF，因為UserCF更傾向於推薦熱門物品。而ItemCF具有較好的新穎性，能夠發現長尾物品。所以大多數情況下，ItemCF在精度上較小於UserCF，但其在覆蓋率和新穎性上面卻比UserCF要好很多。

在介紹本節基於矩陣分解的隱語義模型之前，讓我們先來回顧一下傳統的矩陣分解方法SVD在推薦系統的應用吧。

基於SVD矩陣分解在推薦中的應用可分為如下幾步：

SVD在計算前會先把評分矩陣 A 缺失值補全，補全之後稀疏矩陣 A 表示成稠密矩陣，然後將分解成 A' = U∑V T 。但是這種方法有兩個缺點：（1）補成稠密矩陣後需要耗費巨大的儲存空間，對這樣巨大的稠密矩陣進行儲存是不現實的；（2）SVD的計算復雜度很高，對這樣大的稠密矩陣中進行計算式不現實的。因此，隱語義模型就被發明了出來。

更詳細的SVD在推薦系統的應用可參考 奇異值分解SVD簡介及其在推薦系統中的簡單應用 。

隱語義模型（Latent Factor Model）最早在文本挖掘領域被提出，用於找到文本的隱含語義。相關的演算法有LSI，pLSA，LDA和Topic Model。本節將對隱語義模型在Top-N推薦中的應用進行詳細介紹，並通過實際的數據評測該模型。

隱語義模型的核心思想是通過隱含特徵聯系用戶興趣和物品。讓我們通過一個例子來理解一下這個模型。

現有兩個用戶，用戶A的興趣涉及偵探小說、科普圖書以及一些計算機技術書，而用戶B的興趣比較集中在數學和機器學習方面。那麼如何給A和B推薦圖書呢？

我們可以對書和物品的興趣進行分類。對於某個用戶，首先得到他的興趣分類，然後從分類中挑選他可能喜歡的物品。簡言之，這個基於興趣分類的方法大概需要解決3個問題：

對於第一個問題的簡單解決方案是找相關專業人員給物品分類。以圖書為例，每本書出版時，編輯都會給出一個分類。但是，即使有很系統的分類體系，編輯給出的分類仍然具有以下缺點：（1）編輯的意見不能代表各種用戶的意見；（2）編輯很難控制分類的細粒度；（3）編輯很難給一個物品多個分類；（4）編輯很難給一個物品多個分類；（5）編輯很難給出多個維度的分類；（6）編輯很難決定一個物品在某一個類別中的權重。

為了解決上述問題，研究員提出可以從數據出發，自動找到那些分類，然後進行個性化推薦。隱語義模型由於採用基於用戶行為統計的自動聚類，較好地解決了上面提出的5個問題。

LFM將矩陣分解成2個而不是3個：

推薦系統中用戶和物品的交互數據分為顯性反饋和隱性反饋數據。隱式模型中多了一個置信參數，具體涉及到ALS（交替最小二乘法，Alternating Least Squares）中對於隱式反饋模型的處理方式——有的文章稱為「加權的正則化矩陣分解」：

一個小細節：在隱性反饋數據集中，只有正樣本（正反饋）沒有負反饋（負樣本），因此如何給用戶生成負樣本來進行訓練是一個重要的問題。Rong Pan在其文章中對此進行了探討，對比了如下幾種方法：

用戶行為很容易用二分圖表示，因此很多圖演算法都可以應用到推薦系統中。基於圖的模型（graph-based model）是推薦系統中的重要內容。很多研究人員把基於領域的模型也稱為基於圖的模型，因為可以把基於領域的模型看作基於圖的模型的簡單形式。

在研究基於圖的模型之前，需要將用戶行為數據表示成圖的形式。本節的數據是由一系列用戶物品二元組 (u, i) 組成的，其中 u 表示用戶對物品 i 產生過行為。

令 G(V, E) 表示用戶物品二分圖，其中 V=V U UV I 由用戶頂點 V U 和物品節點 V I 組成。對於數據集中每一個二元組 (u, i) ，圖中都有一套對應的邊 e(v u , v i )，其中 v u ∈V U 是用戶對應的頂點，v i ∈V I 是物品i對應的頂點。如下圖是一個簡單的物品二分圖，其中圓形節點代表用戶，方形節點代表物品，用戶物品的直接連線代表用戶對物品產生過行為。比如下圖中的用戶A對物品a、b、d產生過行為。

度量圖中兩個頂點之間相關性的方法很多，但一般來說圖中頂點的相關性主要取決於下面3個因素：

而相關性高的一對頂點一般具有如下特徵：

舉個例子，如下圖，用戶A和物品c、e沒有邊直連，但A可通過一條長度為3的路徑到達c，而Ae之間有兩條長度為3的路徑。那麼A和e的相關性要高於頂點A和c，因而物品e在用戶A的推薦列表中應該排在物品c之前，因為Ae之間有兩條路徑。其中，（A,b,C,e）路徑經過的頂點的出度為（3，2，2，2），而 (A,d,D,e) 路徑經過了一個出度比較大的頂點D，所以 (A,d,D,e) 對頂點A與e之間相關性的貢獻要小於（A,b,C,e）。

基於上面3個主要因素，研究人員設計了很多計算圖中頂點相關性的方法，本節將介紹一種基於隨機遊走的PersonalRank演算法。

假設要給用戶u進行個性化推薦，可以從用戶u對應的節點 v u 開始在用戶物品二分圖上進行隨機遊走。遊走到任一節點時，首先按照概率α決定是繼續遊走還是停止這次遊走並從 v u 節點重新開始遊走。若決定繼續遊走，則從當前節點指向的節點中按照均勻分布隨機選擇一個節點作為遊走下次經過的節點。這樣，經過很多次隨機遊走後，每個物品被訪問到的概率會收斂到一個數。最終的推薦列表中物品的權重就是物品節點的訪問概率。

上述演算法可以表示成下面的公式：

雖然通過隨機遊走可以很好地在理論上解釋PersonalRank演算法，但是該演算法在時間復雜度上有明顯的缺點。因為在為每個用戶進行推薦時，都需要在整個用戶物品二分圖上進行迭代，知道所有頂點的PR值都收斂。這一過程的時間復雜度非常高，不僅無法在線進行實時推薦，離線計算也是非常耗時的。

有兩種方法可以解決上面PersonalRank時間復雜度高的問題：
（1）減少迭代次數，在收斂之前停止迭代。但是這樣會影響最終的精度。

（2）從矩陣論出發，重新涉及演算法。另M為用戶物品二分圖的轉移概率矩陣，即：

網路社交是當今社會非常重要甚至可以說是必不可少的社交方式，用戶在互聯網上的時間有相當大的一部分都用在了社交網路上。

當前國外最著名的社交網站是Facebook和Twitter，國內的代表則是微信/QQ和微博。這些社交網站可以分為兩類：

需要指出的是，任何一個社交網站都不是單純的社交圖譜或興趣圖譜。如QQ上有些興趣愛好群可以認識不同的陌生人，而微博中的好友也可以是現實中認識的。

社交網路定義了用戶之間的聯系，因此可以用圖定義社交網路。我們用圖 G(V,E,w) 定義一個社交網路，其中V是頂點集合，每個頂點代表一個用戶，E是邊集合，如果用戶va和vb有社交網路關系，那麼就有一條邊 e(v a , v b ) 連接這兩個用戶，而 w(v a , v b )定義了邊的權重。一般來說，有三種不同的社交網路數據：

和一般購物網站中的用戶活躍度分布和物品流行度分布類似，社交網路中用戶的入度（in degree，表示有多少人關注）和出度（out degree，表示關注多少人）的分布也是滿足長尾分布的。即大部分人關注的人都很少，被關注很多的人也很少。

給定一個社交網路和一份用戶行為數據集。其中社交網路定義了用戶之間的好友關系，而用戶行為數據集定義了不同用戶的歷史行為和興趣數據。那麼最簡單的演算法就是給用戶推薦好友喜歡的物品集合。即用戶u對物品i的興趣 p ui 可以通過如下公式計算。

用戶u和用戶v的熟悉程度描述了用戶u和用戶在現實社會中的熟悉程度。一般來說，用戶更加相信自己熟悉的好友的推薦，因此我們需要考慮用戶之間的熟悉度。下面介紹3中衡量用戶熟悉程度的方法。

（1）對於用戶u和用戶v，可以使用共同好友比例來計算他們的相似度：

上式中 out(u) 可以理解為用戶u關注的用戶合集，因此 out(u) ∩ out(v) 定義了用戶u、v共同關注的用戶集合。

（2）使用被關注的用戶數量來計算用戶之間的相似度，只要將公式中的 out(u) 修改為 in(u)：

in(u) 是指關注用戶u的集合。在無向社交網路中，in(u)和out(u)是相同的，而在微博這種有向社交網路中，這兩個集合的含義就不痛了。一般來說，本方法適合用來計算微博大V之間的相似度，因為大v往往被關注的人數比較多；而方法（1）適用於計算普通用戶之間的相似度，因為普通用戶往往關注行為比較豐富。

（3）除此之外，還可以定義第三種有向的相似度：這個相似度的含義是用戶u關注的用戶中，有多大比例也關注了用戶v：

這個相似度有一個缺點，就是在該相似度下所有人都和大v有很大的相似度，這是因為公式中的分母並沒有考慮 in(v) 的大小，所以可以把 in(v) 加入到上面公式的分母，來降低大v與其他用戶的相似度：

上面介紹了3種計算用戶之間相似度（或稱熟悉度）的計算方法。除了熟悉程度，還需要考慮用戶之間的興趣相似度。我們和父母很熟悉，但很多時候我們和父母的興趣確不相似，因此也不會喜歡他們喜歡的物品。因此，在度量用戶相似度時，還需要考慮興趣相似度，而興趣相似度可以通過和UserCF類似的方法度量，即如果兩個用戶喜歡的物品集合重合度很高，兩個用戶的興趣相似度很高。

最後，我們可以通過加權的形式將兩種權重合並起來，便得到了各個好有用戶的權重了。

有了權重，我們便可以針對用戶u挑選k個最相似的用戶，把他們購買過的物品中，u未購買過的物品推薦給用戶u即可。打分公式如下：

其中 w' 是合並後的權重，score是用戶v對物品的打分。

node2vec的整體思路分為兩個步驟：第一個步驟是隨機遊走（random walk），即通過一定規則隨機抽取一些點的序列；第二個步驟是將點的序列輸入至word2vec模型從而得到每個點的embedding向量。

隨機遊走在前面基於圖的模型中已經介紹過，其主要分為兩步：（1）選擇起始節點；（2）選擇下一節點。起始節點選擇有兩種方法：按一定規則抽取一定量的節點或者以圖中所有節點作為起始節點。一般來說會選擇後一種方法以保證所有節點都會被選取到。

在選擇下一節點方法上，最簡單的是按邊的權重來選擇，但在實際應用中需要通過廣度優先還是深度優先的方法來控制遊走范圍。一般來說，深度優先發現能力更強，廣度優先更能使社區內（較相似）的節點出現在一個路徑里。

斯坦福大學Jure Leskovec教授給出了一種可以控制廣度優先或者深度優先的方法。

以上圖為例，假設第一步是從t隨機遊走到v，這時候我們要確定下一步的鄰接節點。本例中，作者定義了p和q兩個參數變數來調節遊走，首先計算其鄰居節點與上一節點t的距離d，根據下面的公式得到α：

一般從每個節點開始遊走5~10次，步長則根據點的數量N遊走根號N步。如此便可通過random walk生成點的序列樣本。

得到序列之後，便可以通過word2vec的方式訓練得到各個用戶的特徵向量，通過餘弦相似度便可以計算各個用戶的相似度了。有了相似度，便可以使用基於用戶的推薦演算法了。

推薦系統需要根據用戶的歷史行為和興趣預測用戶未來的行為和興趣，因此大量的用戶行為數據就成為推薦系統的重要組成部分和先決條件。如何在沒有大量用戶數據的情況下設計個性化推薦系統並且讓用戶對推薦結果滿意從而願意使用推薦系統，就是冷啟動問題。

冷啟動問題主要分為三類：

針對用戶冷啟動，下面給出一些簡要的方案：
（1）有效利用賬戶信息。利用用戶注冊時提供的年齡、性別等數據做粗粒度的個性化；
（2）利用用戶的社交網路賬號登錄（需要用戶授權），導入用戶在社交網站上的好友信息，然後給用戶推薦其好友喜歡的物品；
（3）要求用戶在登錄時對一些物品進行反饋，手機用戶對這些物品的興趣信息，然後給用推薦那些和這些物品相似的物品；
（4）提供非個性化推薦。非個性化推薦的最簡單例子就是熱門排行榜，我們可以給用戶推薦熱門排行榜，然後等到用戶數據收集到一定的時候，在切換為個性化推薦。

對於物品冷啟動，可以利用新加入物品的內容信息，將它們推薦給喜歡過和他們相似的物品的用戶。

對於系統冷啟動，可以引入專家知識，通過一定高效的方式快速建立起物品的相關度表。

在上面介紹了一些推薦系統的基礎演算法知識，這些演算法大都是比較經典且現在還在使用的。但是需要注意的是，在實踐中，任何一種推薦演算法都不是單獨使用的，而是將多種推薦演算法結合起來，也就是混合推薦系統，但是在這里並不準備介紹，感興趣的可以查閱《推薦系統》或《推薦系統與深度學習》等書籍。此外，在推薦中非常重要的點擊率模型以及基於矩陣的一些排序演算法在這里並沒有提及，感興趣的也可自行學習。

雖然現在用的很多演算法都是基於深度學習的，但是這些經典演算法能夠讓我們對推薦系統的發展有一個比較好的理解，同時，更重要的一點——「推陳出新」，只有掌握了這些經典的演算法，才能提出或理解現在的一些更好地演算法。

『肆』 Kmeans聚類演算法簡介（有點枯燥）

1. Kmeans聚類演算法簡介

由於具有出色的速度和良好的可擴展性，Kmeans聚類演算法算得上是最著名的聚類方法。Kmeans演算法是一個重復移動類中心點的過程，把類的中心點，也稱重心(centroids)，移動到其包含成員的平均位置，然後重新劃分其內部成員。k是演算法計算出的超參數，表示類的數量；Kmeans可以自動分配樣本到不同的類，但是不能決定究竟要分幾個類。k必須是一個比訓練集樣本數小的正整數。有時，類的數量是由問題內容指定的。例如，一個鞋廠有三種新款式，它想知道每種新款式都有哪些潛在客戶，於是它調研客戶，然後從數據里找出三類。也有一些問題沒有指定聚類的數量，最優的聚類數量是不確定的。後面我將會詳細介紹一些方法來估計最優聚類數量。

Kmeans的參數是類的重心位置和其內部觀測值的位置。與廣義線性模型和決策樹類似，Kmeans參數的最優解也是以成本函數最小化為目標。Kmeans成本函數公式如下：

μiμi是第kk個類的重心位置。成本函數是各個類畸變程度(distortions)之和。每個類的畸變程度等於該類重心與其內部成員位置距離的平方和。若類內部的成員彼此間越緊湊則類的畸變程度越小，反之，若類內部的成員彼此間越分散則類的畸變程度越大。求解成本函數最小化的參數就是一個重復配置每個類包含的觀測值，並不斷移動類重心的過程。首先，類的重心是隨機確定的位置。實際上，重心位置等於隨機選擇的觀測值的位置。每次迭代的時候，Kmeans會把觀測值分配到離它們最近的類，然後把重心移動到該類全部成員位置的平均值那裡。

2. K值的確定

2.1 根據問題內容確定

這種方法就不多講了，文章開篇就舉了一個例子。

2.2 肘部法則

如果問題中沒有指定kk的值，可以通過肘部法則這一技術來估計聚類數量。肘部法則會把不同kk值的成本函數值畫出來。隨著kk值的增大，平均畸變程度會減小；每個類包含的樣本數會減少，於是樣本離其重心會更近。但是，隨著kk值繼續增大，平均畸變程度的改善效果會不斷減低。kk值增大過程中，畸變程度的改善效果下降幅度最大的位置對應的kk值就是肘部。為了讓讀者看的更加明白，下面讓我們通過一張圖用肘部法則來確定最佳的kk值。下圖數據明顯可分成兩類：

從圖中可以看出，k值從1到2時，平均畸變程度變化最大。超過2以後，平均畸變程度變化顯著降低。因此最佳的k是2。

2.3 與層次聚類結合

經常會產生較好的聚類結果的一個有趣策略是，首先採用層次凝聚演算法決定結果粗的數目，並找到一個初始聚類，然後用迭代重定位來改進該聚類。

2.4 穩定性方法

穩定性方法對一個數據集進行2次重采樣產生2個數據子集，再用相同的聚類演算法對2個數據子集進行聚類，產生2個具有kk個聚類的聚類結果，計算2個聚類結果的相似度的分布情況。2個聚類結果具有高的相似度說明kk個聚類反映了穩定的聚類結構，其相似度可以用來估計聚類個數。採用次方法試探多個kk，找到合適的k值。

2.5 系統演化方法

系統演化方法將一個數據集視為偽熱力學系統，當數據集被劃分為kk個聚類時稱系統處於狀態kk。系統由初始狀態k=1k=1出發，經過分裂過程和合並過程，系統將演化到它的穩定平衡狀態 kiki ，其所對應的聚類結構決定了最優類數 kiki 。系統演化方法能提供關於所有聚類之間的相對邊界距離或可分程度，它適用於明顯分離的聚類結構和輕微重疊的聚類結構。

2.6 使用canopy演算法進行初始劃分

基於Canopy Method的聚類演算法將聚類過程分為兩個階段

(1) 聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在一個子集中，這個子集被叫做Canopy，通過一系列計算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬於任何Canopy的情況，可以把這一階段看做數據預處理；

(2) 在各個Canopy內使用傳統的聚類方法(如Kmeans)，不屬於同一Canopy的對象之間不進行相似性計算。

從這個方法起碼可以看出兩點好處：首先，Canopy不要太大且Canopy之間重疊的不要太多的話會大大減少後續需要計算相似性的對象的個數；其次，類似於Kmeans這樣的聚類方法是需要人為指出K的值的，通過(1)得到的Canopy個數完全可以作為這個k值，一定程度上減少了選擇k的盲目性。

其他方法如貝葉斯信息准則方法(BIC)可參看文獻[4]。

3. 初始質心的選取

選擇適當的初始質心是基本kmeans演算法的關鍵步驟。常見的方法是隨機的選取初始中心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用技術是：多次運行，每次使用一組不同的隨機初始質心，然後選取具有最小SSE(誤差的平方和)的簇集。這種策略簡單，但是效果可能不好，這取決於數據集和尋找的簇的個數。

第二種有效的方法是，取一個樣本，並使用層次聚類技術對它聚類。從層次聚類中提取kk個簇，並用這些簇的質心作為初始質心。該方法通常很有效，但僅對下列情況有效：(1)樣本相對較小，例如數百到數千(層次聚類開銷較大)；(2) kk相對於樣本大小較小。

第三種選擇初始質心的方法，隨機地選擇第一個點，或取所有點的質心作為第一個點。然後，對於每個後繼初始質心，選擇離已經選取過的初始質心最遠的點。使用這種方法，確保了選擇的初始質心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用於點樣本。由於離群點很少(多了就不是離群點了)，它們多半不會在隨機樣本中出現。計算量也大幅減少。

第四種方法就是上面提到的canopy演算法。

4. 距離的度量

常用的距離度量方法包括：歐幾里得距離和餘弦相似度。兩者都是評定個體間差異的大小的。

歐氏距離是最常見的距離度量，而餘弦相似度則是最常見的相似度度量，很多的距離度量和相似度度量都是基於這兩者的變形和衍生，所以下面重點比較下兩者在衡量個體差異時實現方式和應用環境上的區別。

藉助三維坐標系來看下歐氏距離和餘弦相似度的區別：

從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標(即個體特徵維度的數值)直接相關；而餘弦相似度衡量的是空間向量的夾角，更加的是體現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標軸原點，那麼這個時候餘弦相似cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦相似度的不同之處。

根據歐氏距離和餘弦相似度各自的計算方式和衡量特徵，分別適用於不同的數據分析模型：歐氏距離能夠體現個體數值特徵的絕對差異，所以更多的用於需要從維度的數值大小中體現差異的分析，如使用用戶行為指標分析用戶價值的相似度或差異；而餘弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用於使用用戶對內容評分來區分用戶興趣的相似度和差異，同時修正了用戶間可能存在的度量標准不統一的問題(因為餘弦相似度對絕對數值不敏感)。

因為歐幾里得距離度量會受指標不同單位刻度的影響，所以一般需要先進行標准化，同時距離越大，個體間差異越大；空間向量餘弦夾角的相似度度量不會受指標刻度的影響，餘弦值落於區間[-1,1]，值越大，差異越小。但是針對具體應用，什麼情況下使用歐氏距離，什麼情況下使用餘弦相似度？

從幾何意義上來說，n維向量空間的一條線段作為底邊和原點組成的三角形，其頂角大小是不確定的。也就是說對於兩條空間向量，即使兩點距離一定，他們的夾角餘弦值也可以隨意變化。感性的認識，當兩用戶評分趨勢一致時，但是評分值差距很大，餘弦相似度傾向給出更優解。舉個極端的例子，兩用戶只對兩件商品評分，向量分別為(3,3)和(5,5)，這兩位用戶的認知其實是一樣的，但是歐式距離給出的解顯然沒有餘弦值合理。

5. 聚類效果評估

我們把機器學習定義為對系統的設計和學習，通過對經驗數據的學習，將任務效果的不斷改善作為一個度量標准。Kmeans是一種非監督學習，沒有標簽和其他信息來比較聚類結果。但是，我們還是有一些指標可以評估演算法的性能。我們已經介紹過類的畸變程度的度量方法。本節為將介紹另一種聚類演算法效果評估方法稱為輪廓系數(Silhouette Coefficient)。輪廓系數是類的密集與分散程度的評價指標。它會隨著類的規模增大而增大。彼此相距很遠，本身很密集的類，其輪廓系數較大，彼此集中，本身很大的類，其輪廓系數較小。輪廓系數是通過所有樣本計算出來的，計算每個樣本分數的均值，計算公式如下：

aa是每一個類中樣本彼此距離的均值，bb是一個類中樣本與其最近的那個類的所有樣本的距離的均值。

6. Kmeans演算法流程

輸入：聚類個數k，數據集XmxnXmxn。 

輸出：滿足方差最小標準的k個聚類。

(1) 選擇k個初始中心點，例如c[0]=X[0] , … , c[k-1]=X[k-1]；

(2) 對於X[0]….X[n]，分別與c[0]…c[k-1]比較，假定與c[i]差值最少，就標記為i；

(3) 對於所有標記為i點，重新計算c[i]={ 所有標記為i的樣本的每個特徵的均值}；

(4) 重復(2)(3)，直到所有c[i]值的變化小於給定閾值或者達到最大迭代次數。

Kmeans的時間復雜度：O(tkmn)，空間復雜度：O((m+k)n)。其中，t為迭代次數，k為簇的數目，m為樣本數，n為特徵數。

7. Kmeans演算法優缺點

7.1 優點

(1). 演算法原理簡單。需要調節的超參數就是一個k。

(2). 由具有出色的速度和良好的可擴展性。

7.2 缺點

(1). 在 Kmeans 演算法中 kk 需要事先確定，這個 kk 值的選定有時候是比較難確定。

(2). 在 Kmeans 演算法中，首先需要初始k個聚類中心，然後以此來確定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果。多設置一些不同的初值，對比最後的運算結果，一直到結果趨於穩定結束。

(3). 該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，因此當數據量非常大時，演算法的時間開銷是非常大的。

(4). 對離群點很敏感。

(5). 從數據表示角度來說，在 Kmeans 中,我們用單個點來對 cluster 進行建模，這實際上是一種最簡化的數據建模形式。這種用點來對 cluster 進行建模實際上就已經假設了各 cluster的數據是呈圓形(或者高維球形)或者方形等分布的。不能發現非凸形狀的簇。但在實際生活中，很少能有這種情況。所以在 GMM 中，使用了一種更加一般的數據表示，也就是高斯分布。

(6). 從數據先驗的角度來說，在 Kmeans 中,我們假設各個 cluster 的先驗概率是一樣的,但是各個 cluster 的數據量可能是不均勻的。舉個例子,cluster A 中包含了10000個樣本,cluster B 中只包含了100個。那麼對於一個新的樣本,在不考慮其與A cluster、 B cluster 相似度的情況,其屬於 cluster A 的概率肯定是要大於 cluster B的。

(7). 在 Kmeans 中，通常採用歐氏距離來衡量樣本與各個 cluster 的相似度。這種距離實際上假設了數據的各個維度對於相似度的衡量作用是一樣的。但在 GMM 中，相似度的衡量使用的是後驗概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通過引入協方差矩陣,我們就可以對各維度數據的不同重要性進行建模。

(8). 在 Kmeans 中，各個樣本點只屬於與其相似度最高的那個 cluster ，這實際上是一種 hard clustering 。

針對Kmeans演算法的缺點，很多前輩提出了一些改進的演算法。例如 K-modes 演算法，實現對離散數據的快速聚類，保留了Kmeans演算法的效率同時將Kmeans的應用范圍擴大到離散數據。還有K-Prototype演算法，可以對離散與數值屬性兩種混合的數據進行聚類，在K-prototype中定義了一個對數值與離散屬性都計算的相異性度量標准。當然還有其它的一些演算法，這里我 就不一一列舉了。

Kmeans 與 GMM 更像是一種 top-down 的思想，它們首先要解決的問題是，確定 cluster 數量，也就是 k 的取值。在確定了 k 後,再來進行數據的聚類。而 hierarchical clustering 則是一種 bottom-up 的形式，先有數據，然後通過不斷選取最相似的數據進行聚類。

『伍』 ECC 演算法簡介

與 RSA（Ron Rivest，Adi Shamir，Len Adleman 三位天才的名字）一樣，ECC（Elliptic Curves Cryptography，橢圓曲線加密）也屬於公開密鑰演算法。

一、從平行線談起

平行線，永不相交。沒有人懷疑把：）不過到了近代這個結論遭到了質疑。平行線會不會在很遠很遠的地方相交了？事實上沒有人見到過。所以「平行線，永不相交」只是假設（大家想想初中學習的平行公理，是沒有證明的）。

既然可以假設平行線永不相交，也可以假設平行線在很遠很遠的地方相交了。即平行線相交於無窮遠點P∞（請大家閉上眼睛，想像一下那個無窮遠點P∞，P∞是不是很虛幻，其實與其說數學鍛煉人的抽象能力，還不如說是鍛煉人的想像力）。

給個圖幫助理解一下：

直線上出現P∞點，所帶來的好處是所有的直線都相交了，且只有一個交點。這就把直線的平行與相交統一了。為與無窮遠點相區別把原來平面上的點叫做平常點。

以下是無窮遠點的幾個性質。

直線 L 上的無窮遠點只能有一個。（從定義可直接得出）

平面上一組相互平行的直線有公共的無窮遠點。（從定義可直接得出）

平面上任何相交的兩直線 L1、L2 有不同的無窮遠點。（否則 L1 和 L2 有公共的無窮遠點 P ，則 L1 和 L2 有兩個交點 A、P，故假設錯誤。）

平面上全體無窮遠點構成一條無窮遠直線。（自己想像一下這條直線吧）

平面上全體無窮遠點與全體平常點構成射影平面。

二、射影平面坐標系

射影平面坐標系是對普通平面直角坐標系（就是我們初中學到的那個笛卡兒平面直角坐標系）的擴展。我們知道普通平面直角坐標系沒有為無窮遠點設計坐標，不能表示無窮遠點。為了表示無窮遠點，產生了射影平面坐標系，當然射影平面坐標系同樣能很好的表示舊有的平常點（數學也是「向下兼容」的）。

我們對普通平面直角坐標繫上的點A的坐標（x, y）做如下改造：

令 x=X/Z ，y=Y/Z（Z≠0）；則 A 點可以表示為（X:Y:Z）。

變成了有三個參量的坐標點，這就對平面上的點建立了一個新的坐標體系。

例 2.1：求點（1,2）在新的坐標體系下的坐標。

解：

∵X/Z=1 ，Y/Z=2（Z≠0）

∴X=Z，Y=2Z

∴坐標為（Z:2Z:Z），Z≠0。

即（1:2:1）（2:4:2）（1.2:2.4:1.2）等形如（Z:2Z:Z），Z≠0 的坐標，都是（1,2）在新的坐標體系下的坐標。

我們也可以得到直線的方程 aX+bY+cZ=0（想想為什麼？提示：普通平面直角坐標系下直線一般方程是 ax+by+c=0）。

新的坐標體系能夠表示無窮遠點么？那要讓我們先想想無窮遠點在哪裡。根據上一節的知識，我們知道無窮遠點是兩條平行直線的交點。那麼，如何求兩條直線的交點坐標？這是初中的知識，就是將兩條直線對應的方程聯立求解。

平行直線的方程是：

aX+bY+c1Z =0；

aX+bY+c2Z =0  (c1≠c2)； （為什麼？提示：可以從斜率考慮，因為平行線斜率相同）；

將二方程聯立，求解。有

c2Z= c1Z= -（aX+bY）

∵c1≠c2

∴Z=0 

∴aX+bY=0

所以無窮遠點就是這種形式（X：Y：0）表示。注意，平常點 Z≠0，無窮遠點 Z=0，因此無窮遠直線對應的方程是 Z=0。

例 2.2：求平行線 L1：X+2Y+3Z=0 與 L2：X+2Y+Z=0 相交的無窮遠點。

解：

因為 L1∥L2

所以有 Z=0， X+2Y=0

所以坐標為（-2Y:Y:0），Y≠0。

即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0），Y≠0 的坐標，都表示這個無窮遠點。

看來這個新的坐標體系能夠表示射影平面上所有的點，我們就把這個能夠表示射影平面上所有點的坐標體系叫做射影平面坐標系。

練習：

1、求點A(2,4) 在射影平面坐標系下的坐標。

2、求射影平面坐標系下點(4.5:3:0.5)，在普通平面直角坐標系下的坐標。

3、求直線X+Y+Z=0上無窮遠點的坐標。

4、判斷：直線aX+bY+cZ=0上的無窮遠點 和 無窮遠直線與直線aX+bY=0的交點，是否是同一個點？

三、橢圓曲線

上一節，我們建立了射影平面坐標系，這一節我們將在這個坐標系下建立橢圓曲線方程。因為我們知道，坐標中的曲線是可以用方程來表示的（比如：單位圓方程是 x2+y2=1）。橢圓曲線是曲線，自然橢圓曲線也有方程。

橢圓曲線的定義：

一條橢圓曲線是在射影平面上滿足如下方程的所有點的集合，且曲線上的每個點都是非奇異（或光滑）的。

Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3                 [3-1]

定義詳解：

Y2Z+a1XYZ+a3YZ2 = X3+a2X2Z+a4XZ2+a6Z3 是 Weierstrass 方程（維爾斯特拉斯，Karl Theodor Wilhelm Weierstrass,1815-1897），是一個齊次方程。

橢圓曲線的形狀，並不是橢圓的。只是因為橢圓曲線的描述方程，類似於計算一個橢圓周長的方程（計算橢圓周長的方程，我沒有見過，而對橢圓線 積分 （設密度為1）是求不出來的），故得名。

我們來看看橢圓曲線是什麼樣的。

所謂「非奇異」或「光滑」的，在數學中是指曲線上任意一點的偏導數 Fx(x,y,z)，Fy(x,y,z)，Fz(x,y,z) 不能同時為0。如果你沒有學過高等數學，可以這樣理解這個詞，即滿足方程的任意一點都存在切線。下面兩個方程都不是橢圓曲線，盡管他們是方程 [3-1] 的形式，因為他們在（0:0:1）點處（即原點）沒有切線。

橢圓曲線上有一個無窮遠點O∞（0:1:0），因為這個點滿足方程[3-1]。

知道了橢圓曲線上的無窮遠點。我們就可以把橢圓曲線放到普通平面直角坐標繫上了。因為普通平面直角坐標系只比射影平面坐標系少無窮遠點。我們在普通平面直角坐標繫上，求出橢圓曲線上所有平常點組成的曲線方程，再加上無窮遠點O∞（0:1:0），不就構成橢圓曲線了么？

我們設 x=X/Z，y=Y/Z 代入方程 [3-1] 得到：

y2+a1xy+a3y = x3+a2x2+a4x+a6                            [3-2]

也就是說滿足方程 [3-2] 的光滑曲線加上一個無窮遠點O∞，組成了橢圓曲線。為了方便運算，表述，以及理解，今後論述橢圓曲線將主要使用 [3-2] 的形式。

本節的最後，我們談一下求橢圓曲線一點的切線斜率問題。由橢圓曲線的定義可以知道，橢圓曲線是光滑的，所以橢圓曲線上的平常點都有切線。而切線最重要的一個參數就是斜率 k 。

例 3.1：求橢圓曲線方程 y2+a1xy+a3y=x3+a2x2+a4x+a6上，平常點 A(x,y) 的切線的斜率 k 。

解：

令

F(x,y)= y2+a1xy+a3y-x3-a2x2-a4x-a6

求偏導數

Fx(x,y)= a1y-3x2-2a2x-a4

Fy(x,y)= 2y+a1x+a3

則導數為：

f'(x)=- Fx(x,y)/ Fy(x,y)=-( a1y-3x2-2a2x-a4)/(2y+a1x +a3) = (3x2+2a2x+a4-a1y) /(2y+a1x +a3)

所以

k=(3x2+2a2x+a4-a1y) /(2y+a1x +a3)             [3-3]

看不懂解題過程沒有關系，記住結論[3-3]就可以了。

練習：      

1、將給出圖例的橢圓曲線方程Y2Z=X3-XZ2 和Y2Z=X3+XZ2+Z3轉換成普通平面直角坐標繫上的方程。

四、橢圓曲線上的加法

上一節，我們已經看到了橢圓曲線的圖象，但點與點之間好象沒有什麼聯系。我們能不能建立一個類似於在實數軸上加法的運演算法則呢？天才的數學家找到了這一運演算法則

自從近世紀代數學引入了群、環、域的概念，使得代數運算達到了高度的統一。比如數學家總結了普通加法的主要特徵，提出了加群（也叫交換群，或 Abel（阿貝爾）群），在加群的眼中。實數的加法和橢圓曲線的上的加法沒有什麼區別。這也許就是數學抽象把。關於群以及加群的具體概念請參考近世代數方面的數學書。

運演算法則：任意取橢圓曲線上兩點 P、Q （若 P、Q兩點重合，則做 P 點的切線）做直線交於橢圓曲線的另一點 R』，過 R』 做 y 軸的平行線交於 R。我們規定 P+Q=R。（如圖）

法則詳解：

這里的 + 不是實數中普通的加法，而是從普通加法中抽象出來的加法，他具備普通加法的一些性質，但具體的運演算法則顯然與普通加法不同。

根據這個法則，可以知道橢圓曲線無窮遠點 O∞ 與橢圓曲線上一點 P 的連線交於 P』，過 P』 作 y 軸的平行線交於 P，所以有 無窮遠點 O∞ + P = P 。這樣，無窮遠點 O∞ 的作用與普通加法中零的作用相當（0+2=2），我們把無窮遠點 O∞ 稱為零元。同時我們把 P』 稱為 P 的負元（簡稱，負P；記作，-P）。（參見下圖）

根據這個法則，可以得到如下結論 ：如果橢圓曲線上的三個點 A、B、C，處於同一條直線上，那麼他們的和等於零元，即 A+B+C= O∞

k 個相同的點 P 相加，我們記作 kP。如下圖：P+P+P = 2P+P = 3P。

下面，我們利用 P、Q點的坐標 (x1,y1)，(x2,y2)，求出 R=P+Q 的坐標 (x4,y4)。

例 4.1：求橢圓曲線方程 y2+a1xy+a3y=x3+a2x2+a4x+a6 上，平常點 P(x1,y1)，Q(x2,y2) 的和 R(x4,y4) 的坐標。

解：

（1）先求點 -R(x3,y3)

因為 P, Q, -R 三點共線，故設共線方程為

y=kx+b

其中，若 P≠Q (P,Q兩點不重合)，則直線斜率

k=(y1-y2)/(x1-x2)

若 P=Q (P,Q兩點重合)，則直線為橢圓曲線的切線，

故由例 3.1 可知：

k=(3x2+2a2x+a4 -a1y) /(2y+a1x+a3)

因此 P, Q, -R 三點的坐標值就是以下方程組的解：

y2+a1xy+a3y=x3+a2x2+a4x+a6                                   [1]

y=(kx+b)                                                                      [2]

將 [2] 代入[1] 有

(kx+b)2+a1x(kx+b)+a3(kx+b) =x3+a2x2+a4x+a6        [3]

對 [3] 化為一般方程，根據三次方程根與系數關系（若方程x³＋ax²＋bx＋c=0 的三個根是 x1、x2、x3，則： x1＋x2＋x3=－a，x1x2＋x2x3＋x3x1=b，x1x2x2=－c）

所以

-(x1+x2+x3)=a2-ka1-k2

x3=k2+ka1+a2+x1+x2    --------------------- 求出點 -R 的橫坐標

因為

k=(y1-y3)/(x1-x3)

故

y3=y1-k(x1-x3)    ------------------------------ 求出點 -R 的縱坐標

（2）利用 -R 求 R

顯然有

x4=x3=k2+ka1+a2+x1+x2   -------------- 求出點 R 的橫坐標

而 y3 y4 為 x=x4 時 方程 y2+a1xy+a3y=x3+a2x2+a4x+a6 的解化為一般方程 y2+(a1x+a3)y-(x3+a2x2+a4x+a6)=0 , 根據二次方程根與系數關系（如果方程 ax²＋bx＋c=0 的兩根為 x1、x2，那麼 x1+x2=-b/a，x1x2=c/a）

得：

-(a1x+a3)=y3+y4

故

y4=-y3-(a1x+a3)=k(x1-x4)-y1-(a1x4+a3)   ----- 求出點 R 的縱坐標

即：

x4=k2+ka1+a2+x1+x2

y4=k(x1-x4)-y1-a1x4-a3

本節的最後，提醒大家注意一點，以前提供的圖像可能會給大家產生一種錯覺，即橢圓曲線是關於 x 軸對稱的。事實上，橢圓曲線並不一定關於 x 軸對稱。如下圖的 y2-xy=x3+1

五、密碼學中的橢圓曲線

我們現在基本上對橢圓曲線有了初步的認識，這是值得高興的。但請大家注意，前面學到的橢圓曲線是連續的，並不適合用於加密。所以，我們必須把橢圓曲線變成離散的點。

讓我們想一想，為什麼橢圓曲線為什麼連續？是因為橢圓曲線上點的坐標，是實數的（也就是說前面講到的橢圓曲線是定義在實數域上的），實數是連續的，導致了曲線的連續。因此，我們要把橢圓曲線定義在有限域上（顧名思義，有限域是一種只有由有限個元素組成的域）。

域的概念是從我們的有理數，實數的運算中抽象出來的，嚴格的定義請參考近世代數方面的數。簡單的說，域中的元素同有理數一樣，有自己得加法、乘法、除法、單位元(1)，零元(0),並滿足交換率、分配率。

下面，我們給出一個有限域 Fp，這個域只有有限個元素。

Fp 中只有 p（p為素數）個元素 0, 1, 2 …… p-2, p-1

Fp 的加法（a+b）法則是 a+b≡c (mod p) ，即 (a+c)÷p 的余數和 c÷p 的余數相同。

Fp 的乘法（a×b）法則是 a×b≡c (mod p)

Fp 的除法（a÷b）法則是 a/b≡c (mod p)，即 a×b-1≡c  (mod p) ，b-1 也是一個 0 到 p-1 之間的整數，但滿足 b×b-1≡1 (mod p)；具體求法可以參考初等數論。

Fp 的單位元是 1，零元是 0。

同時，並不是所有的橢圓曲線都適合加密。y2=x3+ax+b是一類可以用來加密的橢圓曲線，也是最為簡單的一類。下面我們就把 y2=x3+ax+b 這條曲線定義在 Fp 上：

選擇兩個滿足下列條件的小於 p ( p 為素數) 的非負整數 a、b

4a3+27b2≠0  (mod p)

則滿足下列方程的所有點 (x,y)，再加上 無窮遠點 O∞ ，構成一條橢圓曲線。

y2=x3+ax+b  (mod p)

其中 x,y 屬於 0 到 p-1 間的整數，並將這條橢圓曲線記為 Ep(a,b)。

我們看一下 y2=x3+x+1  (mod 23) 的圖像

是不是覺得不可思議？橢圓曲線，怎麼變成了這般模樣，成了一個一個離散的點？橢圓曲線在不同的數域中會呈現出不同的樣子，但其本質仍是一條橢圓曲線。舉一個不太恰當的例子，好比是水，在常溫下，是液體；到了零下，水就變成冰，成了固體；而溫度上升到一網路，水又變成了水蒸氣。但其本質仍是 H2O。

Fp上的橢圓曲線同樣有加法，但已經不能給以幾何意義的解釋。不過，加法法則和實數域上的差不多，請讀者自行對比。

1. 無窮遠點 O∞ 是零元，有 O∞ + O∞ = O∞，O∞ + P = P

2. P(x,y) 的負元是 (x,-y)，有 P + (-P) = O∞

3. P(x1,y1), Q(x2,y2) 的和 R(x3,y3) 有如下關系：

x3≡k2-x1-x2(mod p) 

y3≡k(x1-x3)-y1(mod p)

    其中

若 P=Q 則 k=(3x2+a)/2y1 

若 P≠Q 則 k=(y2-y1)/(x2-x1)

例 5.1：已知 E23(1,1) 上兩點 P(3,10)，Q(9,7)，求 (1)-P，(2)P+Q，(3) 2P。

解：

(1)  –P的值為(3,-10)

(2)  k=(7-10)/(9-3)=-1/2

2 的乘法逆元為 12， 因為 2*12≡1 (mod 23)

k≡-1*12 (mod 23)

故 k=11

x=112-3-9=109≡17 (mod 23)

y=11[3-(-6)]-10=89≡20 (mod 23)

故 P+Q 的坐標為 (17,20)

3)  k=[3(32)+1]/(2*10)=1/4≡6 (mod 23)

x=62-3-3=30≡20 (mod 23)

y=6(3-7)-10=-34≡12 (mod 23)

故 2P 的坐標為 (7,12)

最後，我們講一下橢圓曲線上的點的階。如果橢圓曲線上一點 P，存在最小的正整數 n，使得數乘 nP=O∞，則將 n 稱為 P 的階，若 n 不存在，我們說 P 是無限階的。 事實上，在有限域上定義的橢圓曲線上所有的點的階 n 都是存在的（證明，請參考近世代數方面的書）

練習：

1． 求出 E11(1,6) 上所有的點。

2．已知 E11(1,6) 上一點 G(2,7)，求 2G 到 13G 所有的值。

六、橢圓曲線上簡單的加密/解密

公開密鑰演算法總是要基於一個數學上的難題。比如 RSA 依據的是：給定兩個素數 p、q 很容易相乘得到 n，而對 n 進行因式分解卻相對困難。那橢圓曲線上有什麼難題呢？

考慮如下等式：

K=kG     [其中 K, G為 Ep(a,b) 上的點，k 為小於 n（n 是點 G 的階）的整數]

不難發現，給定 k 和 G，根據加法法則，計算 K 很容易；但給定 K 和 G，求 k 就相對困難了。這就是橢圓曲線加密演算法採用的難題。我們把點 G 稱為基點（base point），k（key point）就是私有密鑰。

現在我們描述一個利用橢圓曲線進行加密通信的過程：

1、用戶 A 選定一條橢圓曲線 Ep(a,b)，並取橢圓曲線上一點，作為基點 G。

2、用戶 A 選擇一個私有密鑰 k，並生成公開密鑰 K=kG。

3、用戶 A 將 Ep(a,b) 和點 K，G 傳給用戶 B。

4、用戶 B 接到信息後，將待傳輸的明文編碼到 Ep(a,b) 上一點 M（編碼方法很多，這里不作討論），並產生一個隨機整數 r（random）。

5、用戶 B 計算點 C1=M+rK；C2=rG。

6、用戶 B 將 C1、C2 傳給用戶A。

7、用戶 A 接到信息後，計算 C1-kC2，結果就是點 M。因為 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M ，再對點 M 進行解碼就可以得到明文。

在這個加密通信中，如果有一個偷窺者 H ，他只能看到 Ep(a,b)、K、G、C1、C2 而通過 K、G 求 k 或通過 C2、G 求 r 都是相對困難的。因此，H 無法得到 A、B 間傳送的明文信息。

密碼學中，描述一條 Fp 上的橢圓曲線，常用到六個參量：

T=(p,a,b,G,n,h)

p 、a 、b 用來確定一條橢圓曲線，G 為基點，n 為點 G 的階，h 是橢圓曲線上所有點的個數 m 與 n 相除的整數部分。這幾個參量取值的選擇，直接影響了加密的安全性。參量值一般要求滿足以下幾個條件：

1、p 當然越大越安全，但越大，計算速度會變慢，200 位左右可以滿足一般安全要求；

2、p≠n×h；

3、pt≠1 (mod n)，1≤t<20；

4、4a3+27b2≠0 (mod p)；

5、n 為素數；

6、h≤4。

七、橢圓曲線簽名在軟體保護的應用

我們知道將公開密鑰演算法作為軟體注冊演算法的好處是：黑客很難通過跟蹤驗證演算法得到注冊機。下面，將簡介一種利用 Fp(a,b) 橢圓曲線進行軟體注冊的方法。

軟體作者按如下方法製作注冊機（也可稱為簽名過程）

1、選擇一條橢圓曲線 Ep(a,b) 和基點 G；

2、選擇私有密鑰 k；

3、產生一個隨機整數 r ；

4、將用戶名和點 R 的坐標值 x,y 作為參數，計算 SHA（Secure Hash Algorithm 安全散列演算法，類似於 MD5）值，即 Hash=SHA(username,x,y)；

5、計算 sn≡r - Hash * k (mod n)

6、將 sn 和 Hash 作為用戶名 username 的序列號

軟體驗證過程如下：（軟體中存有橢圓曲線 Ep(a,b) 和基點 G 以及公開密鑰 K）

1、從用戶輸入的序列號中，提取 sn 以及 Hash；

2、計算點 R≡sn*G+Hash*K ( mod p )，如果 sn、Hash 正確，其值等於軟體作者簽名過程中點 R(x,y) 的坐標，

因為 sn≡r-Hash*k （mod n）

所以 sn*G+Hash*K=(r-Hash*k)*G+Hash*K=rG-Hash*kG+Hash*K=rG-Hash*K+Hash*K=rG=R；

3、將用戶名和點 R 的坐標值 x,y 作為參數，計算 H=SHA(username,x,y)；

4、如果 H=Hash 則注冊成功，如果 H≠Hash ，則注冊失敗（為什麼？提示注意點 R 與 Hash 的關聯性）。

簡單對比一下兩個過程：

作者簽名用到了：橢圓曲線 Ep(a,b)，基點 G，私有密鑰 k，及隨機數 r。

軟體驗證用到了：橢圓曲線 Ep(a,b)，基點 G，公開密鑰 K。

黑客要想製作注冊機，只能通過軟體中的 Ep(a,b)，點 G，公開密鑰 K ，並利用 K=kG 這個關系獲得 k 才可以，而求 k 是很困難的。

練習：

下面也是一種常於軟體保護的注冊演算法，請認真閱讀，並試回答簽名過程與驗證過程都用到了那些參數，黑客想製作注冊機，應該如何做。

軟體作者按如下方法製作注冊機（也可稱為簽名過程）

1、選擇一條橢圓曲線 Ep(a,b)，和基點 G；

2、選擇私有密鑰 k；

3、產生一個隨機整數 r；

4、將用戶名作為參數，計算 Hash=SHA(username)；

5、計算 x』=x  (mod n)

6、計算 sn≡(Hash+x』*k)/r (mod n)

7、將 sn 和 x』 作為用戶名 username 的序列號

軟體驗證過程如下：(軟體中存有橢圓曲線 Ep(a,b) 和基點 G 以及公開密鑰 K)

1、從用戶輸入的序列號中，提取 sn 以及 x』；

2、將用戶名作為參數，計算 Hash=SHA(username)；

3、計算 R=(Hash*G+x』*K)/sn，如果 sn、Hash 正確，其值等於軟體作者簽名過程中點 R(x,y)

因為 sn≡(Hash+x』*k)/r (mod n)

所以 (Hash*G+x』*K)/sn=(Hash*G+x』*K)/[(Hash+x』*k)/r]=(Hash*G+x』*K)/[(Hash*G+x』*k*G)/(rG)]=rG*[(Hash*G+x』*K)/(Hash*G+x』*K)]=rG=R (mod p)

4、v≡x (mod n)

5、如果 v=x』 則注冊成功。如果 v≠x』 ，則注冊失敗。

主要參考文獻

張禾瑞，《近世代數基礎》，高等 教育 出版社，1978

閔嗣鶴 嚴士健，《初等數論》，高等教育出版社，1982

段雲所，《網路信息安全》第三講，北大計算機系

Michael Rosing ，chapter5《Implementing Elliptic Curve Cryptography》，Softbound，1998

《SEC 1: Elliptic Curve Cryptography》，Certicom Corp.，2000

《IEEE P1363a / D9》，2001

『陸』 人工智慧演算法簡介

人工智慧的三大基石—演算法、數據和計算能力，演算法作為其中之一，是非常重要的，那麼人工智慧都會涉及哪些演算法呢？不同演算法適用於哪些場景呢？

一、按照模型訓練方式不同可以分為監督學習（Supervised Learning），無監督學習（Unsupervised Learning）、半監督學習（Semi-supervised Learning）和強化學習（Reinforcement Learning）四大類。

常見的監督學習演算法包含以下幾類：
（1）人工神經網路（Artificial Neural Network）類：反向傳播（Backpropagation）、波爾茲曼機（Boltzmann Machine）、卷積神經網路（Convolutional Neural Network）、Hopfield網路（hopfield Network）、多層感知器（Multilyer Perceptron）、徑向基函數網路（Radial Basis Function Network，RBFN）、受限波爾茲曼機（Restricted Boltzmann Machine）、回歸神經網路（Recurrent Neural Network，RNN）、自組織映射（Self-organizing Map，SOM）、尖峰神經網路（Spiking Neural Network）等。
（2）貝葉斯類（Bayesin）：樸素貝葉斯（Naive Bayes）、高斯貝葉斯（Gaussian Naive Bayes）、多項樸素貝葉斯（Multinomial Naive Bayes）、平均-依賴性評估（Averaged One-Dependence Estimators，AODE）
貝葉斯信念網路（Bayesian Belief Network，BBN）、貝葉斯網路（Bayesian Network，BN）等。
（3）決策樹（Decision Tree）類：分類和回歸樹（Classification and Regression Tree，CART）、迭代Dichotomiser3（Iterative Dichotomiser 3， ID3）,C4.5演算法（C4.5 Algorithm）、C5.0演算法（C5.0 Algorithm）、卡方自動交互檢測（Chi-squared Automatic Interaction Detection，CHAID）、決策殘端（Decision Stump）、ID3演算法（ID3 Algorithm）、隨機森林（Random Forest）、SLIQ（Supervised Learning in Quest）等。
（4）線性分類器（Linear Classifier）類：Fisher的線性判別（Fisher』s Linear Discriminant）
線性回歸（Linear Regression）、邏輯回歸（Logistic Regression）、多項邏輯回歸（Multionmial Logistic Regression）、樸素貝葉斯分類器（Naive Bayes Classifier）、感知（Perception）、支持向量機（Support Vector Machine）等。

常見的無監督學習類演算法包括：
（1） 人工神經網路（Artificial Neural Network）類：生成對抗網路（Generative Adversarial Networks，GAN），前饋神經網路（Feedforward Neural Network）、邏輯學習機（Logic Learning Machine）、自組織映射（Self-organizing Map）等。
（2） 關聯規則學習（Association Rule Learning）類：先驗演算法（Apriori Algorithm）、Eclat演算法（Eclat Algorithm）、FP-Growth演算法等。
（3）分層聚類演算法（Hierarchical Clustering）：單連鎖聚類（Single-linkage Clustering），概念聚類（Conceptual Clustering）等。
（4）聚類分析（Cluster analysis）：BIRCH演算法、DBSCAN演算法，期望最大化（Expectation-maximization，EM）、模糊聚類（Fuzzy Clustering）、K-means演算法、K均值聚類（K-means Clustering）、K-medians聚類、均值漂移演算法（Mean-shift）、OPTICS演算法等。
（5）異常檢測（Anomaly detection）類：K最鄰近（K-nearest Neighbor，KNN）演算法，局部異常因子演算法（Local Outlier Factor，LOF）等。

常見的半監督學習類演算法包含：生成模型（Generative Models）、低密度分離（Low-density Separation）、基於圖形的方法（Graph-based Methods）、聯合訓練（Co-training）等。

常見的強化學習類演算法包含：Q學習（Q-learning）、狀態-行動-獎勵-狀態-行動（State-Action-Reward-State-Action，SARSA）、DQN（Deep Q Network）、策略梯度演算法（Policy Gradients）、基於模型強化學習（Model Based RL）、時序差分學習（Temporal Different Learning）等。

常見的深度學習類演算法包含：深度信念網路（Deep Belief Machines）、深度卷積神經網路（Deep Convolutional Neural Networks）、深度遞歸神經網路（Deep Recurrent Neural Network）、分層時間記憶（Hierarchical Temporal Memory，HTM）、深度波爾茲曼機（Deep Boltzmann Machine，DBM）、棧式自動編碼器（Stacked Autoencoder）、生成對抗網路（Generative Adversarial Networks）等。

二、按照解決任務的不同來分類，粗略可以分為二分類演算法（Two-class Classification）、多分類演算法（Multi-class Classification）、回歸演算法（Regression）、聚類演算法（Clustering）和異常檢測（Anomaly Detection）五種。
1.二分類（Two-class Classification）
（1）二分類支持向量機（Two-class SVM）：適用於數據特徵較多、線性模型的場景。
（2）二分類平均感知器（Two-class Average Perceptron）：適用於訓練時間短、線性模型的場景。
（3）二分類邏輯回歸（Two-class Logistic Regression）：適用於訓練時間短、線性模型的場景。
（4）二分類貝葉斯點機（Two-class Bayes Point Machine）：適用於訓練時間短、線性模型的場景。（5）二分類決策森林（Two-class Decision Forest）：適用於訓練時間短、精準的場景。
（6）二分類提升決策樹（Two-class Boosted Decision Tree）：適用於訓練時間短、精準度高、內存佔用量大的場景
（7）二分類決策叢林（Two-class Decision Jungle）：適用於訓練時間短、精確度高、內存佔用量小的場景。
（8）二分類局部深度支持向量機（Two-class Locally Deep SVM）：適用於數據特徵較多的場景。
（9）二分類神經網路（Two-class Neural Network）：適用於精準度高、訓練時間較長的場景。

解決多分類問題通常適用三種解決方案：第一種，從數據集和適用方法入手，利用二分類器解決多分類問題；第二種，直接使用具備多分類能力的多分類器；第三種，將二分類器改進成為多分類器今兒解決多分類問題。
常用的演算法：
（1）多分類邏輯回歸（Multiclass Logistic Regression）：適用訓練時間短、線性模型的場景。
（2）多分類神經網路（Multiclass Neural Network）：適用於精準度高、訓練時間較長的場景。
（3）多分類決策森林（Multiclass Decision Forest）：適用於精準度高，訓練時間短的場景。
（4）多分類決策叢林（Multiclass Decision Jungle）：適用於精準度高，內存佔用較小的場景。
（5）「一對多」多分類（One-vs-all Multiclass）：取決於二分類器效果。

回歸
回歸問題通常被用來預測具體的數值而非分類。除了返回的結果不同，其他方法與分類問題類似。我們將定量輸出，或者連續變數預測稱為回歸；將定性輸出，或者離散變數預測稱為分類。長巾的演算法有：
（1）排序回歸（Ordinal Regression）：適用於對數據進行分類排序的場景。
（2）泊松回歸（Poission Regression）：適用於預測事件次數的場景。
（3）快速森林分位數回歸（Fast Forest Quantile Regression）：適用於預測分布的場景。
（4）線性回歸（Linear Regression）：適用於訓練時間短、線性模型的場景。
（5）貝葉斯線性回歸（Bayesian Linear Regression）：適用於線性模型，訓練數據量較少的場景。
（6）神經網路回歸（Neural Network Regression）：適用於精準度高、訓練時間較長的場景。
（7）決策森林回歸（Decision Forest Regression）：適用於精準度高、訓練時間短的場景。
（8）提升決策樹回歸（Boosted Decision Tree Regression）：適用於精確度高、訓練時間短、內存佔用較大的場景。

聚類
聚類的目標是發現數據的潛在規律和結構。聚類通常被用做描述和衡量不同數據源間的相似性，並把數據源分類到不同的簇中。
（1）層次聚類（Hierarchical Clustering）：適用於訓練時間短、大數據量的場景。
（2）K-means演算法：適用於精準度高、訓練時間短的場景。
（3）模糊聚類FCM演算法（Fuzzy C-means，FCM）：適用於精確度高、訓練時間短的場景。
（4）SOM神經網路（Self-organizing Feature Map，SOM）：適用於運行時間較長的場景。
異常檢測
異常檢測是指對數據中存在的不正常或非典型的分體進行檢測和標志，有時也稱為偏差檢測。
異常檢測看起來和監督學習問題非常相似，都是分類問題。都是對樣本的標簽進行預測和判斷，但是實際上兩者的區別非常大，因為異常檢測中的正樣本（異常點）非常小。常用的演算法有：
（1）一分類支持向量機（One-class SVM）：適用於數據特徵較多的場景。
（2）基於PCA的異常檢測（PCA-based Anomaly Detection）：適用於訓練時間短的場景。

常見的遷移學習類演算法包含：歸納式遷移學習（Inctive Transfer Learning） 、直推式遷移學習（Transctive Transfer Learning）、無監督式遷移學習（Unsupervised Transfer Learning）、傳遞式遷移學習（Transitive Transfer Learning）等。

演算法的適用場景：
需要考慮的因素有：
（1）數據量的大小、數據質量和數據本身的特點
（2）機器學習要解決的具體業務場景中問題的本質是什麼？
（3）可以接受的計算時間是什麼？
（4）演算法精度要求有多高？
————————————————

原文鏈接： https://blog.csdn.net/nfzhlk/article/details/82725769