特异群组挖掘的框架算法

对于τ-特异群组挖掘问题，传统的聚类算法无法直接使用。因为，聚类算法通常要求用户指定一个相似性阈值（或相关参数），而这样的限制不能保证结果中相似对象的数量满足阈值τ。一种修改是通过多次调用聚类算法调整参数值，终止的条件是当簇中对象的数量满足用户指定的数量τ。但是，由于重复多次的聚类算法调用，造成大量冗余的计算。更糟糕的情况是，当多个参数之间相关时，计算是相当困难的。虽然层次聚类方法看上去能够简单地使用一个对象数量的阈值作为参数提前终止聚类，且易于处理任何形式的相似性，然而，对象间相似性的计算具有相当高的复杂度［12］。

还有一些聚类算法给出如何选择参数阈值的指导，如DBSCAN算法中的MinPts =4［13］；或者自动调整参数阈值，如SynC算法［14］。但是，对于一般用户，根据参数阈值指导选择参数仍然是一项困难的工作，并且算法推荐的默认值在很多情况下并不适合，因此用户仍然必须进行许多尝试；而自动参数调整方法在某些应用场景中会显示出局限性，例如当为了满足特异群组中用户指定数量τ对象的情况，自动策略如SynC中的MDL（ minimum description length）原则并不适合。此外，Top-c聚类［15］是一种试图将相似性度量阈值转化为簇个数的聚类算法，即将数据集中的数据对象划分到符合簇质量定义的c个簇中，然而，簇的数量c并不能决定对象的数量，即c个簇可能包含数据集中大量的数据对象（如70%）。

因此，简单地修改聚类算法处理τ-特异群组挖掘问题不是很好的解决方案，本质是因为两者的目的不同。

值得指出的是，Gupta等提出bregman bubble clustering（BBC）算法［16］挖掘c个密集的簇，包含τ个对象，这和特异群组挖掘问题的出发点相似。然而，一方面，BBC算法需要指定c个簇的代表点，然后将对象指定到与代表点相近的对象中，直到τ个点被聚类。对于用户而言，指定这样的代表点是困难的；另一方面，BBC试图同时限制对象的数量和簇的数量c，因此又遇到了τ个对象必须划分到c个簇的困境。(www.xing528.com)

图7-3　τ-特异群组挖掘算法框架［4］

考虑到上述问题，下面给出一个特异群组挖掘框架算法。该算法是一个两阶段算法［4］，如图7-3所示。第一阶段是找到给定数据集中的最相似的数据对象对，并采用剪枝策略将不可能包含特异对象的对象对删除，然后从候选对象对中计算得到特异对象；第二阶段将对象对划分到特异群组中。

在第一阶段，采用top k相似点对查询策略找到top k个相似点对，在这些相似点对中的对象被认为是候选对象。不难证明，k与τ之间的关系为k=τ×（τ—1）/2。因为τ是一个相对小的数，对于较小的k，具有剪枝策略的top k相似点对查询算法［17，18，19］有良好的运行效率。其中，即使对于高维数据对象，相似点对查询算法复杂度可以降到O（（dn/B）1.5 ）［18］ （d为数据对象的维度，n为数据对象集中对象数，B为数据集所在外存页字节数）。之后，在获得的top k个点对中找到top τ个具有最大特异度评分的对象作为特异对象。在第二阶段，根据特异群组定义，特异群组中的每对对象之间必须相似，因此特异群组事实上是一个最大团，采用最大团挖掘算法［20，21］将所有的τ个特异对象划分到相应的特异群组中。最大团挖掘的最糟糕情况时间复杂度为O（τ3τ/3 ） ［21］（τ为图的顶点数），因为特异群组挖掘算法第一阶段的输出为topτ个对象，而τ是一个相对较小的数，因此，对τ个数据对象集发现其最大团而言，特异群组挖掘算法具有较好效率。