基于EP的数据流分类算法研究

发布时间：

郑州大学硕士学位论文
基于EP的数据流分类算法研究
姓名：陈崇超申请学位级别：硕士专业：计算机软件与理论
指导教师：范明20070501

郑州人学硕｝学位论文
摘要
在信用卡欺诈监测、差异性营销、网络入侵检测和传感器网络等应用中，随着时间的更迭而生成一种新型的具有连续、有序、变化、快速到达、海量等特征的数据，即“数据流”，其数据量大且数据分布可能会发生变化（即概念漂移）。如何从海量的数据中训练模型来有效地预测未来的数据趋势，正是数据流上的分类算法所要解决的难点，同时也是一件非常有意义的工作。
分类是数据挖掘中的重要分支之一，在很多领域都具有广泛的应用。现在已有许多成熟的分类方法，如决策树、贝叶斯网络、神经网络、支持向量机等，但是在处理数据流时，仍然面临着新的挑战。近年来研究者们提出了几种数据流上的分类方法：ＶＦＤＴ和ＣＶＦＤＴ、ＶＦＤＴｃ、集成分类方法ＥｎｓｅｍｂｌｅＣｌａｓｓｉｆｉｅｒｓ等。集成多个分类器的方法通常可以提高分类准确率，特别是基分类器具有一定的差异性时，它往往比单分类器的准确率高。Ｗａｎｇ等人提出的集成方法以ｃ４．５、
ＲＩＰＰＥＲ、Ｎａｉｖｅ
Ｂａｙｅｓｉａｎ分类为基分类器，而采用其他类型的算法作为基分类
器仍需进一步研究。而ｅＥＰ具有良好的区分能力，并且基于ｅＥＰ的分类算法可以与其他算法相媲美，同时基于ｅＥＰ的分类方法已经成功地应用于ＤＮＡ分析、文本
自动分类等领域。
基于以上考虑，本文提出一种基于ｅＥＰ的数据流分类器集成算法ＣＥＥＰＣＥ。本文的主要工作是：在总结数据流的特性和分析基于ｅＥＰ传统分类算法的算法思想的基础上，将基本窗口和滑动窗口的概念与ｅＥＰ分类算法有机的结合以适应数据流的特性并解决概念漂移的问题；其次在分类器构造的过程中，提出了加权集
成分类器的思想；最后，在未知样本分类的过程中，结合数据流挖掘分析多考虑
最近最新数据的特点，对不同的基分类器赋予不同的权值，提出一种“基于分类误差的加权方法”来加权集成分类器，从而提高分类准确率。
实验对比和性能分析表明，本文提出的ＣＥＥＰＣＥ算法能较好的适应数据流的
概念漂移，并且具有较好的分类准确率，足以与以ＣＡ．５为基分类器的集成多分类器方法相媲美。
关键字：数据流挖掘，数据流，分类，显露模式

垒些！！型
塑型叁兰堡！兰竺丝塞
Ａｂｓｔｒａｃｔ
Ｈｕｇｅｖｏｌｕｍｅｓｏｆｄａｔａｓｔｒｅａｍｓ
ａｒｅ
ｔｈｅｒａｎｇｅ
ｇｅｎｅｒａｔｅｄａｔｕｎｐｒｅｃｅｄｅｎｔｅｄｒａｔｅｓｉｎ
ｏｆａｐｐｌｉｃａｔｉｏｎｓｉｎｃｌｕｄｉｎｇｃｒｅｄｉｔｃａｒｄｆｒａｕｄｐｒｏｔｅｃｔｉｏｎ，ｔａｒｇｅｔｍａｒｋｅｔｉｎｇ，ｎｅｔｗｏｒｋｉｎ“１ｌｓｉＯｎ
ｄｅｔｅｃｔｉｏｎ．∞ｎｓｏｒｎｅｔｗｏｒｋ，ｅｒｅ．Ｔｈｅ
ｄａｔａｓｔｒｅａｍｓａｒｅｃｏｎｔｉｎｕｏｕｓ，ｏｒｄｅｒｅｄ，
ｄａｔａｄｉｓｔｒｉｂｕｔｉｏｎｉｓｌｉｋｅｌｙｔｏｂｅ
ｃｈａｎｇｉｎｇ，ｆａｓｔａｎｄｈｕｇｅ
ａｍｏｕｎｔ，ｍｅａｎｗｈｉｌｅ，ｉｔｓ
ｃｈａｎｇｅｄ，ｎａｍｅｌｙｃｏｎｃｅｐｔ
ｐｒｅｄｉｃｔｔｈｅ
ｄｒｉｆｔｓｗｉｌｌｈａｐｐｅｎ．Ｈｏｗｔｏｔｒａｉｎｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｍｏｄｅｌｔｏ
ｃｏｍｉｎｇ
ｄａｔａｔｒｅｎｄｅｆｆｅｃｔｉｖｅｌｙｉｓ
ａｌｌ
ｊｕｓｔ
ａｂｏｕｔ
ｏｎｅ
ｄｉｆｆｉｃｕｌｔｙ
ｉｎｔｈｅｒｅｓｅａｒｃｈｏｆ
ｄａｔａｓｔｒｅａｍｃｌａｓｓｉｆｉｃａｔｉｏｎａｎｄｉｓａｌｓｏ
ｉｍｐｏｒｔａｎｔｔａｓｋ．
Ｃｌａｓｓｉｆｉｃａｔｉｏｎｉｓ
ａｌｌ
ｉｍｐｏｒｔａｎｔｔａｓｋｉｎｔｈｅｄａｔａｍｉｎｉｎｇｄｏｍａｉｎａｎｄｔｈｅｒｅａｒｅ
ａｓ
ｓｕｃｈ
ｃｏｍｐｒｅｈｅｎｓｉｖｅａｐｐｌｉｃａｔｉｏｎｓ
ｃｒｅｄｉｔ
ｃａｒｄ
ｆｒａｕｄｐｒｏｔｅｃｔｉｏｎ，ｔａｒｇｅｔｍａｒｋｅｔｉｎｇ，
ｎｅｔｗｏｒｋ
ｉｎｔｒｕｓｉｏｎｄｅｔｅｃｔｉｏｎ，ｅｒｅ．Ｔｈｅｒｅｅｘｉｓｔｓｏｍｅｃｌａｓｓｉｃａｌｃｌａｓｓｉｆｉｃａｔｉｏｎｍｅｔｈｏｄｓ
ｉｎｃｌｕｄｉｎｇＤｅｃｉｓｉｏｎＴｒｅｅ，Ｂａｙｅｓｉａｎｔｈｅｙ
ａｒｅ
ｎｅｔｗｏｒｋ，ＮｅｕｒａｌＮｅｔｗｏｒｋａｎｄ
ａｓ
ＳＶＭ，ｅｔｃ，ｗｈｅｒｅａｓ，
ｆａｃｉｎｇｎｅｗｃｈａｌｌｅｎｇｅｓｓｕｃｈ
ｔｈｅｏｖｅｒｗｈｅｌｍｉｎｇｖｏｌｕｍｅｏｆｔｈｅｄａｔａｓｔｒｅａｍｓ
ａｎｄｔｈｅｓｔｒｅａｍ
ｃｏｎｃｅｐｔ
ｄｒｉｆｔｓｗｈｅｎｐｒｏｃｅｓｓｉｎｇｄａｔａ
ｓｔｒｅａｍｓ．Ｄｕｒｉｎｇ
ｔｈｅｓｅｙｅａｒｓｓｅｖｅｒａｌ
ｄａｔａｃｌａｓｓｉｆｉｃａｔｉｏｎａｌｇｏｒｉｔｈｍｓａｒｅｐｒｏｐｏｓｅｄｂｙｓｏｍｅ
ｒｅｓｅａｒｃｈｅｒｓ，ｓｕｃｈａｓ
ｕｓｕａｌｌｙｉｍｐｒｏｖｅｔｈｅ
ＶＦＤＴ＆ＣＶＦＤＴ，ＶＦＤＴｃａｎｄＥｎｓｅｍｂｌｅ
ｃｌａｓｓｉｆｉｅｒｓ，ｅｔｃ．Ｗｅ
ｃａｒｌ
ｃｌａｓｓｉｆｉｃａｔｉｏｎ
ｗｈｅｎｈａｖｉｎｇｓｏｍｅ
ａｃｃｕｒａｃｙｂｙｉｎｔｅｇｒａｔｉｎｇｓｅｖｅｒａｌｃｌａｓｓｉｆｉｅｒｓ，ｅｓｐｅｃｉａｌｌｙ
ｄｉｖｅｒｓｉｔｙｂｅｔｗｅｅｎｅａｃｈｂｙ
ｔｗｏｂａｓｅｃｌａｓｓｉｆｉｅｒｓ．Ｅｎｓｅｍｂｌｅｃｌａｓｓｉｆｉｃａｔｉｏｎｍｅｔｈｏｄｐｒｏｐｏｓｅｄ
ｏｎ
Ｗａｎｇ
ｅｔａｌ
ｉｓｂａｓｅｄ
Ｃ４．５，ＲＩＰＰＥＲ，ＮａｉｖｅＢａｙｅｓｉａｎ，ｗｈｉｌｅ
ｕｓｉｎｇｏｔｈｅｒ
ａｌｇｏｒｉｔｈｍｓ
ａｓ
ｂａｓｅｃｌａｓｓｉｆｉｅｒｓｉｓｓｔｉｌｌｒｅｑｕｉｒｅｄｔｏｓｔｕｄｙ．Ａｓｗｅ
ｔｈｅｆａｖｏｒａｂｌｅｗｉｔｈ
ｋｎｏｗ，ｅＥＰ（ｅｓｓｅｎｔｉａｌ
ａｎｄＥＰ－ｂａｓｅｄ
ｅｍｅｒｇｉｎｇｐａｔｔｅｒｎｓ，ｅＥＰ）ｈａｖｅ
ａｌｇｏｒｉｔｈｍ
ｐｅｒｆｏｒｍｓ
ｄｉｓｔｉｎｃｔｉｖｅｆｕｎｃｔｉｏｎ
ｏｆ
ｃｏｍｐａｒａｂｌｙｏｔｈｅｒｔｙｐｅｓ
ｃｌａｓｓｉｆｉｃａｔｉｏｎ
ａｌｇｏｒｉｔｈｍｓ・
Ｍｅａｎｗｈｉｌｅ，ｅＥＰ．ｂａｓｅｄ
ｓｕｃｈ
ａｓ
ｉｎｍａｎｙｄｏｍａｉｎｓｓｕｃｃｅｓｓｆｕｌｌｙ，
ａｌｇｏｒｉｔｈｍｈａｓｂｅｅｎａｐｐｌｉｅｄ
ＤＮＡａｎａｌｙｓｉｓａｎｄｔｅｘｔａｕｔｏｍａｔｉｃ
ｃａｔｅｇｏｒｉｚａｔｉｏｎ
ｅｔｃ．
ａｌｌ
Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅａｂｏｖｅ—ｍｅｎｔｉｏｎｅｄｆａｃｔｏｒｓ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄｃａｌｌｅｄ
ａｌｇｏｒｉｔｈｍ，
Ｃｌａｓｓｉｆｉｃａｔｉｏｎ
ｂｙｅＥＰ．ｂａｓｅｄＣｌａｓｓｉｆｉｅｒｓＥｎｓｅｍｂｌｅ（ＣＥＥＰＣＥ），ｔｏ
ａｒｃ
ｃｌａｓｓｉｆｙｄａｔａ
ｓｔｒｅａｍｓ．Ｔｈｅ
ｂａｓｅｄ
ｏｎ
ｍａｉｎｒｅｓｅａｒｃｈｃｏｎｔｅｎｔｓｏｆｔｈｅ
ｐａｐｅｒ
ｉｌｌｕｓｔｒａｔｅｄ
ａｓ
ｆｏｌｌｏｗｓ．Ｆｉｒｓｔｌｙ，
ｅＥＰ・ｂａｓｅｄ
ｓｎｍｍａｒｉｚｉｎｇｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｄａｔａｓｔｒｅａｍａｎｄａｎａｌｙｚｉｎｇ

Ａｂｓｔｒａｄ
郑州大学硕Ｊ：学位论文
ａｌｇｏｒｉｔｈｍ，ｗｅｃｏｍｂｉｎｅｄｔｈｅｃｏｎｃｅｐｔｓｏｆｂａｓｉｃｗｉｎｄｏｗｓａｎｄｓｌｉｄｉｎｇｗｉｎｄｏｗｓｗｉｔｈｔｈｅ
ｅＥＰ－ｂａｓｅｄ
ｃｌａｓｓｉｆｉｃａｔｉｏｎ
ａｌｇｏｒｉｔｈｍ
ｔｏｍａｋｅ
ｏｕｒ
ａｌｇｏｒｉｔｈｍ
ａｐｐｒｏｐｒｉａｔｅ
ｆｏｒ
ｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｄａｔａｓｔｒｅａｍｐｒｏｐｏｓｅｄｔｈｅ
ｉｄｅａ
ａｎｄ
ｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｏｆｃｏｎｃｅｐｔｄｒｉｆｔｓ．Ｓｅｃｏｎｄｌｙ．ｗｅ
ｅｎｓｅｍｂｌｅｉｎ
ｔｈｅｐｒｏｃｅｓｓｏｆｔｈｅ
ｏｆｗｅｉｇｈｔｉｎｇｔｈｅｃｌａｓｓｉｆｉｅｒｓ
ｃｏｎｓｔｒｕｃｔｉｎｇ
ｄｉｆｆｅｒｅｎｔｄａｓｓｉｆｉｅｒｓ．Ｆｉｎａｌｌｙ，ｉｎｔｈｅｐｒｏｃｅｓｓｏｆｃｌａｓｓｉｆｙｔｈｅｃｏｍｉｎｇ
ｔｅｓｔ
ｅｘａｍｐｌｅｓ，ｗｅｐａｉｄｍｕｃｈｍｏｒｅａｔｔｅｎｔｉｏｎｔｏｔｈｅｌａｔｅｓｔｄａｔａｂｌｏｃｋｓ，ｔｈｅｒｅｆｏｒｅｅａｃｈｂａｓｅ
ｃｌａｓｓｉｆｉｅｒｗａｓｗｅｉｇｈｔｅｄｂａｓｅｄ
ｓｔｒａｔｅｇｙ
ｏｎ
ｉｔｓａｒｒｉｖｉｎｇｔｉｍｅ，ｉｎｔｒｏｄｕｃｅｄ
ｏｎ
ａ
ｎｅｗｗｅｉｇｈｔｉｎｇ
ｎａｍｅｄｂｙ”ｔｈｅｗｅｉｇｈｔｉｎｇ
ｍｅｔｈｏｄｂａｓｅｄ
ｃｌａｓｓｉｆｉｃａｔｉｏｎａｃｃｕｒａｃｙ”ｔｏ
ｃｌａｓｓｉｆｉｅｒｓｔｏｒａｉｓｅ
ｗｅｉｇｈｔ
ｄｉｆｆｅｒｅｎｔｂａｓｅｃｌａｓｓｉｆｉｅｒｓａｎｄｅｎｓｅｍｂｌｅａｌｌａｃｃｕｒａｃｙ・
Ｏｕｒｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｐｒｅｆｅｒａｂｌｙｓｏｌｖｅ
ｓｅｌｅｃｔｅｄ
ｃｌａｓｓｉｆｉｃａｔｉｏｎ
ｔｈａｔＣＥＥＰＣＥ
ａｌｇｏｒｉｔｈｍ
ｐｒｏｐｏｓｅｄ
ａ
ｉｎ
ｔｈｅｐａｐｅｒ
ｃａｎ
ｃｏｎｃｅｐｔ
ｔｈｅ
ｄｒｉｆｔｉｎｇｉｎｄａｔａｓｔｒｅａｍｓａｎｄｏｗｎｓｈｉｇｈｅｒ
ｗｉｔｈ
ａ洲ａｃｙ
ｏｆ
ｃｌａｓｓｉｆｉｃａｔｉｏｎｔｈａｎ
ｓｉｎ宙ｅｃｌａｓｓｉｆｉｅｒａｎｄｐｅｒｆｏｒｍｓｃｏｍｐａｒａｂｌｙ
ｔｈｅ
ｅｎｓｅｍｂｌｅ
ｍｅｔｈｏｄｂａｓｅｄ０１１Ｃ４．５．
Ｋｅｙｗｏｒｄｓ：Ｄａｔａ
ｓｔｒｅａｍ
ｍｉｎｉｎｇ，ｃｌａｓｓｉｆｉｃａｔｉｏｎ，ｄａｔａｓｔｒｅａｍ，ＥｍｅｒｇｉｎｇＰａｔｔｅｒｎｓ（ＥＰ）
Ⅱ

第～章绪论郑州大学硕｝学位论文
第一章绪论
面对日趋激烈的市场竞争，人们需要从这些蕴含着丰富决策信息的数据中抽取能帮助领导进行决策的知识。在需求的强烈驱动下，数据挖掘【１Ｉ技术应运而生。在信用卡欺诈监测、差异性营销、网络入侵检测和传感器网络等应用中，随着时问的更迭而生成一种新型的具有连续、有序、变化、快速到达、海量等特征的数据，即“数据流【２ｌ”，其数据量大且数据分布可能会发生变化（即概念漂移【３ｊ）。如何从海量的数据中训练模型来有效地预测未来的数据趋势，正是数据流上的分类算法所要解决的难点，同时也是一件非常有意义的工作。
分类是数据挖掘中的重要分支之一，也是一种重要的数据分析形式。分类是一种有指导的学习过程，可以用于从数据库中提取重要数据类的模型或预测未来的数据趋势。在商业、金融、电讯、ＤＮＡ分析、科学研究等诸多领域具有广泛的应用。统计学、机器学习、神经网络等领域的研究者对分类问题进行了大量的研究［４１，提出了一系列的分类算法。
本文研究的内容属于数据挖掘中的分类问题，研究的对象是数据流数据。
１．１数据挖掘
数据挖掘就是从大量的数据（大型数据库和数据仓库）中提取和挖掘知识的
过程，这些知识是人们感兴趣的、隐含的、事先未知的和潜在有用的信息吼
数据挖掘虽然只有十几年的历史，然而它出现之后被广泛应用于许多领域，数据挖掘的研究蓬勃发展。商业、金融、电讯、ＤＮＡ分析、科学研究、医疗卫生等应用领域都有大量数据挖掘技术成功的例子而且多数研究成果都能够迅速的转化为实际应用。数据挖掘的功能一般可以分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般特性，预测性挖掘任务可以在当前数据上进行推断，以进行预测。具体而言，数据挖掘的目标是完成如下功能：
・概念，类描述（Ｃｌａｓｓ／ＣｏｎｃｅｐｔＤｅｓｃｒｉｐｔｉｏｎ）・关联分析（ＡｓｓｏｃｉａｔｉｏｎＡｎａｌｙｓｉｓ）・分类（Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）
●预测（Ｐｒｅｄｉｃｔｉｏｎ）

第一章绪论郑州人学硕士学位论文
・聚类分析（Ｃｌｕｓｔｅｒｉｎｇ）・离群点分析（ＯｕｔｌｉｅｒＡｎａｌｙｓｉｓ）・时序模式（ｒｉｍｅ．ｓｅｒｉｅｓＰａｔｔｅｒｎ）・偏差分析（Ｄｅｖｉａｔｉｏｎ）
每项数据挖掘功能可由多种不同的算法实现，分析研究和设计数据挖掘算法是数据挖掘研究的一个重要课题。而数据挖掘是一个交叉学科领域，受多个学科的影响，包括数据库系统、统计学、机器学习、可视化和信息科学。因此数据挖掘算法的设计也涉及多学科技术，包括数据库技术、统计学、机器学习、高性能计算、模式识别、神经网络、粗糙集理论等。根据数据挖掘的数据类型以及涉及的应用领域，数据挖掘技术又可与空间数据分析、信息检索、图像分析、信号处理、计算机图形学、Ｗｅｂ技术、信息安全、经济、商业金融、生物信息学等领域技术相关。目前数据挖掘技术已经成功的运用于这些领域，它既有多层次的研究价值又有很高的应用价值。
１．２分类问题
分类是数据挖掘中的重要分支之一，也是一种重要的数据分析形式。分类是
一种有指导的学习过程，可以用于从数据库中提取重要数据类的模型或预测未来
的数据趋势。在商业、金融、电讯、ＤＮＡ分析、科学研究等诸多领域具有广泛的应用。统计学、机器学习、神经网络等领域的研究者对分类问题进行了大量的研究，提出了一系列的分类算法。
分类问题可以描述为：数据集是一个标准关系表，它包含Ｎ条记录，这些
记录通常称作元组（ｔｕｐｌｅｓ）、实例咖ｓｔａｎｃｅ）或样本（ｅｘａｍｐｌｅ）。每一个实例用固定数
目的度量标准描述，这种度量标准称作属性（ａｔｔｒｉｂｕｔｅ）。每一个属性都有一个合法的取值范围，称作该属性的域（ｄｏｍａｉｎ）。如果属性域是实数域，那么则称该属性为数值属性（ｎｕｍｅｒｉｃａｌａｔｔｒｉｂｕｔｅ）或连续属性（ｃｏｎｔｉｎｕｏｕｓａｔｔｒｉｂｕｔｅ）。如果属性域是有
限的，那么则称该属性为分类属性（ｃａｔｅｇｏｒｉｃａｌａｔｔｒｉｂｕｔｅ）或离散属性（ｄｉｓｃｒｅｔｅａｔｔｒｉｂｕｔｅ）。这些属性中有一个区别于其他的称作类标号（ｃｌａｓｓｌａｂｅｌ），类标号指示
元组所属的类。除了类标号之外的其他属性是预测未知样本类型的依据，因此也
称作预测属性（ｐｒｅｄｉｃｔｏｒａｔｔｒｉｂｕｔｅｓ）。
２

第一章绪论郑州大学硕十学位论文
在分类研究中，数据集通常被分成训练集和测试集。训练集用来构造分类器，测试集用来评估分类器的预测准确度。因为学习算法可能对数据过度拟合，所以使用训练数据构造分类模型，然后用同样的数据集评估分类模型可能导致过于乐观的估计。因此，通常采用测试集来评估分类模型。在分类研究中，通常采用ＵＣＩ机器学习库【６１（ＵＣＩ
ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ
Ｒｅｐｏｓｉｔｏｒｙ）中的数据集评估不同的分类
模型。这些数据集来源于广泛的应用领域，并且不同数据集的规模、目标类的个数和属性个数变化很大，能够比较全面的反映算法的分类性能。
分类过程可以描述为两个步骤：
第一步，模型构建阶段。通过分析训练数据集，采用既定的算法，建立一个模型，描述预定的数据类或概念集。分类模型也叫分类器，通常以分类规则、决策树、模式或数学公式形式存在。训练阶段的目的是建立分类器，即从训练数据集中获取可以进一步指导未知数据分类的专家知识。各种分类器以不同的形式描述了某个类区别其他类的特征概念集。从另一个角度来看，也可以认为分类模型是以某种特定的形式描述了训练集的数据分布特征。如果训练集能够代表整体数据分布特征，那么由训练集获得的特征概念集就可以用来指导对未知数据的预
测。
第二步，使用模型进行分类。在使用分类模型对未知类标号的实例或对象分
类之前，首先要使用测试集评估分类模型的分类准确率。如果分类准确率达到既
定的目标，则该分类器才可以用于指导未知元组的分类。
１．３研究背景
随着信息技术的快速发展和信息搜集能力的日益提高，产生了海量的数据。这些海量的数据或以静态的形式存储在企业的物理存储器上，或是不被存储而瞬时出现的动态数据。面对如此丰富的海量数据，传统的数据处理方法和能力已远远不能满足实际的需求。基于数据流的相关研究目前已具备了较好的理论基础。如与查询优化相关的：抽样技术川、直方图技术Ｉ引、分位数技术ｆ们、小波分析技术【１０ｌ、草图技术【１１ｌ等；与数据挖掘相关的：决策树技术‘捌、聚类技术【１３１、频繁模式挖掘技术【１４】等；一些相关的理论：模式增长理论【１５ｌ、边界理论１１６ｌ等。基于数据流的数据挖掘必须得到这些技术的有效支持，同时结合数据流和数据挖掘任
３

第一章绪论
郑州大学硕｝学位论文
务本身的特性，从而得到基于数据流的数据挖掘任务解决方案。
分类是数据挖掘中的重要分支之一，在很多领域都具有广泛的应用，基于数
据流的分类算法研究是当前数据挖掘领域的一个热点。现在已有许多成熟的分类方法，如决策树、贝叶斯网络、神经网络、支持向量机等，但是在处理数据流时，仍然面临着新的挑战。近年来研究者们提出了几种数据流上的分类方法：ＶＦＤＴ和ＣＶＦＤＴ［坷、ＶＦＤＴｃ［１７１、集成分类方法ｅｎｓｅｍｂｌｅｃｌａｓｓｉｆｉｅｒｓ［１８】等。集成多个分类器的方法通常可以提高分类准确率，特别是基分类器具有一定的差异性时，它往往比单分类器的准确率高。Ｗａｎｇ［１８】等人提出的集成方法以Ｃ４．５、ＲＩＰＰＥＲ、
Ｎａｉｖｅ
Ｂａｙｅｓｉａｎ分类为基分类器，而采用其他类型的算法作为基分类器仍需进
一步研究。而ｅＥＰ具有良好的区分能力，并且基于ｃＥＰ的分类算法可以与其他算法相媲美，同时基于ＥＰ的分类方法已经成功地应用于ＤＮＡ分析、文本自动分类
等领域。
基于以上考虑，我们对数据流环境下，基于ｅＥＰ的分类算法进行了深入的研
究。
１．４论文结构及本文工作
本文主要的研究内容：首先在总结数据流的特性和分析基于ｅＥＰ传统分类算法的算法思想的基础上，将基本窗口和滑动窗口的概念与ｅＥＰ分类算法有机的结合以适应数据流的特性并解决概念漂移的问题；其次在分类器构造的过程中，提出了加权集成分类器的思想；最后，在未知样本分类的过程中，结合数据流挖掘分析多考虑最近最新数据的特点，对不同的基分类器赋予不同的权值，加权集成分类器，从而提高分类准确率。
论文的组织结构如下：
第一章为本文的引言部分。简单介绍了数据挖掘的相关知识，并论述了本文的研究背景、研究内容及论文的组织结构。
第二章为数据流相关知识的介绍。主要介绍了数据流的概念、特点；数据流
的一个特征——概念漂移；处理数据流的常用技术——糟动窗口技术；最后介绍
了当前数据流分类的研究动态。
第三章为传统分类方法的分析。主要分析了现有的传统分类方法，并以数据
４

第一章绪论
郑州大学硕ｉ。学位论文
流的角度比较算法的优缺点，最后结合自己研究的特点指出选用基于ｅＥＰ的分类方法作为本文分类算法的核心。
第四章为基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ，这是本文的主要研究内容。本章分为两个部分：第一部分是相关知识和概念定义。主要介绍了ＥＰ挖掘问题的相关知识和几个概念的定义。第二部分重点介绍了ＣＥＥＰＣＥ算法。主要包括基本思想、基分类器的构造、集成分类器的产生与更新和分类器集成等内容。
第五章为ＣＥＥＰＣＥ算法的实验结果对比及性能分析。
●
最后是本文工作总结、致谢和参考文献。
５

第二二章数据流挖掘
郑州人学硕ｌ：学位论文
第二章数据流挖掘
在同益增多的信息处理应用中，信息呈现形式较多的不是静态方式，而是动态连续“流”的形式，称之为数据流（ＤａｔａＳｔｒｅａｍ）。所谓数据流【２】是指一系列连续的数据序列…研…，按照下标ｉ的增序读取。数据流每隔一段时间流入一个元组，这个序列中的数据按照固定的次序快速到达，而且只能被读取一次或几次。数据流挖掘有着广泛的应用，如信用卡欺诈监测、差异性营销、网络入侵检测和传感器网络、网络监控、流量控制、Ｗｅｂ日志和网页点击流、商务点击流分析及个性化分析等。
本章介绍数据流相关知识，主要包括：数据流的特征、数据流算法分析处理时应满足的要求、概念漂移的问题、滑动窗口技术以及当前数据流分类算法的动态。
２．１数据流的特征
数据流是只是传统数据的一种特殊形式，但是它具有自己独特的不同于传统
数据的一些特征：
・连续：数据流元素以连续的形式到达。
●有序：数据流是有序的数据序列，系统不能控制数据流中数据的顺序。．●快速：数据流的数据快速到达，因此必须要求数据流挖掘算法能够实时
响应，与数据流元素到达的速率相兼容。
●变化：数据流中的数据分布是持续变化的，而不是保持固定的数据分布
不变，从而采用统一的模式进行处理是不合理的。・海量：数据流数据持续到达，其数量可认为是海量的。
２．２数据流算法分析处理时应满足的条件
基于数据流的上述特征，在对数据流进行分析和处理时，应该基本满足下面
的条件：
●实时处理，实时响应：由于数据流数据快速到达，因此对数据流进行处
６

第二章蠡据流挖掘郑州人学硕ｌ：学位论文
理必须能够快速处理，并且能够实时响应。
・线性扫描：由于数据流快速到达，所以对数据流进行访问时不能采用传
统的多遍扫描数据访问方法，要求必须利用线性扫描方法进行处理。・适应概念漂移：数据流中的数据是持续变化的，因此对数据流的处理在
满足实时性要求的同时，也必须能够捕获这些数据的变化。
・存储概要信息：由于数据流数据的海量特性，对数据流的处理一般是不
存储的。但是，在进行某些分析处理时，必须考虑历史数据的特性，因此必须存储历史数据的一些概要的信息。
’２．３概念漂移
数据流的一个显著特征就是其数据分布随着时间而不断发生变化，这类不断变化的现象就称之为概念漂移【３】口原来绝大部分数据挖掘算法都假设所使用的数据是服从一种固定的分布，但事实上几乎所有用来挖掘的数据都违背了这个假设，当数据不断到达的过程中，数据类分布（目标概念）随时间不断发生变化。
目前解决概念漂移问题主要集中在两个方面：
首先是概念漂移的发现，也就是说发现概念漂移发生的时机。
在预测型的问题中，假设已经建立起一个预测模型，然后使用这个模型对每一个到达的样本进行分类和诊断。如果可以在一段时间之后判断样本的真实属性（比如预测型的问题），就可以对模型的诊断结果进行验证。当收集到足够多的样本之后，就可以通过对样本数据预测准确率的变化来发现是否发生了概念漂移。如果检测到模型对刚刚收集到的训练数据的平均预测准确率和模型以前的平均预测准确率相比突然发生了明显的下降，那么就说明概念漂移发生了。
如果在短期时间内无法知道模型的分析结果（比如描述型的问题），那么就需要引入一个可靠性估计（ＲｅｌｉａｂｉｌｉｔｙＥｓｔｉｍａｔｉｏｎ）的方法，为每一次预测都分配一个可信度的值。尽管每次的预测结果都不一定可以获得，但是可以根据可信度的变化来判断是否发生了概念漂移。
然后是在检测到概念漂移发生之后，如何处理概念漂移。概念漂移的解决办
法基本上有两种：重建模型和模型的自适应。
一般说来，可以给出一个信赖度变化范围的阂值，用统计的方法来检查已经
７

第二章数据流挖掘
郑州大学硕十学位论文
建立起来的模型对当前训练样本的预测准确度。如果准确度的变化范围超过了那个阈值，就标志着模型对当前的样本不再适用，即说明了发生了概念漂移。如果检测到概念漂移已经发生，那么就可以重新设置模型的各种参数，或在必要时重建模型来达到适应概念漂移的目的。该方法的优点在于动态检测模型对最新样本的预测准确率的变化十分方便，而且代价较小，模型可以一直使用，直到其准确度不满足要求。在此期间，模型一直都可以认为是值得信赖的。它的缺点是如果模型中的一些参数需要根据情况重新设置的话，那么在每次重建模型时就需要有一个机器学习和数据挖掘的专家来指导。
另一种方法，就是不必精确的探测出概念漂移以及发生的程度，模型可以自动的根据输入样本的变化来自动的调整自己。在概念漂移的情况下，最高效的机器学习算法应该可以发现概念漂移的发生，可以迅速从概念漂移中恢复，自动调整自己对概念的描述以适应新的概念，而且当新概念与旧概念相似时可以最大程度的利用以前学习到的知识。该方法的优点在于，在整个过程中模型可以自动地维护，动态地调整自身来适应新的概念，而不需要有人专门从事模型维护的工作，更不需要专家的参与。模型在使用过程中随时都是最适应与当前概念的，准确率
更加稳定，可适用性更强。
２．４滑动窗口技术的介绍
由于数据流具有动态性、快速变化性、无限性等特点，它无法在全部地保存下来以后再进行处理，这就要求在有限的存储空间的限制下，数据流处理只能是部分地处理。但是在许多数据流的应用领域中，人们常常关心的是最近到达数据处理的结果，因此，基于滑动窗口的数据流处理技术能够很好地实现关于最近到达的数据流中数据相关处理工作。
滑动窗口阻止陈旧数据影响分析和统计，同时也是有限内存情况下的一种近似工具。已有研究将草图（Ｓｋｅｔｃｈｅｓ），抽样（Ｓａｍｐｌｉｎｇ）和Ｖ－ｏｐｔｉｍａｌ直方图应
用到滑动窗口模型中。
数据流上的滑动窗口技术１１９】【冽【２１】【２２ｌ是指：在数据流上设定一个区域范围，数据流的处理对象就是那些处于窗口内的数据内容。滑动窗口通常包含那些最近
到达的数据；当最新数据到来的时候，窗口将向前移动，将最旧的数据移动出窗
８

第＿二章数据流挖掘
郑州人学硕ｔ学位论文
口。根据滑动窗口具体实现方法的差异，可将滑动窗口技术分为基于序列的滑动窗口技术和基于时间的滑动窗口技术。基于序列的滑动窗口技术特点是：在大小为形的滑动窗口内保存的是最近到达的∥项数据。基于时间的滑动窗口技术特点是：在大小为∥的滑动窗口内保存的是最近∥时间内到达的数据。数据流经常与时间有着紧密联系，因此，基于时间的滑动窗口技术比较适合于数据流处理
过程。
在数据流上利用滑动窗口获取近似值是一种普通的方法。它有以下吸引人的特征：
１）定义明确，易于理解：近似值的语义清晰，所以系统用户能够确信理解在产生近似结果时那些数据被丢弃了；
２）确定性：不必担心不合适的随机选择会产生坏的近似结果；
３）强调最近的数据：在大多数现实应用中最近数据比历史数据更重要和相关，如果你试图实时搞清网络流量模式、电话呼叫记录、事务记录、科学传感器数据的意思，那么基于最近的数据来理解将比基于陈旧数据更有信息量和更有
用。
２．５当前数据流分类研究
近年来，经过许多研究者的辛勤努力，基于数据流的相关研究己具备了较好的理论基础。如与查询优化相关的：抽样技术、直方图技术、分位数技术、小波分析技术、草图技术等；与数据挖掘相关的：决策树技术、聚类技术、频繁模式挖掘技术等；一些相关的理论：模式增长理论、边界理论等。
数据挖掘领域中，已经有许多静态数据上的分类方法，如决策树、贝叶斯分类、神经网络、支持向量机等。分类包含两个阶段：学习或模型构建（基于包含类标号的训练数据集来构建模型）、分类过程或模型使用（用于预测新来数据的类标号）。而后者有助于数据流分类，因为当新样本数据到达时将被立即分类。
如何将传统的分类方法应用于数据流成为一个值得讨论的问题。在传统的框架下，训练数据以相对静态的形式存储于数据库，而且很多分类方法均是多次扫描训练数据集。显然，分类模型构建的过程是离线进行的批处理过程，然而对于
数据流，没有离线阶段，这是因为数据流入速度快，使得存储所有数据和多次扫
９

第二章数据流挖掘郑州大学硕十学位论文
描并不可行。
为进一步阐述为何传统的分类方法不适用于数据流环境，下面以决策树作为模型具体说明。大多数决策树算法一般采用自上而下的迭代策略，然而，所用的选择最佳分裂属性的统计方法有所不同。回顾一下，决策树包括内结点（非叶子结点）、分枝和叶子结点。属性选择方法用来选择当前结点上的最佳分类属性，即能够最佳的区分训练元组。一般地，由分裂属性的每个可能值生长一个分枝，而训练元组被相应地分到各个分枝，整个构建决策树的过程即在每个分枝上迭代的过程。但是，在数据流环境下，既不可能收集所有的数据，并且重新扫描数据也不现实。因此，需要对此方法做修正。
与传统的数据库系统不同，数据流的显著特征是时变性（ｔｉｍｅ－ｖａｒｙｉｎｇ），它仅存储当前数据。数据分布发生变化的特征表现为目标分类模型随时间而发生变化（即概念漂移）。概念漂移是在处理数据流时要考虑的重要因素之一。
在数据流分类方面，研究者们已经提出了不同的分类方法。其中具有代表性
的有四种：Ｈｏｅｆｆｄｉｎｇ树算法【矧、ＷＤＴｔｌ们（ＶｅｒｙＦａｓｔＤｅｃｉｓｉｏｎＴｒｅｅ）、ｃｖｌ州１６１
（Ｃｏｎｃｅｐｔ－ａｄａｐｔｉｎｇｖｅｒｙＦａｓｔＤｅｃｉｓｉｏｎ
Ｔｒｅｅ）和使用投票表决的多分类器加权集成
方法ＥｎｓｅｍｂｌｅＣｌａｓｓｉｆｉｅｒｓ［１８１。
（１）ＨｏｅｆｆｄｉｎｇＴｒｅｅ算法
Ｈｏｅｆｆｄｉｎｇ
Ｔｒｅｅ算法是一种数据流上的决策树学习算法。它已被初步应用到
跟踪ｗｅｂ点击流并构建模型来预测哪些网站或主机经常被访问。该算法时间复
杂度是次线性的，并且能产生与传统的批处理方式下几乎一致的决策树。
Ｈｏｅｆｆｄｉｎｇ
ｔｒｅｅ采用了一种思想：选择最佳分裂属性时，小样本数据常常足够使用。
该思想是基于统计理论Ｈｏｅｆｆｄｉｎｇｂｏｕｎｄ（ａｄｄｉｔｉｖｅＣｈｅｍｏｆｆｂｏｕｎｄ）：对Ｒ范围内
的随机变量ｒ进行Ⅳ次独立观测，，是Ⅳ次观测的平均值。其中ｒ是属性选择方
法，对于Ｈｏｅｆｆｄｉｎｇｔｒ∞，ｒ是信息增益（对于概率，Ｒ为１；对于信息增益，Ｒ为ｌｏｇｃ，ｃ是类的个数１。Ｈｏｅｆｆｄｉｎｇｂｏｕｎｄ理论保证ｒ的真实平均值至少为，一￡的概率为１－ｄ，ｄ由用户指定，ｅ由经验值确定。
￡一√旦学
ｒ●——。一
（＋）
Ｈｏｅｆｆｄｉｎｇｔｒｅｅ算法使用上述理论保证了以高概率、使用小样本来选择节点上
１０

第二章数据流挖掘
郑州大学顾‘Ｌ学位论文
的最优分裂属性。而所选取出的属性和使用无穷样本得到的结果一样。Ｈｏｅｆｆｄｉｎｇｂｏｕｎｄ理论与概率分布无关。因为不可能知道信息增益的概率分布或采用的属性选择方法，所以采用该理论是合适的。
使用Ｈｏｅｆｆｄｉｎｇｔｒｅｅ有另外的两个特性。首先，不再多次扫描数据集。再者，算法能够增量更新。因此，在新数据流入时，可以同时利用已有的模型做预测，并且可以引入新来的数据作为训练集，不断调整模型从而提高模型的准确率。
Ｈｏｅｆｆｄｉｎｇ
ｔｒｅｅ算法有一些不足之处。例如，当两个属性的分裂质量几乎相同
时，算法花费大量时间做此计算。另外，存储空间利用率可以进一步优化。最后，算法无法处理概念漂移。
（２）ＶＦＤＴ和ＣＶＦＤＴ
ＶＦＤＴ（ＶｅｒｙＦａｓｔＤｅｃｉｓｉｏｎ
Ｔｒｅｅ）是对Ｈｏｅｆｆｄｉｎｇ树算法的改进算法，提高了
速度和存储利用率。主要在以下方面做了改进：当结点上累积一定数目的训练样本时才计算增益函数Ｇ；删除最不常用的叶子节点；丢弃无价值的分裂属性；改进初始化方法。但是，仍然不能够处理数据流中的概念漂移。
处理概念漂移的常用方法是使用滑动窗口，它引入新的样本并且删除历史样本。在滑动窗口内反复训练传统的分类器，当新样本到达时，插入窗口的头部，同时剔除尾部数据，从而保证训练得到的分类模型始终反映当前的数据分布。但是，这种方法对窗口大小敏感。当窗口太大时，模型不能准确反映概念漂移；窗口太小时，没有足够的数据用于构建准确的模型。再者，不停地构建分类器模型的代价相当高。
为了解决数据流中的概念漂移，Ｈｕｌｔｅｎ等人对ＶＦＤＴ进行了扩展，提出了ＣＶＦＤＴ算法。ＣＶＦＤＴ仍然使用滑动窗口的方法，但是，它不再每次都在暂存区构建新模型。ＣＶＦＤＴ通过增加（减少）与新（旧）样本相关的计数来更新各结点上的统计信息。因此，当概念漂移发生时，生成可替换子树，当可替换子树比历史子树的分类准确率更高时，替换历史子树。
实验表明，ＣＶＦＤＴ比ＶＦＤＴ拥有更高的准确率，ＣＶＦＤＴ中树的大小比ＶＦＤＴ
的要小。
（３）分类器集成算法Ｅｎｓｅｍｂｌｅ
Ｃｌａｓｓｉｆｉｅｒｓ
２００３年，Ｗａｎｇ等人提出了集成分类器的方法，它使用多个分类器来代替单
１１

第二章数据流挖掘郑州人学硕ｌ：学位论文
个分类器，对不同时间段构造不同的分类器，利用最近的数据决定每个分类器的权重，然后用多个分类器的加权和进行预测。实验表明与单分类器相比，该方法
具有更高的分类准确率。
ＶＦＤＴ和ＶＦＤＴｃ是基于决策树的单分类器算法，利用单个分类器模型来反映整个数据流分布，其预测准确率会受到概念漂移的影响。因为历史数据与未来数据可能具有完全不同的分布。
Ｗａｎｇ等人提出的集成方法以Ｃ４．５、ＲＩＰＰＥＲ、ＮａｉｖｅＢａｙｅｓｉａｎ分类为基分类器，集成多个分类器的方法通常可以提高分类准确率，特别是基分类器具有一定的差异性时，它往往比单分类器的准确率高。
２．６小结
本章首先简单的介绍了数据流的特征和数据流挖掘算法分析处理时应满足的条件；然后，重点介绍了概念漂移问题的相关研究和目前数据流挖掘常用的一种技术——滑动窗口；最后，简要介绍了当前数据流分类方面的研究工作。从而说明本文所提出的分类算法有一定应用需求，同时说明本文算法必须满足的要求，便于更加清楚地介绍。

第三章传统的分类方法郑州人学硕｝学位论文
第三章传统的分类方法
数据挖掘领域中，已经有许多静态数据上的分类方法，如决策树、贝叶斯分类、神经网络、支持向量机等。分类包含两个阶段：学习或模型构建（基于包含类标号的训练数据集来构建模型）、分类过程或模型使用（用于预测新来数据的类标号）。而后者有助于数据流分类，因为当新样本数据到达时将被立即分类。
大多数的数据流挖掘算法都是基于以往的静态数据挖掘算法，在已有算法的基础之上增加了对“流”式数据的处理，早期的增量式数据挖掘算法是数据流挖据算法的基础。增量式使已经建立好的数据模型可以重复使用，使得挖掘“流”式数据成为可能。
如何将传统的分类方法应用于数据流成为一个值得讨论的问题。在传统的框架下，训练数据以相对静态的形式存储于数据库，而且很多分类方法均是多次扫描训练数据集。显然，分类模型构建的过程是离线进行的批处理过程，然而对于
数据流，没有离线的阶段，这是因为数据流入速度快，使得存储所有数据和多次
扫描并不可行。所以，必须对传统分类算法进行分析。
本章主要介绍了决策树分类、贝叶斯分类、源于关联规则的分类、基于ＥＰ的分类算法、Ｋ一最临近分类、神经网络分类等传统分类算法的思想、优缺点和主要的实现算法，同时也比较了各个算法在ＵＣＩ１２个数据集上的分类准确率，从而为选择适当的分类算法作为基分类器的构造算法作好铺垫。
３．１决策树分类
决策树（ＤｅｃｉｓｉｏｎＴｒｅｅ）是一个类似于流程图的树结构，决策树分类算法以树形结构表示分类结果，树根节点代表整个数据集合空间，每个内部节点表示在一个属性上的测试，每个分枝代表～个测试输出，测试将数据集集合空间分割成两个或多个块，而每个树叶节点代表类或是类的分布。由根节点到叶子节点的路径描述了各种分类规则。该算法在统计学、机器学习和数据挖掘领域都有广泛的应用。
决策树算法【２４】的采用“分而治之”的策略，基于信息熵递归地选择分割属性，

第三章传统的分类方法郑州大学硕士学位论文
根据属性集的取值选择实例的类别。主要是在树的每个节点上使用信息增益度量选择测试属性，选择具有最高信息增益的属性作为当前节点的分割属性。
算法的基本策略：
●树以代表训练样本的单个节点开始。
・如果样本都在同一个类，则该节点成为树叶，并用该类标记。
・否则，算法使用成为信息增益的给予上的度量作为启发信息，选择能够
最好地将样本分类的属性（步骤６）该属性成为该节点的“测试”或“判
定”属性。
●对测试属性的每个已知的值，创建一个分枝，并据此划分样本。●算法使用同样的过程，递归地形成每个划分上的样本决策树。一旦一个
属性出现在一个节点上，就不必考虑该节点的任何后代上。●递归划分步骤，当满足下列条件之一时停止：
Ａ、给定节点的说有样本属于同一类；
Ｂ、没有剩余属性可以用来进一步划分样本。在此情况下，使用多
数表决。
Ｃ、分枝测试属性没有样本。
基于决策树的分类算法很多，比较有影响的有ＩＤ３、Ｃ４．５、ＣＡＲＴ、ＳＬＩＱ、ＳＰＲ刖Ｔ、ＢＯＡＴ和ＣＬＯＵＤＳ等算法和ＲａｉｎＦｏｒｅｓｔ框架。
传统的决策树算法的结果容易被人理解、分类模式易于转化成分类规则、输入参数少、能处理多种类型数据（连续值和离散值）、能够设计出具有良好伸缩性的算法。
同时，决策树归纳算法也可能面临一些问题，主要是碎片、重复和复制：碎片是指通过重复划分数据集，可能导致一些叶子包含的样本数目太少而失去统计意义。这些叶子对应的是问题空间中不具有一般意义的规则或是噪音数据引起的过度适应。重复是一个属性沿着树的一个给定分枝重复测试。复制是复制了决策树中已经存在的子树。这三个问题不但使决策树变得更庞大，同时影响决策树的分类准确度。因此，为了防止过分适应训练数据集、构造具有更高分类准确度的决策树，需要采用一些应对策略，如剪枝、属性构造等。
前面２．５中介绍到当前的ＶＦＤＴ和ＣＶＦＤＴ算法，就是根掘决策树的思想提
１４

第三章传统的分类方法
郑州人学硕士学位论文
出了一种ＨｏｃｆｆｄｉｎｇＴｒｅｅ算法，该算法时间复杂度是次线性的，并且能产生与传
统的批处理方式下几乎一致的决策树。且通过实验表明，该算法在数据流分类问题上有显著的效果。
３．２贝叶斯分类
贝叶斯分类【２５１是统计学分类方法，它基于贝叶斯定理，使用后验概率预测类成员关系的可能性，如给定样本属于某一特定类的概率。
假定有Ｋ个类ｃｌｃＩ…，Ｃｘ，给定未知数据样本ｘ可以用一个Ｎ维向量描述为ｘ＝｛ｘｌ，Ｘ２…，Ｉｎ’，分类器将预测未知样本ｘ属于在各属性取值为ｘ条件
下的后验概率最高的类。即选择能够使Ｐ●Ｇ阳最大化的Ｇ作为未知样本所属的类Ｐ（ｃ：ＩＸ）＞Ｐ（ＣｊＩｚ），１‘ＪｓＫ，，＿ｉ。
依据贝叶斯定理
粥Ｉ习＝型；铲
验概率未知，通常假定这些类是等概率的，即Ｐ俐＝尸心ｚＪ＝…＝删。类的先验
本总数。因此，如何获得Ｐ（ｘｌｃｉ）成为基于贝叶斯的分类算法的关键问题。
贝叶斯分类基于贝叶斯定理，它主要有朴素贝叶斯分类和贝叶斯信念网络。
其中，Ｐ（的对于所有的类都是常数，只需Ｐ（Ｘ１Ｇ）Ｐ（Ｃｉ）最大，而如果类的先
概率也可以用ｐ（ｃｏ＝慨Ｉ／Ｉｓｌ，其中ｌＳ，Ｉ是训练集中ｃｆ类的样本数，ＩｓＩ是训练集的样
朴素贝叶斯分类算法（ＮａｉｖｅＢａｙｅｓｉａｎ，ＮＢ）做了一个简单的假定：对于给定的
ｃｆ类，所有属性是相互独立的。在属性值相互条件独立的前提下，Ｐ闭ｃｐ的计算
可以简化为：Ｐ（ＸＩＣｔ）一ｎｐ吒Ｉｃｊ）。概率ｐ伍ＪＩｃ，），ｐＯ，２１ｃ，）～・，ｐ阢Ｉａ可以通
过训练集估算。当条件独立性假设成立时，朴素贝叶斯分类是最精确的，然而朴素贝叶斯分类算法的条件独立性假设在现实数据集上通常是不成立的。
贝叶斯信念网络（Ｂａｙｅｓｉａｎ
Ｂｅｌｉｅｆ
Ｎｅｔｗｏｒｋ）［２６ｌ说明联合概率分布，允许在变
量的子集间定义类条件独立性，通过因果关系图来体现属性之间的依赖关系。它主要由两部分构成：有向无环图和每个属性的条件概率表。它可以通过梯度下降
方法得到训练。分类过程返回类标号属性的概率分布。

第三章传统的分类方法
郑州人学硕｝学位论文
在假设成立的前提下分类速度快准确率高。并且，认为贝叶斯信念网络可以
在线性时间内完成数据的分析同时它还具备学习的可能从而适应数据流的数据不断变化的特点。
３．３源于关联规则的分类
关联规则挖掘［２７］１篮】是数据挖掘研究的一个重要的、高度活跃的领域。数据挖掘技术业已将关联规则挖掘用于分类问题，基于关联规则的分类（Ｃｌａｓｓｉｆｉｃａｔｉｏｎ
Ｂａｓｅｄ０１１Ａｓｓｏｃｉａｔｉｏｎ，ＣＢＡ）算法采用候选项产生测试的方法挖掘所有满足最小支
持度和最小置信度阈值的规则，然后使用数据覆盖的概念来选择一个规则集来建立分类器。ＣＢＡ使用形如ｘ一＞ｖ的关联规则，其中Ｘ是一个属性值的集合而Ｙ是类标号这样的规则被称作类规．贝ｌＪ（Ｃｌａｓｓ
Ａｓｓｏｃｉａｔｉｏｎ
Ｒｕｌｅｓ，ＣＡＲＳ）。由于产生的
ＣＡＲＳ总数很大，所以ＣＢＡ采用启发式的剪枝策略，使用一个可以覆盖所有元组的最有效的规则集来构造分类器。在预测未知元组的时，ＣＢＡ在规则集中从最有效规则开始的按有效性顺序搜索分类规则，并用第一个匹配的规则预测未知元组的类标号。
ＣＭＡＲ算法（Ｃｌａｓｓｉｆｉｃａｔｉｏｎｂａｓｅｄ
ｏｎ
ＭｕｌｔｉｐｌｅＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓ，ＣＭＡＲ）ｔ冽扩
展了ＦＰ．ｔｒｅｅ，在每个节点上添加了类信息，并使用ＦＰ．Ｇｒｏｗｔｈ算法产生完整的关联规则集。并把这些规则存储在一个称作压缩规则树（Ｃｏｍｐｒｅｓｓｅｄ
Ｒｕｌｅｔｒｅｅ，ＣＲ
ｔｒｅｅ）的数据结构上，剪除置信度低的规则并依据关联分析和数据覆盖作进一步剪枝。预测未知元组的类标号时，和ＣＢＡ仅使用一条规则做判断的方法不同，ＣＭＡＲ使用所有匹配的规则共同预测的预测未知元组所属的类。为了解决不同规则预测的类标号不同而造成的冲突，ＣＭＡＲ为每一个关联规则赋予一个权值。ＵＣＩ机器学习库测试表明，ＣＭＡＲ算法的分类准确度优于ＣＡ．５和ＣＢＡ，并且ＣＭＡＲ比ＣＢＡ使用更少的内存具有更好的可伸缩性。
ＣＰＡＲ算法是基于预测规则的分类算法（Ｃｌａｓｓｉｆｉｃａｔｉｏｎ
Ａｓｓｏｃｉａｔｉｏｎ
ｂａｓｅｄ
ｏｎ
Ｐｒｅｄｉｃｔｉｖｅ
Ｒｕｌｅｓ，ＣＰＡＲ）ｔ３０１，它使用预测规则挖掘算法（ＰｒｅｄｉｃｔｉｖｅｒｕｌｅＭｉｎｉｎｇ，
ＰＲＭ）产生预测规则。ＰＲＭ算法继承了ＦＯＬＬ算法的基本思想，ＣＰＡＲ采用贪婪
算法从训练集来直接产生预测规则，而不像传统的基于关联规则的分类算法那样需要产生大量候选规则。但是和传统的基于规则的分类算法相比，ＣＰＡＲ产生并
１６

第三章传统的分类方法郑州人学硕｝：学位论文
测试更多的规则。这是因为ＰＲＭ和ＦＯＬＬ不同，它在发现一个实例被规则覆盖
之后并不删除它，而是降低它的权重。因此，ＰＲＭ算法产生更多规则并且每个实例通常被多个规则覆盖。并且不是仅仅选用最好的一条规则，而是选择所有接近最好的规则的策略可以避免丢失重要的规则。ＣＰＡＲ在预测过程中用预期准确度来度量每一个规则的贡献，使用最好的Ｋ个规则共同决定未知样本的所属类别。测试结果显示，ＣＰＡＲ取得了更好的分类精度和速度。
３．４基于ＥＰ的分类算法
基于显露模式①ｍｅｒｇｉｎｇ
ＰａＲｅｒｎ，ＥＰ）【３１Ｊ【３２１的分类器和传统的分类算法不同。
传统的分类算法在作微观决策的时候仅考虑一个属性或一组属性，而基于ＥＰ的分类算法，通过聚合多个ＥＰ在做决策时考虑了多组属性，能够捕获不同类之间的差异和取值倾向，从而提高了分类的准确率。，所以说，ＥＰ具有很好的区分性能比较适合用来指导分类。
基于ＥＰ的分类算法主要由两个过程，一、基分类器的构建：采用挖掘ＥＰ的算法，根据支持度和增长率的限制在训练数据集中，挖掘出满足条件的ＥＰ，利用这些ＥＰ构建基分类器。二、使用基分类器进行分类，即使用分类器对测试
数据进行评分，从而判断它属于哪个类。
基于ＥＰ的分类算法主要有ＣＡＥＰ，ＪＥＰ．Ｃｌａｓｓｉｆｉｅｒ、ＤｅＥＰｓ、ＢＣＥＰ和ＣＥＥＰ。
ＣＡＥＰ是第一个基于ＥＰ的分类算法【３３１，主要基于以下思想：因为ＥＰ的支持度在不同类之间有显著差异，每一个ＥＰ可以明显的区分该ＥＰ覆盖的样本的类标号。但是一个ＥＰ通常仅仅可以区分所有样本中的一小部分。因此，首先找到满足一定支持度和增长率的Ｃ（１ｓｉｃＫ）类的所有ＥＰｓ，其中把除ｃｆ类之外的所有样本作为非目标类。每个ＥＰ的区分能力通过增长率和在目标类上的支持度
来衡量。
ＪＥＰ．ＣｌａｓｓｉｆｉｅｒＩ驯很多处理策略和ＣＡＥＰ相似，只是它采用一类最具区分能力
的ＥＰ，即ＪＥＰ构造分类器。ＪＥＰ．Ｃｌａｓｓｉｆｉｅｒ也是采用了聚合ＥＰ区分能力的思想，和ＣＡＥＰ的主要不同有：
１）ＣＡＥＰ使用ＥＰ，然而ＪＥＰ—Ｃｌａｓｓｉｆｉｅｒ仅仅使用最具表达能力的ＪＥＰ。２）对于目标类是多个类的情况，ＣＡＥＰ采用了类之间对称挖掘ｃｆ类和非Ｇ

第二三章传统的分类方法郑州大学硕士学位论文
类的方式，而ＪＥＰ．Ｃｌａｓｓｉｆｉｅｒ则采用了按照预定顺序逐一判断ｓ是否属于某个类的方式。
３）在聚集ＥＰ的区分作用时，ＣＡＥＰ使用了增长率和支持度，然而
ＪＥＰ．Ｃｌａｓｓｉｆｉｅｒ仅仅使用支持度衡量。
４）ＣＡＥＰ使用了一定的ＥＰ规约策略，而ＪＥＰ．Ｃｌａｓｓｉｆｉｅｒ因为每一个ＪＥＰ的增
长率都是无穷，因此规约策略要比ＣＡＥＰ简单。同时ＪＥＰ．Ｃｌａｓｓｉｆｉｅｒ没有像ＣＡＥＰ那样采用的标准化策略。
ＪＥＰ．Ｃｌａｓｓｉｆｉｅｒ和ＣＡＥＰ各自具有自身的优点，ＪＥＰ．Ｃｌａｓｓｉｆｉｅｒ面临的主要问题
是某些情况下可能没有足够的ＪＥＰ。对于ＪＥＰ不足的情况下，ＣＡＥＰ的分类准确度高于ＪＥＰ．Ｃｌａｓｓｉｆｉｅｒ。然而如果有足够多的ＪＥＰ可以用来构造分类器，ＤｅＥＰｓ［３５ｌ采用了基于实例的方法，一种懒散的学习方法。ＤｅＥＰｓ能够在不需要重新训练分类器的情况下处理新的训练数据。这个特征在训练数据频繁更新的实际应用中是非常有用的。ＤｅＥＰｓ能够处理数值属性和离散属性，并且对训练实例的数目有很好的可规模性。
ＢＣＥｐｌ３‘Ｓｌ算法混合了基于ＥＰ的分类算法和贝叶斯分类算法的思想。采用了
懒散的学习过程，同时Ｈ．Ｆａｎ和ＫＲａｍａｍｏｈａｎａｒａｏ使用一类特殊的ＥＰ，称为ｅＥＰ，建立基于ＥＰ的Ｂａｙｅｓｉａｎ分类器。
ＣＥＥＰｌ３７１是基于ｅＥＰ的多分类器表决分类算法，它主要是采用前期一个挖掘ｅＥＰ（基本显露模式）的算法构建基分类器，因为并非所有的ＥＰ都具有较强的区分能力，而ｅＥＰ是挖掘出的较短的ＥＰ即基本的显露模式，这样可以避免挖掘的ＥＰ太多影响分类速度；然后它采用了构建多个分类器的方法，通过多分类器表决的方法来确定分类结果。
ＥＰ具有良好的区分能力，比较适合分类。同时可以在线性时间内挖掘出满足条件的ＥＰ。
３．５
Ｋ－最临近分类
最临近分类㈣是基于类比的学习。训练样本用Ｎ维数值属性描述，每个样
本代表Ｎ维空间的一个点，所有训练样本都被存放在Ｎ维模式空问中。给定一
ＪＥＰ．Ｃｌａｓｓｉｆｉｅｒ分类性能通常优于ＣＡＥＰ。

第三鼋传统的分类方法郑州人学硕‘ｌ：学位论文
个未知样本，Ｋ－最临近分类法搜索模式空间，找出最接近未知样本的Ｋ个训练样本。这Ｋ个训练样本是未知样本的Ｋ个近邻，临近性可以用欧几里德距离来
定义。给定两个点ｘ＝｛ｘ１～Ｘ２一函’和Ｙ＝｛ｙ１，Ｙ２，．．．，ｙｎ），则欧几里德距离定义为ｄ（Ｘ，ｙ）一√∑：。“一Ｙｉ）２，未知样本被分配到Ｋ个最临近者中最公共的类。
Ｋ－最临近分类是一种懒散的学习方法，它保存所有训练样本直到未知样本需要时才建立分类，与决策树等急切学习法形成鲜明的对比。因为急切学习方法在接受未知样本之前，已经根据训练数据集构造了一个一般的分类模型。懒散学习法的所有计算都推迟到分类预测时进行，因此如果训练集数据量很大，可能的临近者数量很大，懒散的学习方可能导致很高的计算开销，使分类过程变得缓慢。
３．５神经网络分类
神经网络１３９１最早是由心理学家和神经生物学家提出的，旨在寻求开发和测试神经的计算模拟。神经网络是一组相互连接的输入／输出单元，每个连接都与一个权值相关联。在学习阶段，通过调整神经网络的权，使网络能够正确预测输入
样本的类标号来学习。
神经网络需要很长的训练时间，而且需要大量的参数，这些参数主要靠经验
确定，如网络拓扑或结构。人们很难解释蕴涵在学习权之中的符号的含义，因此
神经网络很难被理解和解释，神经网络的行为也像一个“黑盒子”。
神经网络也有一些其他算法所不具备的优点，如对噪声数据的高承受能力，以及它对未经训练的数据分类模式的优秀表现。由于最近提出一些从训练过的神经网络提耿规则的算法。这些因素推动了神经网络在数据挖掘分类方面的应用。
３．６其他分类算法
其他的分类算法还有很多如：支持向量机ｆ加１、遗传算法、粗糙集算法、基于案例的推理等多种类型的分类算法。这些算法都具有自身的优点和不足，但是都在一定的应用领域取得了成功。如：支持向量机具有良好的可伸缩性并且能够很
好的解决训练数据的过分拟合问题。粗糙集方法分类可以发现不准确数据和噪声
数据的内在联系。遗传算法和只能获得局部最优解的贪婪算法相比，通常能够获
１９

第三章传统的分类方法郑州大学硕ｆ：学位论文
得更具全局意义的满意解。遗传算法易于并行，可以应用于分类和其他优化问题。
上述类型的分类算法并不是彼此孤立的，有些分类算法可能会借鉴上述不同类型算法的优点。不存在某一类型或是某一个算法在所有的数据集上的分类准确度、训练时间、强壮性、可规模化、可解释性等方面性能都优于其他类型的算法。实际应用中最好的解决方案常常是各方面性能要求的折中。因此，评价一个算法的优劣常常是结合具体的应用背景和领域要求。
３．７传统分类算法准确率的比较
为了更好的说明基于ｅＥＰ的分类算法ＣＥＥＰ在传统数据分类算法中的优势，我们收集了各个算法针对ＵＣＩ上１２个数据集中的分类结果。分类法的结果数据取自相应文献１２４”３９】。
表１分类正确率：ＮＢ，Ｃ５．０，ＣＢＡ，ＣＭＡＲ，ＣＡＥＰ，ＢＣＥＰ和ＣＥＥＰ比较
数据集ＡｄｕｌｔＡｕｓｔｒａｌｉａｎＣｌｅｖｅ
Ｄｉａｂｅｔｅ
ＮＢ
ｃ５．０ＣＢＡＣＭＡＲＣＡＥＰ８３．０９
ＢＣＥＰＣＢＥＰ
８４．１２８５．６５８２．７８７５．１３７４．９４８２．２２８９．４５９９．６８７５．９０
８５．５４８４．９３７７．１６
７３．０３７１．９０７６．３０９１．４５
８５．００
８６．４０
８１．８５
８７．８３８４．３３
８４．９０８２．８０７４．５０７３．４０
８１．９０
８６．１０８２．２０７５．６０７４．９０
８２．２０
８６．２１
８３．２５６７．３０
７２．５０
８２．４１７６．８０７４．５０８１．８５
９３．２４１００７５．６６
７４．０８
７３．４０８４．０７９２．５７９９．９０
Ｇｅｒｍａｎ
Ｈｅａｒｔｌｏｎｏ
８３．７０
８９．７６
９２．３０９１．５０
Ｍｕｓｈｒｏｏｍ
Ｐｉｍａ
１００
７５．３９７６．００
９８．８２
７２．９０７７．５０
６８．７０
７５．１０
７５．００
７８．３０６６．３２７４Ｊ３８
７３．０３８５．５０
６７．４４８４．３８８２．３７
Ｓｏｎａｒ
ＶｅｃｈｉｌｅＬｙｍｐｈ
７５．４０
６１．１２８１．８６８０．６９
７９．４０
６８．８０
７８．４０
６８．５８３．１３
６９．８２
７８．２９
７７．８０８０．８６
８３．１０
８１．８８
平均
７９．９８７９．８９８２．１６
通过表Ｉ中的实验结果，我们可以看出ＣＥＥＰ在１２个数据集中的５个获胜，并具有最好的平均正确率。与ＮＢ（朴素Ｂａｙｅｓｉａｎ分类法）相比，ＣＥＥＰ在９个数据集上胜出。与（２５．０（一种决策树分类法）相比，ＣＥＥＰ在８个数据集上胜出。与ＣＢＡ和ＣＭＡＲ是两种基于关联规则的分类法比较，ＣＥＥＰ分别在１０个数据集中的７个和６个上胜出。与早期的基于ＥＰ的分类法ＣＡＥＰ相比，ｃＥＥＰ在１０个数据集上获胜。与基于ＥＰ的Ｂａｙｅｓｉａｎ分类法ＢＣＥＰ相比，虽然ＣＥＥＰ的平均
正确率略高于ＢＣＥＰ。
这就说明ＣＥＥＰ算法在传统分类算法中具有较强的稳定性和较高分类准确率，是我们为了数据流分类寻找的构造基分类器算法。该算法使用了基于模式增

第三章传统的分类方法郑州大学硕十学位论文
长的ｅＥＰ的快速挖掘算法，不但改进了传统的基于ＥＰ算法的评分策略，同时解决了参数的自适应选择等问题。实验表明ＣＥＥＰ算法简洁高效，展示出了优秀的分类性能。
３．８小结
本章主要介绍了决策树分类、贝叶斯分类、源于关联规则的分类、基于ＥＰ的分类算法、Ｋ＿最ｌ临近分类、神经网络分类等传统分类算法的思想、优缺点和主要的实现算法，同时也比较了各个算法在ＵＣＩ１２个数据集上的分类准确率，依据准确率的比较结果，我们认为基于ｅＥＰ的分类算法ＣＥＥＰ通过使用基于模式增长的ｅＥＰ的快速挖掘算法，改进了传统的基于ＥＰ算法的评分策略，同时解决了参数的自适应选择等问题，展示出了优秀的分类性能和白适应能力。我们确定选择ＣＥＥＰ算法作为基于ｃＥＰ的数据流分类算法ＣＥＥＰＣＥ的基分类器构造算法。

第四章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑州人学硕上学位论文
第四章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ
随着近些年信息技术的快速发展和信息搜集能力的日益提高，在诸如信用卡欺诈监测、差异性营销、网络入侵检测和传感器网络等应用中，随着时间的更迭而生成连续的数据流，其数据量大且数据分布可能会发生变化（即概念漂移）。因此如何从海量的数据中训练模型来有效地预测未来的数据趋势成为一个热点，这就使在数据流上的分类算法研究有了一个发展的契机。通过第二章对数据流的特征、概念漂移的分析和对当前数据流分类算法动态的了解，结合第三章对传统分类算法性能的分析，我们提出了一种新颖的基于ｅＥＰ的数据流分类算法（Ｃｌａｓｓｉｆｉｃａｔｉｏｎ
ｂｙｅＥＰ—ｂａｓｅｄＣｌａｓｓｉｆｉｅｒｓ
Ｅｎｓｅｍｂｌｅ，ＣＥＥＰＣＥ）。
本章的主要内容如下：第一部分是相关知识和概念定义。主要介绍了ＥＰ挖掘问题的相关知识和几个概念的定义。第二部分重点介绍了ＣＥＥＰｃＥ算法。主要包括基本思想、基于分类误差的加权方法、基分类器的构造、多分类器的产生与更新和分类器集成等内容。
４．１相关知识和概念定义
在这部分，首先介绍ＥＰ挖掘的相关知识：支持度、增长率、ＥＰ和ｅＥＰ的概念以及ｅＥＰ的优点；然后介绍了数据流、基本窗口和滑动窗口的定义。４．１．１相关知识
１．支持度
项集ｘ在数据集Ｄ上的支持度，记为ＳｕｐＤ∞，定义为Ｓｕｐｏ（１０＝ｃｏｕｎｔＤ（Ｘ）
／ＩＤ｜，其中ｃｏｕｎｔｎ（Ｘ）是数据集Ｄ中包含ｘ的样本个数，而ＩＤＩ是数据集Ｄ中样
本的总数。
２．增长率
给定两个不同的数据集Ｄ’和Ｄ，项集ｘ从Ｄ’到Ｄ的增长率ｇｒｏ，。∞定义如
下：

第网章摹于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑州大学硕Ｉ二学位论文
ｆ
０
如果ｓｕＰｏ．（ｚ）一。％（工）一０
如ＳＵＰＤ．（ｚ）一ｏ，ｓ￡Ｅ％（ｘ）一０
其他
自％．一Ｄ（ｚ）－｛∞
ｌ聊Ｄ暖）／ｓｕｐＤ．“）
如果数据集Ｄ和Ｄ’分别是白类和非白类样本的集合，ｇｒｏ．∞∞记作ｇｒｉ（Ｘ），
它是项集ｘ从非岛类到。类支持度（频率）变化显著程度的度量。
３．ＥＰ的概念
显露模式：给定增长率阈值Ｐ＞１，如果项集ｘ从Ｄ’到Ｄ的增长率跏，。∞
乏Ｐ，则称ｚ是从Ｄ’到Ｄ的ｐ－ＥＰ（或ＥＰ）如果ｚ的增长率为８，则称ｘ从Ｄ’
到Ｄ的ＪＥＰＱｕｍｐｉｎｇＥＰ）。
石从Ｄ’到Ｄ的ＥＰ通常简单地称ｘ是Ｄ的ＥＰ，而ＥＰ在集合Ｄ上的支持度ＳｕｐＤ（Ｘ）则称作ＥＰ的支持度，记作Ｓｕｐｏ（Ｘ）。同时称数据集Ｄ为目标类而称Ｄ’为非目标类。
ＥＰ是那些从一个数据集到另一个数据集支持度发生很大变化的项集，这些项集能够很好地捕获目标类和非目标类上多个属性之间的不同，所以具有很好的区分性。对于任意一个样本Ｓ，工是ｃ／类的ＥＰ，如果ｘ∈Ｓ，那么我们称作Ｓ包
含石或是Ｘ覆盖了样本Ｓ。
ＥＰ具有很好的区分能力。然而，待分类的数据集可能存在大量ＥＰ（数以万计），并且这些ＥＰ不是独立的（存在包含关系）。实践表明使用所有的ＥＰ进行
分类并非很有效。Ｈ．Ｆａｎ和ｋＲａｍａｍｏｈａｎａｒａｏ提议使用一类特殊的ＥＰ，称为ｅＥＰ。ｅＥＰ定义如下：
４．ｅＥＰ的概念
项集ｘ称为Ｄ上的ｅＥＰ，如果工是Ｄ的ＥＰ，并且ｘ在Ｄ中的支持度不小于预先指定的最小支持度阈值毫，而ｘ的任何真子集都不满足上述条件。
ｃＥＰ很多独特的优点使ｅＥＰ自从提出来之后一直为业界所重视。ｅＥＰ是最短的ＥＰ，在满足支撑度和增长率一定条件下，ｅＥＰ可以使用更少的属性，这不但可以简化分类器，同时可以增强分类器的抗干扰能力。
５．ｅＥＰ的优点
基本显露模式（Ｅｓｓｅｎｔｉａｌ
ＥｍｅｒｇｉｎｇＰａｔｔｃｍｓ，ｅＥＰ）是一类特殊的ＥＰ。在事实上，
ｅＥＰ是那些“最短的”ＥＰ，它有着如下的优点：

第四章摹于ｅＥＰ的数据流挖掘算法ｃＥＥＰｃＥ
郑州大学硕１二学位论文
●足够高甚至无穷大的增长率，确保ｅＥＰ具有很好的区分能力；
・最小支持度阈值确保每个ｅＥＰ至少覆盖一定数量的样本，从而具有一定
的统计意义，确保它们的实用性；
●ｅＥＰ的超集对于分类并没有多大用处。其理由如下：假定Ｅ１
ｃ
Ｅ２，并
且Ｅ１是ｅＥＰ。根据定义，Ｅｌ具有很高的增长率，并且被Ｅ２覆盖的样本一定都被Ｅ１覆盖，从而Ｅ２并不提供比Ｅ１更多的分类信息。ｅＥＰ是最短的ＥＰ，不同的ｅＥＰ之间不可能存在包含关系。因此，ｅＥＰ之间的独立性较好，几乎每一个ｅＥＰ都为分类提供了新鲜的知识。由于ｅＥＰ是ＥＰｓ边界表示的左边界，选择ｅＥＰ构造分类器就是使用ｅＥＰ代表了包含它的所有超集，使用ｅＥＰ分类可以减少分类过程中使用的ＥＰ并且损失很少的信息。另外，较短的ＥＰ意味着在分类过程中使用较少的属性，因此利用这样的ｅＥＰ建立分类器不但可以大量压缩分类过程中使用的ＥＰ的数量，而且能够增加分类器的抗噪
声能力。
４．１．２概念定义
定义１．数据流（Ｄａｔａ
Ｓｔｒｅａｍ）
假设ＤＳ是形如：Ｐ＾ｅｚ，…，ｅｂ…，％…的数据流元素序列，其中每个数据流元素研＝ｆ如ｉ６如…，‘，是每个不同属性组成的，每个属性称为一个项，ｉｏ是类标号。
注：数据流元素的长度或是等长的，或是不等长的，本文处理的是后则的情况；本文处理的实验数据，假设数据流的训练集和测试集同时到达。有关实验所采用的数据流，将在第五章进行详细说明。
定义２．基本窗（ＢａｓｉｃＷｉｎｄｏｗ）
假设ＢＷ是一个基本窗口，对应一个数据流子序列ｅ６％…，ｅｌ，长度标记为旧卅，基本窗口标记为６¨，，基本窗口作为训练基分类器的基本单元，它包括训
练数据流ＤＴｒａ如和测试数据流Ｄ砌。
定义３．滑动窗Ｈ（ＳｌｉｄｉｎｇＷｉｎｄｏｗ）
假设ＳＷ是一个滑动窗口，对应一个连续的基本窗口序列。表示为ＳＷ＝ｂｗｌ，．．．，６№，．．．，ｂｗｒ，其中ｂｗｉ表示相对于滑动窗口而言的第ｉ个基本窗口，ｂｗｒ是最新近
的窗口。Ｋ表示一个滑动窗口容纳基本窗口的数目。在基本窗口６¨々训练得到对

第四章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑抖｜大学硕士学位论文
应的基分类器为Ｇ。在算法ＣＥＥＰＣＥ中，滑动窗口的大小就相当于多分类器的个数。滑动窗口的更新采用最早到优先移出的策略。
４．２基于ｅＥＰ的数据流分类
本部分将主要介绍在数据流环境下，基于ｅＥＰ的分类算法ＣＥＥＰＣＥ。首先介绍算法的基本思想，然后介绍基于误差的加权方法、基分类器的构造，多分类器的构造与更新，最后介绍分类器集成。４．２．１基本思想
本文中的算法ＣＥＥＰＣＥ（ＣｌａｓｓｉｆｉｃａｔｉｏｎｂｙｅＥＰ－ｂａｓｅｄＣｌａｓｓｉｆｉｅｒｓＥｎｓｅｍｂｌｅ）是针
对数据流的训练集和测试集同时到达而设计的。
ＣＥＥＰＣＥ综合了基于ｅＥＰ的分类器及集成方法的特性，它以ＣＥＥＰ分类算法作为基分类器，在滑动窗口ＳＷ内训练Ｋ个基分类器的集合Ｅ，当滑动到第Ｋ＋１个基本窗口时，训练基分类器Ｃｋ伽并计算每个基分类器Ｇ的分类误差率，然后依据４．２．３节提出的加权方法加权并选出权重最高的Ｋ个基分类器作为输出。
与传统的基于ＥＰ的分类算法一样，ＣＥＥＰＣＥ算法的分类过程可以描述为以
下两个步骤：
第一步，建立一个分类模型。基于ｅＥＰ的分类器ＣＥＥＰＣＥ以ｅＥＰ作为分类因子，结合数据流的特性和基于ＥＰ分类器的构造思想，我们在建立分类模型的时候提出了一个“三层构造模型”来构造多分类器，即：ｅＥＰ的挖掘和加权、基分类器的构建、多分类器的集成。同时，为了适应数据流的概念漂移我们在分类器建立以后又采用滑动窗口ＳＷ技术来更新多分类器。这部分内容在接下来的
４．２．２和４．２．４节中详细介绍。
第二步，使用模型进行分类。使用多分类器进行分类，结合多分类器的“三层构造模型，在对未知样本进行分类时，我们从ｅＥＰ分类、基分类器分类和多分
类器集成三个层面介绍了分类的细节。并结合数据流挖掘分析多考虑最近最新数
据的特点，对不同的基分类器赋予不同的权值，并加权集成多分类器，从而提高
分类的准确率。这部分内容在接下来的４．２．５中详细介绍。
下面首先介绍ＣＥＥＰＣＥ算法的语言描述：

第叫章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰｃＥ郑州大学硕ｔ学位论文
●滑动窗口数Ｋ，基本窗口大小ＳＷ，支持度Ｓｕｐ，增长率Ｇｒｏ等参数的
初始化。
・接收ｂｗｉ数据流，对训练数据流Ｄ孤加使用ＣＥＥＰ算法构造基分类器Ｇ。・判断此时多分类器内基分类器的个数Ｍ。如果Ｍ＜Ｋ，表明滑动窗口并
没有满，生成的基分类器ｃｆ进入滑动窗口；反之，则需要对滑动窗口进行更新，移出最早进入滑动窗口的基分类器ｃ『，Ｇ进入。
●采用多分类器加权投票的方式，对测试数据Ｄ肺进行分类测试。
●返回第二步骤，直到没有数据流到达。４．２．２基分类器的构造
在前面的３．４基于ＥＰ的分类算法中，已经介绍ｅＥＰ是一种特殊的ＥＰ，这样基于ｅＥＰ的分类算法，也是基于ＥＰ的分类算法。而基于ＥＰ的分类法的核心问题是：使用什么样的ＥＰ，如何有效地从大型数据集中挖掘这些ＥＰ，以及如何使用这些ＥＰ（建立评分标准）确定新样本的所属类。所以ＣＥＥＰ分类算法的主要考虑的问题：（１）如何确定最小支持度阈值毫和最小增长率阈值ｐ；（２）如何挖掘每个类的ｅＥＰ；（３）如何确认单个ｅＥＰ对确定类成员关系的贡献。
１．最小支持度和最小增长率阈值的确定
影响ＣＥＥＰ分类正确率的主要因素是ｅＥＰ的区分度和覆盖率，而它们主要取
决于两个相关的参数：最小支持度和最小增长率阂值。一般地，固定最小支持度阈值，较高的增长率导致产生具有较高区分度的ｅＥＰ（有利于建立更好的分类器），但可能降低覆盖率（不利于建立好的分类器）。而固定增长率，支持度越高，覆盖率就越低；但支持度过低，所产生的ｅＥＰ不具有一般性，也不利于建立好的分类器。
实验表明，对于大多数数据集，最小支持度阈值的较好选择大约在１％左右。但是，最小增长率阈值的较好选择却因数据集不同而相差悬殊。例如，当最小支
持度阈值为１％时，对于数据集Ｍｕｓｈｒｏｏｍ，Ａｕｓｔｒａｌｉａｎ，Ｇｅｒｍａｎ，Ｃｌｅｖｅ和Ｈｅａｒｔｓ，
最小增长率阈值分别取３５，４．４，３．１，２．１和１．８时ＣＥＥＰ分类的精度最高。因此，
给定训练数据集，我们需要在训练阶段确定两个参数：最小支持度阈值毫和最小增长率阈值Ｐ。

第叫章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑州大学硕｝学位论文
对于给定的数据集ＤＢ，ＣＥＥＰ采取随机抽样，将ＤＢ分成１０个大致相等的数据集ＤＢｌ，ＤＢ２，…，ＤＢｌ０。交替地固定最小支持度阈值毫和最小增长率阙值Ｐ中的一个，采用十折交叉验证自适应地选择另一个，直到分类正确率不再提高或满足要求为止。例如，固定最小支持度阈值鼍＝Ｏ．０１，ＣＥＥＰ通过如下步骤选择最小增长率阈值：
（１）置初值：选取最小增长率阙值，例如Ｐ＝２；
（２）使用善和ｐ的当前值，对于ｋ＝１，２…．，１０
（ａ）令Ｄ—Ｕｉ。ＤＢｉ，在Ｄ中挖掘Ｃｉ类和非Ｃｉ类的ｅＥＰ（ｉ＝１，．．．Ⅸ）；（ｂ）对于ＤＢｔ中每个样本Ｓ，使用（１）式计算ｓ属于Ｃｉ类的得分ｓｃｏｒｅ（Ｓ，
ＣＤ（ｉ＝１，．．．Ⅸ），并按分类规则确定Ｓ所属类；
（３）统计分类正确率；如果分类正确率不再提高或满足要求，则结束；（４）将Ｐ增加或减少一个增量，转（２）。
一般地，当分类正确率上升时，可以提高ｐ值；反之，降低Ｐ值。增量可以取固定值（如０．１），也可以用递减的增量。最小支持度阈值毫的自适应选择可以类似地进行。这种参数的自适应选择虽然不能保证得到最佳的参数值毫和Ｐ，但通常可以得到较好的。
可以对不同的类Ｃｉ使用不同的最小支持度阈值擎和最小增长率阙值Ｐｉ。这样需要确定２Ｋ个参数，使得训练时间将大大增加。带来的好处是有助于提高最终分类器的分类正确率。我们的经验表明，对于Ｋ＝２，可以采用不同的最小支持度阈值岛和最小增长率阈值Ｐｉ。当Ｋ较大时，使用不同的最小支持度阈值毛和最
小增长率阈值Ｐ；的好处并不明显。
２．ｅＥＰ的挖掘
对于给定的训练数据集ＤＢ，它包含ｃ』，ｃ２…．，ＣＫ个类。为建立ＣＥＥＰ分类器，
我们需要对于ｉ－１，２，．．．，Ｋ，某支持度阈值芎和增长率阈值Ｐ，求ｑ类和非ｃｉ类的
ｃＥＰ。
如何有效的挖掘ＥＰ呢？我们采用了一种基于模式树（Ｐ．树）的挖掘ｅＥＰ的有效算法。与ＦＰ．树１４１ｌ类似，Ｐ．树存储了训练数据集中所有的项信息。不同的是，Ｐ．树维护了类信息，以支持挖掘ｅＥＰ。该算法采取了模式增长的挖掘方法，并直接地在Ｐ．树中挖掘所有的ｅＥＰ，而不需要附加的空间。该算法的思想部分地与［４２］

第四章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑州大学硕上学位论文
类似。Ｍｉｎｅ．ｅＥＰｓ是一个基于模式增长的挖掘算法，它可以在通过Ｐ－ｔｒｅｅ结构有效的实现。Ｐ．ｔｒｅｅ和ＦＰ－ｔｒｅｅ树相似，两者的主要差别是Ｐ．ｔｒｅｅ的每个节点包含两个计数分别记录每个类到达该节点的路径数。下边将给出Ｍｉｎｅ．ｅＥＰｓ的算法描
述：
为了简明起见，假设类Ｃｌ和类Ｃ２的所有频繁项都被映射到连续的正整数集合｛１，２，…，ｍａｘ｝＆。挖掘类Ｃｌ和类ｃ２的所有的ｅＥＰ可以通过给定初始参数Ｐｒｅｆｉｘ
＝彩，Ｆｉｒｓｔ＝１，ａｎｄ
Ｌａｓｔ＝ｍａｘ调用Ｍｉｎｅ．ｅＥＰｓ完成：
Ｐｒｏｃｅｄｕｒｅ
Ｍｉｎｅ－ｅＥＰｓＷｒｅｒｌｘ，Ｈｒｓｔ，Ｌａｓｔ）
｛
ｗｈｉｌｅ（ＰｒｅｆｉｘＵ｛Ｆｉｒｓｔ｝ｉｓ
ｎｏｔｆｒｅｑｕｅｎｔｉｎｂｏｔｈｏｆｃｌａｓｓＣｌａｎｄ
ｃ９
Ｆｉｒｓｔ＋＋：
ｉｆ（Ｆｉｒｓｔ＞Ｉ．ａｓｔ）ｒｅｔｕｒｎ；ｉｆ（ＰｒｅｆｉｘＵ｛Ｆｉｒｓｔ｝ｉｓ
ａｌｌ
ＥＰｏｆｃｌａｓｓ
１１）｛
ＯｕｔｐｕｔＰｒｅｆｉｘ
Ｕ｛Ｆｉｒｓｔ｝ａｓａｎ
ｅＥＰｏｆｃｌａｓｓｃｌ；
ｒｅｔｕｒｎ；｝
ｉｆ（ＰｒｅｆｉｘＵ｛Ｆｉｒｓｔ｝ｉｓａｎ
ＥＰｏｆｃｌａｓｓ
ｃ２）
Ｏｕｔｐｕｔ
Ｐｒｅｆｉｘ
Ｕ｛Ｆｋｓｔ｝ａｓａｎｅＥＰｏｆｃｌａｓｓｃ２；
ｆｏｒｏ【＝Ｆｉｒｓｔ＋１；ｋ＋＋；ｒａｓｔ）｛
ｉｆ（ＰｒｅｆｉｘＵＩｋ｝ｉｓ
ｆｒｅｑｕｅｎｔｉｎｃｌａｓｓ
Ｃｌｏｒ
ｃ２）｛
ｉｆ（ＰｒｅｆｉｘＵ｛ｋ｝ｉｓ
ａｌｌ
ＥＰｏｆｃｌａｓｓ
Ｃ１）｛
Ｏｕｔｐｕｔ
ＰｒｅｆｉｘＵ｛ｋ｝ａｓａｎ
ｅＥＰｏｆｃｌａｓｓｃｌ；
ｃｏｎｔｉｎｕｅ；｝ｉｆ（ＰｒｅｆｉｘＯ｛ｋ｝ｉｓ
ａｎ
ＥＰｏｆｃｌａｓｓ
ｅ２）｛
Ｏｕｔｐｕｔ
ＰｒｅｆｉｘＵ｛ｋ｝ａｓａｎ
ｅＥＰｏｆｃｌａｓｓｃ２；
ｃｏｎｔｉｎｕｅ；｝
ＡｄｄｋｉｎｔｏＰｒｅｆｉｘ；
Ｍｉｎｅ—ｅＥＰｓ（Ｐｒｅｆｉｘ，Ｆｉｒｓｔ，ｋ－１）；
ＲｅｍｏｖｅｋｆｒｏｍＰｒｅｆｉｘ；
））｝

第四章基于ｅＥＰ的数据流挖掘算法ｃＥＥＰＣＥ郑州大学硕｝学位论文
３．ｅＥＰ加权
由于数据流的数据分布是经常变化的，为了能够使基分类器具有更好的分类行，在进行ｅＥＰ挖掘后，采用了一种通过训练ｅＥＰ实现ｅＥＰ权值自适应地选取的策略【矧，从而当数据分布发生轻微变化时，可以通过再学习调整权值，使得分类器
可以适应新的数据分布。
假定每个ｅＥＰ廊被赋予一个对应的权值ＷＸ。对于待分类样本ｓ，按照如下步
骤决定Ｓ所属的类：
用下式计算ｓ属于ｃｆ类的得分ｓｃｏｒｅ（Ｓ，∞
￥ｃｏｒ啦ｃＩ）－盖，耥喙
其中，’’，ｒ是蹦权值。
将Ｓ划归得分最高的类。如果得分最高的类不唯一，则将ｓ划归得分最高的多数类。
具体的训练过程如下：令每个ｅＥＰ肭初始权值碟’一１，对每个训练样本进行
分类，统计训练误差ｅｒｒ（ｏ）并收集被误分类的训练样本Ｓ。。然后，迭代地调整ｅＥＰ的权值，降低训练误差，直至ｌｌＯＩＩ练误差不能再降低或迭代次数超过某个预先设定
的上限。
第ｋ（±１）次迭代，首先利用品，中的训练样本调整ｅＥＰ，御均初始权值Ｈ，箬一，
得到新的权值ｗ娑’；然后，使用新的权值和３．１介绍的规则对每个训练样本进行分类，统计训练误差ｅｒ，∞并收集被误分类的训练样本岛，。如果Ｐｒ，肚）＞ｅｒｒ（ｋ－１’或迭代
次数超过某个预先设定的上限，则调整结束，令ＷＸ＝皑。１’；否则，女增加１，进
入下一次迭代。在第ｋ次迭代，权值按照如下步骤调整：（１）令每个ｅＥＰＸ的权值增量¨智＝Ｏ；
（２）对于每个训练样本Ｓ∈蕊，
如果ｓ属于ｃｊ类，则对每个彳，ｓ＠ｃｆ）令
Ａｗｘ．＿ｍａｘ（Ａｗｘ，面两１酾’‘６）
其中，七为迭代的次数，Ｉｓ＠ｃｉ）ｌ是ｓ＠ｃｊ）中的ｅＥＰ个数，而是６权值调整参数（稍
后讨论）。
（３）对于每个ｅＥＰＸ，令诈’一碟‘１’＋△¨＿。
第ｋ次调整权值后，ｓ属于Ｃｆ类的得分即ＤＭ＠Ｑ）至少提高８／ｋ倍。这有利于将ｓ

第叫章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑州人学硕士学位论文
正确地分到ｃ；类。然而，权值的调整也可能导致新的误分类。例如，假定ｓ１是ｃｊ
类样本，＆不是Ｃｉ类样本。其中，被Ｓｌ误分类，而岛被正确分类。如果腥Ｃｉ类的ＥＰ并且在ｓ，中出现，则ｘ的权值将被提高。如果啦中出现，则ｓ∞陀∞ｃｆ）将因
瑚权值的提高而增大，可能导致＆被错误地分至＇Ｊｃｉ类。
３．基分类器的构造
假设训练数据集ＤＢ包含Ｋ个类，基分类器的构造方法如下：●确定最小支持度阈值色和最小增长率阈值Ｐｔ。
・使用最小支持度阈值鲁和最小增长率阈值Ｐｔ，对于ｉ＝１…．，Ｋ，在训练数
据集ＤＢ上挖掘。类和非Ｃｉ类的ｅＥＰ。
●采用训练ｅＥＰ实现ｅＥＰ权值自适应地选取，对ｅＥＰ加权这些ｅＥＰ结合评分策略和分类规则构成了一个ＣＥＥＰ分类器ＣＢｉ。４．２．３基于分类误差的加权方法
当ＳＷ滑动到下一个基本窗口ｂｗ时，首先更新滑动窗口内的基分类器，然后依据基分类器在ｂｗ上的分类误差对其赋予权重，以衡量每个基分类器在分类时做出的贡献。这样使得基分类器能够反映数据的变化，从而保证集成分类器是依据数据分布而不是数据到达的时间来决定历史数据对当前模型的影响程度。
假设在整个滑动窗口ＳＷ上训练得到的单个分类器为Ｇｒ，而在各个基本窗
口训练得到集成分类器为Ｅ矗则有下面的性质：
性质１：若采用基于Ｇ在测试数据集上的期望分类误差加权的方法对Ｅ中各分类器Ｇ进行加权，则Ｅｒｒｏｒ（Ｅｇ）《Ｅｒｒｏｒ（Ｇｇ）。
其中Ｅｒｒｏｒ（．）表示分类误差率，其证明见文献【１８】。
为反映集成分类器中每个基分类器分类测试数据集的贡献大小，我们需要为每个分类器赋予权重。本文采用基于分类误差的加权方法，下面具体介绍加权的
方法。
当滑动窗口ＳＷ数据到达时，ｂｗｉ对应的数据块标记为研，基分类器为Ｃｔ，１
≤ｉ≤Ｋ。
根据性质１，给定测试样本集ｒ，我们依据每个分类器Ｇ在ｒ上的分类误差

第刖章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ
郑州大学硕士学位论文
来为其赋予权重忻。假定ＢＫ的类分布最接近于当前测试数据集，因此，可以通过计算ｃｆ在曰ｋ上的分类误差来获得晰。
特别地，假设鲰－包含形如似ｃ）的样本，其中ｃ是真实类标号，则Ｇ对Ｇ，
ｃ）的分类误差为１一ＣＯ），其中∥＠）是由ｃｆ决定的工属于类Ｃ的概率。因此，
Ｇ的均方差（Ｍｅａｎ
Ｓｑｕａｒｅ
Ｅｒｒｏｒ）为：
（１）
ＭＳＥ，一“轰（１一∥ｏ））２
分类器在作随机性预测时的均方差为：ＭＳＥｒ一罗ｐ（ｃｘｌ一ｐ（ｃ））２，即样本ｘ７
被分类为Ｃ的概率等于Ｃ的类分布。例如，对于ＣＥ｛０，１｝，类分布是均匀分布，则ＭＳＥｒ＝Ｏ．２５。因为随机模型不包含数据的有价值知识，所以我们以ＭＳＥ，作为对分类器加权时的阈值，即丢弃分类器的误差率大于ＭＳＥ，的分类器。为简化计算，使用公式（２）计算权重Ｗｉ。
Ｗｉ＝ＭＳＥｒ－－ＭＳＥ，
（２）
４．２．４集成分类器的产生与更新
ＣＥＥＰ算法解决了采用什么算法构造基分类器的问题，但是如何产生一系列的ＣＥＥＰ分类器；以及如何更新多分类器以适应数据流的概念漂移，成为实现
ＣＥＥＰＣＥ算法亟待解决的重要问题。
我们利用数据流基本窗口概念，考虑到数据流的时间性、流动性，将每一个基本窗口ｂｗｉ作为研究的对象，以基本窗口为单位构造基分类器ｃｉ：同时，我们引入滑动窗口的概念，通过移动窗口来更新多分类器Ｅ。
１．集成分类器Ｅ的产生
前面已经讨论将基本窗口作为训练基分类器的基本单元，ｂｗｉ是一个基本窗
口，对应一个数据流子序列％勃…，ｅｉ。对于基本窗口序列６帆…，ｂｗｂ…，ｂｗｋ，
在不考虑滑动窗口的前提下，我们按照各个基本窗口到达的时间先后顺序对不同的基本窗口应用ＣＥＥＰ算法，构建不同的基分类器，从而形成一个基分类器序列
ＣＩ…，Ｇ…，Ｑ，这样的一个序列就构成了一个集成分类器Ｅ，即￡＝他…，ｃｂ…，ＣＯ。
具体的流程如下图所示：
３１

第四章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑州大学硕ｔ学位论文
图１集成分类器Ｅ的产生
ＣＥＥＰＣＥ综合了基于ｅＥＰ的分类器及集成方法的特性，它以ＣＥＥＰ分类算法作为基分类器，在滑动窗口ＳＷ内ｉＪｌｌ练Ｋ个基分类器的集合Ｅ，当滑动到第髟ｆＪ个基本窗口时，训练基分类器ｃｋｊ，并计算每个基分类器ａ的分类误差率，然后依据４．２．３节提出的加权方法加权并选出权重最高的Ｋ个基分类器作为输出。集成分类器Ｅ的产生算法如下：算法１：
ＣＥＥＰＣＥ（Ｋ，Ｄ，Ｅ，Ｓｕｐ，ＧＲ）
输入：
Ｋ：基分类器总数；
Ｄ：基本窗口ｂｗｇ＋１包含的数据；Ｅ：调整权重之前Ｋ个基分类器集合；Ｓｕｐ：支持度，ＧＲ：增长率；输出：
ＥＬ）｛Ｑ＋１）中权重最高的前Ｋ个基分类器
方法：
（１）初始化ＫＳｕｐ，ＧＲ；
（２）ｗｈｉｌｅ（ｂｗｒ＋１数据到达）｛
３２

第ｐｑ章基于ｃＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑州大学硕ｔ学位论文
（３）（４）（５）
ＣＥＥＰ（Ｏ，Ｓｕｐ，ＧＲ）；／／讨，１练基分类器ＣＫ＋Ｉ计算ＣＫ＋ｌ在Ｄ上的误差率（１０一折交叉验证）；计算Ｃｘ＋ｘ对应的权重ｗｉ＋１．／／公式（１Ｘ２）
（６）ｆｏｒ（Ｃ，ＥＥ）｛Ｃ７）（８）（９）（１０）’
当新窗口数据到来时，对每个基分类器作调整的目的是为了增强分类器学习的能力，充分的反映当前数据分布，然后集成所有分类器来做预测。
其中，第３步在新来数据上训练单个分类器；而第５步是依据分类器在测试集上的分类误差计算出分类器对应的权重。我们首先在滑动窗口内调用函数ＣＥＥＰＣＥ（）训练多个分类器，然后使用集成分类器Ｅ来对未来测试样本进行分类。
２．集成分类器的更新
上面集成分类器Ｅ的产生是在不考虑滑动窗口大小的情况下，在实际的应用中，数据流的数据量是极大的，基本窗口的数量也是巨大的，对所有的基本窗口实行ＣＥＥＰ算法，构造每一个基分类器并将它们全部纳入集成分类器Ｅ中是极不现实的。这样就必须限定集成分类器Ｅ的大小，即Ｅ所包含的基分类器ＣＢ的个
数。我们将滑动窗口的大小定义为集成分类器Ｅ的大小，这样对集成分类器的更新就等价于滑动窗口的移动。在这里，我们采用的是固定滑动窗口大小的滑动窗
Ｇ一加加（ＧＤ）；／／增量调整Ｇ
计算Ｇ在Ｄ上的ＭＳＥｉ；／／公式（１）计算Ｇ对应权重Ｍ；｝／／公式（２）
口。接下来，我们所说的滑动窗口的更新即代表集成分类器的更新。
假定滑动窗口的大小为Ｍ＝６，则在滑动窗口更新时有下面两种情况：（１）现有基分类器个数＜６，这时只需要将建立新的一个基分类器ＣＢ。加入到
滑动窗口。
（２）现有基分类器个数＞：６，这时需要移动滑动窗口来实现对现在的滑动窗口进行更新。在按照最早到移出的策略，现有的集成分类器Ｅ中，最先建立的一个基分类器ｃＢ。，将被移出；然后将新建立的基分类器ｃＢｊ添加到集成分类器Ｅ
中。

第四章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ
郑州丈学硕士学位论文
下面我们将用图例来说明滑动窗口第二种更新的情况。
图２集成分类器更新
４．２．５分类器集成
前面介绍的基分类器的构造和集成分类器的产生和更新都是ＣＥＥＰＣＥ算法的第一个步骤分类器的构造，接下来介绍的是该算法的另一个过程：如何对未知的测试数据进行分类。对测试数据需要考虑如下问题：（１）单个ｅＥＰ对确定类成员关系的贡献；（２）如何聚集每个ｅＥＰ的贡献，从而确定基分类器在未知样本判定中的贡献：（３）如何聚集每个基分类器在确定未知样本的时的贡献。
１．使用ｅＥＰ分类
为确定待分类样本Ｓ所属的类，Ｃｉ类的每个ｅＥＰ都试图确定Ｓ是否属于Ｃｉ类。设Ｄｉ是Ｇ类训练样本的集合，Ｄｉ’是非Ｃｉ类训练样本的集合，ｘ是Ｃｉ类的ｅＥＰ。如果ｘ不在Ｓ中出现，则ｘ不能为确定ｓ是否属于Ｃｉ类做出判断。如果ｘ在Ｓ中出现，由于ｘ在Ｃ【类出现的频率（支持度）是在非Ｃｉ类出现的频率的
ＯＲ（Ｘ，Ｄｉ’，Ｄｉ）倍，因此Ｘ将以几率啬湍判定Ｓ属于Ｃｉ类，而以几率时，我们令蠹踹暑１，面瓦￡丽＝０。
面矗忑两判定Ｓ不属于Ｃｉ类。如果Ｘ是ｃｉ类的ＪＥＰ，则ＧＲ（Ｘ，Ｄｉ’，Ｄｉ）＝８。此
同时非Ｃｉ类的ｅＥＰ对于确定Ｓ是否属于Ｇ类也有贡献。令Ｙ是非Ｃｉ类的

第朗章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑州丈学硕Ｊ：学位论文
ｅＥＰ，它在Ｓ中出现。如果Ｙ的增长率很大，Ｙ对确定Ｓ属于Ｇ类的影响可以
忽略。然而，当Ｙ的增长率不太大（如，ＧＲ（Ｙ，Ｄｉ，Ｄｉ’）‘５）时，Ｙ对确定Ｓ属于
Ｇ类的影响相当大。一般地，我们取Ｙ确定Ｓ属于Ｇ类的几率为面面拓丽。
２．基分类器分类
为了对样本Ｓ进行分类，需要组合Ｇ类和非Ｇ类的每个ｅＥＰ的贡献，计算
ｓ属于ｃｆ类的得分ｓｃｏｒｅ（Ｓ，ｃＤ。对于ｉ＿１，２，．．．，Ｋ，令ＰＳ（Ｓ，ｃ．）＝｛ｘｌｘ是Ｄｉ的
ｅＥＰ，并且ｘ在Ｓ中出现），ＮＳ（Ｓ，ｃｆ）＝｛ｘＩｘ是Ｄｉ’的ｅＥＰ，并且ｘ在Ｓ中出现）。Ｓ属于ｃｆ类的得分ｓｃｏｒｅ（Ｓ，ｃｆ）用下式计算：
ｓｃｏｒｅ（Ｓ，卵二局，而ｏｓ（ｘ，Ｄ丽。，ＤＤ＋茹矧丽赢
分类算法将使用如下规则对Ｓ进行分类：将Ｓ划归得分最高的类。如果得分最高的类不唯一，则将Ｓ划归得分最高的多数类。
该规则有两点好的考虑：一、在计算Ｇ类的得分时不仅考虑Ｇ类ｅＥＰ的贡献，而且考虑非Ｇ类ｅＥＰ的贡献。当非Ｇ类ｅＥＰ的增长率很高时（例如，大于２０），非Ｇ类ｅＥＰ影响可以忽略。然而，当非Ｇ类ｅＥＰ的增长率不是很高时（例如，小于１０），这种影响并不能忽略。二、在组合每个ＥＰ的贡献时，对每个ｘ取相同的权值１。这是因为，事实上ｘ在ａ类的支持度反映的是ｘ可以对多大
比例的样本分类起作用。当Ｘ１和Ｘ２都是ＥＰ，并在给定的待分类样本Ｓ中出现时，Ｘｌ和Ｘ２对确定Ｓ所属类的贡献的权重应当是一样的：即，它们的贡献仅由它们的区分能力（增长率）确定。
考虑下面的例子：
例１：假定训练数据集包含２０００个样本，两个类的大小一样。ｏ类和Ｃ２类各有１０００个样本。ｅＥＰｌ覆盖了９００个ａ类样本，４５０个ｃ２类样本。ｅＥＰ２覆盖了１个ｃｊ类样本，３００个ｃ２类样本。显然，ｅＥＰｌ是一个。类的ＥＰ，它的增长率是２。ｅＥＰ２是一个ｃ２类的ＥＰ，增长率是３００。
考虑样本Ｓ，它仅包含两个ｅＥＰ，ｅＥＰｌ和ｅＥＰ２。因为ａ类和ｃ２类中都存在一定数量的包含ｅＥＰｌ的实例样本，所以依据ｅＥＰｌ我们不能断定Ｓ属于哪一个类。然而。类中几乎不存在包含ｅＥＰ２的样本，而ｃ２类中有大量的样本包含
ｅＥＰ２，所以几乎可以断定Ｓ不属于ａ类。综合考虑ｅＥＰｌ和ｅＥＰ２，Ｓ显然应该属于ｃ２类。

第阴章基于ｃＥＰ的数据流挖掘算法ＣＥＥＰＣＥ
郑州人学硕．ｉ：学位论文
基分类器失效：对于未知样本Ｓ，如果基分类器ＣＢｉ没有足够的ｅＥＰ用来
指导分类，那么我们就称ＣＢｒ没有覆盖样本Ｓ，或者说对于未知样本Ｓ，基分类器ＣＢ，失效。
根据上述定义可知，基分类器ＣＢｉ失效意味着没有足够的知识进行预测。当分类器失效的情况下，只能通过只能依据不同类的元组个数采用接近随机猜测的多数表决方式做出判断，因此预测的可信度很低。所以，如果对于未知样本Ｓ，如果基分类器Ｃ研失效，那么它将放弃投票，把决定未知样本Ｓ的权利交给具备足够区分能力的基分类器。我们也可以认为：如果基分类器失效，那么它投票的权值为０。
３．集成分类器的投票方式
．通过上面使用ｅＥＰ分类、基分类器分类的讨论我们已经获得了一个具有Ｎ个基分类器成员的“董事会”，下一个需要解决的问题是这个董事会的组织方式，即：如何组织每一个基分类器的预测结果，从而形成最终的预测。
有权重的投票方式是组合多个分类器预测结果常用的一种有效方法，例如Ｂｏｏｓｔｉｎｇ方法在分类问题中就是采用的这种方式：在ＡｄａＢｏｏｓｔ．Ｍ１算法中，通过对训练数据集的九轮学习，得到一个预测函数（分类器）的序列ｈｌ，ｈ２，．．．，ｈ。同时还有一个与之对应的权重的序列，分类器Ｉ，ｉ对应权重记作”，则这个权重的序列可表示为Ｗ６Ｗ２，…，Ｍ。那么最终输出分类器，记作ｃ・‘砷，可表示为：
ｃ‘仁）－Ｓ劬【∑２。％ＪＩｌｊ僻）】
分类器的组合方式和获得基分类器序列的过程紧密相关。ＡｄａＢｏｏｓｔ．Ｍ１的基分类器之间是有序，它们是通过不断修改训练集实例的权重方式获得的，所以给
它们赋予不同的权重。
结合数据流的时间性、有序性，从我们的集成分类器Ｅ中每个基分类器ＣＢ；的构造方式可知，ＣＢＩ，…，ＣＢｉ是按照时间顺序先后间联系的。并且这些分类器由不同的基本窗口的数据产生，因此我们应该给不同的基分类器设定不同的权值。
这样的话，我们可以采用一种方式来评估每一个基分类器优劣从而为每一个基分类器给定相应的权重，例如：我们可以依据训练误差评估基分类器的优劣。但是模型的评估本身就是很困难的，一般情况下训练误差越小的分类器，测试误

第四章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑州大学硕十学位论文
差也越小，但是在出现过分适应训练集的情况下，训练误差越小的分类器测试误差反而越大。因此，要为每一个分类器赋予合理的权重本身就是一件很困难的事
情。
再如，我们采用了复杂的策略评估分类器的权值，则需要多次扫描训练数据，这样势必会影响算法的处理速度，再则也不符合数据流挖掘分析时实时处理，实时响应、线性扫描的要求。
因此根据数据流挖掘最关心的是最近数据的处理情况，我们对集成分类器中的基分类器按照构造的时间顺序为每个基分类器赋一个固定的权值，例如：在实验过程中，我们为最新的基分类器赋权值ｗｌ＝１，而其他的基分类器按照０．９的幂递减，第二个新的基分类器的权值Ｗ２为（ｏ．９）２，依次类推第ｋ个基分类器的权值为ｗｋ＝（０．９）ｋ这样即使所有的基分类器有一定的区分性，但又不过多地浪费时间。但对于失效的分类器，它投票的权值为０。实验表明，这样的权值设置基本取得
了意想的效果。
’
对于给定的训练数据集Ｄｒｒａ加，它包含Ｃｌ，Ｃ２…．，ＣＫ个类，集成分类器Ｅ有
Ｋ个基分类器，所有基分类器构成的集合，记作ｃｓ（ｃＢ）。为了对未知样本Ｓ分类，我们需要计算ｓ在Ｃｉ类上获得的选票Ｖｏｔｅ（Ｓ，ｃ０，并根据不同基分类器的权值进行整合。令ｖＢｃ（ｓ）是对样本Ｓ具有投票资格的基分类器的集合，则
ＶＢＣ（Ｓ）＝｛ＣＢＩＣＢ属于ＣＳ（ＣＢ），并且ＣＢ覆盖了样本ｓ｝。因为对于样本ｓ失效的
基分类器不能参与投票，所以ｖＢｃ（ｓ）是预测未知样本Ｓ的过程中真正起作用的基分类器的集合。Ｖｏｔｅ（Ｓ，ｃｉ）就是ＶＢＣ（Ｓ）中预测Ｓ为Ｃｉ类的基分类器与其对赢得权值的乘积的代数和，Ｖｏｔｅ（Ｓ，Ｃａ）可以通过如下的表决过程来计算。
对于任意一个未知样本Ｓ，分类过程描述如下：
首先依据权重递减顺序排列基分类器，然后当分类新样本ｓ时，先使用权值最高的分类器进行分类，依次类推。我们采用一种机制，若当前分类器的误差率低于某一阈值口而能够较准确的判定ｓ的类标号时，不再使用后续的分类器，直接返回分类结果；若分类器使用完毕同样中止分类过程。使用所有的分类器进行分类时，采用加权多数【９ｌ的思想输出基分类器对样本的分类结果。算法如下：
参数及其含义：Ｇ：代表基分类器：

第四章基于ｃＥＰ的数据流挖掘算法ＣＥＥＰＣＥ
郑州丈学硕Ｌ学位论文
Ｇ例：返回样本Ｓ的类标号；
类ｃ』，Ｃ２，…，Ｃｍ映射到整数１，２，…，川；ｑ【小表示ｓ属于Ｃｉ类的加权和；
Ｃｌａｓｓｉｆｙ（ｓ，Ｅ）∥用集成分类器Ｅ分类数据样本Ｓ输入：
｛ＧＭ＇：表示分类器Ｇ及其对应的权重ｍ；
ｓ：数据样本；
Ｅ：Ｋ个基分类器集合；输出：
ｍａｘ研１．Ｊ，ｌ】）所对应的类标号
方法：
（１）初始化ｑ［１．Ｊ，ｌ】为０；（２）∞ｎ（｛Ｇ，¨々））；（３）ｆｏｒ（Ｇ∈Ｄ（４）
／／使得Ｍ，ｔｉ＞－－－－１４，ｊ，ｆ可；玎∈１１闻
ｉｆ（ＭＳＥ≤口）ｒｇｔｕｎｌｃｆ（ｓ）；
（５）ｆｏｒ（ｃｆ∈Ｄ（６）
ｉｆ
ｃｆ（ｓ）＝Ｖ，ｔｈｅｎｑｐ】＋＝ｗｉ；／／ＶＥ【１，ｎ】
引入参数目，主要因为数据流量的急剧增加，若始终训练固定个数的分类器来做预测，代价相当高，所以，当若干个（＜＝Ｋ）基分类器能够以高准确率预测时，便不考虑低准确率的基分类器。但是处理周期性概念漂移１２１时，会影响准确率。为解决周期性漂移的情况，可以考虑增加滑动窗口的大小。下一章实验中，口选取ｈ［ｏ．１５５，０．１７］效果较好。
至此，集成分类器分类算法中多个基分类器之间的分类过程就类似一个具有不同股权的股东投票的过程。我们将这个投票成为“董事会股权投票”策略，每一个基分类器都作为一个股东每个股东都有一张不同股权的选票，而每一个类ｃｉ是一个候选项目。在这个董事会中所有的股东按照自己股权的多少排序，他们都有一张不同权额的选票，每一个股东可以依据自己获得的知识选择把自己选票投向自己支持的候选项目。如果某一个成员不能决定哪一位候选项目更应该合
适，则它就不放弃投票。而最终未知元组被划归获得股权最多的类标号。如果获

第四章基于ｅＥＰ的数据流挖掘算法ＣＥＥＰＣＥ郑州大学硕Ｉ：学位论文
得股权最多的类不唯一，那么我们将把样本Ｓ划归获得的股东支持最多即选票张数的最多的类。
４．３小结
本章我们提出并实现了基于ｅＥＰ的数据流分类算法ＣＥＥＰＣＥ。我们分为四个部分详细讨论了ＣＥＥＰＣＥ的实现。首先，我们介绍了算法的基本思想：以ｅＥＰ作为分类因子，使用ＣＥＥＰ分类算法构造基分类器的，进而构造多个分类器，并采用滑动窗口技术来更新集成分类器；其次，我们介绍了基分类器的构造算法ＣＥＥＰ是如何进行ｅＥＰ挖掘、ｅＥＰ加权，进而构造成基分类器；接下来，根据数据流数据的时间性、顺序性和概念漂移的特性，我们介绍了基于基本窗口和滑动窗口技术的集成分类器产生和集成分类器更新；最后，我们介绍了集成分类器Ｅ采用固定权重，按照“加权多数”的策略来确定未知样本Ｓ的类标号。从而，我们得到了一个完成的基于ｅＥＰ的数据流分类算法，在下一章中，我们将通过实验数据说明算法的可行性。

第五章相关实验结果及分析郑州大学硕上学位论文
第五章相关实验结果及分析
为了验证ＣＥＥＰＣＥ算法的分类准确性，我们使用了２００３年Ｗａｎｇ［１８】等人在提出集成分类器的方法中所使用的数据生成器，产生数据流数据。
实验环境为ＰｅｎｔｉｕｍＩＶ，主频１．８ＧＨｚ，内存为２５６ＭＢ，操作系统为Ｗｉｎｄｏｗｓ２０００，算法实现工具为ＭｉｃｒｏｓｏｆｔＶｉｓｕａｌ
Ｃ＋＋。
在这一章，我们首先给出了实验数据生成器的基本原理，然后比较了算法ＣＥＥＰＣＥ、ＧＫ和ＥＣ４．５在不同条件下的准确性，其中ＧＫ代表在大小为Ｋ的滑动窗口上训练得到的单分类器ＣＥＥＰ，ＥＣ４．５是以Ｃ４．５为基分类器的集成分类器。
５．１实验数据
数据流人造数据是通过旋转超平面来模拟不断变化的概念。在办维空间上超
平面是满足下面条件的点ｘ的集合。
善心薯。ｗ０
（。）
其中嚣是点ｘ的第‘个坐标。荟％’％的样本被标记为正样本，而荟嵋毛‘‰的样本被标记为负样本。在模拟时变概念时，我们通过调整相应的
权重来平稳地改变超平面的方位，因此超平面非常重要。
特别地，依据权重的大小进行排序能够表明哪些维（属性）包含最多的信息；极端情况是，除了一个维（属性）的权重外，与其他所有维（属性）相关联的权重均为０时，则具有非０权重的维（属性）包含概念的所有信息。这就允许我们控制属性的相关信息内容，从而通过简单地改变相应的权重即可反映超平面方位
的变化。
产生均匀分布于多维空间『ｏ，ｉｆ上的随机样本。等式（・）中的权重Ⅵ（１ｉ＝ｄ）
初始化为区间【Ｏ，１】上的随机数。我们选择¨，。的值，使之满足超平面将多维空问

第五章相关实验结果及分析郑州大学硕Ｉ：学位论文
分割成相等的两部分，ａＰ
ｗｏ一号∑Ｍｔ，因此，大致上正负样本各占５０％。通过
随机改变ｐ％的样本类标号来引入噪声数据。实验中噪声级别为５％。
实验中，通过设定一系列的参数来模拟概念漂移。参数ｋ表示权重发生改变的总的维数且；参数ｔＥＲ表示权重ｗ１，ｗ２，…，帆的改变量（每隔Ⅳ个样本）；研∈｛－ｉ，１｝表示每个权重ｗ／方位改变量，其中ｊｉ每。权重是不断改变的，例如，每产生一个样本权重Ｈ々改变毋勺／Ⅳ。此外，有１０％的概率使得每隔Ⅳ个样本超平面的方向翻转，即毋被啦取代的概率为１０％。每次权重改变时，我们计算
Ｊ
ｗｏ一｛∑咝薯使之不打乱类的分布。
５．２性能分析
在下面这一部分中，我们主要将算法ＣＥＥＰＣＥ、ＧＫ和ＥＣＡ．．５在不同条件下进行了准确性的比较。主要从四个角度进行准确率的比较：１１随基本窗口大小的变化，准确率变化的情况；２１随滑动窗口大小的变化，准确率变化的情况；３）随发生漂移维数多少的变化，准确率变化的情况；４）随数据流维数多少的变
化，准确率变化的情况。
实验１测试了分类准确率随基本窗口大小（ＥＰＩＢ卅）的变化情况，训练集大
小为１００００，测试集大小为１０００，共１０维，每一维不同取值个数为４，有２维发生漂移，每隔１０００个样本权重发生改变。图３显示基本窗口为［２５０。１５００１时，不同滑动窗口下算法的平均分类准确率。
巨三垂三亟至卫
—－少
—，一
７∞薹皇宵口太小
ｌ∞Ｏ
亭
薯量
－一，／／
、１
＼・ｌ
１５∞
眦盯刚％舭昭¨酗盱刚跎
２∞
——一ｒ
ｓ００
图３不同基本窗口下的准确率比较
４１

第五章相关实验结果及分析
郑州人学硕１：学位论文
从图３可以看出，ＣＥＥＰＣＥ比对应的单分类器ＧＫ更有效，在陋卅４２５０，３时，ＣＥＥＰＣＥ的准确率高于ＥＣ４．５，在２５０＊３４陋卅４２５０・６时，与ＥＣ４．５相媲
美，并且在［２５０＊４，２５０＂６］上，ＣＥＥＰＣＥ准确率下降幅度没有ＥＣ４．５明显，因为在计算每个基分类器的权重之前，我们增量更新了每个模型，能够更好地适应概念漂移。
基本窗口较小时，各算法具有较好的分类性能。因为窗口较小时，其中包含的概念漂移较少，数据的分布较为稳定；若是太小也会降低准确率，因为没有足够的数据用于训练基分类器。而窗口较大时，难以检测到窗口内发生的漂移，也会影响其性能。当窗口较小时，我们通过降低支持度来提升基分类器性能。
实验２测试了分类准确率随滑动窗口大小的变化情况，数据集的参数同实验１。图４显示了滑动窗口分别为２，４，６，８时不同基本窗口下的平均准确率。
巨五亘三互正卫
∥
∞
盯
乒乡芦一。乡一／——一－∥／一
Ｚ
ｑ
●
■
曙
雹＊《謦
甜
ｎ
情动霄０，（小
图４不同滑动窗口下的准确率比较
图４表明，随滑动窗口的增大，ＣＥＥＰＣＥ和ＥＣ４．５准确率不断提高，并且比
ＧＫ有更好的性能，因为ＧＫ不能很好的适应概念漂移。由于集成分类器中基分类器数目的增加，增强了分类器的多样性和差异性，所以不同程度的影响了分类性能。随滑动窗口增加，开始时ＣＥＥＰＣＥ和ＥＣ４．５性能提升很快，以后增幅逐步减小，因为能够较好的检测漂移时，基分类器数目的增加对分类性能的影响将很
微弱。Ｎｓ别＜８时，ＣＥＥＰＣＥ略优于ＥＣ４．５，因为前者对应的单分类器性能优于
Ｃ４．５，Ｋ＞８时，两者性能接近。
实验３测试了发生漂移的维数对准确率的影响。数据集大小为１００００，测试集大小为１０００，共１０维，每一维不同取值个数为４，分别有２，４，６，８维发生漂移。结果如图５所示。可以看出，随着漂移的增加，各算法准确率急剧下降，
以后趋于平稳，而ＧＫ受影响最大，因为没有引入处理漂移的机制。变化维数在

第五章相关实验结果及分析郑州大学硕Ｌ学位论文
【２，４】时，ＣＥＥＰＣＥ与ＥＣＡ．５性能差异很小，而变化维数在【４，８】时，后者准确率下降较为明显，因为面对新流入的数据，没有增量调整决策树。而ＣＥＥＰＣＥ始终保持最具区分力的ｅＥＰ，并不断对获得的ＥＰ进行调整，反映数据的特征。
巨三亟亘互三囝
＼曳＼
Ｉ、’吣
＼瓦专＞。
雹■‘量
＇～＼，二＼、。＼＼、＿
＼
．
∞为∞巧ｍ舒∞巧∞
２
．
．、、
。
ｄ童亿的睦ｔ‘
图５变化的维数目大小对准确率的影响
实验４测试了总的维数目对准确率的影响。数据集大小为１００００，测试集大
小为１０００，各个维不同取值个数为４，扭卅＝２５０，Ｋ＝６。实验结果如图６所示。
巨亘垂亘亟三团
。、专ｏ、？Ｉ
、Ｐ—————¨
ｏｌ一■ｇ謦
啦∞孵坼明钷∞讨
８
加
６总一缝ｔ
图６总的维数目大小对准确率的影响
根据图中曲线的走向，可以看出：随着数据集维数的增加，准确率呈下降趋势。这是因为维数的增加使得ｅＥＰ数量增多，而其支持度和增长率普遍降低，从而降低ｅＥＰ的区分能力，使得分类能力下降，所以ＣＥＥＰＣＥ的准确率下降。ＥＣ４．５随着维数增加，分类规则增多，决策树得不到的规则也会增多，同样造成准确率
下降。当ＣＥＥＰＣＥ的准确率下降时，我们可以通过降低支持度阈值进行调整。
５．３小结
数据流分类算法ＣＥＥＰＣＥ使用ｅＥＰ建立Ｋ个基分类器，依据在新来数据块上的分类误差进行加权，然后选取权重最高的前Ｋ个基分类器来对测试样本进

第五章相关实验结果及分析郑州大学硕ｔ学位论文
行分类。本章我们对ＣＥＥＰＣＥ算法与ＥＣ４．５算法在以下四种情况下的准确率进行了比较：随着基本窗口大小的变化，准确率变化的情况；随滑动窗口大小的变化，准确率变化的情况；随着发生漂移维数多少的变化，准确率变化的情况；随数据流维数多少的变化，准确率变化的情况。实验表明，ＣＥＥＰＣＥ具有很好的分类准确率，足以与以Ｃ４．５为基分类器的集成算法相媲美，并且对概念漂移的适
应性更好。

结柬语郑州大学硕‘ｋ学位论文
结束语
随着近些年信息技术的快速发展和信息搜集能力的日益提高，在日益增多的信息处理应用中，信息呈现形式较多的不是静态方式，而是动态连续“流”的形式。近些年数据流研究领域的工作热火朝天，如何从海量的数据中训练模型来有效地预测未来的数据趋势成为一个热点。由于传统的数据分类算法无法直接应用到数据流环境中，这为我们的研究提供了一个好的机遇。我们创新性地提出将ｅＥＰ分类算法思想引入到数据流分类领域。
首先，我们认真地总结数据流的特征，详细地学习并分析了现有的数据流分类算法的实现思想，熟悉了概念漂移的概念和滑动窗口技术；其次，我们又带着数据流分析算法需要的要求认真分析传统分类算法的基本思想，并通过收集的实验数据比较各个算法在ＵＣＩ１２个数据集上的准确率，最终选择基于ｅＥＰ的分类算法ＣＥＥＰ作为基分类器的构造算法；接下来，我们将基本窗口和滑动窗口的概念和ＣＥＥＰ算法相结合，提出并实现了基于ｅＥＰ的数据流分类算法ＣＥＥＰＣＥ。最后，我们通过在四个方面与已有的基于集成分类器的ＥＣ４．５算法进行比较，结果表明，ＣＥＥＰＣＥ能够较好的适应数据流的概念漂移，具有较好的分类准确率，足以与以Ｃ４．５为基分类器的集成算法相媲美。
虽然，完成了ＣＥＥＰＣＥ算法设计与实现，并通过实验验证，取得了一定的成功，但是由于实验数据来自于生成器模拟的人造数据流，模仿数据流的特性还不太完善，无法很客观地说明算法的优劣性；同时由于当前应用来数据流生成器进行数据流分类算法研究的还不太多，可比性差；最后，通过实验数据可以看出算法在滑动窗口的更新策略还有待进一步的研究和提高。由于基分类器可以同时训练，所以将程序并行化将能够进一步改善算法的性能，并应用于Ｗｅｂ数据挖
掘等具体领域。

致谢郑州丈学硕士学位论文
致谢
在此论文完成之际，首先对我的导师范明教授表示衷心的感谢和深深的敬意。本文在确定论文的选题、方向以及课题的研究、论文的写作过程中遇到了较大的困难，在范老师的不断鼓励和大力帮助下才得以完成。感谢范老师把我带入了数据挖掘这个充满挑战而又富有意义的研究领域。在研究工作中，范老师严谨的治学态度、渊博的学术知识使我受益匪浅、受用终生；在学习和生活中，范老师给了我无微不至的关怀和帮助。在我的三年研究生学业即将完成之际谨向范老师表示衷心的感谢和诚挚的敬意，衷心祝愿范老师身体健康、工作顺利。
叶阳东教授在学习和生活中，给了我热心的帮助，在研究方法上也给了我很多启发和指导，在此表示衷心的感谢，并向叶老师致以美好的祝愿。
感谢我本科以及研究生期间的老师苏锦祥教授、周清雷教授、王相林教授、以及柴玉梅、邱保志、周文俊、昝红英、赵东明、石磊、穆玲玲、钱晓捷、李向丽、关国利等老师，他们传道、授业、解惑，把我带到了广阔的计算机科学与技术领域。感谢我本科期间的辅导员刘广志老师。感谢郭淑艳和高明磊老师。
感谢实验室蒋宏杰师兄、贾玉祥师兄、许红涛师兄和温箐笛学姐，在课题研究期间和他们一起探讨、学习的日子是我学习生涯中的重要经历。向实验室朱真峰、李妍琰、刘东、邓见广、施鸿喜、李睿楠、王春凯、任红伟、孙丽娜、夏春、张培赞、李艳等同学表示感谢，和他们一起学习使我受益匪浅，感谢各位同学对
我的帮助。
感谢我的父亲和母亲，他们无私的爱和辛勤的汗水伴随着我成长的每一个脚印。感谢我的女友杜煜宇，在我学习和生活中遇到困难时，她给了我无限的支持和理解，给了我前进的动力。
由于时间和作者水平有限，论文中不足之处，恳请审阅本论文的专家和老师
以及阅读本论文的同学批评指正，本人将感激不尽。
向参加论文评审和答辩的专家、老师表示感谢。
作者陈崇超
２００７年５月３０日于郑州

基于EP的数据流分类算法研究

推荐内容

相关推荐