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

附件 1： 吉 首 大 学 大学生研究性学习和创新性实验计划项目 申 请 书 学 院 名 称 数学与计算机科学学院 计划项目名称 基于密度的聚类算法研究 _ 计划项目负责人 彭 浩 所 在 专 业 信息与计算科学 所 在 年 级 08 级 联 系 电 话电 子 邮 件 124898764 导 师 姓 名 段明秀 _ 导 师 职 称 讲 师 _ 填 写 日 期 2011-4-20 吉首大学教务处制 填写说明及注意事项 一、申报书逐项认真填写，填写内容必须实事求是，表达明确严 谨。空缺项 要填“ 无”。 二、表格中的字体小四号仿宋体，1.5 倍行距；需签字部分由相关 人员以黑色钢笔或水笔签名。均用 A4 纸双面打印，于左 侧装订成册。 三、大学生研究性学心和创新实验项目是本科学生个人或创新团 队在导师指导下，自主进行研究性学习，自主进行实验方法的设计、 组织设备和材料、实施实验、调查、分析 处理数据、撰写总结报告等工 作。 四、项目实施原则：参与计划的学生要对科学研究或创造发明有 浓厚的兴趣，并在导师指导下完成实验过程；参与学生要自主设计实 验、自主完成实验、自主管理实验；注重创新性实验项目实施过程，强 调项目实施过程中学生在创新思维和创新实践方面的收获。 五、参与大学生创新性实验项目的学生不超过 5 人，项目执行时 间为 1-2 年。 六、指导老师应具有讲师以上职称，每个指导老师指导的项目数 不超过 2 项。 七、计划项目必须先由导师提出意见、由所在学院审核后再推荐 上报。推荐上 报的计划项目表一式三份（均为原件）报送教务处，同时 提交电子文档。 项目名称 基于密度的聚类算法研究 项目主持人 彭浩 学号 20084043032 班级 08 信计 年级 08 级 电话QQ 124898764 学生姓 名 性别 学院名称 专业 年级 联系电话 合作者 签名 杨亚龙 男 数学与计算机 科学学院 信息与计算 科学 08 级邹勇 男 数学与计算机 科学学院 信息与计算 科学 08 级唐超林 女 数学与计算机 科学学院 信息与计算 科学 09 级贺永胜 男 数学与计算机 科学学院 信息与计算 科学 09 级项 目 组 其 他 成 员 姓名 段明秀 性别 女 民族 汉 出生年月 1975.5 职称 讲师 专业 计算机应 用 研究方向 数据挖掘、神经网络 指 导 教 师 情 况 手机号码E-mail Duanmxq126.co m 指导老师签名 一、前期基础（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刘同明数据挖掘技术及其应用长沙：国防工业出版社，2001 1-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 购买移动硬盘等设备存储程序与论文 总计（万元） 1 2条件保障（实验室、设备、场地、 设施等具体情况） 学院及学校领导十分支持该项目研究，我院将向参与项目的学生免费提供专业教 室和专