令 BA,在 X上属性集 B的不可区分关系定义为IND(B)={(X_is, X_is1)∈X×X|A_j∈B, f(X_is, A_j )=f(X_is1, A_j)}∪{(X_is, X_i's2)∈X×X|A_j∈B, f(X_is, A_j )=f(X_i's2, A_j)}(s₁∈{1,2,…,r_i },s₂∈{1,2,…,r_i'}), X/IND(B)={B₁,B₂,…,B_k}表示不可区分关系IND(B)在 X上导出的划分.[X_is]_B表示包含 X_is∈X在 B上的等价类.

定义1 给定一个矩阵数据集 X, 对于任意A_j∈A, IND({A_j})是由A_j确定的不可区分关系, X/IND({A_j})={B₁,B₂,…,B_k}记为由IND({A_j})导出的一个划分. IND({A_j})在 X上的信息熵定义为

ME({A_j})=-∑^k_l=1(|B_l|)/(∑ⁿ_i=1r_i)lb((|B_l|)/(∑ⁿ_i=1r_i))(1)

其中,(|B_l|)/(∑ⁿ_i=1r_i)为等价类B_l的概率,n为对象数量; ∑ⁿ_i=1r_i为矩阵数据集中所有对象的记录条数之和.

对于任意A_j∈A, 若 X/IND({A_j})={X}, 则信息熵ME({A_j})取得最小值0; 若 X/IND({A_j})={{X_is}:X_is∈X}, 则信息熵ME({A_j})取得最大值lb(∑ⁿ_i=1r_i ), 即0≤ME({A_j})≤lb(∑ⁿ_i=1r_i ). 熵越大,不确定性越高.

定义2 给定一个矩阵数据集 X, 对于任意的Aj∈A, Xi在属性Aj上的值域为V AjXi, 对于 Xi在属性Aj上的任意的y∈V AjXi, 有By={Xis|f(Xis, Aj )=y}, 从 X中移除By后,在属性Aj上的信息熵定义为

ME_Aj(X_is,B_y )=-∑^k_l=1,l≠y(|B_l|)/(∑ⁿ_i=1r_i -|B_y|)×lb((|B_l|)/(∑ⁿ_i=1r_i -|B_y|))(2)

其中,X_is在属性 A_j上的相对信息熵RE_Aj(X_is),且

RE_Aj(X_is)={1-(ME_Aj(X_is,B_y))/(ME({A_j})), ME({A_j})>ME_Aj(X_is,B_y)

0, 其他(3)

对于任意 A_j∈A,X_is∈X, 当删除B_y时,若信息熵大幅降低,则可认为B_y中的元素在 X中出现的频率很低; 反之,若信息熵减幅很小或增加,则认为B_y中的元素在 X中出现的频率很高.因此,相对信息熵RE_Aj(X_is)能够反映 X_is的孤立程度.相对信息熵RE_Aj(X_is)越高,则 X_is越孤立.

若 X/IND({A_j})={B_y, X-B_y}, 则ME_Aj(X_is, B_y)=0, 相应地, RE_Aj(X_is)=1. 因此,对于任意的 X_is∈X, 有0≤RE_Aj(X_is)≤1.

给定一个矩阵数据集 X, 为找到X中的孤立点,首先可根据一个给定的标准将 X中的所有对象分成两类:属于 X中的少数群体的对象和属于 X中多数群体的对象.此标准可定义为:

定义3 给定一个矩阵数据集 X, 对于任意Aj∈A, Xi在属性Aj上的值域为VAjXi, 对于任意的y∈VAjXi, 有By={Xis|f(Xis, Aj )=y}. 判别 Xis属于哪一类的相对标准为

RC(X_is, B_y)=|B_y|-(∑^k_l=1,l≠y|B_l|)/(k-1)(4)

当B_y=X时, RC(X_is, B_y)取得最大值∑ⁿ_i=1r_i; 当B_y=1且k=2时, RC(X_is, B_y)取得最小值2-∑ⁿ_i=1r_i.

若RC(X_is,B_y)>0, 则X_is属于多数类; 反之,若RC(X_is, B_y)≤0, 则 X_is属于少数类.

定义4 给定一个矩阵数据集 X,对于任意Aj∈A, Xi在属性Aj上的值域为V AjXi, 对于任意的y∈V AjXi,有By={Xis|f(Xis,Aj )=y}, 则Xis在属性Aj上的孤立度可定义为

OD_Aj(X_is )=RE_Aj(X_is)×

(∑ⁿ_i=1r_i-RC(X_is,B_y))/(2∑ⁿ_i=1r_i)(5)

少数类中对象与多数类中的对象相比,少数类中对象更可能为孤立点.如果RC(X_is,B_y)≤0, 则X_is属于少数类; 相应地,相对信息熵RE_Aj(X_is)越大,孤立度也越大,因此, X_is可能越孤立.

基于给定 X_is∈X在属性A_j上的孤立度,下面给出矩阵对象耦合度的定义.

定义5 给定一个矩阵数据集 X, 对于任意一个对象X_i, 耦合度定义为

Cou(X_i)=

(∑m j=1∑ris=1(1-ODAj(Xis))×WAj(Xis))/(m×|ri|)(6)

其中, m为属性数量; 对于任意的A_j∈A, W_Aj:X→(0,1]是一个权重函数, W_Aj(X_is )=((|[X_is]^{A_j|)/(∑n_i=1r_i))1/2. 一个对象的权重越小,其包含的元素出现的频率越低,也就越孤立.}

考虑对象的耦合度后,可进一步定义矩阵对象的内聚度.

定义6 给定一个矩阵对象 Xi, 对于任意Aj∈A, Xi在属性Aj上的值域为V AjXi, 对于任意y∈V AjXi, 有vy={Xis|f(Xi,Aj )=y}, 则 Xi在属性Aj上的信息熵为

ME_Aj(X_i )=-∑_{y∈V ^AjXi}(|v_y|)/(r_i)lb((|v_y|)/(r_i))(7)

由于0≤ME_Aj(X_i)≤lb r_i, 所以归一化为HE_Aj(X_i )=ME_Aj(X_i )/lb r_i.

可见,一个矩阵对象内聚度可定义为

Coh(X_i)=(∑^m_j=1ME_Aj(X_i ))/m(8)

在定义了一个矩阵对象的耦合度和内聚度的基础上,该矩阵对象的孤立因子可定义为:

定义7 给定一个矩阵对象 X_i, 其孤立因子为

OF(X_i )=(1-Cou(X_i))×

(1+Coh(X_i))(9)

在矩阵数据中检测孤立点,既要考虑矩阵对象的耦合度,也要考虑内聚度,但对象的耦合度占主要因素,因此,要减少内聚度所占的权重,将内聚度加1.矩阵对象的孤立因子越大,孤立度越大.

给定一个矩阵数据集 X={X₁,X₂,X₃,X₄,X₅},A={A₁,A₂}, 见表2.

表2 一个矩阵数据集
Table 2 A matrix-object data set

矩阵对象 X₁的孤立因子计算过程如下:

1)根据定义2,每个属性上的信息熵分别为

ME({A₁})=1.927 5

ME({A₂})=1.828 9

2)根据定义3,对象 X₁中,每个 X_1s所在的等价类删除时的信息熵为

ME_A1(X₁₁)=1.685 5

ME_A2(X₁₁)=ME_A2(X₁₃)=1.657 7

ME_A1(X₁₂)=ME_A1(X₁₃)=1.488 5

ME_A2(X₁₂)=1.352 0

由此可得相对熵

RE_A1(X₁₁)=0.125 5

RE_A2(X₁₁)=RE_A2(X₁₃)=0.093 6

RE_A1(X₁₂)=RE_A1(X₁₃)=0.227 7

RE_A2(X₁₂ )=0.260 7

3)根据定义4,相对标准为

RC([X₁₁]_A1)= 5.500 0

RC([X₁₁]_A2)=RC([X₁₃]_A2)=6.750 0

RC([X₁₂]_A1)=RC([X₁₃]_A1)=1.750 0

RC([X₁₂]_A2)=1.750 0

4)根据定义5,可得

OD_A1(X₁₁)=0.043 6

OD_A2(X₁₁)=OD_A2(X₁₃)=0.029 2

OD_A1(X₁₂)=OD_A1(X₁₃ )=0.102 8

OD_A2(X₁₂ )=0.117 7

5)根据定义6,可得对象X₁的耦合度为

Cou(X_i )=0.570 2

6)根据定义7,可得对象X₁的内聚度为

Coh(X_i)=0.579 2

7)根据定义8可得对象 X₁的孤立因子为

OF(X₁ )=0.678 8

同理可得,OF(X₂ )=0.820 3、OF(X₃ )= 0.820 3、OF(X₄ )= 0.728 1和OF(X₅ )=1.265 9. 可见, X₅的孤立因子最大,即孤立度最大.

图1给出了分类型矩阵数据孤立点检测算法(outlier detection algorithm for matrix-object data, ODAMD)的伪代码.

ODAMD算法

输入:一个矩阵数据集

输出: P个孤立点

for i=1 to n

根据定义5,计算每个矩阵对象的Cou(X_i);

根据定义6,计算每个矩阵对象的Coh(X_i);

根据定义7,计算每个矩阵对象的OF(X_i);

end

对OF(X_i)进行降序排序,选择P个最大值的对象为孤立点

图1 ODAMD算法伪代码
Fig.1 The pseudocode of ODAMD algorithm

算法ODAMD的时间复杂度为O(m×(|V ^j|+|V ^j|²)). 其中, |V ^j|为属性A_j上的值域.

在大多数情况下,真实数据集的分布是无序的.实验中3个真实数据集中的孤立点也没有明确标注信息.为解决此问题,首先要对给定的数据集进行预处理.通过可视化技术,可以删除一些点,以获得相对清晰的数据分布,也可以清楚地看到一些对象是孤立的,因此,能够得到一个带有标记信息的数据集.最后,在新的数据集上运行本算法并评估算法的性能.为获得给定分类型数据集的分布,使用多维尺度变换(multi-dimensional scaling, MDS)技术^[15]来可视化数据集,该技术的主要方法是将距离公式获得的n阶距离方阵传递给Matlab的mdscale函数,获得n个点的坐标,然后可视化这n点来反映数据的分布.以下是3个真实数据集的预处理过程.

3.1.1 Market basket data

从Data website下载的Market basket data记录了1 001个用户交易信息,每个用户有4个属性(用户ID、时间、产品名称和产品ID).本研究只考虑用户ID和产品ID,而不考虑时间和产品名称,因为所有用户在属性时间上都具有相同的值,而产品名称的值与产品ID是一一对应的. 此外,Market basket data的突出特点是每个用户都有7条交易记录. 因此, 每个用户是一个典型的分类型矩阵对象.

Market basket data的预处理过程为:首先,通过MDS技术对数据集进行可视化; 然后,在坐标系中选择位于x<-0.2,y<0.2或x>0.5内的对象,形成一个包含319个矩阵对象的新数据集.新数据集的分布如图2.

图2 预处理后的Market basket数据集分布
Fig.2 Distribution of preprocessed Market basket data

其中,“+”和“+×”表示新生成的数据集,“+”表示的对象可认为孤立点.从图2可见,经过统计分析可得,“+”表示的对象属性值出现频率很低.

3.1.2 Microsoft web data

从UCI下载的Microsoft web data是通过对网站www.microsoft.com上的日志进行采样和处理而创建的.它记录了32 711名匿名用户在1998年2月访问该网站时的信息,每个人可多次访问网站.每个用户都有2个属性,包括用户ID和统一资源定位符(uniform resource locator, URL). 因此, 每个用户都是一个分类型矩阵对象.

预处理过程为:在初始数据可视化后,选择横坐标值位于x<0或x>0.68的点,形成589个对象的新矩阵数据集,然后可视化新矩阵数据集,结果如图3.

图3 预处理后的Microsoft web数据集分布
Fig.3 Distribution of preprocessed Microsoft web data

从图3可见,数据集由两部分组成,其中由符号“+”表示的对象可被视为新数据集中的孤立点.

3.1.3 MovieLens data

实验使用了MovieLens数据集,它包含6 040个用户对3 900部电影的1 000 209条评分,由4个属性表示,分别为UserID(用户编号)、MovieID(电影编号)、Rating(评分)和Timestamp(时间).因为属性Timestamp在每个记录具有不同的值,因此不考虑该属性.

预处理过程为:在初始数据集可视化后,选择坐标系中-0.1<x<0.1, y<-0.3或y>0.6范围内的对象作为新的数据集.新数据的可视化结果如图4.

图4 预处理后的MovieLens数据集分布
Fig.4 Distribution of preprocessed MovieLens data

从图4可见,数据集是由一个大类和一些散点组成的,这些由符号“+”描绘的散点可看作是孤立点.

3.1.4 数据预处理结果

预处理后的数据集如表3.其中, p为孤立点的数目.

表3 预处理后的数据集
Table 3 Preprocessed data set

3.3 实验结果

为验证本研究提出的孤立点检测算法的有效性,将ODAMD算法与基于共同近邻(common-neighbor-besed, CNB)算法^[17]、LOF和基于信息熵(information entropy-beased, IE-based)算法^[8]进行比较.由于现阶段没有方法可以处理分类型矩阵数据集,所以先将矩阵数据集进行了压缩,每个矩阵对象用频率最高的属性值来表示,新生成的数据集中,一个对象只有一条记录,然后在新生成的数据集中进行实验.

真实数据集上的实验结果如表4至表6.从表4至表6可见,提出的孤立点检测算法效率很高,但其他方法并不理想. 因为数据集进行压缩时,会导致许多信息的丢失.

表4 不同算法在真实数据集中的精确度
Table 4 Precision of different algorithms in real data sets

表5 不同算法在真实数据集中的召回率
Table 5 Recall of different algorithms in real data sets

表6 不同算法在真实数据集中的F-度量
Table 6 F-measure of different algorithms in real data sets

为进一步验证提出的算法的扩展性,在真实数据集上设置不同的孤立点数目,检测新算法与比较算法的精确度,实验结果如图5至图7.

图5 不同算法在Market basket数据集上不同孤立点数目的精确度
Fig.5 (Color online)Precision of different algorithms for different number of outliers in Market basket data

图6 不同算法在Microsoft web数据集上不同孤立点数目下的精确度
Fig.6 (Color online)Precision of different algorithms for different number of outliers in Microsoft web

图7 不同算法在MovieLens数据集上不同孤立点数目下的精确度
Fig.7 (Color online)Precision of different algorithms for different number of outliers in MovieLens data

从图5至图7可见,随着孤立点数目的增加,提出算法的准确率比较高且比较稳定,而3个比较算法精确度偏低,且不稳定.比如CNB算法在数据集中存在4个孤立点时,精确度为1,但在其他孤立点数目的情况下,精确度比较低.