這裡隻記錄我在讀此篇論文時認為重要的章節部分。
一、論文背景和貢獻
1，論文背景
1）在2013年波士頓馬拉松爆炸案發生後，有成千上萬的圖像和視訊需要在短時間内分析調查，進而縮小調查範圍。
2）人臉聚類也試圖解決以下問題：給定大量未标記的人臉圖像，将它們聚為這些資料中的單個辨別。這種情況出現在從社交媒體到執法等許多不同的應用場景中。
2，論文貢獻
一種改進的聚類算法，改進了Rank-Order Clustering提出的方法。貢獻點如下：
1，利用近似最近鄰方法的可擴充性，獲得更好的聚類精度；
2，基于深度網絡的大規模人臉識别的大規模人臉聚類實驗；
3，提出的人臉聚類方法對視訊的适用性做了初步調查；
4，定義了每個聚類品質度量。
二、聚類算法
1，人臉聚類流程
2，擷取人臉特征
擷取人臉特征步驟：
1，用dlib進行68個特征點的提取
2，用dlib進行人臉對齊（face align）
3，建構卷積神經網絡提取人臉特征
4，最終輸出320維的人臉feature
3，Rank-Order Clustering 改進前的算法
是一種層級聚類
基于排序距離的聚類算法（人臉與其他人臉的相似度的排序）
3.1 層級聚類
1，将所有資料點本身作為簇；
2，然後找出距離最近（相似度最高）的兩個簇，且其距離小于給定的threshhold，則将它們合為一個；
3，不斷重複以上步驟直到不能再合并（大于threshhold）。
4，特點是不需要指定聚類數量K。
3.2 Rank-Order Distance
First step: a set of unlabeled face images
Second step: nearest neighbor lists are computed for each image
Third step:
3.3 Rank-Order Distance Measure
fa(i)表示a的清單中第i張臉,Ob(fa(i))則表示臉fa(i)在b的清單中的序号位置。
3.4 Approximate Rank-Order Clustering 改進後的聚類算法
Rank-Order Clustering方法存在一個明顯的問題，因為它需要計算資料集中的每個樣本的最近鄰樣本清單，如果直接計算，時間成本為O(n2)。
Approximate Rank-Order Clustering改進點：
1.使用opencv FLANN庫的随機k-d tree算法求出每個人臉圖檔的k個最近鄰圖檔排序。
2.不計算每一個人臉的所有最近鄰清單，而是計算每一個人臉的k個最近鄰清單。
改進點 1 使用opencv FLANN庫的k-d tree算法求出每個人臉圖檔的近鄰圖檔排序：
這步用于前面的Second step: nearest neighbor lists are computed for each image
1，k-d tree是k-dimensional樹的簡稱，利用k-d tree搜尋，利用特殊的結構存儲資料，能減少大部分的資料搜尋，進而減少距離計算的次數。
2，對于中等規模的資料集，時間複雜度能降到O(nlogn)。
3，但是要注意，kd樹更适合于資料樣本數目遠大于空間維數的k近鄰搜尋，當空間維數接近于樣本數目時，它的效率會迅速下降，接近于線性掃描。
改進點2 計算每一個人臉的k個最近鄰清單：
其中Ib(x,k)是一個訓示函數，如果Ob(fa(i))輸入b的k近鄰中，則為值為0，否則為1。忽略了距離排序順序，隻關注在k近鄰中還是不在。
舉例：If k= 4, dm(a,b) = (0+1+0+1) = 2
簇距離歸一化公式：
3.5 聚類步驟：
為資料集中的每一張臉提取深度特征；
2) 為資料集中的每個人臉計算一組k最近鄰清單；
3) 計算每個人臉與其他人臉的簇距離，用前面的歸一化公式；
4) 合并距離低于門檻值的所有人臉對。
三、算法評估
請參考博文 人臉聚類Fscore評估
四、實驗結果
五、總結
基于rank-order cluster論文，利用FLANN庫的随機 k-d tree算法計算每個人臉的rank-order，并從計算每個人臉的rank-order distance改進為隻計算前k個近鄰人臉的距離。進而提高了準确率，減少了算法的時間複雜度。
介紹了一種評估人臉聚類算法Fscore的計算方法。