Class Conditional Nearest Neighbor for Large Margin Instance Selection 

Marchiori, E.;
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Volume: 32 , Issue: 2
Digital Object Identifier: 10.1109/TPAMI.2009.164 
Publication Year: 2010 , Page(s): 364 - 370

IEEE Journals  

Abstract  |  Full Text: PDF (1703 KB)

我之前对此文章的介绍：

http://www.sciencenet.cn/m/user_content.aspx?id=295926

=====================回顾====================：

其实，这篇文章的最核心的思想在于：将类别信息引入最近邻搜索，提出了同类和异类的最近邻，然后有两个图来描述这两中关系。

插话：其实这个思想已经不新鲜，已经有人做过，将类别信息引入最近邻搜索，并提出了一种判别分析的方法。 

Graph Embedding and Extensions: A General Framework for Dimensionality Reduction

Shuicheng Yan; Dong Xu; Benyu Zhang; Hong-Jiang Zhang; Qiang Yang; Lin, S.;
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Volume: 29 , Issue: 1
Digital Object Identifier: 10.1109/TPAMI.2007.250598 
Publication Year: 2007 , Page(s): 40 - 51

IEEE Journals

Abstract  |  Full Text: PDF (1900 KB)

 

 

 

作者的方法是：先建立两个图：

The within-class 1NN graph,和The between-class 1NN graph,

用这两个图，作者提出了两个算法：

Class Conditional selection phase (CC).把不靠谱的样本去掉：去掉那些深入敌境的样本，去掉那些远离人群的样本；

Thin-out selection phase (THIN).：去掉那些对确定边境无关紧要的内部样本。

1.Class Conditional selection phase

图里面的节点，每一个箭头指过来（入度），说明另个样本把自己作为同类（异类）最近样本了。

很显然，做别人同类最近样本是好事，而做别人的异类最近样本，说明你不太靠谱，有点叛逆投敌的嫌疑。

根据这样的规则，提出了一种样本评判的得分：

有了这个分数，就有了对样本进行筛选的算法CC：

2.Thin-Out Instance Selection: THIN

还有一点，我们之前没介绍的：除了把那些不靠谱的踢掉，那些靠谱的人中间，也很很多是平庸的，也可以踢掉，只留下那些在边境上的精英们：Thin-Out Instance Selection: THIN

其实，这篇文章的启示还有：

1. 一些思想，也可以用在样本选择上，样本选择也是一个应用的领域；

2. 再一次，别忘记了，用这些得分对检索的样本重新排序。