（计算机应用技术专业论文）基于数据流的分类算法研究.pdf

基于数据流的分类算法研究 摘要 摘要 通信、计算机和网络技术的飞速发展将人类带入信息社会，大量的数据可以用来 衡量人们生活的方方面面。这些数据在给人们带来方便的同时也使人类陷入数据的海 洋中。数据挖掘就是人们用来从大量的随机应用数据中，提取隐含的信息和知识的技 术。近年来出现了许多新型应用，传统的数据挖掘技术无法很好的处理这些应用数据， l l - , 女n 传感器网络、互联网点击流、金融数据和在线监控事务日志等，这种新型数据形 式称为数据流。如何在有限存储空间下，对这些数据流进行快速处理，为数据挖掘的 应用和研究带来了新的机遇和挑战。 为应对这些挑战，本文提出了一种新的分类算法e v f d t ，并将此算法运用到一个 多分类器系统框架下，最后通过实验验证了e v f d t 算法的效率和准确率，以及多分类 器系统对概念漂移的数据流的良好性能。本文的主要工作如下所示： ( 1 ) 在v f d t 算法基础上提出了e v f d t 算法，该算法引入一种非均匀间隔剪枝的方 法处理连续属性，将算法扩展到包含连续属性的数据流挖掘领域，并具有较高效率。 ( 2 ) 使用朴素贝叶斯处理决策树的叶节点和内部节点，缩小了训练需要的样本空 间，提高了决策树的训练效率。 ( 3 ) 提出一个综合分类框架，并将e v f d t 算法和其它一些经典的算法构成一个系 综分类器，并提出一个检测概念漂移的方法，以分类概念漂移的数据流。 ( 4 ) 根据局部性原理提出基于准确率的赋权方法，以及使用基于权值的剪枝方法 最系综中的分类器剪枝，使系综方法的准确率和时间效率得以提高。 ( 5 ) 通过实验验证了e v f d t 算法和集成了该算法的系综分类器的效果。实验结果 显示，新算法较同类算法在时间效率和存储空间上都有一定的优势，集成了新算法的 系综分类器对挖掘概念漂移的数据流具有良好的性能。 关键词：数据挖掘，数据流，分类，决策树，朴素贝叶斯，非均匀间隔剪枝 作者：李飞雄 指导老师：刘全( 教授) t h er e s e a r c ho nc l a s s i f i c a t i o na l g o r i t h m so v e rd a t as t r e a m a b s t r a c t t h eh i g h s p e e dp r o g r e s so fc o m m u n i c a t i o n s ，c o m p u t e r sa n dn e t w o r k st a k et h ep e o p l e i n t ot h ei n f o r m a t i o ns o c i e t y t h es c a l eo ft h ed a t ai si n f l a t i n gs oq u i c k l y t h e yt a k et h e c o n v e n i e n c ei n t ot h el i f e ，a n dm a k ep e o p l ef u z z y d a t am i n i n gi st h en e wt e c h n i q u et oh e l p p e o p l eg e tt h ed e s t i n a t i o n i ti st oe x t r a c tu s e f u li n f o r m a t i o nf r o mm a s s i v ev o l u m e so fd a t a r e c e n t l yan e wd a t ap r o c e s s i n gm o d e l ，k n o w na sd a t as t r e a m ，h a sa r i s e n e x a m p l e a p p l i c a t i o n si n c l u d ef i n a n c i a lt i c k e r s ，n e t w o r kt r a f f i cm o n i t o r i n g ，w e ba n dt r a n s a c t i o nl o g a n a l y s i s ，a n ds e n s o rn e t w o r k s t h i sp a p e re x p l o i t san e wc l a s s i f i c a t i o nm e t h o dc a l l e de v f d t , a n da ne n s e m b l e c l a s s i f i e r ss y s t e m w ed e s i g n e ds o m ee x p e r i m e n tt ov a l i d a t e t h e p r e c i s i o n a n d t i m e - e f f i c i e n c yo fe v f d t a n de n s e m b l ec l a s s i f i e r s t h em a i nw o r ki sl i s t e da sf o l l o w s ： i w ee x p l o i tam e t h o dc a l l e du n e v e ni n t e r v a lp r u n i n gt om a k et h ea l g o r i t h mh a sa a b i l i t yt os p l i tn u m e r i c a la t t r i b u t e s t h i sm e t h o dh a sg o o dp e r f o r m a n c e s i i u s en a i v eb a y e sc l a s s i f i e rt od e a lw i t ht h ei n n e rn o d e sa n dl e a fn o d e s t h i s m e t h o dr e d u c e dt h es a m p l es p a c ew h e nt r a i n i n gt h ed e c i s i o nt r e e i i i p r o p o s e da ne n s e m b l ec l a s s i f i e r sa n dad e t e c t i o nm e t h o df o rc o n c e p t d r i f t i n gt o d e a l 、析t l lt h ec o n c e p t - d r i f t i n gd a t as t r e a m i v w ep r o p o s eaw e i g h t e dm e t h o db a s e do i lt h ep r e c i s i o nf r o mp r i n c i p l eo fl o c a l i t y , a n dap r u n i n gm e t h o db yt h ew e i g h t v d e s i g nas e r i e se x p e r i m e n t st ov a l i d a t et h ep e r f o r m a n c eo ft h ee v f d ta l g o r i t h m a n dt h ee n s e m b l ec l a s s i f i e r s t h er e s u l t ss h o wt h ee v f d th a sh i 曲p r e c i s i o na n dt i m e e f f i c i e n c y , a n de n s e m b l ec l a s s i f i e r sh a v eg o o dp e r f o r m a n c eo nc o n c e p t d r i f t i n g d a t a s t r e a l t l k e y w o r d s ：d a t am i n i n g ，d a t as t r e a m ，c l a s s i f i c a t i o n ，u n e v e ni n t e r v a lp r u n i n g ，n a i v e b a y e sc l a s s i f i e r s i l w r i t t e nb yf e i x i o n gl i s u p e r v i s e db yq u a n l i u 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名绰日期：孕办 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 日期：埠盟 盐毕 ： 、 名 名 签 签 生 师 究 导 研 基于数据流的分类算法研究第1 章绪论 1 1 问题的提出 第一章绪论 信息时代的特征之一，就是数据无处不在。人们做出任何决策的背后都隐藏着一 大堆数据。各种各样的新设备和新服务正改变着人们的生活，并使人们随时都可以接 触到大量的数据，从简单的调节空调器的温度到根据职业和年龄等因素来分配信用额 度和给保险定价，都离不开数据的支持。大量的数据在给人们带来方便的同时也带来 了很多问题：第一是信息量非常大，不易消化；第二是信息真假难以辨识；第三是信 息安全难以保证；第四是信息形式不一致，难以统一处理。人们开始考虑：“如何才 能不被信息淹没，而是从中及时发现有用的知识、提高信息利用率? ”n 1 另一方面， 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越 多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析， 以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统 计等功能，但缺乏挖掘数据背后隐藏的知识的手段，无法发现数据中存在的关系和规 则，无法根据现有的数据预测未来的发展趋势。存放在大型数据存储库中快速增长的 海量数据集，由于没有强有力的工具，理解它们已经远远超出了人的能力口1 。结果导 致这些大型数据存储库中的数据变成了“数据坟墓”，出现“数据爆炸但知识贫乏 的现象口1 。如何更好地利用数据成为迫切的需要。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种商业数 据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展 到对数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能 对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系，从而发现有 价值的信息h 1 。 传统的数据挖掘技术都有一个共同点，即数据源都存储在永久性介质中，可以多 次访问。然而，近几年来，一类新的数据应用模型对其提出了挑战。这类模型具有广 泛的应用背景，包括信用卡欺诈消费行为的监测、传感器网络数据中的异常监测、网 络日志分析等，这种模型被称为数据流啼3 。数据流所包含的几乎无限的数据、以及经 第l 章绪论 基于数据流的分类算法研究 常性的概念漂移等特点使得数据流上的分类模型不同于传统的分类模型，需要能够快 速的处理流入的数据，并且及时对模型进行调整以反映新的分类概念。 在数据流模型中，挖掘算法只能对其中的数据进行实时地操作，因此不能频繁地 对数据进行访问。并且，由于内存空间大小非常有限，只能保存数据的概要信息而不 是数据全体。而传统的数据挖掘算法针对的是静态的数据库，因此不能直接应用于数 据流，这促使人们设计新的挖掘算法来适应新型数据流模型1 。 1 2 国内外研究现状 传统的存储于数据库中的数据可以称为静态数据。静态数据的挖掘过程可以分成 两个部分：先把数据收集起来存储在数据库或其它固定的地方，然后再应用各种分析 和挖掘技术挖掘其中所蕴含的信息。 而数据流中的数据则可以看成是动态数据，它们通常数据规模庞大，增长迅速并 且潜在无限，无法预测其数据总量。相对于传统的数据挖掘技术来说，数据流挖掘出 现得要晚一些。 数据流具有以下几点特性d 3 ： ( 1 ) 数据实时到达； ( 2 ) 数据到达次序不受应用系统所控制； ( 3 ) 数据规模宏大且不能预知其最大值； ( 4 ) 数据一经处理，除非特意保存，否则不能被再次取出处理，或再次提取数据 代价昂贵。 因此，对于流数据的收集过程和挖掘过程必须是同时进行的，我们必须以最快的 速度，从不断到来的数据中挖掘出感兴趣的知识，来为用户的决策提供支持。基于数 据库的传统数据挖掘对数据分析处理的精确性有很高的要求，但对于流数据，由于数 据收集时间的有限性，我们无法在精确度上做过多要求，而更多的关注对数据流分析 处理的速度，这使得挖掘结果的近似性成了不同于传统数据挖掘的一个特点。经过十 多年的研究与探索，该领域已经提出了很多算法。 f l o r a 船3 是系统是第一个对概念漂移进行处理的系统。f l o r a 使用种称为“描述 项的数据结构来对概念进行描述，它是一种值对集合。随着窗口向前移动，动态的 2 基于数据流的分类算法研究 第1 章绪论 添加或删除描述项。由于f l o r a 考虑所有出现的值对组合，描述项的个数非常多，这 使得模型更新的代价非常高。 h u l t e n 阳j 们提出了c v f d t 用来处理数据流上的分类问题。c v f d t 基于之前分类算 法v f d t 。v f d t 是一种只扫描一次训练集来构造决策树的算法。在w d t 中，每个节点 的分裂不再需要扫描整个训练集，它只扫描一部分训练数据来分裂节点n 。分裂每个 节点所需要的数据量使用h o e f f d i n gb o u n d s n 2 1 来计算。通过h o e f f d i n gb o u n d s 选 取的训练数据，能够在概率保证的情况下模拟整个数据集的特点n 羽。c v f d t 基于v f d t ， 随着数据的流入，考察决策树中每个节点的情况，当一个节点的分裂属性有了更好的 替代属性时，就更新这个节点。通过删除不再适用的节点和增加新的节点，使得决策 树能够动态的调整来处理概念漂移。 在文献 1 4 ，j i n 对v f d t 提出了两点改进。第一点，v f d t 只能处理离散属性， j i n 使用n i p ( n u m e r i c a li n t e r v a lp r u n i n g ) 来处理数值型属性的分裂；第二点，他 使用信息熵来减小每个节点分裂所需要的数据数量，这个工作使得改进后的算法增加 了对连续属性的处理能力，并在效率上有所提高。 w f a n 提出了“在对数据流进行分类时，如何才能更加有效的使用旧的数据 的 问题n 鲥。文献阐述了“错误的使用旧的数据将影响分类器的准确性”的观点，并提出 了一种新的数据流上的分类方法。每当从数据流流入一批数据，比较下列四种分类器 的准确性并选择一种：( 1 ) 旧的分类器；( 2 ) 使用新数据训练得到的分类器；( 3 ) 基于 新数据，并从旧数据中抽取和新数据类似的数据训练得到的分类器；( 4 ) 基于旧数据， 并从新数据中抽取类似的数据训练得到的分类器。从对这四种分类器分别进行交叉验 证以比较它们的准确性，并选择一种准确率高的作为新的分类器。 c c a g g a r w a l u 司提出了一种基于聚类的分类器。在这个算法中，每个类使用若干 个聚类( 文u s t e r ) 来表示，这些聚类根据数据的流入进行动态调整来反映流中数据的 变化。当进行预测时，计算待分类纪录和每个聚类的距离，并把最近的聚类的类标签 作为待分类记录的类标签。 虽然在该领域不断的取得新的进展，但问题和挑战依然存在，各种算法的准确率 和运算效率都具有很大的波动性，很大程度上受行业和数据特性的局限，日益增长的 应用需求促使许多研究人员正不懈努力以取得更大的突破，这使得该领域一直是研究 的热点。本文是作者经过数年努力的研究成果，为该领域贡献了自己的一份力量。 第1 章绪论基于数据流的分类算法研究 1 3 本文主要工作与内容安排 本文主要以数据流为研究对象，研究了数据流的概念漂移和分类问题，提出了一 种处理样本中连续属性的方法，并提出一个系综分类器，结合了当前流行的分类方法， 对各个分类器根据预分类的准确率赋权，并用实验检验了分类效果。因为数据流挖掘 不同于传统的数据挖掘，它的数据是持续不断，潜在无限的，所以有必要采取新的策 略和算法来解决内存与计算量的挑战。本文内容安排如下： 第一章为绪论部分。首先分析了本文的选题背景和研究意义，阐明了数据挖掘特 别是分类数据挖掘的基本概念；然后以及国内外对数据流挖掘的研究现状，介绍了几 种经典的数据流分类算法，以及当前数据流挖掘遇到的难点和挑战；最后介绍了全文 的结构和主要研究内容。 第二章介绍了数据挖掘和数据流分类的相关理论知识。首先讲解了数据挖掘的产 生和数据挖掘所解决的问题，介绍了数据挖掘的主要对象；其次介绍了一种新的数据 模型数据流，和几种生活中常见的数据流应用，以及针对数据流建模的几个经典 模型；接下来详细介绍了流数据挖掘算法的主要特点，介绍了数据流模型，以及基于 数据流的分类的相关知识，几种广泛使用的分类方法，并重点介绍决策树分类器，包 括传统决策树算法如i d 3 和c 4 5 ，以及挖掘数据流的v f d t 算法和c v f d t 算法；最后 介绍了概念漂移和检测概念漂移的方法。 第三章在v f d t 的基础上提出了e v f d t 算法，主要针对v d f t 无法处理连续属性， 以及在分裂决策点时样本需求量大而导致运算效率低的问题。用一系列宽度不等的间 隔将连续属性划分在不同区间内，在不降低精度的情况下，将连续属性离散化。同时 使用朴素贝叶斯方法处理决策树的各个节点，包括内部节点和叶节点，缩小了训练决 策树需要的样本空间，提高了对确定属性值和缺失属性值的处理效率，使算法的准确 率和时间效率大大提高。 第四章对挖掘概念漂移的数据流做了深入研究，提出了一个多分类器系综方法， 处理概念漂移数据流。根据局部性原理提出基于准确率的赋权方法，选取对当前样本 集准确率最高的前k 个分类器，处理到来的下一个样本。并使用权值剪枝方法，在检 测到概念漂移时，重新从这r 1 个分类器中选择适合新概念的k 分类器组成一个新的系 综分类器。同时提出一种检测概念漂移的方法，以提高检测概念漂移的灵敏度。最后 4 基于数据流的分类算法研究 第1 章绪论 从理论上分析了系综方法与单分类器方法的性能优势。 第五章用实验验证e v f d t 算法和系综分类器的性能。本章分为两部分，分别针对 第三章和第四章提出的方法，与现有经典算法为参照，比较说明了新方法的性能和实 用价值。第一部分使用k d d - c u p 一9 9 网络入侵经典数据集验证e v f d t 算法的准确率和 时间效率，并同v f d t 算法做了比较。第二部分同时使用人工数据和真实信用卡交易 数据检验系综分类器对概念漂移数据流的分类效果，比较了准确率和时间效率以及分 类器引入剪枝后的性能变化。 第六章总结全文内容，分析了当前数据流挖掘的挑战与进展，以及本文针对的主 要问题，以及解决办法。并对分类数据流挖掘的前景提出自己的观点，分析了分类数 据流挖掘未来有价值的研究方向。 最后列出了本文所引用的主要参考文献，和研究生期间发表论文，并向研究生学 习期间，在科研及论文写作过程给我指导和帮助的导师和同学们表示感谢。 第2 章理论基础基于数据流的分类算法研究 2 1 数据挖掘概述 2 1 1 数据挖掘的由来 第二章理论基础 从数据库中发现知识( k n o w l e d g eo i s c o v e r yi nd a t a b a s e s ，k d d ) 是2 0 世纪8 0 年代末开始的，k d d 一词是在1 9 8 9 年8 月于美国底特律市召开的第一届k d d 国际学 术会议上正式形成的。k d d 研究的问题有：( 1 ) 定性知识和定量知识的发现；( 2 ) 知识 发现方法；( 3 ) 知识发现的应用等。1 9 9 5 年在加拿大召开了第一届知识和数据挖掘 ( d a t am i n i n g ，d m ) 国际学术会议。由于把数据库中的“数据 形象的比喻成矿床， “数据挖掘”一词很快流传开来n 7 1 。 数据挖掘( d a t am i n i n g ，d m ) 的定义与“数据库知识发现”( 常简称为知识发现， k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 密切相关。一种观点认为知识发现是从 大规模数据中发现知识的整个过程，而数据挖掘只是这个过程的一个重要步骤，其它 还包括数据选取( d a t ap r e p a r a t i o n ) 和数据的解释和评估( 工n t e r p r e t a t i o n e v a l u a t i o n ) 1 8 , 1 9 ；另一种观点则认为两者是等价概念，均指发现知识的全过程乜们。 还有一种简单的定义是：数据挖掘( d a t am i n i n g ) 就是从海量的实际应用数据中，提 取隐含在其中的有用信息和知识的过程，这些数据可能是不完全的、有噪声的、模糊 的、随机的，动态的。这是不可能通过人工做到的，只能通过现代计算机技术实现， 这就是数据挖掘技术雎。 本文采用文献 1 6 的观点，认为数据挖掘从理论和技术上继承了知识发现领域的 成果，同时又具备独特的内涵。数据挖掘更着眼于设计高效的算法以达到从海量数据 中发现知识的目的，而将数据挖掘具体定义为“数据挖掘是一个从大型数据库中抽取 隐含的、事先未知的、潜在有用的信息或知识的过程n 6 | 。 2 1 2 数据挖掘对象与功能 目前数据挖掘系统已经越来越成熟，越来越复杂，功能从最初的简单分类到如今 6 基于数据流的分类算法研究 第2 章理论基础 满足用户需求的多种功能，如分类与预测、聚类分析、挖掘频繁模式与关联规则等。 挖掘的对象已经由简单的磁盘数据集发展到随时间变化的数据流和互联网，数据类型 也越发多种多样。 现代数据挖掘的主要来源就是各种数据库、数据流和互联网。数据库的类型千差 万别，存储的数据类型也多种多样，从各种遗留的异构的数据库到现代的对象或关系 一对象型数据库，数据有文本、图像、音频和视频、股票交易、顾客购物序列、w e b 点击流和生物学序列等等。 数据挖掘的任务就是发现隐藏在数据中的模式其可以发现的模式一般分为两大 类：描述型模式和预测型模式。描述型模式是对当前数据中存在的事实做规范描述， 刻画当前数据的一般特性。预测型模式则是以时间为关键参数，对于时间序列型数据， 根据其历史和当前的值去预测其未来的值和模式特征。 数据挖掘功能一般可以分为如下几种： ( 1 ) 概念描述。概念描述是典型的描述模式，可以理解为通过样例训练学习到一 个概念的特征，并能据此区分同种类样例。 ( 2 ) 挖掘频繁模式与关联规则。频繁模式是在数据中频繁出现的模式，常见的有 项集、子序列和子结构等。挖掘频繁模式主要发现数据中有趣的关联和相关，比如顾 客在同一次购买活动中所购买的不同商品之间的相关性。 ( 3 ) 分类和预测。分类找出描述和区分数据类或概念的模型( 或函数) ，以便能够 使用模型预测类标号未知的对象类。导出模型是基于对训练数据集( 即类标号已知的 数据对象) 的分析。决策树是一种典型的分类方法，其中每个节点代表在一个属性值 上的测试，每个分枝代表测试的一个输出，而树叶代表类或类分布。决策树容易转换 成分类规则。神经网络是一组类似于神经元的处理单元，单元之间加权连接。还有构 造分类模型的其它方法，如朴素贝叶斯分类、支持向量机和k 最近邻分类。 ( 4 ) 聚类分析。聚类( c l u s t e r i n g ) 分析数据对象不考虑已知的类标号。对象根据 最大化类内部的相似性、最小化类之间的相似性的原则进行聚类或分组。 ( 5 ) 离群点( o u t l i e r ) 分析。数据库中可能包含一些数据对象，它们与数据的一般 行为或模型不一致。这些数据对象是离群点。大部分数据挖掘方法将离群点视为噪声 或异常而丢弃。然而，在一些应用( 如欺骗检测) 中，罕见的事件可能比正常出现的 事件更令人感兴趣。 7 第2 章理论基础基于数据流的分类算法研究 ( 6 ) 演变分析。数据演变分析描述行为随时间变化的对象的规律或趋势，并对其 建模。尽管这可能包括时间相关数据的特征化、区分、关联和相关分析、分类、预测 或聚类，这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于相 似性的数据分析。 2 2 数据流 2 2 1 数据流概述 传统的数据库管理系统用于那些需要永久性存储数据以及对这些数据进行复杂 查询的应用。通常情况下，一个数据库包含若干无序的记录，这些记录是相对静态的。 记录的插入、更新、删除的频率大大低于对这些数据的查询的频率。当用户提交一个 查询时，数据库管理系统处理这些查询，得到的结果反映了数据库当前的状态。但是， 最近几年出现了大量新类型的应用，传统的数据库管理系统无法很好的处理这些应用。 这些应用的典型特点是数据以序列的形式出现，比如传感器数据、互联网数据、金融 数据( 股票价格等) 、在线拍卖以及事务日志( 网站访问日志、电话记录日志) 等。 数据流被定义为实时的、连续的、有序的记录序列。记录到来的顺序是无法控制 的，并且由于有限的硬盘等资源限制，无法将由于到来的记录存储在永久介质中。数 据流上的查询也与传统的查询不同，查询一旦被提交，将连续地在数据流上进行处理。 每当新的数据到来，将根据新的数据返回新的结果。近似和适应性是数据流上查询的 两个非常重要的特点。 现实生活中有很多应用会产生数据流，比如电信数据、金融数据、网络流量分析、 传感器网络等等，这些数据流都有各自的特点，在进行数据挖掘时要有针对性的分析 和处理。 ( 1 ) 电信数据流。电信业已经迅速地从单纯地提供市话和长话服务演变为提供综 合电信服务，包括传真、寻呼、移动电话、因特网信息、图像、电子邮件、计算机和 w e b 数据传输，以及其它数据通信服务。通信技术与计算机网络和各种其它通信与计 算工具的融合也是大势所趋。此外，随着许多国家对电信业的开放和新的计算机与通 信技术的发展，电信市场正在迅速扩张并越发竞争激烈。这迫切需要数据挖掘技术， 8 基于数据流的分类算法研究第2 章理论基础 帮助理解商业行为和捕捉盗用行为，更好地利用资源和提高服务质量。 一个典型的数据流挖掘问题是骚扰用户的发现。那些使用骚扰短信或电话的用户 往往在短时间内发出大量短信或呼叫，随后将号码弃之不用，而在此之前则没有任何 活动。传统的挖掘方法在实时性处理方面不够，很难在这方面有所作为。数据流挖掘 则可以在大量的话单流中发现这类用户，以方便采取适当的干预措施。类似的如流失 用户的预警、话费欺诈或盗用的检测等都可以进行处理。 ( 2 ) 金融数据流。大部分银行和金融机构提供丰富多样的银行服务、信用服务和 投资服务。银行和金融机构收集的数据通常相对完整、可靠并具有高质量，方便了系 统化的数据分析和数据挖掘。 对银行来说，贷款偿还预测和顾客信用政策分析是至关重要的。很多因素都会对 贷款偿还履行和顾客信用等级评定产生不同程度的影响。例如，与贷款风险相关的因 素包括贷款率、贷款期限、负债率( 月负债总额与月收入总额之比) 、偿还收入比、 顾客收入水平、受教育水平、居住地区和信用史等。我们要做的就是综合各项因素， 从中找出影响重大的因素对其进行挖掘。比如说，偿还收入比是主要因素，而受教育 水平和负债率则不是。于是，银行可以据此调整贷款发放政策。 ( 3 ) 网络流量监控。在实时情况下，i n t e r n e t 通信量的a d - h o c 网络分析系统已 经应用在流量统计和关键条件的检测( 例如拥塞和服务的拒绝) 等方面，在因特网中， 受欢迎的信息源和目的地址的流量模式遵守能量分配规律，即大多数带宽被少部分通 信量巨大的用户所消耗。 在t c p 三次握手过程中，由第二步和第三步组成的逻辑流上对不同的源目的对的 数量进行比较，如果数量上存在巨大的差异，则意味着可能会发生服务拒绝攻击。 ( 4 ) 传感器网络。传感器网络被用在地理监控( 地表的温度、湿度等) 、公路交通 状况监控、移动追踪、医疗设备监控、制造流程监控等。这些应用包含复杂的过滤， 要求能够及时的发现记录中不正常的模式。同时对多个数据流处理时，要求能够进行 聚集和多个数据流的连接操作。 传感器上的数据挖掘可能要求访问历史数据。典型的查询包括：当某个区域的多 个传感器产生的数据同时超过给定阈值时处理器能够激发一个触发器报告异常；在天 气地图上绘出温度轮廓，对多个产生温度数据的流进行连接操作，对温度数据和静态 的地理数据( 经纬度) 进行连接操作；发电站接收并分析每个城市最近的电力使用情 9 第2 章理论基础基于数据流的分类算法研究 况，从而在必要时能够调整发电量和各个城市间的电力分配。 2 2 2 数据流模型 由于数据流的特殊性：短时间内有大量数据连续到达，且这些数据随时间动态变 化，怎样对这些数据流进行快速实时的处理以获取有用信息，为数据挖掘及其应用研 究带来了新的机遇和挑战。由于众多应用领域的需求，近几年数据流上的查询处理问 题，特别是数据流上的分类、聚类、关联规则和频繁模式等常见的数据挖掘应用问题 己受到越来越多的研究人员关注。顶尖数据库和机器学习方面的国际会议( 如i g k d d ， p k d d ，s i g m o d 和v l d b 等) 都为数据流研究开辟了专栏。 数据流是一个以一定速度连续到达的数据项序列，其速度与数据项到达的次序无 法被控制。数据流通常具有潜在无限的体积，且数据可能的取值是无法预测的。处理 数据流的系统无法保存整个数据流。因此，数据流只能在线处理，数据流中的数据项 在被读取一次之后，就被丢弃，以后不可能再次读取。在实际应用中，某些超大型的 静态数据集要求处理算法只能进行一次线性扫描以降低算法的处理代价。此时，算法 的输入也可看作是一种数据流3 。 目前，在数据流研究领域中存在多种数据流模型。不同的数据流模型具有不同的 适用范围，需要设计不同的处理算法。可以分别按照数据流中数据描述现象的方式和 算法处理数据流时所采用的时序范围对这些模型进行划分。 按照数据流中数据描述现象的方式可以将这些模型分为三类： ( 1 ) 时序( t i m es e r i e s ) 模型，此时数据流中的每个数据项都代表一个独立的信 号。 ( 2 ) 现金登记( c a s hr e g is t e r ) 模型，此时数据流中的多个数据项增量式地表达 一个信号。 ( 3 ) 十字转门( t u r n s t i l e ) 模型，此时数据流中的多个数据项表达一个信号。随 着数据的流入，表达一个信号的数据项数目可能会增加，也可能会减小。 在这三种模型中，t u r n s t i l e 是最具一般性的数据流模型，其适用范围最广，也 最难处理。流数据分类与聚类通常使用的是时序模型，它们将数据流中的每个数据项 看作一个独立的对象。若将a j 记为信号j 出现的次数，则流数据频繁模式挖掘通 1 0 基于数据流的分类算法研究第2 章理论基础 常使用的是c a s hr e g i s t e r 模型，只允许数据的插入。也有算法研究了同时存在数据 插入和删除时的流数据频繁模式挖掘问题。此时算法应用的是数据流的t u r n s t i l e 模型。 由于数据流是一个长期、动态的过程，部分算法在处理数据流时并不是将所有的 数据流数据作为处理对象，而是根据应用需求选取某个时间范围内的数据进行处理。 按算法处理数据流时所选取的时序范围，数据流模型可分为以下几类口引： ( 1 ) 快照模型( s n a p s h o tm o d e l ) ：处理数据的范围限制在两个预定义的时间戳之 间。 ( 2 ) 界标模型( l a n d m a r km o d e l ) ：处理数据韵范围从某一个已知的初始时间点到 当前时间点为止。 ( 3 ) 滑动窗口模型( s l i d i n gw i n d o wm o d e l ) ：处理数据的范围由某个固定大小的 滑动窗口确定，此滑动窗口的终点永远为当前时刻。其中滑动窗口的大小可以由一个 时间区间定义，也可以由窗口所包含的数据项数目定义。 在这3 种模型中，界标模型和滑动窗口模型是采用得比较多的两种模型。界标模 型通常将数据流的起始点作为数据处理的初始时间点，此时算法对数据流中所有数据 进行处理，数据流上只存在插入操作。在滑动窗口模型中，窗口随着数据的流入向前 滑动，窗口中存在数据的插入和删除。滑动窗口模型非常适用于只要求对最近时间段 内的数据进行处理的应用。 2 2 3 流数据挖掘算法的特点 数据流实时、连续、快速到达的特点以及在线分析的应用需求，对流数据挖掘算 法提出了诸多挑战。挖掘数据流的算法一般要求具有如下特点： ( 1 ) 单次线性扫描。即算法只能按数据的流入顺序依次读取数据一次。 ( 2 ) 低时间复杂度。流算法是在线算法，为了适应数据流的速度，算法处理每个 数据项的时间不能太长，最好能为常数时间。 ( 3 ) 低空间复杂度。流算法是主存算法，其可用的空间是有限的，算法的空间复 杂度不能随数据量无限增长。 ( 4 ) 能在理论上保证计算结果具有好的近似程度。 第2 章理论基础基于数据流的分类算法研究 ( 5 ) 能适应动态变化的数据与流速。产生数据的现象可能在不断变化，导致数据 内容与流速的改变。 ( 6 ) 能有效处理噪音与空值。这是一个具有健壮的算法所必须具有的能力。 ( 7 ) 能作o n - d e m a n d 的挖掘。即能响应用户在线提出的任意时间段内的挖掘请求。 ( 8 ) 能作a n y - t i m e 的回答。即算法在任何时刻都能给出当前数据的挖掘结果。 ( 9 ) 建立的概要数据结构具有通用性。算法所构建的概要数据结构不仅能支持算 法当前的目标计算，而且能支持其它的计算。 在上述要求中，第1 至3 条是一个流数据挖掘算法所必须满足的。早期的流数据 挖掘算法都是以这三项为目标设计的。对于算法的空间复杂度，理想的情况是它与数 据流长度n 无关。但是，目前大部分问题都无法找到这样的解。因此，这个要求就让 步为找到空间复杂度为o ( p o l y ( 1 0 9 n ) ) 的算法，即次线性算法瞳4 1 。算法的时间复杂度 通常以每个数据项到来时，更新概要数据结构或目标计算结果所需要的时间来衡量， 理想的情况是算法处理每个数据项的时间为常数。其中，概要数据结构是算法为支持 目标计算而在内存中保存的数据流数据的压缩信息。对于构建概要数据结构的算法， 通常没有对在概要数据结构上计算目标函数所需要的时间做严格的要求。 近似性与自适应性是数据流算法的两大特点。由于一次线性扫描以及时间与空间 的限制，数据流算法往往只能得到对所处理的问题的近似计算结果。能在理论上保证 其计算结果的近似程度，是算法应该考虑的一个问题。算法的自适应性是指当流数据 内容或流速受各种因素的影响而发生改变时，算法能够根据这些改变自动调整计算策 略与计算结果。 噪音与空值是一个健壮的算法所必须解决的问题。对于流数据挖掘算法，这个问 题显得更为突出。这是因为在挖掘数据库中的静态数据集之前，通常会进行数据的预 处理，消除数据中的噪音与空值。而在在线进行的流数据挖掘过程中，无法在挖掘前 对数据进行预处理。而且，数据流中的数据在采集以及传输过程中，都可能出现错误， 产生噪音或空值。数据流的动态变化性更进一步增加了噪音识别的困难。当产生数据 流的现象发生改变时，新数据无法被现有数据模型所描述，可能被误认为是噪音。 在一些应用中，用户可能在数据流流入过程中提出对某个时间段内的数据进行挖 掘的请求。能回答这种请求的算法被称为具有o n - d e m a n d 回答能力的算法。算法通常 采用多窗口技术来近似解决这类问题。能对挖掘请求给出a n y t i m e 的回答，指算法 1 2 基于数据流的分类算法研究 第2 章理论基础 在任何时刻都能给出对当前数据最精确的计算结果。这要求算法每读取一个数据项， 就更新处理结果。 有些算法构建的概要数据结构只能用来支持算法的目标计算，如文 2 5 中为计算 数据流对之间的滞后关联而保留的统计量。有的概要数据结构是对数据流数据一般性 的压缩，还可用来支持其它计算，如文 2 6 中保留的多个基本窗口内数据的傅立叶变 换系数。这样的概要数据结构显然比只能支持当前计算的概要数据结构更为有用。 2 3 决策树分类器 2 3 1 数据分类 经历了多年的研究，数据挖掘己经发展成为一个大的学科，主要方向包括：关联 规则、分类、聚类等。其中，分类是一个很重要的分支。它的目的是从大量数据中提 取描述重要数据的模型或预测未来的趋势。分类算法包括两个步骤：建立一个模型， 描述预定的数据类集和概念集；使用模型对类标签未知的元组进行分类。己经有大量 的分类法用于构造各种类型的分类器，包括决策树砼引、贝叶斯分类器啪1 、神经网络3 、 最近邻分类算法m 3 等。这些算法被广泛的应用于各个行业，提供自动化的分类预测功 能。 假定每个元组属于一个预定义的类，由一个称作类标签的属性确定。为建立模型 而被分析的数据元组形成训练数据集。训练数据集中的每个元组称作训练样本。由于 提供了每个训练样本的类标号，该步也称作有指导的学习m 3 。通常，学习模型用分类 规则、判断树或数学公式的形势提供。当使用模型对类标签未知的元组进行分类或对 测试数据进行检测时，如果预测精度达不到要求，则需要重新构造分类器。 最为典型的分类方法是决策树。通过对样本属性一系列的测试构造内部节点，最 后根据类标签生成决策节点，即样本所属的类别。增量式的决策树算法在树不能对所 有对象给出正确的分类时，会选择一些例外样本集加入到训练集中，重复该训练过程 直到生成正确的决策树。最终结果是一棵树，其叶节点是类名，中间节点是带有分枝 的属性，该分枝对应该属性的某一可能值。 第2 章理论基础基于数据流的分类算法研究 2 3 2 决策树的产生与发展 决策树是用样本的属性作为节点，用属性的取值作为分支的树型结构。它是利用 信息论原理对大量样本的属性进行分析和归纳而产生的。决策树的根节点是所有样本 中信息量最大的属性。树的中间节点是以该节点为根的子树所包含的样本子集中信息 量最大的属性。决策树的叶节点是样本的类别值。 决策树用于对新样本的分类，即通过决策树对新样本属性值的测试，从树的根节 点开始，按照样本属性的取值，逐渐沿着决策树向下，直到树的叶节点，该叶节点表 示的类别就是新样本的类别。决策树方法是数据挖掘中很有效的方法。 决策树是一种知识表示形式，它是对所有样本数据的高度概括，即决策树能准确 的识别所有样本的类别，也能有效的识别新样本的类别。 决策树方法中影响最大的是j r o u i n l a n 于1 9 8 6 年提出的i d 3 算法口3 1 ，他提 出用信息熵( 即信息论中的互信息) 来选择属性作为决策树的节点。由于决策树的建 树算法思想简单，识别样本效率高的特点，使i d 3 算法成为当时机器学习领域中最有 影响的方法之一。后来，不少学者提出了改进i d 3 的方法，以j r o u i n l a n 本人在 1 9 9 3 年提出的c 4 5 泓1 算法最具代表性。 当使用决策树建模时，遇到的挑战有很多。其中之一就是如何处理连续属性。我 们知道计算机可以很容易的处理离散属性，但是现实世界中许多用来衡量的变化的参 数的取值是连续的，在分类的时候这类连续属性值带来很大麻烦，我们必须将这些连 续属性离散化。 2 3 3 常见的决策树算法 i d 3 算法是较早也是最著名的决策树归纳算法。该算法利用信息论中的互信息 ( 信息增益) 寻找数据库中具有最大信息增益的属性字段，建立决策树的一个节点，再 根据该属性字段的不同取值建立树的分支。在每个分支子集中重复建立树的下层节点 和分支过程。这种方法的优点是描述简单、分类速度快，特别适合大规模的数据处理。 但i d 3 算法是借用信息论中的互信息作为单一属性能力的度量，其启发式函数并不是 最优的，存在的主要问题有：( 1 ) 互信息的计算依赖于属性取值的较多特征，而这一 属性不一定最优；( 2 ) i d 3 不是增量学习算法；( 3 ) 抗噪性差，训练例子中正例和反例 1 4 基于数据流的分类算法研究第2 章理论基础 较难控制。对i d 3 算法的早期改进算法主要是i d 3 的增量版i d 4 ，i d 5 及c 4 5 ，c a r t ， f a c t 和c h a i d 算法等。后期的改进算法主要有q u e s t 和p u b l i c 等。 j r o u i n l a n 本人在1 9 9 3 年提出的i d 3 的改进算法c 4 5 幽3 最具代表性。c 4 5 方法对i d 3 方法的主要改进有以下几个方面： ( 1 ) 用信息增益率取代信息增益来选择属性作为决策树的节点，从而克服了用信 息增益选择属性时偏向于选择取值较多的属性的不足。 ( 2 ) 在树构造过程中或者构造完成之后加入剪枝过程。 ( 3 ) 内黄了离散化步骤，能够完成对连续属性的直接处理。 基于无遗漏搜索算法的决策树倾向于选择能提供更多的分裂变量，q u e s t 弱化了 这种偏见。它采用与f a c t 类似的分裂选择策略，即统计学测试指导变量选择方法。 但与f a c t