形式化描述特异群组挖掘

设Fd为d-维特征空间，D= ｛O1， O2， …， ， …， ｝是对象集合，Oi∈Fd。两个对象Oi和Oj间的相似性f由相似性函数sim（Oi， Oj）计算（0≤f≤1）。

定义7.1（相似对象）：给定一个相似性阈值δ，对于一个对象Oi（ Oi ∈ D），如果数据集中至少存在另一个对象Oj，使得sim （Oi， Oj） ≥ δ。那么对象Oi称为对象集合D中关于δ的相似对象。

在特异群组挖掘问题中，由于大部分数据对象都是不相似的，只有群组中的对象才是相似对象，表现出相异于大部分对象的特性，因此，在特异群组挖掘问题中，相似对象被称为特异对象，特异对象的集合记为P，剩下不在P中的对象记为D\P。相应地，度量数据对象是否为相似对象的相似性函数被称为特异度度量。特异度度量是定义一个特异群组的基础。

对于一个数据集，形成特异群组集合中的数据对象相对整个数据集中的数据对象是少数的。在很多情况下，指定合适的相似性阈值对用户而言是困难的。例如，在证券市场合谋操纵账户挖掘中，多个账户在一定时间段内的多次相同交易行为是价格操纵的基本行为。简单直观地可以用相同交易行为的数量l来定义两个账户的相似度，用这个数量作为相似度阈值。然而，在实际实施过程中，这个相似性阈值对用户而言是困难的。

但是，对于特异群组挖掘需求而言，用户更容易知道的是他们希望发现的特异对象的数量，例如，作为证券监管者，更加清楚他们希望发现的涉嫌操纵股价的账户数量。进一步来说，特异群组挖掘问题是挖掘“少量”数据对象构成的特异群组，一般观点认为20%应该已经很少了，但在许多应用中，如证券市场合谋操纵账户挖掘这个例子中，10%都不是“少量”，操纵账户可能小于0.2%或更小才是“少量”，这个数量完全由实际问题的用户理解所决定。例如，用户可以根据预算的经费和时间等指定其期望的特异对象数量。同时，这也是用户的直接需求，用户易于理解和指定。于是，对特异群组挖掘问题进行定义。

定义7.2（ τ-特异群组挖掘）：特异群组挖掘是在一个数据集中发现特异群组的过程，这些特异群组形成的集合包含τ个数据对象，τ是一个相对小的值（τ＜＜n×50%， n是数据集中对象总个数）。

性质7.1（相似性阈值的存在性）：给定一个特异对象的数量的阈值τ，一个潜在的相似性阈值δ存在，对于τ个特异对象形成的集合P中每一个对象O，都存在至少有另一个对象Q与其相似，sim（O， Q） ≥ δ。

性质7.1说明了数据集中具有相似性的数据对象（特异对象）的数量τ可以反映数据集中对象间的相似性阈值，即选择一个特异对象数量作为代替相似性阈值的方法是合适的。

特异对象的数量τ不仅易于用户描述其需求，而且因为τ相对较小，算法可以利用τ设计剪枝策略，以提高大数据集特异群组挖掘算法的效率。

定义7.3（对象的特异度评分，特异对象）：一个对象Oi的特异度评分ω是Oi和该数据集中其他对象间的最大相似性值，即ω（Oi）=maX1≤j≤n， j≠iS （Oi，Oj ），其中S（Oi，Oj）表示对象Oi和Oj的相似性度量值。

给定一个特异度评分阈值δ＞0，当一个对象O的特异度评分ω（Oi）＞δ，则该对象O是一个特异对象。用Ö来表示在整个数据集中θ特异对象的集合。

在特异度评分定义的基础上，定义特异群组。

定义7.4（特异群组）：一个特异对象的集合G是一个候选特异群组，当且仅当|G |≥2，并且G中的每两个对象都是相似的，即对于Oi，Oj ∈ G，有S（Oi， Oj） | ≥δ。如果不存在任何一个G的超集是一个候选特异群组，那么G是一个特异群组。

特异群组的紧致性度量如下：

设Fd为d-维特征空间，D= ｛O1， O2， …， ， …， ｝是对象集合，Oi∈Fd。两个对象Oi和Oj间的相似性f由相似性函数sim（Oi， Oj）计算（0≤f≤1）。

定义7.1（相似对象）：给定一个相似性阈值δ，对于一个对象Oi（ Oi ∈ D），如果数据集中至少存在另一个对象Oj，使得sim （Oi， Oj） ≥ δ。那么对象Oi称为对象集合D中关于δ的相似对象。

在特异群组挖掘问题中，由于大部分数据对象都是不相似的，只有群组中的对象才是相似对象，表现出相异于大部分对象的特性，因此，在特异群组挖掘问题中，相似对象被称为特异对象，特异对象的集合记为P，剩下不在P中的对象记为D\P。相应地，度量数据对象是否为相似对象的相似性函数被称为特异度度量。特异度度量是定义一个特异群组的基础。

对于一个数据集，形成特异群组集合中的数据对象相对整个数据集中的数据对象是少数的。在很多情况下，指定合适的相似性阈值对用户而言是困难的。例如，在证券市场合谋操纵账户挖掘中，多个账户在一定时间段内的多次相同交易行为是价格操纵的基本行为。简单直观地可以用相同交易行为的数量l来定义两个账户的相似度，用这个数量作为相似度阈值。然而，在实际实施过程中，这个相似性阈值对用户而言是困难的。

但是，对于特异群组挖掘需求而言，用户更容易知道的是他们希望发现的特异对象的数量，例如，作为证券监管者，更加清楚他们希望发现的涉嫌操纵股价的账户数量。进一步来说，特异群组挖掘问题是挖掘“少量”数据对象构成的特异群组，一般观点认为20%应该已经很少了，但在许多应用中，如证券市场合谋操纵账户挖掘这个例子中，10%都不是“少量”，操纵账户可能小于0.2%或更小才是“少量”，这个数量完全由实际问题的用户理解所决定。例如，用户可以根据预算的经费和时间等指定其期望的特异对象数量。同时，这也是用户的直接需求，用户易于理解和指定。于是，对特异群组挖掘问题进行定义。

定义7.2（ τ-特异群组挖掘）：特异群组挖掘是在一个数据集中发现特异群组的过程，这些特异群组形成的集合包含τ个数据对象，τ是一个相对小的值（τ＜＜n×50%， n是数据集中对象总个数）。

性质7.1（相似性阈值的存在性）：给定一个特异对象的数量的阈值τ，一个潜在的相似性阈值δ存在，对于τ个特异对象形成的集合P中每一个对象O，都存在至少有另一个对象Q与其相似，sim（O， Q） ≥ δ。(www.xing528.com)

性质7.1说明了数据集中具有相似性的数据对象（特异对象）的数量τ可以反映数据集中对象间的相似性阈值，即选择一个特异对象数量作为代替相似性阈值的方法是合适的。

特异对象的数量τ不仅易于用户描述其需求，而且因为τ相对较小，算法可以利用τ设计剪枝策略，以提高大数据集特异群组挖掘算法的效率。

定义7.3（对象的特异度评分，特异对象）：一个对象Oi的特异度评分ω是Oi和该数据集中其他对象间的最大相似性值，即ω（Oi）=maX1≤j≤n， j≠iS （Oi，Oj ），其中S（Oi，Oj）表示对象Oi和Oj的相似性度量值。

给定一个特异度评分阈值δ＞0，当一个对象O的特异度评分ω（Oi）＞δ，则该对象O是一个特异对象。用Ö来表示在整个数据集中θ特异对象的集合。

在特异度评分定义的基础上，定义特异群组。

定义7.4（特异群组）：一个特异对象的集合G是一个候选特异群组，当且仅当|G |≥2，并且G中的每两个对象都是相似的，即对于Oi，Oj ∈ G，有S（Oi， Oj） | ≥δ。如果不存在任何一个G的超集是一个候选特异群组，那么G是一个特异群组。

特异群组的紧致性度量如下：

定义7.5（紧致性）：一个特异群组G的紧致性ζ是该群组中所有对象的总体特异度评分之和，即

设C是特异群组集，Ç的紧致度是Ç中所有特异群组紧致度之和。

前已述及，特异度评分阈值δ在实际应用中用户是很难设置的。为了克服这个困难，用户可以设置一个特异群组集合的对象总数阈值τ，这对于用户以及特异群组挖掘问题本身而言是一个容易设置和接受的阈值。这两个阈值（τ和δ）间的关系如下：

给定一个相对小的阈值τ（τ≥2） （特异群组集合中的对象个数相对较少，因此τ的值相对较小），可以找到具有最高特异度评分的τ个对象。那么，第τ个对象的特异度评分就是相应的特异度评分阈值δ，即这τ个对象具有最高的特异度评分值，并且包含τ个对象的特异群组集Ç的紧致度最大。

在对象特异度评分定义基础上，给出进一步深化的特异群组挖掘任务定义。

定义7.6（ τ-特异群组挖掘）：特异群组挖掘问题是找到数据集中所有的特异群组，满足特异群组集合Ç的紧致度最大，且|Ç|=τ，其中τ（τ≥ 2）是一个给定阈］值。

定义7.5（紧致性）：一个特异群组G的紧致性ζ是该群组中所有对象的总体特异度评分之和，即

设C是特异群组集，Ç的紧致度是Ç中所有特异群组紧致度之和。

前已述及，特异度评分阈值δ在实际应用中用户是很难设置的。为了克服这个困难，用户可以设置一个特异群组集合的对象总数阈值τ，这对于用户以及特异群组挖掘问题本身而言是一个容易设置和接受的阈值。这两个阈值（τ和δ）间的关系如下：

给定一个相对小的阈值τ（τ≥2） （特异群组集合中的对象个数相对较少，因此τ的值相对较小），可以找到具有最高特异度评分的τ个对象。那么，第τ个对象的特异度评分就是相应的特异度评分阈值δ，即这τ个对象具有最高的特异度评分值，并且包含τ个对象的特异群组集Ç的紧致度最大。

在对象特异度评分定义基础上，给出进一步深化的特异群组挖掘任务定义。

定义7.6（ τ-特异群组挖掘）：特异群组挖掘问题是找到数据集中所有的特异群组，满足特异群组集合Ç的紧致度最大，且|Ç|=τ，其中τ（τ≥ 2）是一个给定阈］值。