2014硕士论文开题报告模板

沈 阳 航 空 航 天 大 学 硕 士 学 位 论 文 开 题 报 告 题 目： 面向计数问题的公式发现 院 （部） 计算机学院 学 科、专 业 计算机技术 研 究 生 蔡东风（教授） 学 号 朱耀辉 导 师 20130603008 开题报告日期 2014.10.19 研究生学院制 1. 课题来源及研究的目的和意义 1.1 课题来源 发现科学规律，在人工智能领域一直是一个难点问题，由于本人对数学的喜好， 在老师的指导下，由实验室自定课题。 1.2 选题价值及意义 知识发现（KDD：Knowledge Discovery in Database）是从数据集中识别出有效的、 新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。知识发现将信息变为知 识。 知识发现的是十分广阔的。已经远远超出了最初的“货架子工程”。从工业到农 业，从天文到地理，从预测预报到决策支持，KDD 都发挥着越来越重要的作用。许 多计算机软件开发商都已经推出了其数据挖掘产品，如 IBM Microsoft，SPSS SGI，SLPInfoware ，SAS(ObjectBusiness)等。 在大数据时代，知识发现是从大量的、不完整的、有噪声的、模糊的和随机的数 据中，提取隐含在其中的、人们事先不知道的、但又是可信的、潜在的和有价值的信 息和知识的过程。本文课题是面向精准无噪声、小数据的知识发现，其发现的知识也 是以公式形式的知识，这是面向科学的知识发现。在科学知识的发现过程中，一般都 是科学家、工程师等用已知的科学知识和经验，经过复杂的推导和验证才发现出来。 这要耗费他们大量的时间。本文用基于数据驱动的方法，发现数据之间的规律，从而 指导科学知识的发现。 2. 国内外在该方向的研究现状及分析 知识发现的目的是向使用者屏蔽原始数据的繁琐细节，从原始数据中提炼出有意 义的、简洁的知识，直接向使用者报告。基于数据库的知识发现(KDD)和数据挖掘还 存在着混淆，KDD 是确定数据中有效的、新颖的、潜在有用的、基本可理解的模式 的特定过程。而数据挖掘可认为是观察数据中模式或模型的抽取，这是对数据挖掘的 一般解释。 知识发现的基本任务包括：数据分类、数据聚类、衰退和预报、关联和相关性、 顺序发现、描述和辨别、时间序列分析等任务；知识类型包括：广义型知识、分类型 知识、关联型知识、预测型知识、偏差型知识等；应用的技术有典型技术和创新技术 两大类。典型技术的基于算法的知识发现技术包括：或然性和最大可能性估计的贝叶 斯理论 、衰退分析、最近邻、决策树、K-方法聚类、关联规则挖掘 、Web 和搜索 全日制工学（工程）硕士学位论文开题报告 - 3 - 引擎、数据仓库和联机分析处理、神经网络、遗传算法、模糊分类和聚类、粗糙分类 和规则归纳等。创新技术基于可视化方法是在图形学、科学可视化和信息可视化等领 域发展起来的，包括：几何投射技术、基于图标技术、面向像素的技术、基于图表技 术、混合技术等。 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) 全日制工学（工程）硕士学位论文开题报告 - 5 - 系数 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 研究方案 通过分析得到如下的系统构思。系统主要有模式识别、启发式搜索模块、公式生 成验证模块。 输入数据 特征表示 分类器 模式求解公式生成 公式输出 错误分析 数据项 （ x ， y ） 函数库 选择 原型 精炼算子 公式 验证 循环控制 图 1.1 系统流图 1. 模式识别。此模块包括特征表示、分类器、模式求解三个子模块。 特征表示：提取给出的数字数据的特征。 分类器：得到模式类别。 模式求解：求解模式中的参数。 2. 启发式搜索模块。 精炼算子：分析已有数据项，产生新的数据项。 全日制工学（工程）硕士学位论文开题报告 - 7 - 错误分析：分析错误，为生成新数据提供信息。 函数选择模块：用误差分析信息选择函数产生新的数据项。 3. 公式生成验证模块。生成公式并验证所得公式是否完全拟合数据。 4.1.1 模式识别模块 分类器模块： 本文采用机器学习中的分类模型，使用一些经典的模型 NB、SVM 、KRL 等分类 模型，SVM 在分类效果上可能较好，但本文希望模型输出类别的概率，这样对类别 区分度不大的，都可以为他求解，居于这个原因也可以考虑 KRL 模型。有关模型的 训练数据，可以根据已经定义的模型，用计算机随机生成模型参数再产生训练数据。 模式定义： 1. 模式： 为 多 项 式)(,ngan 解决问题：n 个点完全图的边数、等差数列等。 2. 模式： 为 参 数,为 一 阶 多 项 式)(和*）n（f an 解决问题：等比数列等。 3. 模式： 2211*)( nnnn fafa为 一 阶 多 项 式)(和、 2 解决问题：斐波那契数列、卢卡斯数列、卡特兰数等。 4. 模式： 。）(21nnn afaf为 一 阶 多 项 式、 21 5. 模式： 。）(*） 21nnn为 一 阶 多 项 式、 21f 以上模式只是二元基本模式的一部分。模式一是多项式模式，在给定 N+1 测试 数据，只要多项式的阶不小于 N 就能满足要求，但阶数过高不一定符合真实情况， 本文提出最简多项式，即转为如下优化问题： （3） n0i2ma 1,432,1i，)(：St Nyxfi 上式中 n=N，n 的确定可以通过 的随 n 增大的变化规律来确定， n0imvala 者中规律是当设多项式的次数小于真实的多项式次数，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 预计目标 全日制工学（工程）硕士学位论文开题报告 - 9 - 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 研究”.计算机工程与设计.2010 4. 胡珉,吴耿锋,杨晶.”基于 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,8 13. Langley P.Rediscovering physics with Bacon.3. Proceedings of the Sixth International Joint Conference on Artificial Intelligence.1979,8 14. Langley P.Bacon:A production system that discovers empirical laws.Proceedings of the Fifth International Joint Conference on Artificial Intelligence.1977,8 15. 陈文伟等.经验公式发现系统 FDD1.小型微型计算机系统 .1999,2 16. 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: 007. 26. 27. 28. 毛峡, 丁玉宽 图像的情感特征分析及其和谐感评价 J 电子学报, 2001, 29(12A) 1923-1927 29. 刘国钧, 王连成图书馆史研究M 北京：高等教育出版社 , 1979: 15-50 30. 毛 峡 ， 绘 画 的 音 乐 表 现 A 中 国 人 工 智 能 学 会 2001 年 全 国 学 术 年 会 论 文 集 C 北京： 北京邮 电大学出版社, 2001: 739-740 31. 32. 33. 34. 35. 36. 5 号宋体，1 倍的行间距 全日制工学（工程）硕士学位论文开题报告 - 11 - 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 规定，对参考文献类型在文献题名后应该用方括号加以标引，以单 字母方式标志以下各种参考文献类型（见下表）： 参考 文献 期刊 文章 专著 论文 集 学位 论文 专利 标准 报纸 文章 报告 资料 汇编 其它 文献 5 号 Times New Roman，1 倍的行间距， 所有冒号、逗号和句号都 是英文的，后面加一个英 文空格。 类型 标志 J M C D P S N R G Z 4、电子文献类型标志 对于数据库、计算机程序及电子公告等电子文献类型的参考文献，用如下字母表 示（见下表）： 电子参考文献类型 数据库 计算机程序 电子公告 标志 DB CP EB 对于非纸张型载体的电子文献，当被应用为参考文献时需要在参考文献类型标志 中同时标明其载体类型，采用双字母表示电子文献载体类型： 磁带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 Contra