论文阅读笔记：A Scalable Exemplar-based Subspace ClusteringAlgorithm for Class-Imbalanced Data
ECCV 2018
Chong You, Chi Li, Daniel P. Robinson, Rene Vidal
的子空間聚類方法由于其經(jīng)驗上的成功和理論上的保證，已成為無監(jiān)督學(xué)習(xí)的常用工具。然而，它們的性能可能會受到不平衡數(shù)據(jù)分布和大規(guī)模數(shù)據(jù)集的影響。本文提出了一種基于樣本的子空間聚類方法來解決大規(guī)模數(shù)據(jù)集的不平衡問題。
通過計算表示系數(shù)的范數(shù)，所提出的方法搜索最能代表所有數(shù)據(jù)點的數(shù)據(jù)集子集。為了有效地求解我們的模型，我們引入了一種最遠優(yōu)先搜索算法，該算法迭代地選擇代表性最差的點作為樣本。當(dāng)數(shù)據(jù)來自子空間的并集時，我們證明了即使數(shù)據(jù)是不平衡的，計算的子集也包含足夠多的來自每個子空間的樣本來表示所有數(shù)據(jù)點。我們的實驗表明，在兩個不平衡的大規(guī)模圖像數(shù)據(jù)集中，該方法優(yōu)于現(xiàn)有的子空間聚類方法。我們還證明了我們的方法在人臉圖像分類任務(wù)的無監(jiān)督數(shù)據(jù)子集選擇上的有效性。
1. 簡介
不同類別的未標(biāo)記數(shù)據(jù)集中的數(shù)據(jù)樣本數(shù)量差異很大。因此，在無監(jiān)督的學(xué)習(xí)任務(wù)中，處理不平衡的數(shù)據(jù)是一個重大挑戰(zhàn)。傳統(tǒng)的無監(jiān)督學(xué)習(xí)方法利用了一個事實，即在許多計算機視覺應(yīng)用中，數(shù)據(jù)的基本維度遠小于環(huán)境維度，因此可以用低維子空間的并集來建模。子空間聚類是從此類數(shù)據(jù)中進行無監(jiān)督學(xué)習(xí)的一種流行方法，它聯(lián)合學(xué)習(xí)子空間的并集，并將每個數(shù)據(jù)點分配給相應(yīng)的子空間。
本文貢獻
我們提出了一種基于樣本的子空間聚類方法來解決不平衡和大規(guī)模數(shù)據(jù)的問題。給定一個數(shù)據(jù)集，我們的想法是選擇一個子集，我們稱之為范例，并將每個數(shù)據(jù)點作為點在中的線性組合寫入（而不是在SSC中的）：
相比于標(biāo)準(zhǔn)的SSC，上式顯然對不平衡數(shù)據(jù)集更加魯棒（如果選擇的子集是類別均衡的），此外，當(dāng)相對于原始數(shù)據(jù)較小時，SSC能更有效地求解。因此，為了實現(xiàn)對不平衡數(shù)據(jù)的魯棒性和對大型數(shù)據(jù)集的可伸縮性，我們需要一種高效的算法來選擇在不同類之間更平衡的示例。
在本文中，我們提出了一個新的模型來選擇樣本，該模型基于最小化數(shù)據(jù)的最大表示代價。此外，我們還介紹了一種有效的算法來解決具有線性時間和內(nèi)存復(fù)雜性的優(yōu)化問題。與SSC相比，基于樣本的子空間聚類對不平衡數(shù)據(jù)不太敏感，對大數(shù)據(jù)更有效（見圖1）。此外，我們的工作做出了以下貢獻：
2 相關(guān)工作
略
3 基于范例的子空間聚類（ESC）
我們首先建立了從中選擇樣本子集的模型。由于該模型是一個組合優(yōu)化問題，我們提出了一種有效的近似求解算法。最后，我們描述了從示例生成聚類分配的過程。
3.1 基于自表示代價的樣本選擇
回想一下，在SSC中，每個數(shù)據(jù)點xj∈ X被寫成所有其他數(shù)據(jù)點與系數(shù)向量的線性組合。而每個中的非零項確定了一個可以用來表出的的子集，所有的集合通常需要整個數(shù)據(jù)集。在ESC中，目標(biāo)是找到一個可以表示中所有數(shù)據(jù)點的小子集。特別地，集合應(yīng)該包含來自每個子空間的樣本，這樣每個數(shù)據(jù)點的解都是子空間保持的。下面，我們根據(jù)（2）中的優(yōu)化定義一個成本函數(shù)，然后給出我們的示例選擇模型。
定義1?自表示代價
幾何上，定義了數(shù)據(jù)點是否被很好地包含在子集中（見第4節(jié)）。函數(shù)具有以下性質(zhì)?
引理1： 函數(shù)是對集合單調(diào)的
即：
引理2：的取值范圍在之間。
區(qū)間的下界即只有一個點，有定理1知，上界來自于。
因此我們建議通過搜索在限制子集的樣本點的個數(shù)來執(zhí)行樣本選擇使自表示成本函數(shù)最小化，即：
?
其中為采樣點的個數(shù)。通過如下引理可知也是單調(diào)的。
引理3：自表示損失（即函數(shù)的上界）對于集合是單調(diào)的
求解上述上界的最小化的優(yōu)化問題是全局NP-hard的，它需要評估所有最大數(shù)目為k的所有子集對應(yīng)的。在下一節(jié)，我們提出了一種高效的近似計算算法。
3.2 A Farthest First Search (FFS) for ESC
在算法1中我們近似地求解上述優(yōu)化問題。
該方法逐步擴增初始為空集的候選子集知道包含k個點。對于每次迭代，如step 3所示，選擇的點是當(dāng)前子集最難線性表出的（即損失最大的），這暗合了引理2的要求，因為只有該點或不屬于子集時才能使當(dāng)前的損失最大。注意到FFS可以被看作最遠優(yōu)先遍歷算法的一種擴展。
高效的實現(xiàn)。每次迭代中。算法1需要評估所有點的。因此計算復(fù)雜度為是總樣本點數(shù)N的線性關(guān)系（假設(shè)k確定且遠小于N）。然而，計算本身就是困難的，他需要求解一個稀疏優(yōu)化問題。在接下來，我們提出了算法2來跳過某些點計算的步驟。
?這是因為引理2表明了是單調(diào)的，因此有。在FFS算法中，子集的容量是不斷增長的，這隱含著函數(shù)相對迭代次數(shù)i的增加是單調(diào)非增函數(shù)。在算法2的step 2中，我們對所有點相對于初始化后子集計算，對于之后的所有迭代i，這是對應(yīng)損失的上界。我們先對進行排序，使得，之后當(dāng)按照該排序的數(shù)據(jù)點計算（step 7）的同時通過可變的max_cost跟蹤的最大值（step 9）。我們可以根據(jù)該指標(biāo)提前停止計算（setp 11），即，一旦我們就可以斷言任何index比更大的數(shù)據(jù)點都不能再最大化，從而避免了計算剩下點的。
3.3 從ESC得到聚類結(jié)果
4 實驗
在本節(jié)中，我們將演示ESC在子空間聚類和無監(jiān)督子集選擇任務(wù)中的性能。計算自表示代價的步驟(如算法2的step 7)由SPAMS包中實現(xiàn)的LARS算法的LASSO版本解決。
4.1 子空間聚類
數(shù)據(jù)集。Extended-MNIST（EMNIST）是MNIST數(shù)據(jù)集的擴展，它包含灰度的手寫字母。我們將所有190998張對應(yīng)于26個小寫字母的圖像作為26類聚類問題的數(shù)據(jù)。該數(shù)據(jù)集中每個圖像的大小為28×28。之后，每個圖像由散射卷積網(wǎng)絡(luò)計算出的特征向量表示，該網(wǎng)絡(luò)具有平移不變性和變形穩(wěn)定性（即，它將小變形線性化）。因此，EMNIST的這些特征大致遵循子空間并集模型。
EMNIST是不均衡的。在EMNIST中，每個字母的圖像數(shù)量從2213（字母“j”）到28723（字母“e”）不等，每個字母的樣本數(shù)量大約等于它們在英語中的出現(xiàn)頻率。
EMNIST的結(jié)果。下圖顯示了EMNIST的結(jié)果。從左到右，子圖分別顯示了作為樣本數(shù)（X軸）函數(shù)的Acc、F-score和運行時間（Y軸）。回想一下，在SSC中，每個數(shù)據(jù)點都表示為所有其他點的線性組合。通過選擇樣本子集并使用這些樣本表達點，當(dāng)樣本數(shù)達到200時，ESC-FFS能夠優(yōu)于SSC。相比之下，ESC-Rand的表現(xiàn)并沒有顯著優(yōu)于SSC，這表明了FFS樣本選擇的重要性。在運行時間方面，我們發(fā)現(xiàn)ESC-FFS比SSC快很多。具體來說，ESC-FFS幾乎與ESC-Rand一樣有效，這表明所提出的FFS算法2是有效的。?
總結(jié)
以上是生活随笔為你收集整理的论文阅读笔记：A Scalable Exemplar-based Subspace ClusteringAlgorithm for Class-Imbalanced Data的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 包,内部类,常用类,集合
- 下一篇： 二进制代码运算规律是逢二进一