第2期 张贺，等：信息熵度量的离群数据挖掘算法 ·151· 下不足之处：1)需要人为事先给出一些参数和阈 问题；2)文中提到GreedAlg算法需要全面扫描数据 值，受人为因素影响较大，从而导致检测结果的客观 集k次，因此V0代价通常比较高；3)因为使用贪婪 性较差.例如：基于距离的离群检测算法需要人为事 算法的策略，计算过程中很容易陷入局部最小，而该 先确定参数，当pct、dmin参数选择不当时，会产生 算法未对此问题采取有效措施；4)作者在文中没有 错误结论；2)不能对非数值型数据进行处理，例如： 解释依据最大熵影响(maximal entropy impact)来识 基于统计和距离的离群检测算法较难对非数值属性 别离群点的原理， 数据进行挖掘；3)可解释性和可用性差，例如：基于 2008年，倪巍伟等人提出基于局部信息熵的加 统计的方法在解释时会发生多义性.原因是：同一个 权子空间离群点检测算法(SPOD).通过对数据点 离群点有可能是不同的分布模型检测出来的，即产 在各维进行邻域信息熵分析，生成数据点相应的离 生离群点的机制有可能不惟一，从而产生了多义性 群子空间和属性权向量，对离群子空间中的属性赋 数据的维度是多少才能算高维数据？10维、 以较高的权值，进一步提出子空间加权距离等概念 100维，还是1000维.实际上，高维数据拥有多少个 采用基于密度离群点检测的思想，分析计算数据对 属性并没有一个既定的界限，而是相对于某个算法 象的子空间离群影响因子，判断是否为离群点.算法 而言.例如，基于统计的方法：只能处理单变量数据 能够有效地适应于高维数据离群点检测.缺点是在 集，即当数据维度为2时，算法不再有效；再如：基于 处理高维数据时与LOF算法处于一个数量级 深度方法，当数据维度大于3时，算法的可行性则非 0(2),而且还需要人为事先设置很多参数，从 常差；基于距离和密度的方法，当数据的维度增加到 而影响了检测的结果. 一定程度，由于距离和密度对离群数据定义的局限 同年，于绍越等人提出基于信息嫡的相对离群 性，使得方法执行效率也随之减弱.因此离群检测算 点的检测方法(ENBROD).文中首先引入一种新的 法在处理高维数据时，其可扩展性是尤为重要的， 信息熵增量的概念一去一划分信息熵增量，并在 信息熵可以用来度量一个系统无序和杂乱程 其基础上给出了每个对象所对应的相对离群点因子 (ROF)的定义.利用ENBROD算法来实现对ROF 度.嫡值越大，说明系统中的数据越无序，系统越 “杂乱”；反之，嫡值越小，则说明系统中的数据越有 的计算，但ENBROD算法也需要人为事先设置参 序，系统越“纯净”[8].出现在数据中的离群点是造 数，而这正影响了算法的运行效果[12]。 成数据无序的主要原因之一，因此利用信息熵来度 2信息熵 量、识别造成数据中无序的数据点[4]，可以客观地 信息熵被用来度量一个系统的“无序”程度和 识别出数据中的离群点].同时，利用信息嫡来度 “纯净”程度8].信息嫡是信息有用程度的一种表现 量原始数据的无序特性，客观性比较强，受人为因素 形式 影响较小，不需要人为干预，从而得出更符合客观的 定义1称四元有序组D=（U,A,V,f)为 结果.信息熵也可以运用于非数值型属性数据集，例 数据集，其中：U为所考虑对象的非空有限集合且 如标称属性数据集.本文提出一种新的离群点检测 IU川=m,称为对象集；A为属性非空有限集合，属性 方法—基于信息嫡的离群数据挖掘算法(OM 集的势为lA|=n;V=UVa,而V。为属性a的值域； BE).通过引入离群数据度量因子量化地度量每个 f:U×A→V是一个映射函数，Hx∈U,a∈A, 数据点的无序程度，即离群程度，并利用其挖掘造成 f(x,a)∈V.,对于给定对象x,f八x,a)赋予对象x在 数据无序的离群点，挖掘时无需人为事先设置参数 属性a下的属性值.数据集也可以简记为 或阈值，算法可以自动产生离群点，并能很好地解释 D=(U,A). 离群点的含义. 在本文中约定，数据集D=(U,A)中的对象集 基于信息熵的离群数据挖掘研究现状 的势为IU1=m,属性集的势为|A|=n;记录、数据 点、对象是在不同范畴下表述的同一个事物 2006年，何曾友等人提出了基于信息熵的快速 定义2假设有一组离散的符号集{1,2，…， 贪婪算法(GreedAlg)[o].GreedAlg算法事先人为设 v},每个符号具有相应的出现频率P.为了衡量用 定期望产生的离群点个数，同时参数k用于发现一 这组符号组成的特定序列的随机性（不确定性或不 个势为k的离群数据集O(101=k);但此算法存 可预测性)，定义离散分布的熵为 在以下不足：1)需要人为事先给出期望产生的离群 H=- (1) 点个数k,这会有不能发现全部和多发现离群点的