吉首大学大学生研究性学习和创新性实验计划项目申请书.doc

附件1：吉 首 大 学大学生研究性学习和创新性实验计划项目申 请 书学 院 名 称 数学与计算机科学学院 计划项目名称 基于密度的聚类算法研究 _计划项目负责人 彭 浩 所 在 专 业 信息与计算科学 所 在 年 级 08级 联 系 电 话电 子 邮 件 124898764 导 师 姓 名 段明秀 _导 师 职 称 讲 师 _填 写 日 期 2011-4-20 吉首大学教务处制填写说明及注意事项一、申报书逐项认真填写，填写内容必须实事求是，表达明确严谨。空缺项要填“无”。二、表格中的字体小四号仿宋体，1.5倍行距；需签字部分由相关人员以黑色钢笔或水笔签名。均用A4 纸双面打印，于左侧装订成册。三、大学生研究性学心和创新实验项目是本科学生个人或创新团队在导师指导下，自主进行研究性学习，自主进行实验方法的设计、组织设备和材料、实施实验、调查、分析处理数据、撰写总结报告等工作。四、项目实施原则：参与计划的学生要对科学研究或创造发明有浓厚的兴趣，并在导师指导下完成实验过程；参与学生要自主设计实验、自主完成实验、自主管理实验；注重创新性实验项目实施过程，强调项目实施过程中学生在创新思维和创新实践方面的收获。五、参与大学生创新性实验项目的学生不超过5人，项目执行时间为1-2年。六、指导老师应具有讲师以上职称，每个指导老师指导的项目数不超过2项。七、计划项目必须先由导师提出意见、由所在学院审核后再推荐上报。推荐上报的计划项目表一式三份（均为原件）报送教务处，同时提交电子文档。项目名称基于密度的聚类算法研究项目主持人彭浩学号20084043032班级08信计年级08级电Q124898764项目组其他成员学生姓名性别学院名称专业年级联系电话合作者签名杨亚龙男数学与计算机科学学院信息与计算科学08勇男数学与计算机科学学院信息与计算科学08超林女数学与计算机科学学院信息与计算科学09永胜男数学与计算机科学学院信息与计算科学09导教师情况姓名段明秀性别女民族汉出生年月1975.5职称讲师专业计算机应用研究方向数据挖掘、神经网络手机号-mailD指导老师签名一、前期基础（500字以内） 项目组成员均来自吉首大学数学与计算机科学学院的大二、大三的信息与计算科学专业，已系统进行过数学理论方法训练（尤其针对数值计算，信息论，数学建模等），曾获得过校级数学建模大赛的三等奖，为设计高效聚类算法打下了扎实的数学基础。计算机方面，已熟练掌握了C、C+ 、JAVA，matlab(数学工具软件)等语言，并且在数据结构、算法设计、框架构造等方面也有一些经验积累，对算法的优化与测试具备良好的计算机基础。项目组成员均具有良好的程序设计基础及扎实的数学功底，并且对编程及算法研究具有浓厚的兴趣。多名成员已通过英语4、6级考试，具备了较强的英语读写能力，能够阅读相关的外文文献。项目指导老师在相关领域从事了多年的教学和科研工作，比较全面的掌握了数据挖掘领域的相关文献和研究现状，并已经在聚类算法领域进行了较为深入的研究，取得了一些研究成果。在项目指导老师的积极指导与督促下，项目组成员已阅读了大量的相关国内外文献，对聚类算法特别是基于密度的聚类算法有了一定的知识积累，对聚类算法的发展历程和最新发展趋势有一定了解，对算法的评价标准有了更深刻的认识。二、项目立论依据（2000字以内）1项目研究目的和意义数据挖掘是从海量数据中以高度精确和高度可靠的手段挖掘和产生新的知识，这些新的知识将为决策者提供有力的科学决策依据。数据挖掘涉及多学科技术，包括数据库技术、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理和空间数据分析等。已在医学、电信、零售业等科学或商业领域得到了成功应用。聚类分析是数据挖掘领域中一个非常活跃的研究课题，它应用于统计学、机器学习、空间数据库、生物学以及市场营销等领域，应用于各个领域的聚类算法非常多。针对各行业不同的应用，目前己经提出了大量的聚类算法。这些算法在速度、效率、可伸缩性、处理能力、准确度等方面有了不同程度的改进。聚类算法的聚类效果受数据集的分布情况影响很大，有的算法只能辨识凸形簇，有的算法不能很好的处理数据中的离群点，有的算法的时间效率不能满足大数据集的聚类要求等等，然而，现实中的数据集很多并不是凸形分布。基于密度的聚类方法的研究解决了这个问题，基于密度的聚类算法通过寻找密度连通区域来辨识任意形状的簇。通过密度聚类，人们能够识别密集的和稀疏的区域，从而发现全局的分布模式，以及数据属性之间的有趣的相互关系。在商务上，密度聚类能帮助市场分析人员从客户基本信息库发现不同的客户群，并且用购买模式来刻画不同的客户群特征。在生物学上，密度聚类能用于推导植物与动物的分类，对基因进行分类，获得对种群固有结构的认识。密度聚类在地球观测数据库中对相似地区的确定，汽车保险持有者的分组，以及根据房屋的类型，价值和地理位置对一个城市中房屋的分组上也可以发挥作用。但一些经典的基于密度的聚类算法存在一些不足，比如时间性能，对于密度分布不均数据集聚类效果差等，科研者对这些问题也进行了深入的研究，通过一些方法来改善基于密度的聚类算法存在的问题。基于密度的聚类方法在实际中有广泛的应用，因此，对于基于密度的聚类算法的研究是很有理论和实际意义的。2国内外研究现状基于密度的聚类方法是聚类算法中一项研究重点，该方法是通过度量区域中所包含的对象数目来进行聚类的，经典的基于密度的方法主要有DBSCAN和 OPTIC。1996年，Ester等提出了DBSCAN，该算法具有将高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的簇。DBSCAN存在一些不足，科研者以DBSCAN为基础研究了一系列的改进算法。 J.orgsander， MartinEste以DBSCAN为基础提出了用于多维空间数据库聚类的基于密度的空间聚类算法GDBSCAN。刘宗田等提出了可以用于大型空间数据库的基于数据分区的并行DBSCAN算法。陈治平、王雷提出了基于密度梯度的聚类算法，通过分析数据样本及其周边的点密度变化情况，选择沿密度变化大的方向寻找不动点，以获得聚类中心，然后利用边界点的分布对类进行合并。1999年Ankerst等提出了OPTIC聚类排序方法。算法生成代表基于密度的聚类结构的一个参数化的数据库的排序，通过这种排序包含的信息及参数设置可以得到与基于密度聚类相同的聚类结果。陈燕俐，朱梧橙在DBSCAN和OPITC的基础上在提出一种简单有效的基于密度的聚类算法，该算法给出了一种简单且效率较高的邻域查询方法一哈希表法，对整个数据集合或部分数据做网格化处理。3主要参考文献 1Jiawei Han，Micheline Kamber著范明，孟小峰等译数据挖掘概念与技术北京：机械工业出版社，2004.1-262 2Anil K.Jain，Richard C.DubesAlgorithms for Clustering DataPrentice Hall，19881-334 3Pang Ning Tan，Michael Steinbach，Vipin KumarIntroduction to Data MiningPosts & Telecom Press，2004132-212 4Paolo Giudici著袁方，王煜，王丽娟等译实用数据挖掘 北京：电子工业出版社，20031-232 5Margaret HDunham著郭崇慧，田凤占等译数据挖掘教程北京：清华大学出版社，20041-201 6Mehmed Kantardzic著闪四清，陈茵，程雁等译数据挖掘-概念、模型、方法和算法北京：清华大学出版社，20031-5 7 C.M. Bishop and M.E. TippingA Hierarchical Latent Variable Model for Data VisualisationIEEE TPAMI3，1998(20):281-293 8田盛丰，黄厚宽人工智能与知识工程长沙：中国铁道出版社，1999123 9C. WilliamsA MCMC Approach to Hierarchical Mixture Modelling Advances in NIPS，2000(1):680-686 10 C. FraleyAlgorithms for Model-Based Hierarchical ClusteringSIAM J. Sci. Comput，1998(1)：279-281 11 David PollardStrong Consistency of Kmeans ClusteringAnnals of Statistics，1981(9)：135-140 12刘同明数据挖掘技术及其应用长沙：国防工业出版社，20011-65 13张颖数据采掘的研究与应用：博士学位论文北京：中国科学院计算技术研究所，1999 14Fayyad UMining Databases：Towards algorithm for konwledge discoveryIEEE Bulletin of the Technical Committee on Data Engineering，1998，21(1)：39-48 15Fayyad U，Piatesky Shapiro G，Smyth PThe KDD process for extracting useful knowledge form volumes of dataCommunication of the ACM，1996，39(11)：27-35 16Fayyad U，Piatetsky Shapiro et alFrom data mining to knowledge discovery： An overviewAdvances in Knowledge Discovery and Data Mining. Menlo Park，CA： AAAI/MIT Press，199634-56 17 陈燕俐，洪龙，金达文等一种简单有效的基于密度的聚类分析算法南京邮电学院学报，200525(4)：24-29 18 谷淑化，吕维先，马于涛关于数据挖掘中聚类分析算法的比较现代计算机： 2005（3）：26-29 19 汤效琴，戴汝源数据挖掘中聚类分析的技术方法微计算机信息，2003（19）：3-4 20 黄修丹数据挖掘领域中的聚类分析及应用闽江学院学报，2004（25）：44-47 21 赵法信，王国业数据挖掘中聚类分析算法研究通化师范学院学报，2005（26）：11-13 22 http：//post/20871/156213三、项目实施方案（2500字以内）1项目研究目标、研究内容和拟解决的关键问题在各研究成员的兴趣驱动以及指导老师的认真耐心指导下，通过对基于密度的聚类算法研究与实现，自主管理自主完成项目的研究，注重在项目的实施过程中对各成员的创新思维培养和对问题的剖析能力进行有意识的锻炼，并期望在对现有算法实现的基础上，进一步对算法进行优化。研究目标：(1)鉴于基于密度的聚类算法中所存在的密度函数计算效率不高以及对参数十分敏感两个问题，进行深入的研究与分析，通过改进算法，并对其进行优化提高密度函数的计算效率，并实现对参数的一般化，使算法实现更有效，更可行。(2)选择一些经典实例解析，针对实际问题运用基于密度的聚类算法进行解答，用程序流程图把解题过程表示出来，编程实现，提高分析问题，解决问题的能力。(3)借助各种工具和已经写好的代码和数据结构中所学的知识，检验改进后算法的效率、分析算法的时间复杂度和空间复杂度。(4)将基于密度的聚类算法应用到具体的应用领域。研究内容：（1）聚类分析前对数据预处理方法的研究。（2）列举目前常用的基于密度的聚类算法，并对算法进行详细的描述和分析。指出各算法的适用领域及局限性。（3）重点研究经典的DBSCAN算法、OPTICS算法、DENCLUE算法（算法思想、算法缺陷、算法改进、算法实现、算法性能分析）并进行编程实现。（4）就其中的某种算法的缺陷进行改进。拟解决的关键问题：(1)对基于密度的聚类算法中的经典算法分进行分析，从而对算法进行改进与优化，并提出自己的见解与想法。(2)分析算法的时间复杂度和空间复杂度。(3)通过对算法的研究与实现，注重在项目的实施过程中对各成员的创新思维和分析解决问题能力的培养。(4)运用基于密度的聚类算法解决实际问题。2拟采取的研究方法、技术路线、实验方案及可行性分析 采取理论与实践相结合的研究方法。先从理论上对基于密度的聚类算法中的经典算法进行时间和空间复杂度分析，并针对某种算法的缺陷，从理论上提出改进方案，算法拟采用c语言实现，并用matlab进行仿真,通过对比试验，从聚类的正确性、精度、算法执行时间、参数设置、数据输入顺序、数据及密度等方面对算法进行测试、分析、评价。 3本项目的创新之处 (1) 对目前常用的基于密度的聚类算法进行比较和分析，比较各种算法的优缺点。 (2) 针对现有算法的不足，提出改进方法。 (3) 结合具体的应用环境，从可行性和执行效率角度考察改进算法的实际应用价值。4项目研究计划及预期进展 第一阶段：（2011年6月2011年8月） 全面搜集相关书籍、文献资料、网络资料数据。 学习相关科研知识、科研技能，提高科研基本素质。 对已搜集的文献资料数据进行汇总、整理与筛选。第二阶段：（2011年9月2012年2月） 根据基于密度的聚类算法的基本原理，对基于密度的聚类算法进行详细的描述。并借助各种文献、材料，以及前辈的总结与经验，借助我们对基于密度的聚类算法的了解。对基于密度的聚类算法进行改进与优化，并提出自己的见解。第三阶段：（2012年2月2012年4月）总结所得的分析结果，结合对一些实际问题的分析、解答，把改进的基于密度的聚类算法以伪码的形式写出。同时对算法中的数据结构、所用函数进行说明，并绘制程序流程图，随后分析改进后算法的时间复杂度和空间复杂度，并与原算法进行比较。最后用Visual C+ 6.0 编程实现该算法。第四阶段：（2012年5月2012年6月）通过做各种对比试验对基于密度的聚类算法的正确性、精度、参数设置、数据输入顺序以及数据密度等进行对比分析，对改进的基于密度的聚类算法进行测试、评估。选出最优的、可行性法案，并认真完成项目论文5项目研究的预期成果 通过团队成员的分工合作，艰苦探索，辛勤研究，搜集各种资料，借鉴别人的经验与所得，可达到以下预期成果:(1)在省级以上学术刊物上公开发表1-2篇与该课题相关的学术论文；(2)增强项目组成员独立思考，团结合作的能力，激发探究新知的兴趣，培养良好的科学素养。(3)提高团体合作能力，为今后的学习和科研项目开发提供坚实的知识基础。 （4）进行课题总结，形成总结报告。四、项目保障机制（800字以内）1经费预算及经费使用计划经费开支项目经费预算（万元）用途简要说明资料费0.3用于购买或复印一些相关书籍和文献学术交流费0.4同相关领域专家进行学术交流论文版面费0.2发表项目论文所需的版面费和审稿费存储设备0.1购买移动硬盘等设备存储程序与论文总计（万元）12条件保障（实验室、设备、场地、设施等具体情况） 学院及学校领导十分支持该项目研究，我院将向参与项目的学生免费提供专业教室和专业教学仪器设备等。课题组成员都来