·152. 智能系统学报 第5卷 式中：对数的底a可为任何正数，一般取2，此时熵 OMF(xj)=H(D)-H(D;) 的单位为“bit”.规定当P:=0时， 式中：对象x:对应的离群数据度量因子OMF(x:)的 1=0 ∑plog. 值越大，成为离群点的可能性越大 (2) =0 通过离群数据度量因子定义的离群点与LOF算 这里要特别注意熵的值并不依赖于符号（对 法中通过局部异常因子定义的离群点类似，即离群不 象、数据)本身，而只依赖于这些符号（对象、数据） 再是一个二值属性，它摒弃了以前异常定义中非此即 的概率]」 彼的绝对异常观念，更加符合现实生活中的应用.离 定义3如果X是一个离散的随机变量，S(X) 群数据度量因子OMF(x)可以量化地度量每个数据 是X可能取值的集合，P(x)是X的概率函数，那么 点x:的离群程度，OMF()的值越大，x:离群程度越 信息嫡H(X)如式(3)所定义8] 强；反之，OMF(x:)越小，x:离群程度越弱.因此，引进 H(X)=- ∑p(x)lg(p(x). (3) 该因子既可以发现离群程度强的离群点，也可以发现 xES(X) 对于含有多个属性的记录=X,…,X}的 离群程度弱的离群点，离群数据度量因子OMF(x:)是 信息熵如式(4)计算： 将数据集中的每个数据点看作一个有机整体并对其 进行统一度量的，而不像GreedAlg算法把每个数据 H()=-∑…∑[p(x1,…,xn）· ES(X1)nE5(X) 点孤立地度量.此外，文中给出离群数据度量因子 lgp(x1,…,xn)]. (4) OMF(x:)时，很好地利用了熵值并不依赖于符号（对 如果记录的属性之间相互独立，式(4)可以转 象、数据)本身，而只依赖于这些符号（对象、数据）的 化成式(5).为了简化对信息嫡的计算，在本文中一 概率4这一特性此方法不需要人为事先输入参数 律假设数据集中的记录的属性间是相互独立的. 或设置阈值，从数据自身的本质和特征出发，更有利 H(X)=-】 ∑…∑[(p(x)p(x)）· 于挖掘隐藏在数据中的知识 1e31)e3n) 3.2算法描述 lg(p(x1)p(x.)]= 根据上个小节的基本思想，图1给出了信息嫡 H(X)+H(X2)+…+H(Xn). (5) 度量的离群数据挖掘算法(outlier mining based on 3基于信息熵的离群数据挖掘算法 information entropy,OMBIE)的流程. Algorithm:信息嫡度量的离群数据挖掘算法OMBIE 3.1离群数据度量因子 Input:数据集D 信息嫡可以用来度量一个系统无序和杂乱程度， Output:离群数据集Outliers 熵值越大，说明系统中的数据越无序，系统越杂乱；反 1)初始化将离散化的数据集存入数组Array[m[n巾； 之，熵值越小，则说明系统中的数据越有序，系统越 2)计算数据集D的总信息嫡itotalInfoEtp: 纯净8].如果将信息熵理论应用到离群数据挖掘中， 3计算每个数据点对应的离群数据度量因子OMF(x,): 根据Hawkins21对离群点定性地描述，出现在数据中 For i=0tom- 计算别除第记录后得到的新数据集的信息 的离群点是使系统不“纯净”、“杂乱”的原因，相当于 熵limlnfoEtpl 系统中的“杂质”，如果去除系统中的不“纯净”因素， OMF[i]=totalInfoEtp-ElimInfoEtp[i]; 那么系统则变得相对“有序”和“纯净”，熵值比去除 End For 前相对变小.去除后，嫡值相对减小地较大，说明去除 4)将0M按大到小排序； 的因素相对“杂乱”；熵值相对减小地较小，说明去除 5)输出离群数据集。 的因素相对“纯净”.与此同时，从另外一个角度来讲， 图1算法OMBIE的描述 被去除的不“纯净”因素，也就是要寻找的离群数据， Fig.1 The Description of OMBIE algorithm 基于此理论基础，可通过测量熵值的变化来检测离群 OMBE算法的基本思想与GreedAlg算法相似， 点.为此定义了如下“离群数据度量因子”，来度量数 区别在于：1)不需要事先设置参数和阈值，从而避 据集中的离群数据。 免GreedAlg算法不能找出尽可能多的离群点或多 定义4离群数据度量因子(outlier measure fac- 识别错误的离群点；2)GreedAlg算法需要扫描数据 tor,OMF).在数据集D=(U,A)中，从对象集U中别 集k趟(k是人为事先输人的参数)，大大地增加了 除对象x:后，得到的新数据集，记作D=O:,A},其 算法的时间复杂度，而OMBE算法只需对数据扫描 与原数据集D的信息嫡的差H(D)-H(D)定义为对 一趟，从而大幅度地降低了算法的时间复杂度， 象：的离群数据度量因子，记作OMF(x:). OMBIE算法的复杂度主要受数据集中的记录