该文提出一种可适用于高维数据空间的相似度和密度的度量方法(实际上它可以适用于任何维度的数据).与传统的直接采用两个数据对象之间的距离(或其它系数)来定义其相似度的做法不同,这是一种间接的方法,首先根据两个数据对象的最近邻列表的交集,即它们的共享最近邻来定义其间的相似度，换言之，两个数据对象之间的相似度是通过它们共同的近邻对象来加以确认.具体地，如果对象A接近于对象B，且A和B同时都接近某个对象集合C，则我们说A和B相似具有很高的置信度，因为它们之间的相似度得到了集合C中对象的确认.这种共享最近邻的思想最先出现在R.A.Jarvis和E.A.Patrick于1973年提出的一种聚类方法中（文中简称J-P方法）.当时提出这种方法是为了解决在低维数据空间中，如何采用非参数化的方法来解决非球形数据簇的聚类问题.与J-P方法类似的思想在两个新近提出的层次聚类算法ROCK和CHAMELEON中有所体现.我们发现，这种基于共享最近邻的方法具有一些良好的性质.首先它能够识别数据分布密度不同的簇，因为该方法具有自我伸缩性能.即，位于不同密度区域的数据对象，所包含一定数量k的最近邻的邻域大小也不同，密集区域中的数据对象所需的邻域半径较小，而稀疏区域中的数据对象要包含同样数量的最近邻则需要较大半径的邻域.这样，聚类过程不再依赖于传统的基于距离的密度度量，而是取决于了近邻列表长度k和共享最近邻对象数量的设定.其次，这种方法具有传递性，即，如果数据对象a与b之间存在许多（超过阈值）相同的最近邻对象，而数据对象b与c也同样具有许多共离最近邻对象，那么数据对象a、b和c将属于同一个簇.这一传递性使得这种聚类方法能够处理不同的形状和不同大小的簇.进一步地，我们基于一个点的高度相似的近邻来定义其密度，这一密度值越大，该点作为代表点的可能性就越高;反之，该点就有可能是噪音数据或孤立点，该文通过一组阈值来控制代表点和噪音数据的确定.在此基础上，该文提出一个基于共享最近邻的聚类算法（简称SNNC算法）.该算法首先找出每个数据对象的k个（由参数确定）最近邻，然后根据共享最近邻计算两两对象之间的相似度，并对每个数据对象计算其密度.于是通过去除噪音数据，关联非噪音数据点与核心或代表点来构造簇.SNNC算法的原始思想来源于J-P方法，但是J-P方法存在一些不足之处.J-P方法基于图进行聚类，利用一个阈值参数控制数据对象之间的链接强度，链接强度小于阈值的边则被删除，而图中剩余的相连成分即为所要求的聚类结果.问题在于J-P方法采用的是单链接策略，因此阈值t必须设置得相当高，否则当数据集中的模式（主要指的是簇分布）不十分明显时，有可能得到质量不好的结果.特别地，当阈值设为1时，两个由不同（分布）的数据构成的簇，即使它们之间只存在一个链接，也有可能合并为一个簇.而另一方面，如果阈值t设的太高，则一个自然簇可能会被划分为许多小簇，这是由于自然簇内相似性不一所致（即有可能从链接强度较低的地方被分离）.对于实际的数据集而言，可能不存在正确的阈值.为了解决这一问题，SNNC算法采用了两组阈值，其中一组参数与图中链接的强度相关，另一组与每个数据对象的强链接数量相关，阈值由相应的参数确定.