基于相对熵的投影聚类算法研究

《基于相对熵的投影聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Y1219507分类号TP311．13密级公开重庆邮电大学硕士学位论文论文题目基于相对熵的投影聚类算法研究英文题目TheResearchofRelativeEntropyBasedProjectiveClusteringAlgorithm硕士研究生高嵩指导教师夏芸劐煎蕉学科专业计算机应用技术论文提交日期2QQ2生§旦论文答辩日期2QQ!生§旦2旦论文评阅人王盘熬盘鱼壹叁羔姿￡显壅壁垒杰垃整熏鍪鱼空垫盔坠答辩委员会主席王国胤教授重庆邮电大学2007年5月20日重庆邮电大学硕士论文摘要聚类就是将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。相异度

2、是根据描述对象的属性值来计算的。距离是经常采用的度量方式。技术进步使得数据收集变得更加简单和快速，从而产生了大量复杂的高维数据。由于这种数据存在的普遍性，使得对高维聚类算法的研究有着非常重要的意义。传统的聚类算法受“维灾”的影响在处理高维数据时变的异常困难，主要表现为索引结果效率低、用于相似性度量的距离函数失效、聚类描述中存在冗余的维以及算法执行效率低等问题，使得聚类算法的应用受到很大的局限性。发现高维空间中存在于不同子空间的聚类问题一般被称为投影聚类问题。在已有投影聚类算法EPCH(EfficientProjectiveClusteringtechniquebyHistogramcons

3、truction)的基础上，本文提出了一种基于相对熵的改进算法REPCH(RelativeEntropybasedProjectiveClusteringbyHistogramsconstruction)。在数据分布的特征空间中，将每一个d维子空间划分成网格结构。根据网格单元的密度构建每一个d维子空间的直方图。直方图的相对熵可以反映子空间中数据的实际分布与平均分布之间的相似度。相对熵会随着密集区域的减少而单调递增，并逐渐趋近于1。根据这个原理，直方图中密集区域和稀疏区域可以被识别。算法在人工数据集上进行了大量的实验，对算法的聚类质量、性能等指标进行了测试。与原有的EPCH算法相比，REPC

4、H算法是一种有效的投影聚类算法，且对数据量及维数有很好的可伸缩性，适用于高维数值数据聚类。关键词：聚类分析，高维数据，投影聚类，直方图，相对熵重庆邮电大学硕士论文AbstractClusteringistodividedataobjectsintoseveralclassesorclusters．Dataobjectsaresimilartooneanotherwithinthesameclusterandaredissimilartotheobjectsinotherclusters．Dissimilarityiscalculatedaccordingtothefeaturesofdat

5、aobjects．Distancemeasuresarecommonlyusedforcomputingthedissimilarityofobjcots．Technologyadvanceshavemadedatacollectioneasierandfaster，resultinginlarger,morecomplexdatasetswithmanyobjectsanddimensions．Theuniversalityofhighdimensionaldatamakesresearchesonhighdimensionalclusteringalgorithmsveryimport

6、ant．Processinghighdimensionaldataisextraordina“lydifficulttotraditionalclusteringalgorithmsbecauseofthecurseofdimensionality．Itismainlypresentedasfollows．Indexhaslowperformanceforhigh—dimensionaldataset．Irrelevantdimensionsexistintheclusters．Distancemeasuresareineffective．Andbecauseofhighdimension

7、ality,thetimecomplexityoftraditionalclusteringalgorithmisveryhigh．TheselimittheirUSeinapplication．Todiscoverclustersexistingindifferentsubsetofdimensionsisusuallyknownastheprojectiveclusteringproblem．Basedonexist