第2期 张贺，等：信息嫡度量的离群数据挖掘算法 ·153· 数(m)、每条记录的属性个数(n)、每个属性值的类 视为离群数据.选用此数据集和此方案来做实验是 别个数(c)影响.OMBE算法中，主要是2个步骤： 因为Z00数据集的背景知识对于大家是熟知的，算 1)计算每条记录对应的离群数据度量因子；2)将其 法检测出来的离群数据，可以从客观角度去分析和 排序找出离群点.第1步最坏的情况是数据集中每 检验算法的有效性和可行性. 个属性的属性值互不相等，时间复杂度O(m×n× 表1列出的是从客观实际角度，统计属性集合 m):但是实际情况下，每个属性的属性值的类别个 中每个属性对应的对象集合中的对象是与众不同的 数c远远的小于数据集的记录条数m,因此，此步骤 次数.其中，与众不同的评判标准是：对象集中某个 的时间复杂度应为O(m×n×c).第2步就是一个 属性为某个属性值时，有小于15.22%的对象取该 简单的排序，可以选用一个时间复杂度在 属性值，则此对象在这个属性上是与众不同.从客观 O(mlog m)的排序算法.所以，OMBE算法的时间 实际角度分析和解释，如果某对象入选次数越多，则 复杂度是O(m×n×c). 说明此对象成为离群点的可能性越大.在表2中，参 数取值是ENBROD、LOF和GreedAlg算法获得期望 4 实验分析 目标（将所有的爬行动物数据找出来）的较优取值； 对OMBE算法的性能进行实验分析.实验平台 而OMBE算法在进行挖掘离群点的过程中，不需要 配置如下：在PentiumIV3.0GCPU,512MB内存， 人为进行干预，即不需要事先输入任何参数和阈值： Windows XP操作系统、DBMS为ORACLE9i,采用 从表2中，可以知道OMBE算法在发现离群点的准 Visual C++6.0实现了OMBIE、ENBROD[12、LOF 确度上优于ENBROD和LOP算法.通过表1和表2 I和GreedAlg?算法Io) 的对比，OMBIE和GreedAlg算法更能挖掘出符合客 4.1应用实例分析 观规律的离群点· 选用UCI中的Z00数据集，此数据集中有101 表1Z00数据集中与众不同的对象入选次数统计 条记录，每条记录拥有18个属性一由1个动物名 Table 1 The number of distinct objects selected in ZOO 称属性、15个布尔属性、2个数值属性组成.其中，15 data set 个布尔属性与动物腿个数的离散数值属性是条件属 入选 与众不同的对象 性；动物类别的离散数值属性是决策属性，采用文献 次数 [12]中使用的方法，只取动物类别是哺乳动物和爬 7 seasnake 行动物2类.这样做的原因是：1)使用数据集中的 6 pitviper 5 slowworm 所有记录会使离群特征表现不显著；2)为了构造不 tortoise tuatara seal dolphin porpoise 平衡的分布，构造出来的新数据集中有41个哺乳动 物(89%)和5个爬行动物(11%)，其中将爬行动物 表2算法的检测准确度对比 Table 2 The contrast of algorithm accuracy 检测5个离群爬行动物数据 算法 参数 正确率/% 1 2ad 3州 4 ENBROD MinPts =45,46 seasnake pitviper tortoise slowworm seal 80 OMBIE无需事先设置参数 seasnake pitviper slowworm tortoise tuatara 100 LOF MinPts =5 seasnake pitviper slowworm tortoise seal 80 GreedAlg k=5 seasnake pitviper slowworm tortoise tuatara 100 4.2UCI数据集13] 为了测试算法对数据集维数的伸缩性，从UCI 的数据点作为离群点，得到测试数据集.由图2可 中选取UCI_ZO0(18维)、UCI_MUSHR00M(22 知，随着测试数据集维数的增加，OMBE算法的准 维)、UCL_CHESS(36维)和UCI_LUNGCANCER(56 确度变化不大并且比LOF算法和ENBROD算法有 维)4个数据集，分别均匀地加入3%具有较大偏差 所提高，与GreedAlg算法的准确度相当