2014硕士论文开题报告模板.doc

全日制工学（工程）硕士学位论文开题报告沈阳航空航天大学硕士学位论文开题报告题 目： 面向计数问题的公式发现 院 （部） 计算机学院 学 科、专 业 计算机技术 研 究 生 蔡东风（教授） 学 号 朱耀辉 导 师 20130603008 开题报告日期 2014.10.19 研究生学院制1. 课题来源及研究的目的和意义1.1 课题来源发现科学规律，在人工智能领域一直是一个难点问题，由于本人对数学的喜好，在老师的指导下，由实验室自定课题。1.2 选题价值及意义知识发现（KDD：Knowledge Discovery in Database）是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。知识发现将信息变为知识。知识发现的是十分广阔的。已经远远超出了最初的“货架子工程”。从工业到农业，从天文到地理，从预测预报到决策支持，KDD都发挥着越来越重要的作用。许多计算机软件开发商都已经推出了其数据挖掘产品，如IBMMicrosoft，SPSSSGI，SLPInfoware，SAS(ObjectBusiness)等。在大数据时代，知识发现是从大量的、不完整的、有噪声的、模糊的和随机的数据中，提取隐含在其中的、人们事先不知道的、但又是可信的、潜在的和有价值的信息和知识的过程。本文课题是面向精准无噪声、小数据的知识发现，其发现的知识也是以公式形式的知识，这是面向科学的知识发现。在科学知识的发现过程中，一般都是科学家、工程师等用已知的科学知识和经验，经过复杂的推导和验证才发现出来。这要耗费他们大量的时间。本文用基于数据驱动的方法，发现数据之间的规律，从而指导科学知识的发现。2. 国内外在该方向的研究现状及分析知识发现的目的是向使用者屏蔽原始数据的繁琐细节，从原始数据中提炼出有意义的、简洁的知识，直接向使用者报告。基于数据库的知识发现(KDD)和数据挖掘还存在着混淆，KDD是确定数据中有效的、新颖的、潜在有用的、基本可理解的模式的特定过程。而数据挖掘可认为是观察数据中模式或模型的抽取，这是对数据挖掘的一般解释。知识发现的基本任务包括：数据分类、数据聚类、衰退和预报、关联和相关性、顺序发现、描述和辨别、时间序列分析等任务；知识类型包括：广义型知识、分类型知识、关联型知识、预测型知识、偏差型知识等；应用的技术有典型技术和创新技术两大类。典型技术的基于算法的知识发现技术包括：或然性和最大可能性估计的贝叶斯理论 、衰退分析、最近邻、决策树、K-方法聚类、关联规则挖掘 、Web和搜索引擎、数据仓库和联机分析处理、神经网络、遗传算法、模糊分类和聚类、粗糙分类和规则归纳等。创新技术基于可视化方法是在图形学、科学可视化和信息可视化等领域发展起来的，包括：几何投射技术、基于图标技术、面向像素的技术、基于图表技术、混合技术等。2.1. 知识发现的相关研究徐丽平，张俊卿，姜利群，赵亮等人一种新的基于知识库的知识发现系统，在知识库建立过程中，引入了本体的概念，充分挖掘了文档的语义信息，并以统一的格式描述知识即形成知识项存储于知识库中，为用户进行知识发现提供了一种新的数据存储方式。以此为基础构建了知识发现系统，系统通过友好的用户界面为用户提供知识发现服务，系统通过对用户的问题进行语义解析、推理机的推理以及语义映射等，从知识库中检索出用户满意的知识。杨立,左春,王裕国等人提出了一种新的面向服务的知识发现体系结构SOA4KD, 将用户的知识发现需求分为内容需求和质量需求，并提出了扩展的知识发现任务本体EKDTO，以自然语言的方式进行用户意图获取；在考虑到KDS的服务特性的前提下，充分分析了KDS自身的特点，提出了KDS质量本体KDSQO，采用元学习来进行选择最适合的KDS。相对于目前的体系结构，提出了为最终用户提供高质量知识发现服务的一些新方法和技术，为面向服务的知识发现系统设计与实现提供了一个新的参考模型。张新有，曾华燊，贾磊等人为了更好评价各种入侵检测算法的性能，指出了入侵检测数据集应当具备的特点。分析了两种有影响的入侵检测数据集：MIT LL入侵检测数据集和由此整理形成的KDD CUP99入侵检测数据集的特点及构成，重点分析了KDD CUP99训练数据集和测试数据集的各攻击类型及详细分布、数据集中每条连接的特征分类及其各个特征的含义，并对数据集的使用进行了说明。最后，对KDD CUP数据集存在的问题及相应改进措施给出了建议。2.2. 计算科学知识发现的相关研究在科学发展史上,各种物理学、化学、天文学中的自然规律都是著名科学家大量的实验数据进行深入的研究,最后得到了自然规律.如牛顿三大定律、万有引力定律、开普勒行星运行定律等.这些自然定律是科学发展和社会进步的奠基石.自然界存在着无数的规律，除了已被发现的外,还有很多规律需要人们去继续发现。在找到完全精确的规律性之前，一般用经验性规律(带有一定的误差)来代替。经验规律的发现一般是由有经验的工程师来完成的。随着人工智能技术的发展，机器发现技术得到发展。比较典型的系统有：科学定律发现系统BACON，数学概念发现系统AM、经验公式发现系统FDD。它们都造成了巨大的影响。BACON系统是运用人工智能技术从试验数据中寻找其规律比较成功的一个系统。是Patl Langly于1980年研制的。它运用数据驱动方法,即这种方法使用的规则空间与假设空间是分开的。系统的规则空间包括若干精炼算子,通过精炼算子修改假设。所谓精炼算子就是修改假设空间的子程序,每个精炼算子以特定的方式修改假设空间。整个学习程序由多个精炼算子组成,程序使用探索知识对提供的训练例进行分析,决定选用哪个精炼算子。这类学习方法的大致步骤为:（1） 收集某些训练例;（2） 对训练例进行分析,决定应该使用的精炼算子;（3） 使用选出的算子修改当前的假设空间。重复执行步骤1到步骤3直到取得满意的假设为止。BACON系统的思想是程序反复地考察数据并是用精炼算子创造新项,直到创造的这些项中有一个是常熟时为止。于是一个概念就用“项二常数”的形式表示出来,其中项为变量运算的组合而形成的表达式。经验公式发现系统FDD(Formula Discovery from Data)是应用人工智能的机器发现技术和数值计算中的曲线拟合技术以及可视化技术结合起来的系统。它是从大量实验数据中发现经验公式。逐步完成任意函数的任意组合(线性组合、初等运算组合、复合函数运算组合等)对自然规律和经验规律的发现。FDD系统是由国防科技大学研制的基于试验数据库的经验公式发现系统。FDD运用了人工智能中的启发式搜索方法和数据处理中的曲线拟合技术，通过对所提供原型之间的线性组合和一定程度的复合不断逼近试验数据，最终得到蕴藏在大量实验资料中的经验公式。FDD系统的基本思想是利用人工智能启发式搜索原型函数不断寻找具有最佳线性逼近关系的原型函数，并结合曲线拟合技术来求得数据间的规律性。FDD发现的经验公式是经过组合的初等函数，相对于高次多项式，由初等函数组合而成的公式更为直观地反映出实验数据之间的规律以及发展趋势。FDD.1系统的启发函数公式为：f(y)=a+bf(x)(1)系数a和b由最小二乘法经过拟合得出。线性逼近误差公式为：dt=(a+bf(x)-f(y)/ f(y) (2)在公式的搜索中,其基本原则是始终选取dt最小的f(x)作为继续搜索的当前结点进入下一次迭代,直到误差满足要求为止。胡珉,吴耿锋,杨晶在分析了基于遗传原理的公式发现方法的优势与不足的基础上，根据免疫原理和MHC(major histocompatibility complex)在免疫系统中的调控作用，提出了一种应用于公式发现领域的算法IFDA(immune formula discovering algorithm)来解决公式进化中优良结构不易保护的问题。该算法将公式翻译成树状图，并按深度优先的编码方法形成抗体的恒定区和可变区代码，把公式片段编码成为MHC代码，借鉴MHC调控原理指导抗体进化，寻找出数据集合中蕴涵的规律，并用公式的形式表示。通过对多组基准数据的实验说明，此方法在公式复杂度和收敛速度方面比基因表达式算法有更好的性能。陈金强，关永，刘瑾，宁婷等人提出一种基于FPGA的SoPC技术实现嵌入式经验公式发现系统的思想，通过对MicroBlaze处理器软核的配置及接口设计搭建硬件平台，并移植了uClinux 嵌入式操作系统，结合FDD算法，实现了基于FPGA的嵌入式FDD系统。Dzeroski S,Langley P,Todorovski L等人研究计算科学发现，通过研究科学家们发现科学知识的方式，了解科学发现方法，用计算机来发现计算科学知识。在面对数据挖掘与计算科学发现发展等明知识发现技术应用还不够成熟，Langley从已经出现的科学领域总结了一些教训。Schwabacher M,Langley P等人从时空数据发现可交互的科学知识，一般的机器学习的数据都是经验数据，当处理随着时间空间变化的数据时，经验数据就不一定有效，提出对时空数据的研究方法。Park C,Bridewell W,Langley P等人介绍了处理时空数据聚成的模型。3. 主要研究内容本课题研究是面向计数问题公式发现，是基于数字数据驱动的知识发现。在采纳现有公式发现系统方法基础上，并根据本课题的特点，从以下几个内容研究：模式库的构建、模式识别、模式求解、搜索。1. 模式库的构建：用人工定义的方式构建模式库。2. 模式识别：从观察数据中分析出其所属模式。3. 模式求解：求解模式中的参数。4. 搜索：在模式求解未成功时，怎样启发式的搜索。4. 研究方案及进度安排，预期达到的目标4.1 研究方案通过分析得到如下的系统构思。系统主要有模式识别、启发式搜索模块、公式生成验证模块。图1.1 系统流图1. 模式识别。此模块包括特征表示、分类器、模式求解三个子模块。 特征表示：提取给出的数字数据的特征。 分类器：得到模式类别。 模式求解：求解模式中的参数。2. 启发式搜索模块。 精炼算子：分析已有数据项，产生新的数据项。 错误分析：分析错误，为生成新数据提供信息。 函数选择模块：用误差分析信息选择函数产生新的数据项。3. 公式生成验证模块。生成公式并验证所得公式是否完全拟合数据。4.1.1 模式识别模块分类器模块：本文采用机器学习中的分类模型，使用一些经典的模型NB、SVM、KRL等分类模型，SVM在分类效果上可能较好，但本文希望模型输出类别的概率，这样对类别区分度不大的，都可以为他求解，居于这个原因也可以考虑KRL模型。有关模型的训练数据，可以根据已经定义的模型，用计算机随机生成模型参数再产生训练数据。模式定义：1. 模式：解决问题：n个点完全图的边数、等差数列等。2. 模式：解决问题：等比数列等。3. 模式：解决问题：斐波那契数列、卢卡斯数列、卡特兰数等。4. 模式：。5. 模式：。以上模式只是二元基本模式的一部分。模式一是多项式模式，在给定N+1测试数据，只要多项式的阶不小于N就能满足要求，但阶数过高不一定符合真实情况，本文提出最简多项式，即转为如下优化问题： （3）上式中n=N，n的确定可以通过的随n增大的变化规律来确定，者中规律是当设多项式的次数小于真实的多项式次数，fval的值随着n的变大显著变小；当设多项式的次数符合真实的多项式次数，评价函数fval的值随着n的变大变化很微小。在确定多项式系数时，本文不是做上述一次优化，而是用多次迭代的方法求解，描述如下：1. A为多项式系数数组，i=n，置A=。2. a=fminv(i,x,y)。3. 若i+1=N，则Aj=aj(j=0,1.i)，转到5。4. c =ai，c=roundn(c,k)，Ai=c，yj=yj-c*exp(xj,i)(j=1,2.N)，i=i-1；如果i+1N,转到2。5. 结束。a=fminv(i,x,y)为(3)式的求解。roundn(c,k)为c保留k位小数。由于本文研究数据范围是整数，所以k=0，即保留到整数。当n=Na的方法求解，余下的测试数据作为验证，若验证不成功，则逐次增加Na的数量继续用这种方法求解直到验证成功。基本模式能求解部分公式，但还是有很多公式不能求解，一种方法就是定义基本模式组合模式；还有一种方法就是把它转化为多次基本模式求解，这种方法可以多次使用基本模式，解决了人工用枚举的方法定义组合模式，但这种方法很难实现。首先需要解决的问题就是定性的分析目标公式的成分；其次，就是能够给出各个成分量的关系。4.1.2 启发式搜索模块初步借鉴Bacon系统和FDD系统的方法。4.2 预计目标1. 对数据中蕴含的公式成分进行较好的分析。2. 用已经定义的模式产生的数据进行测试，都能够精确的求解。3. 用启发式的方法能够求解未定义的模式。4. 尝试用该系统发现一些新的公式。4.3 研究计划进度1）2014年9月2014年10月：搜集资料，阅读文献，调研开题。 2）2014年11月2014年12月：对公式进行分析，将公式进行归类。3）2015年1月2015年3月：能够用模式方法求解，并融合其他方法。 4）2015年4月2015年8月：对融合方法进行优化。5）2015年8月2015年10月：搭建毕业系统，进行完善。 6）2015年11月2016年1月：撰写毕业论文。参考文献1. 徐丽平,张俊卿,姜利群,赵亮.“基于知识库的知识发现的研究”.计算机工程与设计.2008.2. 杨立,左春,王裕国.”面向服务的知识发现体系结构研究与实现”.计算机学报.2005.3. 张新有，曾华燊，贾磊.“入侵检测数据集KDD CUP99 研究”.计算机工程与设计.20104. 胡珉,吴耿锋,杨晶.”基于 MHC 调控的免疫公式发现算法”.软件学报.2008.5. 陈金强，关永，刘瑾，宁婷.”基于MicroBlaze的公式发现系统研究”.计算机工程与设计.2009.6. Dzeroski S,Langley P,Todorovski L. Computational discovery of scientific knowledge. Computational discovery of communicable scientific knowledge. 2007.7. Schwabacher M,Langley P.Discovering communicable scientific knowledge from spatio-temporal data. Computational discovery of communicable scientific knowledge.2007.8. Park C, Bridewell W,Langley P.Integrated systems for inducing spatio-temporal process models. Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence.2007.9. Langley P, Zytkow J M.Data-driven approaches to empirical discovery.Artificial Intelligence.1990,2 10. Langley P, Bradshaw G L,Simon H A.Heuristics for empirical discovery. Computational models of learning.1987,8.11. Langley P, Bradshaw G L,Simon H A.Rediscovering chemistry with the Bacon system.Machine learning: An artificial intelligence approach. 12. Langley P, Bradshaw G L,Simon H A.Bacon.5: The discovery of conservation laws. Proceedings of the Seventh International Joint Conference on Artificial Intelligence.1981,813. Langley P.Rediscovering physics with Bacon.3. Proceedings of the Sixth International Joint Conference on Artificial Intelligence.1979,814. Langley P.Bacon:A production system that discovers empirical laws.Proceedings of the Fifth International Joint Conference on Artificial Intelligence.1977,815. 陈文伟等.经验公式发现系统FDD1.小型微型计算机系统.1999,216. J Zhu,T Hastie. ” Kernel logistic regression and the import vectormachine ”.Advances in Neural Information Processing Systems.2001.17. S S Keerthi,K Duan,S K Shevade and A N Poo. ” A Fast DualAlgorithm for Kernel Logisic Regression ”, Machine Learning.2005.18. P Karsmakers,K Pelckmans,J A K Suykens.”Multi-classkernel logistic regression: a fixed-size implementation”.Accepted for publication in Proc. of IJCNN.2007.19. Karsmakers P,Pelckmans K,Suykens J A K,Van hamme H. Fixed-Size Kernel Logistic Regression for Phoneme Classification .INTERSPEECH.2007,8.20. Elisseeff A, Weston J. A kernel method for multi-labelled classificationC/Advances in neural information processing systems. 2001: 681-687.21. Zhang M L, Pea J M, Robles V. Feature selection for multi-label naive Bayes classificationJ. Information Sciences, 2009, 179(19): 3218-3229.22. Zhang M L, Zhou Z H. ML-KNN: A lazy learning approach to multi-label learningJ. Pattern recognition, 2007, 40(7): 2038-2048.23. Zhang M L, Zhou Z H. Multi-label neural networks with applications to functional genomics and text categorizationJ. Knowledge and Data Engineering, IEEE Transactions on, 2006, 18(10): 1338-1351.24. 葛雷, 李国正, 尤鸣宇.多标记学习的嵌入式特征选择J. 南京大学学报: 自然科学版, 2009, 45(5): 671-676.25. 邵欢, 李国正, 刘国萍,等.多标记中医问诊数据的症状选择J. 中国科学: 信息科学, 2011, 11: 008. 毛峡, 丁玉宽 图像的情感特征分析及其和谐感评价J 电子学报, 2001, 29(12A) : 1923-192729. 刘国钧, 王连成图书馆史研究M 北京：高等教育出版社, 1979: 15-5030. 毛峡，绘画的音乐表现A 中国人工智能学会2001年全国学术年会论文集C 北京：北京邮电大学出版社, 2001: 739-74031. 5号宋体，1倍的行间距32. 33. 34. 35. 36. 5号Times New Roman，1倍的行间距，所有冒号、逗号和句号都是英文的，后面加一个英文空格。37. Chen S, Billing S A, Cowan C F, et al. Practical identification of MARMAX models. Int J Contral,1990,52(6):1327-1350附：参考文献书写格式要求（不打印） 按照国家标准文后参考文献著录规则GB7714-87和中国博硕士学位论文编写与交换格式，建议研究生学位论文参考文献著录及标引采用下述内容和方式： 1、著录标准 （1）排列次序：依据在正文中被首次引用的先后次序列出各条参考文献。 （2）具体要求：项目齐全，内容完整，顺序正确，标点无误。 （3）注意事项： a、只有3位及3位以内作者的，其姓名全部列上，中外作者一律姓前名后，外国作者第一个字母大写； b、共有三位以上作者的，只列前3位，其后加“，等”或“，et al”； c、外文文献中表示缩写的实心句点“.”一律略去； d、原本就缺少某一项目时，可将该项连同与其对应的标点符号一起略去； e、页码不可省略，起止页码之间用“-”相隔，不同的引用范围之间用“，”相隔。 2、著录范围 非纸张型电子文献应注明载体类型。 其它性质的资料可作为正文的随文脚注。 3、参考文献类型及其标志 根据GB3469规定，对参考文献类型在文献题名后应该用方括号加以标引，以单字母方式标志以下各种参考文献类型（见下表）：参考文献类型期刊文章专著论文集学位论文专利标准报纸文章报告资料汇编其它文献标志JMCDPSNRGZ 4、电子文献类型标志对于数据库、计算机程序及电子公告等电子文献类型的参考文献，用如下字母表示（见下表）：电子参考文献类型数据库计算机程序电子公告标志DBCPEB 对于非纸张型载体的电子文献，当被应用为参考文献时需要在参考文献类型标志中同时标明其载体类型，采用双字母表示电子文献载体类型： 磁带MT；磁盘DK；光盘CD；联机网络OL。 以下格式表示包括了文献载体类型的参考文献类型标示：电子文献类型/载体类型标示，如： DB/OL 联机网上数据库； DB/MT 磁带数据库； M/CD 光盘图书； CP/DK 磁盘软件； J/OL 网上期刊； EB/OL 网上电子公告。参考文献的著录范围示例见下表。序号文献类型格 式 示 例学术 期刊 序号 作者.题名.刊名，出版年份，卷号(期号)：起页-止页1 高景德，王祥珩.交流电机的多回路理论J.清华大学学报，1987，27(1)：1-8(完整)2 高景德，王祥珩.交流电机的多回路理论J.清华大学学报，1987(1)：1-8(缺卷)3 Chen S, Billing S A, Cowan C F, et al. Practical identification of MARMAX models. Int J Contral,1990,52(6):1327-1350(完整的)2学术