Hui Wang;
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Volume: 28 , Issue: 6
Digital Object Identifier: 10.1109/TPAMI.2006.126 
Publication Year: 2006 , Page(s): 942 - 953

IEEE Journals

Abstract  |  Full Text: PDF (3519 KB)

最近博客访问量低靡，看来是发的文章太没趣味性了，本次特发一篇泡妞博文，请各位单身猥琐男学习。

如何测定俩样本的相似度？这是机器学习领域的一个重要问题。

而如何让美女觉得咱俩很相似很投缘？这也是猥琐男们的一个重要问题。

直接上去套近乎？这个技巧太低劣了！泡妞高手告诉我们：又漂亮又有品位的知性美女很重感觉，只喜欢那种“原来你也在这里”的男生～ 具体地说，要经常偶遇在一些相同的场合，让俩人觉得：咱们的确有很多相同点呀！

猥琐男领悟了，于是开始了泡妞行动：先了解到美女参加了那些社团，然后很“偶然地”跟她一起出现，下面的我就不说了，总之发现了很多共同点而成为朋友->知己->恋人……

其实这给我们很大启示：如何衡量两人的关系，可以看他们共同被包含在多少个团体里。若两人的确有很多相似之处，那么共同属于的团体肯定也就很多。于是，算一下大家有多少共同的团体就可以作为相似度的衡量标准了。

这正是这篇文章的灵魂！

在机器学习里，“团体”的概念被称为Neighborhood，算团体称为Neighborhood Counting.

关键的是：如何定义和计算Neighborhood？

作者解决这个问题的思路很新颖，值得借鉴：

作者从多元数据的每个属性的域着手解决这个问题，从而把Neighborhood 转化为一些域的范围的交集，并为每一个属性a_i定义了一个函数J_i来表达这个范围。

这样，Neighborhood Counting 的过程为：

1. 把所有的Neighborhood 找出来，实际上是所有属性的域的可能组合，看看有多少个。
2. 给出一个样本t，看看可能包含这个样本的Neighborhood 有多少个？实际上，把那些把t的属性露在外面的范围的情况去掉。
3. 最后，又给出一个x,数数上面的Neighborhood 中，多少包含了x，就得到了能包含t和x的Neighborhood counting： cov(t,x)，作为输出。

一个问题是：第3步，数数的过程太耗时间了！作者又提出了一种代替的，节省时间的方法：只去数数同时能包括t和x的i属性的那些范围，这样也能算出来cov(t,x)，而且多快好省！

到此为止，方法介绍结束。

启发：

1. 计算共同的Neighorhood作为相似度测度，这个主意很有意思；

2. 如何计算Neighborhood，作者用属性的角度来考虑，也非常有趣；

3. 刚看到题目，以为是计算两人的交际圈里的交集的大小，也许这个主意有点意思？

后记：后来还有人提出质疑，作者作出了答复，还发在PAMI上，要不是作者的答复，我也不可能发现这篇好文，呵呵……

Neighborhood Counting Measure and Minimum Risk Metric 

Hui Wang;
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Volume: 32 , Issue: 4
Digital Object Identifier: 10.1109/TPAMI.2010.16 
Publication Year: 2010 , Page(s): 766 - 768

IEEE Journals

Abstract  |  Full Text: PDF (1047 KB)

The neighborhood counting measure is a similarity measure based on the counting of all common neighborhoods in a data space. The minimum risk metric (MRM) is a distance measure based on the minimization of the risk of misclassification. The paper by Argentini and Blanzieri refutes a remark about the time complexity of MRM, and presents an experimental comparison of MRM and NCM. This paper is a response to the paper by Argentini and Blanzieri. The original remark is clarified by a combination of theoretical analysis of different implementations of MRM and experimental comparison of MRM and NCM using straightforward implementations of the two measures. Read More» 

• <!-- showFullAbstract: false
  showOpenUrl: false
  showSubId: false
  -->

   

  About Neighborhood Counting Measure Metric and Minimum Risk Metric 

  Argentini, A.; Blanzieri, E.;
  Pattern Analysis and Machine Intelligence, IEEE Transactions on
  Volume: 32 , Issue: 4
  Digital Object Identifier: 10.1109/TPAMI.2009.69 
  Publication Year: 2010 , Page(s): 763 - 765

  IEEE Journals

  Abstract  |  Full Text: PDF (951 KB)

最后上作者王道：王辉教授，吉林大学校友。