虚假交易识别(3)--Clustering-Based Outlier Rankings方法
06 Sep 2013
从例子来看方法的主要思想
除了识别（1）和识别（2）介绍的两种方法，再来介绍一种识别异常值的方法—基于聚类的异常值排秩。这种方法思想巧妙：通过观察异常观测在“层次聚类过程”中的特殊表现来识别异常值。不禁要问：异常观测在层次聚类过程中会有那些特点呢？好，慢慢道来。
首先，我们对USArrests来作聚类分析。这组数据包含了美国50个州每十万人中谋杀犯（Murder)、强奸犯(Rape)、攻击犯（assault,翻译为攻击犯对不对？）的人数，另外还有郊区人数比例(UrbanPop)。下面给出了数据的一部分：
Murder Assault UrbanPop Rape
Alabama 13.2 236 58 21.2
Alaska 10.0 263 48 44.5
Arizona 8.1 294 80 31.0
Arkansas 8.8 190 50 19.5
California 9.0 276 91 40.6
Colorado 7.9 204 78 38.7
通过这些数据将这50个州分类，来看看哪些州的治安情况类似。下面是基于平均距离的层次聚类方法的结果：
这批数据准确性毋庸置疑，也就是说所有的数据都是真实的，所以聚类过程也非常的“普通”。我们注意一下红色方框标出的怀俄明州的位置（”Wyoming”)。
下面，我们“制造”一个异常值，这个异常值发生在怀俄明州。怀俄明州原来的数据为：（ 6.8 ，161 ， 60， 15.6），改变为：（30, 450, 100, 55），这个值可谓是非常“异常”了。这时候聚类过程发生了什么变化呢？如下图，变化是显著的！尤其是关于怀俄明州的聚类。我们发现，由于怀俄明州的数据明显的偏离其他观测数据，所以在聚类的初期，怀俄明州都被视为“异类”，聚类过程基本上对其不闻不问。只是到了倒数第四个合并过程，才把这个“异常”的孩子纳入过来。异常值的出现，使其很难与其他类别合并，所以它就被扔到了最后。
含有异常值的观测合并过程一定发生在聚类的最后吗？不尽然，它也可以在最初就开始与其他观测合并。举个例子，对怀俄明州和威斯康辛州的数据都人为改变，制造两个异常值：
> USArrests1["Wyoming", ] <- c(30, 450, 100, 55)
> USArrests1["Wisconsin", ] <- c(30, 450, 108, 56)
再次聚类的过程如下图。由图可见，怀俄明州与威斯康辛州虽然都是异常值，但是由于它俩比较接近，因此，这两个家伙竟然早早的就“结合”在了一起。所谓“沆瀣一气，同流合污”就是这个意思吧。所以说“直到最后合并”并不是异常值的主要特点，它表现更抢眼的一点是含有异常值的那个团体与其他普通团体合并时（比较红框与篮框），这两个团体的观测差别很大！我们可以用这个观测数的差别来表征这个团体内观测的“异常值趋势”。也就是说，在两个团体合并时（这是在聚类过程中一直发生的事），如果我们发现这两个团体观测数差别很大的话，那么我们怀疑那个较小的团体含有异常值的可能性更大，即较小的团体中观测是异常值的可能性更大！
计算过程简介
总结一下，问：如何衡量一个观测是“异常值”的程度呢？答：我们跟踪含有这个观测的所有两两合并过程，尤其是含有这个观测的那个团体相对于它的合并对象观测数少的哪些合并过程，对于这些情况，我们就提取两个团体观测数差异作为该观测的异常值度量。如果从聚类开始到结束关于一个观测这样的差异值可能会有好多个，我们找那个最大的作为该观测异常程度的度量。
形式化的表述如下：对于每个合并过程\(i\),涉及到了两个组(\(g_{x,i},g_{y,i}\)),计算如下的值:
\[of_{i}(x)=max(0,\frac{\|g_{y,i}\|-\|g_{x,i}\|}{\|g_{y,i}\|+\|g_{x,i}\|})\]其中，\(g_{x,i}\)表示观测\(x\)所在的那个团体，\(\|g_{x,i}\|\)表示这个团体中观测的个数。纵观整个过程，用\(OF_{H}(x)=max\{of_{i}(x)\}\)来衡量观测\(x\)是异常值的程度。当然每个观测都会得到这么一个度量值，从而达到了寻找异常值的目的。以怀俄明州为例，红框和篮框的观测数目分别为2和16，那么怀俄明州的异常程度度量值：
\[OF_{H}(怀俄明州)=\frac{16-2}{16+2} = 0.7778\]其他各个观测同样可以求得。对于以上过程，R中对应函数为outliers.ranking()，该函数在DMwR包里。使用方法为：
library(DMwR)
o <- outliers.ranking(USArrests1, method = "sizeDiff",
clus =list(dist = "euclidean",alg = "hclust",meth="ward"))
结果整理后得下表，从前到后排列的是最有可能是异常值到最没有可能是异常值的一个序列。
回到虚假交易的识别
采用这种方法对虚假交易的识别结果如下图：
从上图看到，这种方法较前两种方法更为出色：首先，在PR图中，相同的查准率，其查全率更高；其次，在CR图中，要达到相同的查全率，需要审查的交易记录数目要少很多。