PageRank算法在孤立点检测中的应用
摘 要:简略介绍了PageRank算法，给出其在孤立点检测应用中的算法及实验结果和分析，最后将该算法与其他算法进行比较。结果证明，该方法能较准确地检测到孤立点，并能适应各种图形。
关键词:PageRank; 算法; 孤立点检测
在数据挖掘和图像分析中，孤立点的检测是一个重要的内容。在很多情况下，发现孤立点比发现普通情况更有意义，如：KNORR E M和NG R T把孤立点检测方法应用到运动员数据NHL(National Hockey League)的分析中，从而找到那些特别的运动员；YAMANISHI K和TAKEUCHI J将检测方法应用到股票的变动检测中等等。另一方面，PageRank(页面分级)算法是PAGE L和BRIN S在就读斯坦福大学研究生院时研发出来的,他们后来创建了著名的Google公司，现在分别担任该公司的CEO和总经理。而PageRank算法就是Google搜索服务的一个核心技术。事实证明该算法在搜索服务上是非常成功的。
页面分级的思想与在二维平面上作孤立点检测的思想非常相近,于是本文把PageRank算法运用到孤立点检测中，并给出实验结果和本文算法与其他的主流算法的比较。
1 PageRank算法
1.1 PageRank算法的核心思想
对于世界上众多的网页，这些网页有的十分重要，而有的重要性十分轻微。当想要快速地在这么多的网页中找到想要的网页时，无论想查关于哪一方面的信息，都会希望别人给出的查找结果是那些重要的网页，而不是微乎其微的网页。所以在查找之前就应该把网页(或者称为页面)进行重要性排序。用什么来衡量一个页面的重要性呢？计算机能否由页面的内容来判断页面的重要性呢？答案是不能，计算机还没先进到这个程度。但PageRank算法给出了一个行之有效的思想：从许多优质的页面链接过来的页面，必定还是优质的页面[5]。这一思想容易理解，如果有很多的页面链接到A页面，那么就认为A页面是比较重要的，那如果B页面被A页面链接(反过来说也就是A页面链出到B页面），因为A页面被一个认为重要的页面链接，所以也就把B页面的重要性作一个大幅度的提高，认为B页面也是重要的。通过互联网中页面间本身就存在的链接，是容易算得页面的重要性的。
但另一方面，有些页面为了提高重要性，相互间做一种商业上的链接，为了杜绝这一种情况，PageRank在计算页面重要性的时候，对于链接进来的页面也是要考虑其重要性的，即重要性高的页面链接进来，则对当前页面重要性的提高有很大帮助；重要性低的页面链接进来，则对当前页面重要性的提高帮助很小。
1.2 PageRank算法的简略步骤
假设有N个页面，这些页面间有相互链接。
(1) 制作一个N×N的矩阵S，如果页面a链出到页面b，则S(a,b)=1；
(2) 将矩阵S转置，得到矩阵S′，因为这里关心的不是该页面链出到多少其他的页面，而是有多少其他的页面链进来当前页面；
(3) 对S′的每一列，算出非零元的总数sum，在把该列中的每一个非零元除以sum。这样就得到一个新的矩阵M；
(4) 算出M的特征值和特征向量;
(5) 找出最大特征值所对应的特征向量，并把该特征向量标准化。标准化后的结果就是各个页面对应的重要性的度量值，称为PageRank值。
2 PageRank算法在孤立点检测中的应用
2.1 应用思想
