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

1、附件1:吉首大学大学生研究性学习和创新性实验计划项目申请书学院名称数学与计算机科学学院计划项冃名称 基于密度的聚类算法研究计划项目负责人彭浩所在专业信息与计算科学所在年级08级联系电子邮件124898764qq. com导师姓名段明秀师职称讲师填写n期2011-4-20吉首大学教务处制填写说明及注意事项一、申报书逐项认真填写，填写内容必须实事求是，表达明确严 谨。空缺项要填“无”。二、表格中的字体小四号仿宋体，1.5倍行距；需签字部分由相 关人员以黑色钢笔或水笔签名。均用a4纸双面打印，于左侧装订成 册。三、大学生研究性学心和创新实验项目是本科学生个人或创新团 队在导

2、师指导下，自主进行研究性学习，自主进行实验方法的设计、 组织设备和材料、实施实验、调查、分析处理数据、撰写总结报告等 工作。四、项目实施原则：参与计划的学生要对科学研究或创造发明有 浓厚的兴趣，并在导师指导下完成实验过程；参与学生要自主设计实 验、自主完成实验、自主管理实验；注重创新性实验项目实施过程， 强调项目实施过程中学生在创新思维和创新实践方面的收获。五、参与大学生创新性实验项目的学生不超过5人，项目执行时 间为1-2年。六、指导老师应具有讲师以上职称，每个指导老师指导的项目数 不超过2项。七、计划项目必须先由导师提出意见、由所在学院审核后再推荐 上报。推荐上报的计划项目表一式三份（均为

3、原件）报送教务处，同 时提交电子文档。项目名称基于密度的聚类算法研究项目主持人彭浩学号20084043032班级08信计年级08级电q124898764项 b 组 其 他 成 员学生姓 名性别学院名称专业年级联系电话合作者 签名杨亚龙男数学与计算机 科学学院信息与计算 科学08勇男数学与计算机 科学学院信息与计算 科学08超林女数学与计算机 科学学院信息与计算 科学09永胜男数学与计算机 科学学院信息与计算 科学09导教师情况姓名段明秀性别女民族汉出牛年月1975.

4、 5职称讲师专业计算机应 用研究方向数据挖掘、神经网络手机号e-mai 1 duanmxqtil26. com指导老师签名一、前期基础（500字以内）项目组成员均来自吉首大学数学与计算机科学学院的大二、大三的信息与计算科学专 业，已系统进行过数学理论方法训练（尤其针对数值计算，信息论，数学建模等），曾获 得过校级数学建模大赛的三等奖，为设计高效聚类算法打下了扎实的数学基础。计算机方 面，已熟练掌握了 c、c+、java, matlab（数学工具软件）等语言，并且在数据结构、算 法设计、框架构造等方面也有一些经验积累，对算法的优化与测试具备良好的计算机基础。 项目组成员

5、均具有良好的程序设计基础及扎实的数学功底，并且对编程及算法研究具有浓 厚的兴趣。多名成员已通过英语4、6级考试，具备了较强的英语读写能力，能够阅读相关 的外文文献。项目指导老师在相关领域从事了多年的教学和科研工作，比较全面的掌握了数据挖掘 领域的相关文献和研究现状，并已经在聚类算法领域进行了较为深入的研究，取得了一些 研究成果。在项目指导老师的积极指导与督促下，项目组成员已阅读了大量的相关国内外文献， 对聚类算法特别是基于密度的聚类算法有了一定的知识积累，对聚类算法的发展历程和最 新发展趋势有一定了解，对算法的评价标准有了更深刻的认识。二、项目立论依据（2000字以内）1. 项目研究目的和意义

6、数据挖掘是从海量数据中以高度精确和高度可靠的手段挖掘和产生新的知识，这些 新的知识将为决策者提供有力的科学决策依据。数据挖掘涉及多学科技术，包括数据库 技术、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、信息检索、 图像与信号处理和空间数据分析等。已在医学、电信、零售业等科学或商业领域得到了 成功应用。聚类分析是数据挖掘领域中一个非常活跃的研究课题，它应用于统计学、机器学习、 空间数据库、生物学以及市场营销等领域，应用于各个领域的聚类算法非常多。针对各 行业不同的应用，目前己经提出了大量的聚类算法。这些算法在速度、效率、可伸缩性、 处理能力、准确度等方面有了不同程度的改进。聚类

7、算法的聚类效果受数据集的分布情 况影响很大，有的算法只能辨识凸形簇，有的算法不能很好的处理数据中的离群点，有 的算法的时间效率不能满足大数据集的聚类要求等等，然而，现实中的数据集很多并不 是凸形分布。基于密度的聚类方法的研究解决了这个问题，基于密度的聚类算法通过寻 找密度连通区域来辨识任意形状的簇。通过密度聚类，人们能够识别密集的和稀疏的区 域，从而发现全局的分布模式，以及数据属性之间的有趣的相互关系。在商务上，密度 聚类能帮助市场分析人员从客户基本信息库发现不同的客户群，并且用购买模式来刻画 不同的客户群特征。在生物学上，密度聚类能用于推导植物与动物的分类，对基因进行 分类，获得对种群固有结

8、构的认识。密度聚类在地球观测数据库中对相似地区的确定， 汽车保险持有者的分组，以及根据房屋的类型，价值和地理位置对一个城市中房屋的分 组上也可以发挥作用。但一些经典的基于密度的聚类算法存在一些不足，比如时间性能, 对于密度分布不均数据集聚类效果差等，科研者对这些问题也进行了深入的研究，通过 一些方法来改善基于密度的聚类算法存在的问题。基于密度的聚类方法在实际中有广泛 的应用，因此，对于基于密度的聚类算法的研究是很有理论和实际意义的。2. 国内外研究现状基于密度的聚类方法是聚类算法中一项研究重点，该方法是通过度量区域中所包含 的对象数目来进行聚类的，经典的基于密度的方法主要有dbscan和opt

9、ic。1996年， ester等提出了 dbscan,该算法具有将高密度的区域划分为簇，并可以在带有“噪声” 的空间数据库中发现任意形状的簇。dbscan存在一些不足，科研者以dbscan为基础研 究了一系列的改进算法。j.orgsander, martineste以dbscan为基础提出了用于多维 空间数据库聚类的基于密度的空间聚类算法gdbscan.刘宗田等提出了可以用于大型空 间数据库的基于数据分区的并行dbscan算法。陈治平、王雷提出了基于密度梯度的聚 类算法，通过分析数据样本及其周边的点密度变化情况，选择沿密度变化大的方向寻找 不动点，以获得聚类中心，然后利用边界点的分布对类进行合

10、并。1999年ankerst等提 出了 optic聚类排序方法。算法生成代表基于密度的聚类结构的一个参数化的数据库的 排序，通过这种排序包含的信息及参数设置可以得到与基于密度聚类相同的聚类结果。 陈燕俐，朱梧橙在dbscan和opitc的基础上在提出一种简单有效的基于密度的聚类算 法，该算法给出了一种简单且效率较高的邻域查询方法一哈希表法，对整个数据集合或 部分数据做网格化处理。3. 主要参考文献1 jiawei han, micheline kamber著.范明，孟小峰等译.数据挖掘概念与技术.北 京：机械工业出版社，2004. 1-2622 ani 1 k. jain, richard c

11、. dubes algorithms for clustering data prentice hall, 1988. 1-3343 pang ning tan , michael steinbach , vipin kumar . introduction to data mining. posts & telecom press, 2004. 132-2124 paolo giudici著.袁方，王煜，王丽娟等译.实用数据挖掘.北京：电子工业出 版社，2003. 1-2325 margaret h. dunham著.郭崇慧，田凤占等译.数据挖掘教程.北京：清华大学出 版社，2004

12、. 1-2016 mehmed kantardzic著闪四清，陈茵，程雁等译.数据挖掘一概念、模型、方法和 算法.北京：清华大学出版社，2003. 1-57 c. m. bishop and m. e. tipping. a hierarchical latent variable model for datavisualisation. ieee tpami3, 1998 (20): 281-2938 田盛丰，黄厚宽.人工智能与知识工程.长沙：中国铁道出版社，1999. 1239 c. williams. a mcmc approach to hierarchical mixture mod

13、el 1ing. advances in nips, 2000 (1): 680-68610 c. fraley. algorithms for model-based hierarchical clustering. siam j. sci. comput, 1998(1): 279-28111 david pol lard. strong consistency of kmeans clustering. annals of statistics, 1981 (9): 1 35-14012 刘同明.数据挖掘技术及其应用.长沙：国防工业出版社，2001. 1-6513 张颖.数据采掘的研究与

14、应用：博士学位论文.北京：中国科学院计算技术研究 所，199914 fayyad u. mining databases： towards algorithm for konwledge discovery. ieee bulletin of the technical committee on data engineering, 1998, 21 (1)： 39-4815 fayyad u, piatesky shapiro g, smyth p. the kdd process for extracting useful knowledge form volumes of data. co

15、mmunication of the acm, 1996, 39 (11): 27-3516 fayyad u, piatetsky shapiro et al. from data mining to knowledge discovery: an overview- advances in knowledge discovery and data mining. menlo park, ca： aaai/mit press, 1996. 34-5617 陈燕俐，洪龙，金达文等.一种简单有效的基于密度的聚类分析算法.南京邮电 学院学报，2005. 25 (4): 24-2918 谷淑化，吕维

16、先，马于涛关于数据挖掘中聚类分析算法的比较现代计算机：2005 (3): 26-2919 汤效琴，戴汝源.数据挖掘中聚类分析的技术方法.微计算机信息，2003 ( 19 ): 3-420 黄修丹.数据挖掘领域中的聚类分析及应用闽江学院学报，2004 ( 25 ): 44-4721 赵法信，王国业.数据挖掘中聚类分析算法研究.通化师范学院学报，2005 ( 26 ): 11-1322 http： / /156213三、项目实施方案（2500字以内）1. 项目研究目标、研究内容和拟解决的关键问题在各研究成员的兴趣驱动以及指导老师的认真耐心指导下，通过对基于密度的聚类 算法研究与实现，自主管理自主完

17、成项目的研究，注重在项目的实施过程中对各成员的 创新思维培养和对问题的剖析能力进行有意识的锻炼，并期望在对现有算法实现的基础 上，进一步对算法进行优化。研究目标：(1) 鉴于基于密度的聚类算法中所存在的密度函数计算效率不高以及对参数十分敏 感两个问题，进行深入的研究与分析，通过改进算法，并对其进行优化提高密度函数的 计算效率，并实现对参数的一般化，使算法实现更有效，更可行。(2) 选择一些经典实例解析，针对实际问题运用基于密度的聚类算法进行解答，用 程序流程图把解题过程表示出来，编程实现，提高分析问题，解决问题的能力。(3) 借助各种工具和已经写好的代码和数据结构中所学的知识，检验改进后算法的

18、 效率、分析算法的时间复杂度和空间复杂度。(4) 将基于密度的聚类算法应用到具体的应用领域。研究内容：(1) 聚类分析前对数据预处理方法的研究。(2) 列举目前常用的基于密度的聚类算法，并对算法进行详细的描述和分析。指 出各算法的适用领域及局限性。(3) 重点研究经典的dbscan算法、optics算法、denclue算法(算法思想、算法 缺陷、算法改进、算法实现、算法性能分析)并进行编程实现。(4) 就其中的某种算法的缺陷进行改进。拟解决的关键问题：(1) 对基于密度的聚类算法中的经典算法分进行分析，从而对算法进行改进与优 化，并提出自己的见解与想法。(2) 分析算法的时间复杂度和空间复杂度

19、。(3) 通过对算法的研究与实现，注重在项目的实施过程中对各成员的创新思维和分 析解决问题能力的培养。(4) 运用基于密度的聚类算法解决实际问题。2. 拟采取的研究方法、技术路线、实验方案及可行性分析采取理论与实践相结合的研究方法。先从理论上对基于密度的聚类算法中的经典算 法进行时间和空间复杂度分析，并针对某种算法的缺陷，从理论上提出改进方案，算法 拟采用c语言实现，并用matlab进行仿真，通过对比试验，从聚类的正确性、精度、算 法执行时间、参数设置、数据输入顺序、数据及密度等方面对算法进行测试、分析、评 价。3. 本项目的创新之处（1）对目前常用的基于密度的聚类算法进行比较和分析，比较各种

20、算法的优缺点。（2）针对现有算法的不足，提出改进方法。（3）结合具体的应用环境，从可行性和执行效率角度考察改进算法的实际应用价 值。4. 项目研究计划及预期进展第一阶段：（2011年6月一2011年8月）全面搜集相关书籍、文献资料、网络资料数据。学习相关科研知识、科研技能，提高科研基本素质。对已搜集的文献资料数据进行汇总、整理与筛选。第二阶段：（2011年9月一2012年2月）根据基于密度的聚类算法的基本原理，对基于密度的聚类算法进行详细的描述。并 借助各种文献、材料，以及前辈的总结与经验，借助我们对基于密度的聚类算法的了解。 对基于密度的聚类算法进行改进与优化，并提出自己的见解。第三阶段：（

21、2012年2月一2012年4月）总结所得的分析结果，结合对一些实际问题的分析、解答，把改进的基于密度的聚 类算法以伪码的形式写出。同时对算法中的数据结构、所用函数进行说明，并绘制程序 流程图，随后分析改进后算法的时间复杂度和空间复杂度，并与原算法进行比较。最后 用visual c+ 6. 0编程实现该算法。第四阶段：（2012年5月一2012年6月）通过做各种对比试验对基于密度的聚类算法的正确性、精度、参数设 置、数据输入顺序以及数据密度等进行对比分析，对改进的基于密度的聚 类算法进行测试、评估。选出最优的、可行性法案，并认真完成项目论文5. 项目研究的预期成果通过团队成员的分工合作，艰苦探索

22、，辛勤研究，搜集各种资料，借鉴别人的经验 与所得，可达到以下预期成果：(1) 在省级以上学术刊物上公开发表1-2篇与该课题相关的学术论文；(2) 增强项目组成员独立思考，团结合作的能力，激发探究新知的兴趣，培养良好 的科学素养。(3) 提高团体合作能力，为今后的学习和科研项目开发提供坚实的知识基础。(4) 进行课题总结，形成总结报告。四、项目保障机制(800字以内)1.经费预算及经费使用计划经费开支项目经费预算(万 元)用途简要说明资料费0. 3用于购买或复印一些相关书籍和文献学术交流费0.4同相关领域专家进行学术交流论文版面费0.2发表项目论文所需的版面费和审稿费存储设备0. 1购买移动硬盘等设备存储程序与论文总计(万元)12.条件保障(实验室、设备、场地、设施等具体情况)学院及学校领导十分支持该项目研究，我院将向参与