动态数据挖掘研究

第28卷 2008年 6月 计算机应用 Computer Apphcafions V01．28 June 2oo8 文章编号 ：1001—9081(2008)S1—0160—03 动态数据挖掘研究 滕明鑫 ，熊忠阳 ，张玉芳 (1．重庆大学 计算机学院，重庆 4O0044； 2．重庆通信学院 计算机科学与技术教研室，重庆 400035) (qiaohua629@yahoo．corn．cn) 摘 要：提出了一种新的数据挖掘形式——动态数据挖掘(DDM)，寻求在不断更替产生的动态数据信息中找出 能被应用的知识。给 出动态数据挖掘的体系结构，并分析 了动态数据挖掘实现过程，运用滑动窗口与动态数据窗口 动态采集与处理动态新增数据 ，同时运用后续数据进行挖掘结果评价，用K标号法平滑地使用动态 目标数据集进行 数据挖掘，得出了一个动态数据挖掘测试算法。 关键词：动态数据挖掘；体 系结构；动态数据采集；动态数据处理；滑动窗口；动态数据窗口 中图分类号：TP311．13 文献标志码：A Research OH dynamic data mi ning TENG Ming—xin ，XIONG Zhong—yang ，ZHANG Yu—fang (I．College ofComputer Science， 。聊 Un M 嘲 zng4oo044，China； 2．Teaching andResearch SectionofComputerScience and Technology, 嘲 ￡昭 CommunicationInstitute， 嘴 z昭 400035，China)) Abstract：Dynamic Data Mining(DDM)，a new data mining way-to sort out the information available from the changing dynam ic data information WaS pmpesed．The arcllitectuIe of dynamic data mining system along with the realization of dynam ic data mi ning process was described．Sliding window and dynami c data window were used to acquisite and process the new adding datum，and back arriving datum was used to evaluate the mi ning resets．K-mark method was adopted to mi ne smoothly from targrt data sets，and a dynam ic data mi ning testing algorithm for data mining was pmpesed． Key words：Dynamic Data Mining(DDM)；system architecture；dynamic data acquisition；dynamic data processing； sliding window；dyn am ic data window 0 引言 随着信息技术的进一步发展，对知识的新颖性越来 越强。我们处在每天都有大量新鲜信息产生的社会中，如果 采用原来的针对静态数据源(如数据仓库)进行知识提取的 数据挖掘技术来分析这些不断产生的信息可能无法满足现实 应用要求，因为传统的数据挖掘可能挖掘到的是过时或失效 的知识。社会在不断进步，时代在不断改变，信息的时效性变 得越来越短。为了能充分把握新颖性的信息，对实际应用数 据源(数据库、序列数据或流式数据等)在其运行的同时进行 数据动态提取并加以分析来得到相关知识是十分必要的。这 方面的工作有持续数据挖掘⋯、流式数据挖掘和 web在线数 据挖掘。当然实际生活中还有许多与时间关系不大且不涉及 Web在线的各种应用，针对这些应用数据源进行动态实时挖 掘也是十分必要的。为此，本文提出了一种动态数据挖掘方 法，给出了动态数据挖掘的体系机构，并分析了动态数据挖掘 过程。 1 动态数据挖掘问题 在实际应用数据源运行过程中动态提取数据用于知识发 现时，关键的是如何选取当前数据集，如何保持与历史数据平 滑过渡，以及如何平滑地获取后续数据集。所以动态数据挖 掘是集过去、现在与未来于一体的动态的过程 ，下面给出一些 相关定义：给定实际运行数据源，将其称为动态数据源 (Dynamic Data Soume，DDS)，DDS中的数据记为d (i为数据 标志号，i∈Z )。 定义1 设当前时间点为 ，存在数8(8∈R )，DDS中 在 T～6时刻以前生成的所有 d 组成的数据集合称为历史数 据集，记为D0Id。 定义2 设当前时间点为 ，存在数8(8∈R )，DDS中 在 T～6时刻到 时刻生成的所有d 组成的数据集合称为当 前数据集，记为D 一 。 定义3 设当前时间点为 ，存在数6(6∈R )，DDS中 在 时刻以后生成的所有d 组成的数据集合称为称为后续数 据集，记为 D一。 定义4 在DDS中运用当前数据集D。— 与历史数据集 D。 结合后续数据集 D一 进行分析，提取出其中有意义的、新 颖的、关键的知识与规则的过程称为动态数据挖掘(Dynamic Data Mining，DDM)。 从以上定义可以看出，动态数据挖掘与传统的基于数据 仓库的数据挖掘有很大的不同，传统的数据挖掘主要是基于 历史数据集进行挖掘 ，提取出隐藏在其中的知识 ，而动态数据 挖掘是集过去现在与未来于一体的知识提取的过程。为了便 于进一步研究动态数据挖掘问题，下面就动态数据挖掘的体 系结构进行分析。 收稿日期：2007一II一17。 作者简介：滕明鑫(1980一)，男 ，重庆人，讲师，硕士，主要研究方向：数据挖掘、数据库系统、计算机网络； 熊忠阳(1962一)，男，重庆人，教 授，博士生导师，博士，主要研究方向：网格与并行处理、数据挖掘、互联网应用； 张玉芳(1965一)，女，重庆人，副教授，博士，主要研究方向：数 据挖掘、网络入侵检测、信息网络与信息系统、现代远程教育。 维普资讯 http://www.cqvip.com 6月 滕明鑫等：动态数据挖掘研究 161 2 动态数据挖掘的体系结构 描述。 动态数据挖掘主要体现在它能动态地从 DDS中提取数 据进行分析，找出其中的知识与规则，从而更加及时新颖地为 企事业单位或各管理部门提供决策方案，其实现过程大致可 分为动态数据采集、数据处理、数据挖掘、挖掘评价几个过程。 动态数据挖掘关键是要解决后续数据集D 的动态采集以及 动态处理问题，本文提出一种基于滑动窗口的动态数据采集 方法，来保证新旧数据的平滑以及数据的及时或实时获取，运 用动态数据窗口进行数据的实时动态处理；由于动态数据挖 掘在运行过程中，DDS也在运行，即后续数据集D一 在不断 增加，鉴于此，在数据处理以及后续的数据挖掘过程中必须 要有较高的处理效率并且能支持自动更新处理；数据挖掘与 挖掘评价是紧密结合的两个过程，采用后续数据集中数据对 挖掘结果进行评价，评价结果不符合要求则修正挖掘过程或 重新挖掘以适应应用环境的改变，尤其在对事务进行统计分 析或趋势预测分析时显得尤为重要。 图1 动态数据挖掘体系结构 3 动态数据采集 动态数据采集(Dynamic Data Acquisition，DDA)是指在 动态运行数据源中动态地获取其中的历史的当前的或者即将 生成的数据集。对于从历史数据集或当前数据集中获取数据 可以一次提取完成，但对于还未生成或正在生成的数据获取 就只能分步来不停地获取，为了保证获取数据的平滑性，采用 滑动窗口作为动态数据获取窗口。 3．1 滑动窗口 滑动窗口(Sliding Window，SW) 在计算机网络通信、 时间序列数据挖掘、移动数据流数据挖掘等方面都有应用。 本文也借鉴这一技术来实现数据的动态获取。世间万物都是 处于时空中的，事物的产生 、发展 以及灭亡都与时间有关联； 为此，对于动态数据源的数据动态获取中滑动窗口度量均可 采用时间来确定。下面给出滑动窗口的相关定义。 图2 数据窗口划分 定义5 在 DDS中，按照数据 d (i为数据标识号，i z )的生成时间分成窗 口大小为 ( 为时 间段，且 = (n Ez ，且 ≥1))的数据段 (k N)，每个数据段为 一 个数据窗口，．r为数据门限值。 定义6 对于正数∞，∞=nr(17,∈z ，且 ／7,≥1)，某时刻 r，有数据段集D={D，，D ，⋯，D l落人到窗口大小为∞的 窗口SW中，该窗口每隔．r时间向前移动s(s∈z ，1≤s≤／7,) 个数据窗口大小的位置，称窗口SW为滑动窗口。 为了说明滑动窗口动态采集数据的功能，方便起见，图3 以滑动窗口大小为两个数据窗口每次移动一个窗口为例进行 o f 2f 3f 4r ⋯ hi" T (a) fb) Dl D2 图3 滑动窗口示意图 3．2 动态数据采集分析 数据窗口是基于时间段来划分的，为了能快速及时地从 DDS中获取数据，如果数据是时间性关联不是很强的数据或 者是离散性数据，往往是通过数据库来保存的，这就需要存储 DDS的数据库存储数据的产生时间，这样就能采用数据库查 询语言快速检索到满足要求的数据。 例 1 如在银行信贷管理系统中，要查看最近 2小时内 发生的所有信贷交易，可使用如下SQL语句实现： SELECT · FROM Credit _ Database ． WHEREtime betweenT一2 andT(T为当前时间) 对于时间关联性较强的领域，可以看成是在数据流上寻 找某时刻的一个历史快照，目前很多大学和机构正在致力于 开发一种面向新的应用的数据流管理系统，比较成型的原型 系统有斯坦福大学 的 STREAM系统，布朗大学、麻省理工大 学等联合开发的 Aurora，美 国加州大学伯克利分校 的 Telegraph CQ等。有关流式数据库的研究也引起了国内数据 库工作者的高度重视，但国内的研究还处于初期阶段 ，具有一 定深度的研究成果还不多见 ]。 例2 要观察过去2小时内ID号为“ID—nuln”的股票的 平均交易价格，并且每 l小时计算一次，可以用 SQL语言 示为： SELECT Avg(Price) FROM Stock[2 hours，1 hour] WHERE ID=’·ID hum” 4 动态数据处理 动态数据处理(DyrI锄ic Data Processing，DDP)是相对于 传统的数据挖掘的数据处理过程而言的。传统的数据挖掘只 是针对特定的数据固定的数据集进行；而动态数据挖掘中，为 了找出新颖的、最近的、感兴趣的知识，在数据处理过程中也 要求能动态处理各实时数据。动态数据处理包括消除噪声、 缺失数据处理、类型转换、特征提取以及数据降维处理等。处 理可采用传统的数据预处理数据变换、规约等方法，主要在于 如何动态处理动态数据采集过程传来的动态实时数据。由于 动态数据采集传来的数据都是基于时间段的实时数据，考虑 到在数据处理过程中，边界数据可能被忽略，结合重叠窗口技 维普资讯 http://www.cqvip.com 162 计算机应用 2008盎 术，选择一种动态数据窗口来处理动态实时数据。 4．1 动态数据窗口 文献[8]针对固定的有限数据集合进行聚类分析时第一 次提出了动态数据窗口(Dynamic Data Window，DDW)概念， 并第一次运用窗口重叠移动进行聚类分析。将一个有限数据 集合Z= ， ：，⋯， }c R。划分成(2k一1)个数据窗口， 第i个与第i+1个窗口的部分重叠，让重叠部分的数据(边界 数据)重复计算，一个一个窗口处理下去直到处理完毕。这样 数据窗口的部分重叠克服了k-means方法难以发现各种不同 下来选取密度点时贡献一样大，而且选出的密度点不因k值 的变动而变化很大。 动态数据挖掘处理的是从动态数据采集窗口传来的动态 实时数据，数据量在不停的增加。动态数据处理窗口每隔r时 间间隔就传过来s个数据窗口的实时数据，为了使各数据dl 都被分析处理到，定义动态数据窗口大小sr，对 DDW进行如 下划分：0一s为第 1个窗口；口一s+口为第2个窗口(0<口≤ s)；s一2s为第3个窗口；s+口一25+口为第4个窗口⋯⋯ 即 第i个与第 i+1个窗口的部分重叠，随着数据窗口的向前移 大小的聚类的缺点，使得每个数据窗口分界处的样本点在接 动，我们可以不断地实时处理动态数据，如图4所示。 0 v 5+ 2s 2s+V ⋯ H5 H + 2ns⋯ T ) 图4 动态数据窗口的重叠划分示意图 4．2 动态数据处理分析 图4中的 代表样本点，重叠窗口划分中的 值根据具 体情况而定，如果时间段划分较长，则选取 为接近s的某个 值为宜，因为时间段长，在很短的时间内可能就有很多样本数 据存在；选取较小 值会使重复处理的数据量增大从而造成 大量的时间耗费。当 =s时表示在不进行特征提取、数据降 维等数据变换与规约处理时以提高数据处理的效率，比如只 需要类型转换、部分缺失数据处理或消除噪声等数据预处理 方面。 下面以动态数据流特征提取为例说明动态数据处理过 程 ： 对于从动态数据采集中滑动窗口传来的m维流式数据 。， ： ，⋯ ， ，⋯ 序列，到达数据处理窗口的时间为 t，，t：，⋯， t -·序列，由定义 5与定义6可知： =(t 一t )／r，记 ： {Dfj_。1x|+ 1 0minsp&&cx>mincx){ ／／找到二项频繁项，并且它们是强关联 ) ) ／／第二次遍历一项频繁集结束 } ／／第一次遍历一项频繁集结束 5 实验结果 该数据挖掘改进算法已经用TOM联通WAP业务一天的 日志进行了验证 ，试验的环境是在 htel Pentium 1 GHz处理器 和512 MB内存机器上进行的，运行的平台为Linux。 WAP业务一天的所有日志120万，由于该算法只需下载 日志，所以从中抽取所有下载 日志9．8万，下载 日志会话数 (下载素材的用户)约 1．2万，下载 日志中一天被下载的素材 种类数约5 000，从这些下载日志使用该数据挖掘算法的运行 时间如表 1。 表 1 不同支持度阈值下运行时间比较(不包括预处理时间J 支持度阈值 数据挖掘时间T／s O．0o1 O．005 0．010 71 38 22 以上结果是在把9．8万下载13志放入内存下的情况得到 的，笔者还实验了在其他程序不变的情况，用扫描数据库的方 式，支持度阈值为0．01的条件下，运行了1小时15分钟。扫 描内存比扫描数据库运行存在很大的差别。 。 6 结语 由于本改进算法用一项频繁集生成二项候选集，减少大 量二项候选集；扫描内存代替扫描数据库，减少大量扫描时 间，所以得到良好的运行效果。本改进算法除了在WAP增值 业务应用外，还可以在电子购物、专业下载网站等地方使用。 参考文献： 【1】 孔吴，周长胜．Web日志挖掘预处理研究【J】．北京机械工业学 院学报，2005，20(4)：28—31． 【2】 庄力可，寇忠宝，张长水．网络 日志挖掘中基于时间间隔的会话 切分【J】．清华大学学报：自然科学版，2005，45(1)：115—118． 【3】 张友志，钱萌，程玉胜．基于关联规则 Web 13志挖掘方法的研究 【J】．安庆师范学院学报：自科学版，2006，12(1)：57—59． [41 林杰斌，刘明德，陈湘．数据挖掘与OLAP理论与实务【M】．北 京：清华大学出版社，2003． 【5】 http：／／www．progra~an．corn／article／article．asp?classid=19[EB／ OL]．【2003—1O一151． (上接第 162页) 造成挖掘空转，即大量的挖掘过程发现不了更新颖的知识与 规则；时间过大会造成不能及时获取到新知识；0的确定还与 挖掘任务有关，在关联规则获取、相关性分析、建模等挖掘任 务中由于时间关联不是很大，可设定较大的挖掘启动时间跨 度，而在趋势预测、聚类、统计分析等与时间关联性很强的挖 掘任务中，挖掘跨度不能太大，特别是在导弹轨迹预测、实时 监控方面需要尽可能小的挖掘时间跨度，当然也与挖掘算法 有关。 6 结语 动态数据挖掘适用于动态数据聚类分析、动态趋势预测、 动态关联规则提取、专家系统知识学习、动态数据统计分析等 方面；在与数据库集成上也是一个十分有效的策略。 本文针对传统的数据挖掘不能满足对动态数据源的数据 分析要求，提出了动态数据挖掘形式，给出了动态数据挖掘的 体系结构；为了体现以及适应对动态数据的数据挖掘，对于动 态数据采集过程、动态数据处理过程、数据挖掘的动态实现以 及动态挖掘评价都作了分析并给出了实现思想；在动态数据 采集中采用滑动窗口平滑采集数据，再通过动态数据窗口动 态处理数据采集过程送来的动态实时数据；在数据挖掘过程 中，通过一种 K标号法保证数据挖掘过程的动态平滑性；通 过结合后续数据集来动态评价挖掘结果，给出了 空间的 动态数据挖掘测试算法 DDMTA算法。 参考文献： 【1 1 AGRAWAL凡 PSAILA G．Active data mining【el／／Proceedings ofthe 1st International Conference on Knowledge Discovery and Data Mining：KDD'95．California：AAAI Press．1995：3—8． 【21 GIBBONS P B，TI瑚rHAPURA S．Distributed sheaIIls algorithms for sliding windows【C】／／Proceedings of the ofthe 14th Annual ACM Symposium O11 Parallelism in Algorithms and Architectur~． Win— nipeg，Manitoba：ACM Press，2004：1—22． 【3】 CHI YUN，WANG HA1-XUN，YU P S．et aL Catch the moment： maintaining closed frequent itemsets over a data strealTl sliding win· dow【J】．Knowledge and Information Systems，2006，10(3)：265— 294． 【4】 司开君，毛宇光．一种新的基于数据流的数据模型【J1．计算机技 术与发展，2O07，17(1)：1—3． 【5】 邓维维，彭宏，郑启伦．基于数据流的移动数据挖掘研究综述 【J]．计算机应用研究，2007，24(1)：5—8。 【6】 ZHOU AO·YING，CAO FENG，QIAN WEI·NING，et a1．Tracking clusters in evolving data streams over sliding windows【J】．Knowl— else and Information Systems，20o8，15(2)：181-214． 【7】 王达．时间序列数据挖掘研究与应用【D】．杭州：浙江大学， 2004． 【8】 王天真．智能融合数据挖掘方法及其应用【D】．上海：上海海事 大学，2006． 【9】 武红江，赵军平，彭勤科，等．基于波动特征的时问序列数据挖掘 【JJ．控制与决策，2007，22(2)：160—163． 【1O】潘定，沈钧毅．持续时态数据挖掘的研究【J】．控制与决策，2007， 22(3)：278—283． 维普资讯 http://www.cqvip.com