毕业设计开题报告 -事件序列上频繁情节挖掘算法的研究.doc

南京理工大学泰州科技学院毕业设计(论文)开题报告学 生 姓 名：学 号：专 业：信息管理与信息系统设计(论文)题目：事件序列上频繁情节挖掘算法的研究指 导 教 师: 2014年1月19日开题报告填写要求1开题报告（含“文献综述”）作为毕业设计（论文）答辩委员会对学生答辩资格审查的依据材料之一。此报告应在指导教师指导下，由学生在毕业设计（论文）工作前期内完成，经指导教师签署意见及所在专业审查后生效；2开题报告内容必须用黑墨水笔工整书写或按教务处统一设计的电子文档标准格式（可从教务处网页上下载）打印，禁止打印在其它纸上后剪贴，完成后应及时交给指导教师签署意见；3“文献综述”应按论文的格式成文，并直接书写（或打印）在本开题报告第一栏目内，学生写文献综述的参考文献应不少于15篇科技论文的信息量，一般一本参考书最多相当于三篇科技论文的信息量（不包括辞典、手册）；4有关年月日等日期的填写，应当按照国标GB/T 740894数据元和交换格式、信息交换、日期和时间表示法规定的要求，一律用阿拉伯数字书写。如“2010年3月15日”或“2010-03-15”。 毕 业 设 计（论 文）开 题 报 告1结合毕业设计（论文）课题情况，根据所查阅的文献资料，每人撰写2000字左右的文献综述：文 献 综 述摘要 近年来，在许多管理信息系统及决策支持系统中频繁出现了大量的有序事件，挖掘这些事件背后隐藏的规律具有十分重要的意义。本文研究了“情节”的相关概念及事件序列上的频繁情节挖掘算法，包括WINEPI、MINEPI、NONEPI等算法的设计思想和基本原理，分析了各种算法的优势和存在的不足。在此基础上,研究了应用Java语言实现算法的相关技术。关键词 数据挖掘 事件序列 频繁情节 NONEPI NONEPI+1 研究背景随着计算机网络技术的飞速发展，近年来在许多管理信息系统、信息分析系统及决策支持系统应用中出现了大量的由一系列值对（事件类型，发生时间）组成的事件序列，如网络监控日志、入侵检测序列、股票交易日志、基因序列等。这些事件序列背后隐藏了大量的规律，对他们进行挖掘和分析，可以发现事件之间的紧随关系，从而揭示系统潜在的行为模式，这种模式被定义为“频繁情节”。基于事件序列上的频繁情节挖掘已经成为时序数据挖掘领域的热点之一，它具有广阔的应用前景，为商业预测、决策提供了科学依据，目前已被广泛应用于电信故障诊断、股票趋势分析、道路交通监控、用户行为预测等领域。为了解决频繁情节挖掘问题，ManiLLa等人首先引入了情节的概念，并提出了两个经典算法WINEPI、 MINEPI。其中，WINEPI基于滑动窗口(SLiding window)来定义支持度，而MINEPI是基于情节的最小发生来定义支持度。这些算法都采用了Apriori算法的基本思想，能挖掘出所有的频繁情节，但是在计算支持度时可能包含了多次重叠的发生，从而导致“过计数”问题。为此Laxman等人引入了“非重叠发生”的概念来定义一个情节的支持度，并且提出了一个高效的频繁情节挖掘算法NONEPI，该算法通过采用有限状态机来计算情节支持度，不足之处，该算法与Apriori算法类似，需要多遍扫描事件序列，并产生大量候选情节。虽然一些改进算法对产生的候选情节预先进行“剪枝”，提高了效率。然而，当事件序列很长时，多遍扫描序列仍然需要较高的空间和时间代价。为了克服以上算法的不足，本文拟在研究和实现NONEPI算法的基础上，对NONEPI算法进行改进，以期提高频繁情节挖掘的效率。2 相关技术本文基于Eclipse平台及Java开发工具（Java Development Kit，JDK），应用Java语言实现NONEPI算法及改进的NONEPI+算法。 2 .1 数据挖掘数据挖掘（Data mining）是数据库知识发现（Knowledge-Discovery in Databases，简称：KDD)中的一个步骤。数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。数据挖掘通常与计算机科学有关，并通过统计、在线分析处理、情报检索、机器学习、专家系统和模式识别等诸多方法来实现上述目标。数据挖掘利用了来自如下一些领域的思想：(1) 来自统计学的抽样、估计和假设检验，(2)人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论。数据挖掘也迅速地接纳了来自其他领域的思想，这些领域包括最优化、进化计算、信息论、信号处理、可视化和信息检索。一些其他领域也起到重要的支撑作用，如需要数据库系统提供有效的存储、索引和查询处理支持。源于高性能（并行）计算的技术在处理海量数据集方面常常是重要的。分布式技术也能帮助处理海量数据，并且当数据不能集中到一起处理时更是至关重要。数据挖掘常见的分析方法包括分类 （Classification）、估计（Estimation）、预测（Prediction）、相关性分组或关联规则（Affinity grouping or association rules）、聚类（Clustering），典型的数据挖掘系统结构如图1所示。图1 数据挖掘系统结构图2 .2 EclipseEclipse 是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言，它只是一个框架和一组服务，用于通过插件组件构建开发环境。Eclipse 附带了一个标准的插件集，即Java开发工具（JDK）。Eclipse 还包括插件开发环境（Plug-in Development Environment，PDE），这个组件主要针对希望扩展 Eclipse 的软件开发人员，因为它允许构建与 Eclipse 环境无缝集成的工具。2 .3 JAVA语言JAVA语言是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台（JavaSE, JavaEE, JavaME）的总称。Java 技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。在全球云计算和移动互联网的产业环境下，Java更具备了显著优势和广阔前景。Java语言的跨平台特性也为算法设计提供了强有力的支持，目前很多数据挖掘算法都是基于Java语言实现。如Java数据挖掘包（JDMP）是一个开源的Java程序库，用于数据分析和机器学习。3 课题优势（1）本课题研究的频繁情节挖掘算法属于时序数据挖掘的范畴，由于越来越多的数据都与时间有着密切的关系，时序数据挖掘已成为数据挖掘的热点之一，它具有广阔的应用前景，因此本课题具有一定的研究意义和应用价值。（2） 本课题研究的是事件序列上非重叠发生的频繁情节，这类情节克服了WINEPI及MINEPI算法在计算支持度时可能存在的“重复计数”问题。（3） 本课题研究的算法采用Java语言实现，Java语言具有很好的可移植性和可扩展性，可以定义接口供其他应用程序调用，也可方便地迁移到手机平台上应用。（4） 本课题针对NONEPI算法的不足，提出对其改进的思路和方法，预期可以提高频繁情节挖掘的效率。参 考 文 献1 Manilla H, Toivonen H, Verkamo A. Discovering frequent episodes in sequencesC/Proceedings of the First International Conference on Knowledge Discovery and Data Mining.1995:210-215.2 Mannila H, Toivonen H, Verkamo A I. Discovery of frequent episodes in event sequencesJ. Data Mining and Knowledge Discovery,1997,1(3): 259-289.3 Mannila H, Toivonen H. Discovering Generalized Episodes Using Minimal OccurrencesC/KDD.1996,96:146-151.4 Laxman S, Sastry P S, Unnikrishnan K P. Discovering frequent episodes and learning hidden markov models: A formal connectionJ.Knowledge and Data Engineering,IEEE Transactions on,2005,17(11):1505-1517.5 Zhou W,Liu H,Cheng H.Mining closed episodes from event sequences efficientlyM/Advances in Knowledge Discovery and Data Mining. Springer Berlin Heidelberg,2010:310-318.6 Zhu H,Wang P,He X,et al.Efficient episode mining with minimal and non-overlapping occurrencesC/Data Mining (ICDM),2010 IEEE 10th International Conference on.IEEE,2010:1211-1216. 7 刘世平.数据挖掘技术及应用M.北京:北京高等教育出版社,2010,1:1012.8 王超.间隔事件流上的频繁情节挖掘方法研究D.东北大学,2010.9 杨杰,姚莉秀.数据挖掘技术及其应用M.上海:上海交通大学出版 社,2011,1:822.10 宋威,李晋宏,徐章艳,等.一种新的频繁项集精简表示方法及其挖掘算法的研究J.计算机研究与发展,2012,47(2):277285.11 陈光鹏,杨育彬,高阳,等.一种基于 MapReduce 的频繁闭项集挖掘算法水J.模式识别与人工智能,2012,25(2):220224.12 朱辉生,汪卫,施伯乐.基于频繁闭情节及其生成子的无冗余情节规则抽取J.计算机学报,2012,35(1):5363.13 朱辉生,汪卫,施伯乐.基于最小且非重叠发生的频繁闭情节挖掘J.计算机研究与发展,2013,50(4):852860.14 林树宽,乔建忠.一种基于情节矩阵和频繁情节树的情节挖掘方法J.控制与决策,2013,28(3):2225.15 袁红娟.BIDEFCE:一种基于双向扩展的频繁闭情节挖掘算法J.南京师范大学学报:工程技术版,2013,13(4):5156. 毕 业 设 计（论 文）开 题 报 告本课题要研究或解决的问题和拟采用的研究手段（途径）：(1) 本课题要研究或解决的问题本课题针对管理信息系统及决策支持系统中频繁出现的事件序列，研究事件序列上的频繁情节挖掘算法，并基于Java程序设计语言实现该算法，解决的问题包括： 设计并实现NONEPI算法，并用Java语言实现； 设计并实现NONEPI算法的改进算法，并用Java语言实现； 通过模拟和真实数据验证两个算法，进行验证和对比。(2) 拟采用的研究手段（途径） 采用面向对象程序设计（OOP）的编程思想，对算法涉及的类进行设计和封装。提高软件的重用性、灵活性和扩展性。 采用Eclipse 平台及Java语言实现该算法，充分利用Java开发工具（JDK）及Java语言提供的多线程机制、泛型等技术。 采用IBM数据合成器QUEST合成模拟数据，及南京理工大学泰州科技学院图书馆WEB服务器提供的真实数据集验证、对比算法。毕 业 设 计（论 文）开 题 报 告指导教师意见：1对“文献综述”的评语：阅读文献的数量达到15篇，文献综述内容具备一定的深度和广度，较为清楚地描述了课题的研究背景，介绍了频繁情节挖掘算法的研究现状及其优势和不足。文献综述写作规范，内涵丰富，符合文献综述的基本要求。2对本课题的深度、广度及工作量的意见和对设计（论文）结果的预测：