搜索
毕业设计(论文)开题报告学生姓名：罗崇珺学号：0909290204专业：信息与计算科学设计(论文)题目：基于混合约束的半监督聚类算法的研究指导教师：郭新辰2013年3月8日开题报告填写要求1．开题报告（含“文献综述”）作为毕业设计（论文）答辩委员会对学生答辩资格审查的依据材料之一。此报告应在指导教师指导下，由学生在毕业设计（论文）工作前期内完成，经指导教师签署意见及所在系审查后生效；2．开题报告内容必须用黑墨水笔工整书写或按教务处统一设计的电子文档标准格式打印，禁止打印在其它纸上后剪贴，完成后应及时交给指导教师签署意见；3．“文献综述”应按论文的格式成文，并直接书写（或打印）在本开题报告第一栏目内，学生写文献综述的参考文献应不少于10篇（不包括辞典、手册）；4．有关年月日等日期的填写，应当按照国标GB/T7408—94《数据元和交换格式、信息交换、日期和时间表示法》规定的要求，一律用阿拉伯数字书写。如“2002年4月26日”或“2002-04-26”。毕业设计（论文）开题报告1．结合毕业设计（论文）课题情况，根据所查阅的文献资料，每人撰写2000字左右的文献综述：文献综述1）基于混合约束的半监督聚类算法的研究背景和意义半监督聚类是近几年来机器学习研究的一个热门课题，现有的半监督聚类算法很多是在传统聚类算法的基础上引入监督信息发展而来的，代表算法是基于经典K-means算法的各种半监督K-means算法．例如，WagstaffK等人提出将must-link和cannot-link成对约束引用到半监督聚类算法中；Basu等人在K-means算法的基础上提出了少量已标签数据的seeded-K-means和constrained-K-means算法．也有一些文献将隐马尔可夫模型、SVM算法、Bayes算法和遗传算法等引入到半监督聚类学习当中来．半监督聚类的优越性主要在于针对无标签样本进行聚类时，可以利用少量有监督的样本信息．因此，如何在聚类算法中更好地利用有标签样本所包含的领域知识指导聚类过程，是进一步提高聚类质量的关键问题之一．目前，半监督学习的研究主要包括半监督分类、半监督聚类和半监督回归．而半监督聚类是当今研究的热点．现有的半监督聚类算法很多事在传统聚类算法基础上引入监督信息发展而来的，代表算法是基于经典K-means算法的各种半监督K-means算法．半监督聚类，它综合了无监督学习和有监督学习的特点，提高聚类的质量．半监督聚类是基于少量先验信息的，先验信息可以使标点号信息和成对点约束信息，通常认为标点号信息和成对点约束信息是不等价的，前者可以转换成后者，反之则不能．因此现有的半监督聚类算法大多是基于成对点约束信息的．但是，现实数据中往往两类先验信息同时存在，简单地将标点信息转换为成对点约束信息会使标点信息的意义减弱，例如：医生为病人诊治时，“确诊一个病人”和“认定两个病人有同一种病却不知道是什么病”提供的信息是大不相同的，因此本课题的研究如何在半监督聚类算法中同时潜入标点号信息和成对点约束信息，以更加有效地确定数据集的内部结构，具有更好的聚类结果和更快的速度．2)基于混合约束的半监督聚类算法研究现状聚类是人类一项基本的、最重要的认识活动，在许多领域中被广泛地应用．半监督学习是今年来在机器领域新发展的一种学习方法，国外半监督聚类的研究开始得比较早，已经取得了一定的成果．JanneSinkkonen和SamulKaski等人在2000年及以后提出了相关的算法研究，并初步应用在基因分析、文本内容挖掘等领域，取得了很大的进步，相对来说研究工作还比较少．聚类分析试图将一组未标签样本按照一定的相似度准则分到几个类中去，使得在同一类中的样本有着较大的相似度，不同类间的样本的相似度较小，聚类分析作为一种非监督学习，是机器学习领域中一个重要的研究方向，同时也是数据挖掘中进行数据处理的重要分析工具和方法。国内外有部分学者正在研究半监督聚类算法及其应用，相对来说研究工作还比较少．在提出一种用于求解混合约束问题的方法上，目前在求解混合约束中的数值约束时是不完全的，即它不能够明确地告诉用户所求解的约束问题是否有解．鉴于此，目前半监督聚类中常见的先验知识表现为反映样本间相似关系的约束条件文献对约束条件的定义，即两个样本属于同一类为Must-Link，不属于同一类的则为Cannot-Link．有约束的半监督聚类是一种结合用户指定或面对应用的约束进行半监督聚类的方法，依靠用户提供的标号或约束指导算法，产生更合理的数据划分．3)研究本课题，将达到的目的①掌握半监督聚类算法的思想；②在半监督聚类算法中同时嵌入约束信息，提高聚类效果；③培养严谨的治学态度，以及能够独立的查阅、学习文献资料的能力，使学生具有一定的科技写作能力；④培养学生应用理论知识解决实际问题的能力，为学生进一步学习或者走上工作岗位打下一个良好的基础．4)本研究课题所涉及到的两种算法①Consistency算法Consistency算法是一种高效的聚类算法，综合考虑了数据的分布情况和给定的标号信息，但该算法不能表达成对点约束信息．本课题聚类的过程要考虑到局部一致性和全局一致性，即靠得近的点应该有相同的标号(局部一致性)．Consistency算法要求设计的分类函数对已标号和未标号数据的内部结构足够光滑，通过传递标号点的标号信息给它的近邻，达到一个全局的稳定状态．②Consistency算法改进得出HCC算法本课题对Consistency算法进行改进，提出基于混合约束的半监督聚类算法．Wagstaff提出两种类型的成对点约束，即must-link(ML)和cannot-link限定两个点必须在同一类中，cannot-link限定两个点不能在同一类中．而Consistency算法只利用了类标号信息，并没有考虑信息结合起来进行考虑，在原基础上进一步添加了ML和CL信息，通过最小化可发挥两种信息的综合作用，同时表达标号信息、成对点约束信息以及数据的分部信息，提高先验信息的利用能力．其中标号信息、成对点约束是随机生成的，使得标点号和成对点约束在HCC算法上都能起到提高聚类性能的作用．参考文献[1]蔡晓妍，戴冠中，黎斌．谱聚类算法综述[J]．计算机科学，2008,35(7)：14-18．[2]周志华，王珏主编．机器学习及其应用[M]．北京：清华大学出版社,2007．[3]ShiJ，MalikJ.Normalizedcutsandimagesegmentation[J]．IEEETransactionsonPatternAnalysisandMachineIntelligence,2000,22(8):888-2905．[4]王玲，薄列峰，焦李成．密度敏感的半监督谱聚类[J]．软件学报，2007,18(10)：2412-2422．[5]肖宇，于剑．基于近邻传播算法的半监督聚类[J]．软件学报，2008，19(11)：2803-2813．[6]刘涛，尹红健．基于半监督学习K-均值聚类算法研究[J]．计算机应用研究，2010,27(3):914-916．[7]黄海超．基于领域知识的半监督聚类算法的研究[D]．北京：北京化工大学硕士学位论文,2009．[8]孙雪，李昆仑，胡夕坤，等．基于半监督K-means的K值全局寻优算法[J]．北京交通大学学报,2009，33(6):106-109．[9]汪军，王传玉，周鸣争．半监督的改进K-均值聚类算法[J]．北京交通大学学报，2009,45(28):137-139．[10]高滢，刘大有，齐红，刘赫．一种半监督K均值多关系数据聚类算法[J]．软件学报，2008,19(11):2814-2821．[11]WagstaffK,CardieC,RogersS,etal．ConstrainedK-MeansClusteringwithBackgroundKnowledge[C].Proceedingofthe18thInternationalConferenceonMachineLearning.Burlington:KaufmannMorganPublishers,2001:577-584．毕业设计（论文）开题报告２．本课题要研究或解决的问题和拟采用的研究手段（途径）：1）本课题解决的问题①掌握半监督聚类算法思想；②在半监督聚类算法中同时嵌入标号点信息和成对点约束信息，以更加有效地确定数据集的内部结构，提高聚类效果；③设计基于混合约束的半监督聚类算法；④给出算法的仿真结果．2）本课题的研究方法①在Consistency算法基础上提出一种混合约束的半监督聚类算法HCC，使得标号点和成对点约束信息在指导聚类的过程中能发挥各自的作用，设计相应的目标函数并推导出其最优解的表达式算法的性能测试结果；②通过实验数据进行约束调整；③最后由实验结果做出分析以及改进．3）本课题工作进度计划2013.02.28~2013.03.09查阅资料，整理，提炼，撰写文献综述及开题报告；2013.03.10~2013.03.31基于半监督聚类算法的文献阅读及外文文献翻译；2013.04.01~2013.04.20HCC算法设计与分析；2013.05.11~2013.05.25撰写论文初稿；2013.05.26~2013.06.11修改论文，完成终稿；2013.06.12~2013.06.19打印、装订成文；2013.06.20~2013.06.21上交所有与毕业设计有关的材料；2013.06.14~2013.06.26论文答辩．毕业设计（论文）开题报告指导教师意见：1．对“文献综述”的评语：通过阅读大量的文献，该生很好的完成了文献综述撰写工作。文献综述系统的阐述了混合约束半监督聚类的背景、意义以及研究课题的目的．通过对HCC算法的研究，掌握了半监督聚类算法的思想，并且说明了通过此算法会实现在半监督聚类算法中同时嵌入标号点信息和成对点约束信息，以更加有效地确定了数据集的内部结构，提高聚类效果；理解了基于混合约束半监督聚类算法的研究以后对机器学习研究的重大作用．2．对本课题的深度、广度及工作量的意见和对设计（论文）结果的预测：本课题是基于混合约束的半监督聚类算法的研究，是研究如何在半监督聚类算法中同时潜入标点号信息和成对点约束信息，以更加有效地确定数据集的内部结构，具有更好的聚类结果和更快的速度．由实验数据来表明增加成对点约束信息和标点号信息能否提高算法的聚类性能，在实验中成对点约束信息和标点号信息是随机生成的，目的是为了在成对约束质量不确定的情况下测试个算法的聚类能力．本课题具有一定的深度、广度，工作量适中，按设计的计划进度该生能够顺利完成本设计．指导教师：年月日所在院（系）审查意见：负责人：年月日