① MapRece之金庸的江湖人物分析項目
通過一個綜合數據分析案例：」金庸的江湖——金庸武俠小說中的人物關系挖掘「，來學習和掌握MapRece程序設計。通過本項目的學習，可以體會如何使用MapRece完成一個綜合性的數據挖掘任務，包括全流程的數據預處理、數據分析、數據後處理等。
1 任務1 數據預處理
1.1 任務描述
從原始的金庸小說文本中，抽取出與人物互動相關的數據，而屏蔽掉與人物關系無關的文本內容，為後面的基於人物共現的分析做准備。
1.2 關鍵問題
1.2.1 中文分詞和人名提取
使用開源的Ansj_seg進行分詞。Ansj_seg不僅支持中文分詞，還允許用戶自定義詞典，在分詞前，將人名列表到添加用戶自定義的詞典，可以精確識別金庸武俠小說中的人名。
但實際測試的時候發現，Ansj_seg分詞會出現嚴重的歧義問題，比如「漢子」屬於人名列表中的人名(nr)，但Ansj_seg可能會錯誤地將它分類為名詞(n)。因此，如果根據詞性提取人名，會導致最後提取的人名太少。解決方法是在提取人名的時候，需要在將人名加入用戶自定義詞典的同時，構造一個包含所有人名的字典，對分詞的結果逐個進行測試，如果在字典里，就是人名。
1.2.2 文件傳輸
使用HDFS傳遞數據。考慮到人名列表文件已經存放在了HDFS里，所以使用HDFS的方式不需要移動人名列表文件，只需要在Configuration中設置文件在HDFS文件系統中的路徑，然後在Mapper的setup()函數里調用HDFS的函數獲取文件內容即可。
1.2.3 單詞同現演算法
兩個單詞近鄰關系的定義：實驗要求中已經說明，同現關系為一個段落。
段落劃分：非常慶幸的是，小說原文中一個段落就是一行，因此，不需要自己定義FileInputFormat和RecordReader。
1.3 MapRece設計
1.3.1 Mapper
1.3.2 Recer
1.3.3 Driver
2 任務2 特徵抽取：人物同現統計
2.1 任務描述
完成基於單詞同現演算法的人物同現統計。在人物同現分析中，如果兩個人在原文的同一段落中出現，則認為兩個人發生了一次同現關系。我們需要對人物之間的同現關系次數進行統計，同現關系次數越多，則說明兩人的關系越密切。
2.2 關鍵問題
2.2.1 人名冗餘
在同一段中，人名可能多次出現，任務一隻負責提取出所有的人名，沒有剔除多餘的人名，任務必須在輸出同現次數之前處理冗餘人名。我的做法是在Mapper中創建一個集合，把所有人名放入集合中，集合會自動剔除冗餘的人名。
2.2.2 同現次數統計
兩個人物之間應該輸出兩個鍵值對，如「狄雲」和「戚芳」，應該輸出「<狄雲，戚芳> 1」和「<戚芳，狄雲> 1」。多個段落中允許輸出相同的鍵值對，因此，Recer中需要整合具有相同鍵的輸出，輸出總的同現次數。
2.3 MapRece設計
2.3.1 Mapper
2.3.2 Recer
3 任務3 特徵處理：人物關系圖構建與特徵歸一化
3.1 任務描述
根據任務2人物之間的共現關系，生成人物之間的關系圖。人物關系使用鄰接表的形式表示，人物是頂點，人物之間關系是邊，兩個人的關系的密切程度由共現次數體現，共現次數越高，邊權重越高。另外需要對共現次數進行歸一化處理，確保某個頂點的出邊權重和為1。
3.2 關鍵問題
3.2.1 確保人物的所有鄰居輸出到相同結點處理
在Mapper結點將輸入的鍵值對「<狄雲，戚芳> 1」拆分，輸出新的鍵值對「<狄雲> 戚芳:1」，「狄雲」的所有鄰居會被分配給同一個Recer結點處理。
3.2.2 歸一化
在Recer結點首先統計該人物與所有鄰居同現的次數和sum，每個鄰居的的同現次數除以sum就得到共現概率。為了提高效率，在第一次遍歷鄰居的時候，可以把名字和共現次數保存在鏈表裡，避免重復處理字元串。
3.3 MapRece設計
3.3.1 Mapper
3.3.2 Recer
4.1 任務描述
經過數據預處理並獲得任務的關系圖之後，就可以對人物關系圖作數據分析，其中一個典型的分析任務是：PageRank 值計算。通過計算 PageRank，我們就可以定量地獲知金庸武俠江湖中的「主角」們是哪些。
4.2 PageRank原理
PageRank演算法由Google的兩位創始人佩奇和布林在研究網頁排序問題時提出，其核心思想是：如果一個網頁被很多其它網頁鏈接到，說明這個網頁很重要，它的PageRank值也會相應較高；如果一個PageRank值很高的網頁鏈接到另外某個網頁，那麼那個網頁的PageRank值也會相應地提高。
相應地，PageRank演算法應用到人物關系圖上可以這么理解：如果一個人物與多個人物存在關系連接，說明這個人物是重要的，其PageRank值響應也會較高；如果一個PageRank值很高的人物與另外一個人物之間有關系連接，那麼那個人物的PageRank值也會相應地提高。一個人物的PageRank值越高，他就越可能是小說中的主角。
PageRank有兩個比較常用的模型：簡單模型和隨機瀏覽模型。由於本次設計考慮的是人物關系而不是網頁跳轉，因此簡單模型比較合適。簡單模型的計算公式如下，其中Bi為所有連接到人物i的集合，Lj為認為人物j對外連接邊的總數：
在本次設計的任務3中，已經對每個人物的邊權值進行歸一化處理，邊的權值可以看做是對應連接的人物占總邊數的比例。設表示人物i在人物j所有邊中所佔的權重，則PageRank計算公式可以改寫為：
4.3.2 PageRanklter類
GraphBuilder將數據處理成可供迭代的格式，PageRank的迭代過程由PageRanklter類實現，包含一個Map和Rece過程。Map過程產生兩種類型的<key,value>：<人物名，PageRrank值>，<人物名，關系鏈表>。第一個人物名是關系鏈表中的各個鏈出人物名，其PR值由計算得到；第二個人物名是本身人物名，目的是為了保存該人物的鏈出關系，以保證完成迭代過程。以上面的輸出為例，則Map過程產生的鍵值對為<完顏萍, 1.0 0.005037>，<小龍女, 1.0 0.017632>，……，<一燈大師, #完顏萍:0.005037783;……>。
Rece過程將同一人物名的<key,value>匯聚在一起，如果value是PR值，則累加到sum變數；如果value是關系鏈表則保存為List。遍歷完迭代器里所有的元素後輸出鍵值對<人物名，sum#List>，這樣就完成了一次迭代過程。
PR值排名不變的比例隨迭代次數變化的關系圖如下，由於我們考慮的是找出小說中的主角，所以只要關心PR值前100名的人物的排名的變化情況，可以看到迭代次數在10以後，PR值排名不變的比例已經趨於穩定了，所以基於效率考慮，選取10作為PR的迭代次數。
4.3.3 PageRankViewer類
當所有迭代都完成後，我們就可以對所有人物的PageRank值進行排序，該過程由PageRankViewer類完成，包含一個Map和Rece過程。Map過程只提取迭代過程輸出結果中的人物名以及對應的PageRank值，並以PageRank值作為key，人物名作為value輸出。為了實現PageRank值從大到小排序，需要實現DescFloatComparator類來重寫compare方法以達成逆序排序。由於可能存在PageRank值相同的情況，所以還需要一個rece過程來把因PageRank值相同而匯聚到一起的人物名拆開並輸出。
PageRankMapper
PageRankRecer
Driver類
5.1 任務描述
標簽傳播（Label Propagation）是一種半監督的圖分析演算法，他能為圖上的頂點打標簽，進行圖頂點的聚類分析，從而在一張類似社交網路圖中完成社區發現。在人物關系圖中，通過標簽傳播演算法可以將關聯度比較大的人物分到同一標簽，可以直觀地分析人物間的關系。
5.2 標簽傳播演算法原理
標簽傳播演算法（Label Propagation Algorithm，後面簡稱LPA）是由Zhu等人於2002年提出，它是一種基於圖的半監督學習方法，其基本思路是用已標記節點的標簽信息去預測未標記節點的標簽信息。LPA基本過程為：（1）每個結點初始化一個特定的標簽值；（2）逐輪更新所有節點的標簽，直到所有節點的標簽不再發生變化為止。對於每一輪刷新，節點標簽的刷新規則如下：對於某一個節點，考察其所有鄰居節點的標簽，並進行統計，將出現個數最多的那個標簽賦值給當前節點。當個數最多的標簽不唯一時，隨機選擇一個標簽賦值給當前節點。
LPA與PageRank演算法相似，同樣需要通過迭代過程來完成。在標簽傳播演算法中，節點的標簽更新通常有同步更新和非同步更新兩種方法。同步更新是指，節點x在t時刻的更新是基於鄰接節點在t-1時刻的標簽。非同步更新是指，節點x在t時刻更新時，其部分鄰接節點是t時刻更新的標簽，還有部分的鄰接節點是t-1時刻更新的標簽。若LPA演算法在標簽傳播過程中採用的是同步更新，則在二分結構網路中，容易出現標簽震盪的現象。在本次設計中，我們考慮到了兩種更新方法，並進行了比較。
5.3 標簽傳播演算法在maprece上的實現細節
5.3.1 LPAInit類
為實現LPA的迭代過程，需要先給每個人物賦予一個獨特標簽，標簽初始化由LPAInit類完成，僅包含一個Map過程。標簽由數字表示，Map過程由1開始，為每一個人物名賦予一個獨特的標簽。為了便於後面的可視化分析，我們需要把PageRank值和標簽整合在一起，所以LPAInit的輸入文件直接採用PageRank過程的輸出文件，格式如下：
5.3.2 LPAIteration類
LPAIteration類完成標簽的更新過程，其格式與LPAInit的輸出格式一致，包含一個Map和Rece過程。Map過程對輸入的每一行進行切割，輸出四種格式的<key,value>：<人物名，關系鏈表>，<人物名，PageRank值>，<人物名，標簽>，<鏈出人物名，標簽#起點人物名>。第四種格式個鍵值對是為了將該節點的標簽傳給其所有鄰居。
Rece過程對value值進行識別，識別可以通過Map過程把預先定義好的特殊字元如『#』、『@』來實現前綴到value上來實現。由於人物關系圖中的各個邊都是有權重的，並且代表兩個人物的相關程度，所以標簽更新過程不是用邊數最多的標簽而是權重最大標簽來更新，我們可以預先把權重最大的若干個保存到一個鏈表中，如果存在多個權重相同的標簽，則隨機選取一個作為該人名新的標簽。非同步方法更新標簽需要使用一個哈希表來存儲已經更新標簽的人物名和它們的新標簽，並且在更新標簽時使用該哈希表裡面的標簽。同步方法更新標簽則不需要存儲已更新的標簽。
本次設計中比較了同步和非同步更新兩種方法，下圖為標簽不變的比例隨迭代次數的變化。可以發現，非同步收斂速度更快，只要6次迭代即可完全收斂，且標簽不變的比例可達100%。而同步更新方法則不能達到100%，說明人物關系圖中存在子圖是二部子圖。
5.3.3 LPAReorganize類
LPA演算法迭代收斂後，所有人物名的標簽不再變化，但是此時的標簽排列是散亂的，需要把同一標簽的人物名整合在一起。該過程由LPAReorganize類完成，包含一個Map和Rece過程。Map過程對輸入的每一行進行切割，以<標簽，人物名#PageRank值#關系鏈表>格式輸出。Rece過程中，同一標簽的人物名匯聚在一起，然後根據每個標簽人物集合的大小從大到小排序，重新賦予標簽（從1開始）。這樣輸出文件中同一標簽的人物名就會聚集在一起。最後的輸出格式如下：
5.3.2 LPAMapper類
LPAIteration類完成標簽的更新過程，其格式與LPAInit的輸出格式一致，包含一個Map和Rece過程。Map過程對輸入的每一行進行切割，輸出四種格式的<key,value>：<人物名，關系鏈表>，<人物名，PageRank值>，<人物名，標簽>，<鏈出人物名，標簽#起點人物名>。第四種格式個鍵值對是為了將該節點的標簽傳給其所有鄰居。
5.3.2 LPARecer類
Rece過程對value值進行識別，識別可以通過Map過程把預先定義好的特殊字元如『#』、『@』來實現前綴到value上來實現。由於人物關系圖中的各個邊都是有權重的，並且代表兩個人物的相關程度，所以標簽更新過程不是用邊數最多的標簽而是權重最大標簽來更新，我們可以預先把權重最大的若干個保存到一個鏈表中，如果存在多個權重相同的標簽，則隨機選取一個作為該人名新的標簽。非同步方法更新標簽需要使用一個哈希表來存儲已經更新標簽的人物名和它們的新標簽，並且在更新標簽時使用該哈希表裡面的標簽。同步方法更新標簽則不需要存儲已更新的標簽。
Driver類
6.1 可視化工具Gephi
Gephi是一款開源的跨平台的基於JVM的復雜網路分析軟體。把PageRank和LPA的結果，轉化為gexf格式，在Gephi中繪制圖像並分析大數據實驗結果，更加直觀、易於理解。
gexf實際上是一種特殊的XML文件，python的gexf庫提供了介面方便我們編輯和生成gexf文件，因此我們選擇使用python處理PageRank和LPA的結果。頂點有兩種屬性，LPA生成的標簽和PageRank計算的PR值，每條邊的權重是PageRank計算出的值。在可視化的時候，標簽決定頂點顯示的顏色，PR值決定標簽的
6.2 可視化預處理
編寫一個python程序transform2xml.py，將數據分析部分得到的PR值，標簽以及點連接關系處理成一個可供Gephi讀取的gexf文件。
6.3 可視化結果
7 輸出結果截圖
7.2 同現次數統計
7.4 PageRank
② 綜述：廣義的分布外檢測（異常檢測、開集識別、OOD檢測）
Generalized Out-of-Distribution Detection: A Survey Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu https://github.com/Jingkang50/OODSurvey
分布外（Out-Of-Distribution，OOD）檢測對確保機器學習系統的可靠性和安全性至關重要。例如，在自動駕駛中，當遇到它從未見過、無法給出安全決策的非常規情形或物體，我們需要駕駛系統發出警告並且將控制權交給人類。自2017年被提出起，這個問題越來越受研究者關注，各種解決方案層出不窮，大致包括：基於分類的、基於密度的、基於重構的、基於距離的方法。與此同時，其他幾個問題在動機和方法上與分布外檢測緊密相關，這些問題包括：異常檢測（Anomaly Detection，AD）、新類檢測（Novelty Detection）、開集識別（Open Set Recognition，OSR）和離群檢測（Outlier Detection，OD）。盡管他們各自定義和問題設定不同，這些問題經常使讀者和實踐者感到困惑，這導致有些現有工作誤用了這些術語。實際上，AD、ND、OSR、OOD、OD這五個問題能夠統一在廣義的分布外檢測框架下，都可以視作分布外檢測的特例或子任務，並且能夠輕易地被區分。這篇綜述通過總結最新的技術發展對這五個問題做了深入的回顧，並以該領域的開放挑戰和潛在的研究方向作結。
可信的視覺識別系統不僅僅在已知的情境下能給出精確預測，還應該能檢測到未知的樣本並且丟棄或將它們交給用戶來做安全地處理。
比如，一個訓練良好的食物分類器應該丟棄像用戶自拍照之類的非食物圖片，而不是胡亂判定其屬於某已知的食物類別。在安全要求極高的應用中，比如無人駕駛，系統應該在它碰到不尋常的、未在訓練中見到的情形或物體時發出警告並將控制權交給司機。
大多數現有機器學習模型都基於封閉世界假設（the closed-world assumption）來訓練，即測試集和訓練集獨立同分布，或者說兩者來源於同一分布（in-distribution）。然而，當模型被部署在開放世界場景（open-world scenario）中，測試樣本的分布可以是取自不同於訓練集分布的分布的（out of distribution），因而需要被謹慎處理。分布的變化可能是語義漂移（比如，OOD樣本取自別的類別）、協變數漂移（也稱輸入漂移，比如OOD樣本取自其他領域？？）。
只考慮語義漂移和協變數漂移兩類漂移。
異常檢測目的在於在測試階段檢測異常的樣本，「異常」指的是偏離預定義的「正常」。這種偏離可能是協變數漂移或是語義漂移導致的。異常檢測可以分為兩個子任務：
與異常檢測的區別 ：1） 動機上，新類檢測中並不像異常檢測把沒見過的「新」樣本看做錯誤的或是有害的，而是將珍視這些新樣本為後續模型的學習資源；2）新類檢測首要關注的是語義漂移；3）新類檢測中，沒有限制ID樣本屬於單個類，在訓練集中可以有多個類別的樣本。
新類檢測目的在於檢測出不屬於任何訓練類別的測試樣本。檢測到的新奇樣本通常預備用於未來程序的構建，比如特異性更強的分析、當前模型的增量學習等。依據訓練類別數量的差異，新類檢測分為：
OSR需要一個多類別分類器來同時1）精確地分類 訓練類別的 測試樣本（ID）；2）識別出測試樣本中 不屬於訓練類別 的樣本（OOD）。
OSR = multi-class ND
需要模型拒絕標簽遷移的樣本以保證預測可靠性和安全性
分布外檢測目的在於檢測測試樣本
當某個樣本顯著區別於其他的樣本時，認為它是「離群」的。在異常檢測、新類檢測、開集識別、分布外檢測的問題設定中，都存在這訓練-測試的流程，要挑出測試中出現的不屬於訓練分布的樣本。
而離群檢測無「訓練分布」、「測試分布」，而是直接挑出所有可見樣本中顯著區別於其他的那些樣本。
給定同構的ID數據，最直接的方法是1）基於密度的方法，這些方法估計ID的密度，拒絕那些偏離估計的OOD的測試樣本。其他的方法包括：2）依靠圖片重構的質量來識別異常樣本，3）直接學習一個決策邊界來區分ID和OOD樣本，4）基於距離的方法，5）基於元學習的方法
基於密度的方法嘗試去建模正常數據（ID數據）的分布，這種做法基於一個實踐假設：異常的測試樣本在估計的密度模型下游較低的概率值，而正常樣本概率值較高。
參數密度估計假設ID樣本的密度能夠被表示為某種定義好的分布。一種方法是在訓練數據上擬合一個多變數高斯分布，並且度量測試樣本與訓練樣本的期望之間的馬氏距離（協方差距離，計算兩個未知樣本集的相似度的方法。與歐氏距離不同的是它考慮到各種特性之間的聯系）。其他的工作採用了更復雜的假設，認為訓練分布是混合的高斯分布或是泊松分布等。
非參數密度估計考慮了更貼合實際的情形：預定義的分布不能夠建模真實分布。可以簡單地用直方圖對訓練分布進行建模。核密度估計（KDE）進一步使用核函數作為離散直方圖的連續替代版，它可以靈活地使用點權重和帶寬去控制估計的分布。
雖然經典的密度估計方法在很多任務上獲得了很好的AD性能，但它們更適合低維任務。
對於計算機視覺任務中的高維數據，這些方法的計算性和可伸縮性受到影響。為緩解維數災難，有些方法通過特徵工程降維[277]，[278]。
通過由潛在嵌入重建出輸入，自編碼器能學到無標簽數據的高效表達。變分自編碼器將輸入的圖片編碼為服從高斯分布的潛在向量。習得的潛在嵌入可被視為輸入的低維表示。傳統密度估計方法可以應用在這些深度表示之上。
生成對抗網路由一個生成網路和一個判別網路構成，兩者在零和博弈中相互競爭。典型地，生成網路學習從潛在空間到所研究數據分布的映射，而判別網路試圖分辨生成器生成的數據和真實數據。然而，不同於基於自編碼器/變分自編碼器的範式，少了一個編碼器使得GAN難以直接為一張輸入圖片找到相應的嵌入。針對這個問題，ADGAN [90] 對一個給定的樣本，在潛在空間搜索一個好的表示。如果找不到這樣的表示，這個樣本被認為是異常的。該方法計算代價極高。
規范化的流描述了一個概率分布經過一系列可逆映射的轉化過程。通過重復施加變數變化的規則，初始的密度「流」過了一系列可逆映射。因此，使用規范化的流的方法能夠直接估計輸入空間的可能性。基於流的方法有優雅的數學表示，但是它們同樣僅對低維特徵敏感。若不進行降維，基於流的方法計算代價高。
除通過生成式模型獲取可視化嵌入外，一些方法主要通過擴充模型容量來增加提取到的特徵的表示能力，這或許可以讓正常（ID）能被更精確地特徵化為密度估計。這些策略包括數據增強，對抗訓練，蒸餾，損失函數增強，使用淺表/局部特徵。
基於能量的方法使用一個標量能量評分來表述變數概率密度，這個標量採用非標准化的負對數概率，
然而，和標準的深度學習模型相比，訓練基於能量的方法代價昂貴，因為馬爾可夫鏈蒙特卡羅法（MCMC，在概率空間，通過隨機采樣估算興趣參數的後驗分布）采樣和估計需要積分運算。
為解決這個難題，研究者提出了評分匹配方法和隨機梯度之類的方法來支持高效訓練。
現有工作也探索了使用頻域分析方法做異常檢測。人類通過圖片的低頻信息來理解圖片，而CNN更多依賴高頻信息來做決策。人們提出了CNN核平滑和譜引導的數據增強之類的方法去抑制高頻分量的影響。還有一些工作發現，對低頻分量的對抗攻擊也很難被檢測到，因此提出
基於頻率的方法專注於感官異常檢測（尤其是檢測對抗樣本），或許不適用於語義異常檢測。
基於重構的方法的核心在於在ID數據上訓練得到的編解碼器（encoder-decoder）框架通常對ID和OOD樣本返回不同的效果。
模型表現的差異可以被用作異常檢測的指標。模型表現的差異可以用特徵空間的差異或是重構誤差來度量。
系數重構假定每個正常樣本都能被有限個基礎函數精確重構，而異常數據的重構開銷則更大，因此生成了稠密表示。稀疏表示的典型技巧包括基於L1正則的核PCA和低階嵌入網路。
重構誤差方法依賴於以下假設：在正常數據上訓練得到的重構模型在輸入為正常測試樣本時會輸出更高質量的結果。深度重構模型（包括自編碼器AE、變分自編碼器VAE、生成對抗網路GAN和U-Net等）都能夠被用作這類方法的backbone。
除去這種結合AE/VAE和重構誤差這種標准做法，其他方法使用了更加精細的策略，比如通過memorized normality重構，調整模型架構、部分/有條件的重構。
在半監督設定下的異常檢測中，CoRA分別在ID樣本和OOD樣本上訓練，得到兩個自編碼器。這兩個自編碼器的重構誤差被用作異常檢測的指標。
GAN中的判別器本質上是 通過計算重構誤差 實現異常檢測。更進一步，GAN的變種，比如去雜訊的GAN和類別-條件GAN通過 增加重構難度 獲得了更好的性能。有些方法 利用重構圖片在下游任務中的表現來進一步放大異常樣本的重構誤差 。集成也能夠優化模型性能。
異常檢測、單類別的新類檢測通常被形式化為無監督學習問題，將所有的ID樣本看做一類。
【283】做了完全有監督的異常檢測
半監督的異常檢測中，模型訓練時用到了無標簽數據。
PU學習針對這個問題被提出
自監督方法3.3.3
單個類別分類直接學到一個決策邊界
未完成
共性：ID樣本的類別（訓練類別）為多個。
差異：開集識別還需要精確地給ID樣本分類，而新類檢測只需得到區分ID/OOD的二分類器。
由於開集識別和多類別新類檢測的訓練類別為多個，大多數方法都是基於分類的。其餘方法包括基於ID原型的以及基於重構的。極少數模型是基於密度的。
為了解決
開集識別和多類新類檢測都關注ID樣本包含多個類別的情形。分類問題中，一般採用獨熱編碼來編碼類別信息。然而，獨熱編碼忽略了類別間的內在聯系。舉例來說，「狗」-「貓」，「狗」-「車」之間有相同的距離顯然不合情理。有些工作考慮這一點，嘗試利用新類的標簽空間上的信息來解決這個新類檢測問題。重分配大的語義空間，形成已知類別的層次化分類
基於標簽組織重設，自上而下的分類策略和分組softmax訓練被證實有效。應一組工作使用詞向量嵌入來自動地構建標簽空間。【169】中稀疏獨熱標簽被幾組產生自不同NLP模型的稠密詞向量替代，形成了多個回歸頭來做魯棒的訓練。
測試時，標簽（同所有不同頭給出的嵌入向量距離最小的標簽被作為預測結果輸出，
如果這個最小距離超出閾值，這個樣本被分類為「新」。近期工作進一步採用語言-圖片預訓練模型輸出的特徵來更好地檢測新類，圖片編碼空間中也包含來自標簽空間的豐富特徵。）
基於距離的開集識別方法需要「原型」來實現class-conditional。維持ID樣本的分類性能。
基於類別的聚類和原型（prototyping）操作在分類器提取到的視覺特徵上進行。
OOD樣本能夠通過計算樣本與聚類之間的距離而被識別。
有些方法還引入了對比學習來為已知類別學到更加緊密的聚類，從而拉遠ID和OOD樣本之間的距離。
CROSR【177】通過拼接分類器和用於距離計算的重構模型給出的可視化嵌入來在拓展的特徵空間中得到強化的特徵。除了使用分類器給出的特徵，GMVAE【178】使用重構VAE來提取特徵，將訓練集的嵌入建模為一個多中心的混合高斯分布以便後續基於距離的操作。使用最近鄰的分類器也適用於開集識別問題。通過存儲訓練樣本，最近鄰距離比值被用於在測試中識別未知樣本。
基於重構的方法希望ID和OOD樣本被重構時表現不同。這種差異能夠在潛在特徵空間或重構圖片的像素空間中被捕捉到。
通過將已知類別的圖片轉化為稀疏表示，開集樣本由於相對稠密能被識別出。用於稀疏編碼的技巧包括：疏密指數（sparsity concentration index）【180】和核虛空間方法（kernel null space method）【181，182】。
通過固定在ID樣本訓練得到的多分類視覺編碼器來維持在ID樣本上的分類性能，C2AE訓練一個以表情按向量為條件的解碼器，使用極值理論估計重構後的圖片來區分未知類別。後續的工作使用條件高斯分布，使得不同潛在特徵逼近類內（class-wise）高斯模型，以達到在分類已知類別樣本的同時能拒絕未知類別樣本。其他方法生成反事實（counterfactual）圖片來幫助模型更關注語義。對抗防禦【186】也以這種思路去增強模型魯棒性。
後處理檢測的方法優點在於無需修改訓練程序和目標就可以輕易應用。這一點對現實生產環境中的OOD檢測方法很重要。早期的ODIN是一個使用temperature scaling和輸入擾動來放大ID/OOD差別的後處理方法。該方法中，一個足夠大的temperature有很強的平滑作用，能夠將softmax值轉換到logit空間（），從而有效區分ID和OOD樣本。注意這種方式與信心校準不同，它採用了更溫和的T
而校準更關注表達ID樣本真實的正確概率
ODIN的評分最大化了ID和OOD樣本之間的差異，可能從預測信心的角度看不再有意義。
基於這個見解，近期【189】提出使用能量分值來做OOD檢測，該方法不需要超參數並且性能與ODIN相當甚至更好。能量函數將logit輸出通過便捷的 logsumexp 運算符映射為標量。能量值相對低的測試樣本被認為是ID的，反之為OOD。
【55】進一步提出了聯合能量值（JointEnergy score）
為OOD檢測定製的基於信心的方法能夠通過設計信心估計分支和類別數據增強（結合leaving-out留一策略、對抗訓練、更強的數據增強、不確定性建模、利用理想深度的特徵）來實現。
特別地，為了增強對協變數偏移的敏感性，一些方法關注神經網路中間層的隱藏表示。泛化的ODIN通過使用DeConf-C作為訓練目標來擴展ODIN，選擇ID數據上的擾動尺度作為超參。
由於ODIN需要模型訓練過程，它未被歸類到後處理方法。
為了得到質量更優的隱藏層特徵以便進行密度估計，分層的 Mahalanobis距離、 Gram Matrix等技巧被引入。
OOD檢測的另一分支利用收集到的OOD樣本集（離群樣本集），在訓練中幫助模型學到ID和OOD的差異。
總的來說，採用離群點暴露的OOD檢測能達到明顯更優的性能。然而，其性能受給定OOD樣本和真實OOD樣本間相關性強弱影響明顯，如何將OOD由已經暴露的OOD泛化到更廣泛的OOD還需進一步探索。
離群點暴露方法依賴於OOD訓練數據可獲取這一強假設，該條件在實際可能不成立。在OOD數據不可獲取時，一些方法嘗試去合成OOD樣本從而讓ID和OOD可區分。現有工作利用GAN來生成OOD訓練樣本並使模型輸出均勻（uniform 正態？？？）的預測，從而在低密度區域生成邊界樣本，或者類似地，生成高置信度的OOD樣本。
現有的OOD檢測方法主要依賴輸出或特徵空間來給出OOD評分，而忽視了梯度空間的信息。ODIN【188】首次探索了使用梯度信息檢測OOD。ODIN使用經過預處理的輸入，其預處理為施加由輸入梯度得來的細微擾動。ODIN擾動的目標在於增強模型對預測標簽的信心從而增加任何給定輸入的softmax值。最終，可以找到能使ID和OOD輸入的softmax評分差異更大的擾動，從而使得它們更能被區分，使得OOD檢測性能更好。ODIN僅隱式地通過擾動來利用梯度。GradNorm則使用梯度向量的范數，從softmax輸出和正態概率分布的KL散度反向傳播。
貝葉斯模型是一類統計模型，應用貝葉斯法則來推測模型中所有的不確定性。其中，最有代表性的是貝葉斯神經網路，該方法通過馬爾可夫鏈蒙特卡洛方法、拉普拉斯方法、變分推斷來構成模型的認知不確定性，從模型的後驗分布中采樣。它們最明顯的缺陷在於預測不精確，計算代價高使得它們難以用於實際。近期工作嘗試了幾種less principled（理論性較弱??）的近似，包括 MC-dropout [224] 和深度融合 [225]，299] 用於更快、更好地估計不確定性。這些方法在OOD不確定性估計上不太有競爭力。更進一步的探索需要在保留貝葉斯原理的優勢的同時，採用自然梯度變分推理，從而能夠採用實用且可負擔的現代深度學習訓練。狄利克雷先驗網路Dirichlet Prior Network (DPN) 也在OOD檢測中被運用，使用對模型不確定性、數據不確定性以及分布不確定性三個不同來源的不確定性進行不確定性建模，出現了一系列工作 [227], [228], [229]。
近期工作推進了更貼近實際應用的大規模OOD檢測。研究的兩個方向是：將OOD檢測擴展到大的語義空間、利用大型的預訓練模型。例如，【168】指出，在基於CIFAR benchmark數據得到的方法在語義空間更大的benchmark ImageNet上並不奏效，這強調了在大型真實設定下評估OOD檢測的必要性。為解決上述挑戰，MOS的關鍵理念是將大的語義空間解構為有相似概念的更小的群組，這簡化了已知和未知數據之間的決策邊界。強有力的預訓練模型在各種任務、模態都達到了驚人的性能。同期的工作 [171], [230], [231] 證實預訓練過的transformer在特定的困難的OOD任務上性能顯著改善。
OOD檢測領域中，基於密度的方法用一些概率模型顯式地建模分布內數據，並將低密度區域的測試數據標記為OOD。即使OOD檢測在分布內數據為多類別的情形下和異常檢測不同，3.1.2節中的密度估計方法能夠通過將分布內數據統一成一個整體而直接適用於OOD檢測。當分布內含多個類別時，class-conditional高斯分布能夠顯式地建模分布內數據，因而分布外樣本能夠根據輸出的預測概率而被識別【207】。基於流的方法 [92], [232], [233], [234]也可被用於概率建模。直接估計OOD概率似乎是一種自然的解決方法，也有一些方法 [235], [236], [237] 通過給OOD樣本輸出更高的概率預測值來實現OOD檢測。【238】嘗試使用likelihood ratio來解決這個問題。【239】發現，對輸入復雜度，概率值存在明顯偏差，提出了一種基於概率值比例的方法來削減輸入復雜度的影響。近期的方法轉而使用新的評分，例如likelihood regret【240】或是集成多個密度模型【236】。整體上，生成式模型的訓練和優化難度幾乎是不可接受的，它們的性能也往往落後於基於分類的方法（3.3）
基於距離的方法基本理念在於，測試中OOD樣本應當相對遠離分布內類別的中心（centroid）或原型（prototype）。【207】使用相對所有類別中心的最小Mahalanobis距離來檢測。一個後續工作【241】將圖片分為前景和背景，再計算這兩個空間間的Mahalanobis距離比例。一些工作使用測試樣本特徵和類別特徵間的餘弦相似度來確定OOD樣本【242】、【243】。被訓練特徵的的第一奇異向量一維的子空間
更進一步，其他工作利用了徑向基函數核距離（distance with radial basis function kernel）、輸入的嵌入向量到類別中心的歐拉距離。
OOD檢測領域自出現以來發展迅速，其解決方案從基於分類的、基於密度的、再到基於距離的。在多類別設定下，典型的OOD檢測是開集識別問題（第4節），在類別空間Y中精確分類分布內的測試樣本，並且丟棄語義不被Y所支持的分布外樣本。然而，OOD檢測包含了更廣泛的學習任務（比如，多標簽分類）和解法（比如，密度估計和離群點暴露）。一些方法放寬了開集檢測的限制條件，並且達到了更強的性能。
離群檢測需要所有樣本可見，其目標是檢測出那些顯著偏離大多數的分布的樣本。離群檢測方法通常是轉導式的，而不是歸納式的。 [13], [14], [15], [16]綜述主要回顧了數據挖掘領域的離群檢測方法。以下主要回顧離群檢測方法，尤其是為計算機視覺設計的使用深度神經網路的方法。即使深度學習方法極少能直接解決離群檢測問題，數據清洗程序（從開集臟數據學習的先決條件）和開集半監督學習的方法也在解決離群檢測問題。
離群檢測模型的基本理念是將整個數據集建模為一個高斯分布，將偏離均值超過三杯標准差的樣本標記為離群【300】【301】。其他帶參數的概率方法利用Mahalanobis距離[266] 和高斯混合模型 [302]來建模數據密度。和「三倍標准偏離」規則類似，四分位距也可通過構建傳統的無參數概率模型來檢測離群樣本【247】。為了魯棒和簡化，局部離群因子（local outlier factor）方法【248】藉助給定點的鄰居和它自身局部可達性的比值，去估計給定點的密度。RANSAC【252】迭代地估計數學模型的參數來擬合數據並且找到對估計貢獻較少的樣本作為離群點。
總體上，經典的異常檢測的密度方法比如，核密度估計（3.1節），也可應用於離群檢測。即便這些方法由於圖片數據維度太高而應用困難，也可以通過降維方法【253,254】和基於最近鄰的密度方法(3.1節)來緩解。
檢測離群的一個簡易方法是計數某特定半徑內的鄰居數量，或者度量第k近鄰居的距離【303,304】。以下主要介紹基於聚類的方法和基於圖的方法。
DBSCAN【255】依照基於距離的密度來積聚樣本構成聚類。處在主要聚類之外的樣本被識別為離群樣本。後續工作通過考慮聚類標簽的信心改良了聚類的方式【256】。
另一類方法利用數據點之間的關系，並構造鄰域圖[305], [306]（或其變體[307]），利用圖的屬性和圖挖掘技巧來找到異常的樣本【257，258】，比如圖聚類[259], [260]、圖分割【308】、使用圖神經網路的標簽傳播【261】。
③ Neo4j中使用Louvain演算法和標簽傳播演算法(LPA)對漫威英雄進行社群分析
在本系列第一篇 在Neo4j中構建漫威世界的社交網路 中我們從英雄到漫畫的二分圖推導出英雄到英雄的一分圖。接著在第二篇 在Neo4j中對漫威社交網路進行初步分析 中得到一些基本的網路信息以幫助我們了解正在處理的網路情況。
在本篇中我將會在漫威英雄的網路上使用Louvain演算法和標簽傳播演算法(LPA)，發現一些有趣的社群。
本文中的可視化是使用Gephi來進行呈現，關於Gephi的更多信息可以看我之前的文章《Neo4j to Gephi》(https://tbgraph.wordpress.com/2017/04/01/neo4j-to-gephi/)。關於社群可視化還可以使用neovis.js(https://github.com/johnymontana/neovis.js)。
Neo4j圖演算法一般是在圖的子集上進行，而這個子集通常是一個虛擬圖，Neo4j圖演算法載入這種圖有兩種辦法。第一種簡單的辦法是通過指定結點的標簽和關系的類型將其載入到圖演算法中。
但是，如果我們要運行的邏輯是在一個特定的子圖上，而僅使用結點標簽和關系類型無法描述出這個子圖，同時也不想去修改實體圖，這時要怎麼辦呢？
不用擔心，我們還可以使用Cypher語句來指定要載入的子圖。使用查詢結點的Cypher語句代替結點標簽參數，使用查詢關系的Cypher語句來代替關系類型參數。
但是注意，在參數中一定要指明 graph:'cypher' 。
如下示例：
CALL algo.unionFind(
//第一個Cypher語句指定了要載入的結點。
'MATCH (p:User)
WHERE p.property = 'import'
RETURN id(p) as id',
//第二個Cpyher語句指定要載入的關系
'MATCH (p1:User)-[f:FRIEND]->(p2:User)
RETURN id(p1) as source, id(p2) as target,f.weight as weight',
{graph:'cypher',write:true})
通過Cypher語句映射和載入子圖，可以非常好的描述要運行演算法的子圖。不僅如此，我們還可以剔除一些關系，間接的映射一個虛擬圖用於運行演算法，而那些剔除的關系又並不會從實際圖中刪除。
Cpyher映射使用場景：
* 過濾結點和關系
* 載入間接關系
* 映射雙向圖
* 相似性閾值（後面詳情介紹）
在對各種網路的研究過程中，如計算機網路、社交網路以及生物網路，我們發現了許多不同的特徵，包括小世界特性，重尾分布以及聚類等等。另外，網路都有一個共同的特徵即社群結構，也就是連通和分組。而現實網路世界的連通並不是隨機或同質的，而是存在著某種自然的聯系。
社群識別演算法在一個全連通的圖上運行，效果並不會很好。因為大多數據結點都是緊密連接的，他們是屬於一個社群的。在這些的圖上運行演算法，最終結果就是：得到一個覆蓋圖大部分區域的大社群和一些邊邊角角小社群。
這時我們可以使用相似性閾值來進行調控，將大於某個值的關系保留，而小於此值的關系將會剔除。而這個虛擬圖就可以通過Cypher語句輕松的映射出來了。
在本文中，我會將漫威社交網路中KNOWS的weight作為閾值，將其設置到100，大於100的關系將會保留，小於100的關於將會剔除，這樣，得到的社群將會非常緊密。
連通分量或並查集演算法都是找到相互連接的結點集，或者稱之為島，而在這個集合中的所有點都是可以相互連通的。
在圖論中，無向圖的連通分量（或者僅分量）是一個子圖，其中此子圖任何兩個頂點通過路徑相互連接。
當我遇到一個新的網路時，我第一時間想知道是：這個網路有多少個連通分量，以及他們每個都包含多少結點。在漫威英雄的網路中，當前我們已經把KNOWS的weight閾值設置到100了，而前一篇文章的閾值是10，因此，本文得到的連接肯定要比前一篇文章()中的連接要少。
在下面的示例中，我們直接使用結點標簽和關系類型，所有標簽為Hero的結點和所有類型為KNOWS的關系都將被載入到演算法中。由於我們將閾值設置到100，所以，當前演算法只考慮weight大於100的關系。
CALL algo.unionFind.stream('Hero', 'KNOWS',
{weightProperty:'weight', defaultValue:0.0, threshold:100.0,concurrency:1})
YIELD nodeId,setId
RETURN setId as component,count(*) as componentSize
ORDER BY componentSize DESC LIMIT 10;
正如我所料，漫威英雄網路是一個稀疏圖，有1個大社群和6小社群組成，大社群有101個英雄，而小社群基本也就2~4個英雄。這表示，在6439個英雄中，有116個英雄至少一個KNOWS關系的weight值是大於100的。
如果想在瀏覽器中仔細瀏覽那個包含101英雄的大社群，會很容易發現隱藏在這裡面的一些直觀的東西以及社群之間的橋梁結點。接下來我們將嘗試使用Louvain演算法和標簽傳播演算法來看看這個116個英雄的子圖的社群結構。
社群就是網路中結點集合，它們彼此之間的連接比其他節點更緊密。Molarity是一種度量刻度，被用於衡量社群發現演算法結果的質量，它能夠刻畫社區的緊密程度。在一個隨機的網路中，將一個結點歸類到某一個社群，Molarity值就是會生變化，進而給出這種分配後社區的質量。Molarity即量化了此結點與社群中其他結點的連接緊密程度。社群識別的Louvain方法，是一種基於啟發式Molarity最大化的網路社群檢測演算法。
如前所述，我們將通過Cypher查詢來僅映射weight大於110的關繫到演算法中。
CALL algo.louvain.stream(
// load nodes
'MATCH (u:Hero) RETURN id(u) as id',
// load relationships
'MATCH (u1:Hero)-[rel:KNOWS]-(u2:Hero)
// similarity threshold
WHERE rel.weight > 100
RETURN id(u1) as source,id(u2) as target',
{graph:"cypher"})
YIELD nodeId,community
MATCH (n:Hero) WHERE id(n)=nodeId
RETURN community,
count(*) as communitySize,
collect(n.name) as members
order by communitySize desc limit 5
我使用Gephi進行社群結果可視化，因為Gephi的表現力比表格更好，更有洞察力。
我並不是漫威漫畫的專家，所以我只能根據數據來做一個簡單的解釋。我們總共劃分出8個社群。最大的社群是紫色的社群，它由以美國隊長為首的神盾局和復仇者聯盟組成。在左邊我們能看到神奇先生和神奇四俠也在紫色社群里。亮蘭色是蜘蛛俠團隊，蜘蛛俠帕克是他們與外界聯系的唯一橋梁，其他人都是內部交流，與外界並無聯系。深蘭色是阿斯加德人，他們也是比較封閉，他們僅僅和雷神托爾有聯系。哦？難以置信，綠巨人也是自己的社群（粉紅色），而綠巨人是這個社群唯一與外界有聯系的英雄。我們還看到野獸亨利是紫色社群與綠色社群的橋梁，位置特殊，而綠色是X-Men社群。
標簽傳播演算法是由Raghavan等人於2007年首次提出，（譯者言：網路顯示此演算法於2002年由Zhu等人提出）此演算法是由每個結點使用其唯一標識作為標簽，然後根據大多數鄰居結點的標簽為基礎進行標簽傳播，每個結點再從他的鄰居結點身上取出現次數最多的標簽加到自己身上。LPA演算法的具體步驟是這樣：結點X有一些鄰居結點，且每個鄰居結點都有一個標簽，標明他們所屬的社群。然後網路中的每個結點都選擇加入其大多數鄰居所屬的那個社群，同時再隨機的斷開一些連接。在開始時，每個節點都用唯一標簽進行初始化，然後這些標簽開始在網路中進行傳播，傳播的每一步，每個結點都會根據鄰居標簽的情況更新自己的標簽，隨著標簽的傳播，最終連接緊密的結點集合將會達成一個共識，而他們身上的標簽也將不再發生變化。
與Louvaint演算法類似，我們也採用Cypher語句進行圖映射，在映射時僅載入weight值大於KNOWS關系。同時會將對結點進行回寫，導出結果到Gephi中進行可視化展示。
CALL algo.labelPropagation(
// supports node-weights and defining
// initial communities using parameter value
'MATCH (u:Hero) RETURN id(u) as id, 1 as weight,id(u) as value',
// load relationships
'MATCH (u1:Hero)-[rel:KNOWS]-(u2:Hero)
// Similarity threshold
WHERE rel.weight > 100
RETURN id(u1) as source,id(u2) as target, rel.weight as weight',
'OUT',{graph:"cypher",partitionProperty:"lpa" })
YIELD computeMillis
最終我們得到21個社群，包括單點社群。復仇者聯盟（紫色）和神奇四俠（亮蘭色）被分為兩個社群了。蜘蛛俠（綠色），綠巨人（青綠色）和阿斯加德人（紅色）三個社群的結果與Louvain演算法一致。我們還發現X-Man被劃分成兩個社群，加農炮小組比Louvain的結果要稍微大點，同時也顯的不那麼孤立。
你發現沒有？Neo4j圖演算法庫真的很神奇，用起來也簡單。通過與Cypher查詢語句結合進行虛擬圖映射，可以簡單有效的對圖進行分析和理解。
本來，我打算在本文中介紹中心性演算法的使用，但那樣本文將會非常長，不便於閱讀，所以， 我後續將會再寫文章來介紹使用Cypher映射進行中心性演算法的示例。敬請期待吧。