高维数据聚类技术中的若干算法研究硕士学位论文.docx

高维数据聚类技术中的若干算法研究硕士学位论文.docx

《高维数据聚类技术中的若干算法研究硕士学位论文.docx》由会员分享，可在线阅读，更多相关《高维数据聚类技术中的若干算法研究硕士学位论文.docx（45页珍藏版）》请在冰点文库上搜索。

高维数据聚类技术中的若干算法研究硕士学位论文

分类号学号M05725

UDC密级

学位论文

高维数据聚类技术中的若干算法研究

ResearchonsomeAlgorithms

forHigh-DimensionalDataClustering

AthesissubmittedtotheSchoolofInformation&EngineeringofYangzhouUniversity

Inpartialfulfilmentoftherequirementsforthe

MasterDegreeofComputerScience

By

JiajiaLiu

DepartmentofComputerScience,SchoolofInformation&

Engineering,YangzhouUniversity

Supervisor:

AssociateProfessorKongfaHu

May2008

学位论文原创性声明

本人郑重声明：

所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。

除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。

对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。

本人完全意识到本声明的法律后果由本人承担。

作者签名：

日期：

年月日

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。

本人授权　　　　大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

涉密论文按学校规定处理。

作者签名：

日期：

年月日

导师签名：

日期：

年月日

摘要

数据挖掘是一种可以在数据库上挖掘有用信息的技术，这些信息被称为知识，所以数据挖掘又称知识发现。

从大量数据中挖掘出的知识可用于决策支持、数据分析等领域，随着数据库的发展，数据挖掘已显得越来越重要。

随着数据规模的不断增大，传统聚类分析方法难以发挥作用。

聚类操作实际上是数据对象之间相似性的度量，相似度高的对象被归为一类。

在低维空间中经常使用欧氏距离等函数来度量相似性，但在高维情况下由于相似性没有传递性，距离函数不再发挥作用，而高维数据的距离函数难于定义，因此必须重新考虑新的度量数据对象相似性的标准或准则。

另外，由于维数很高，传统聚类算法的计算复杂度会很高，其应用也受到了很大的局限性。

针对高维数据引起的“维度灾难”问题，本文研究了高维数据的特点，充分利用单维与多维的关系，提出了用单维来分割高维数据，并将数据进行整合，按维序逐次聚类的HDCA_SDP算法。

在单个维上进行聚类时，采用索引转换技术来预处理数据，从而简化高维数据处理问题。

该算法每次处理只针对一个维层次，经过层层处理，最终就能得到完整数据空间上的聚类。

在HDCA_SDP算法的基础上，分析并整合了传统数据聚类算法K-means算法的几种改进算法，提出了适用于更高维空间的聚类算法DFBC。

DFBC算法首先在高维数据空间上，将维划分为比较低的维组合，在这些维组合的数据空间上运用改进的K-means算法进行聚类，以维组合为层次，聚类过程是逐层进行的，这实际上跟单维分割聚类技术是相似的，所有层处理完之后就得到了最终的聚类结果。

相比于单维分割聚类技术，使用维分组的聚类技术更适用于大型更高维的数据空间。

该算法按照维组层次的增长，计算时间也是呈线性变化的，但是就算法的思想来说，它是低维聚类与高维聚类技术的一种折衷。

本文还对网格的聚类技术进行了研究，分析了固定网格划分聚类与自适应网格划分聚类存在的缺陷，针对GCOD算法存在的缺陷，提出了一种改进的方法。

GCOD算法主要采用了相交网格划分的措施，对固定网格划分与自适应网格划分技术采取了一种折衷的处理策略。

但是GCOD算法未对相交网格的大小进行限制，使得这其中会存在许多不合理化聚类。

我们针对这个问题提出了对网格大小进行限制的方法，并且提出了更加合理的密度计算方法。

研究了子空间聚类的一些算法，针对经典算法CLIQUE存在的缺陷，提出了基于半相交网格划分的HIGSC算法。

它首先利用半相交网格划分方法在单个维上进行聚类，然后利用类Apriori规则来形成子空间，在子空间形成的过程中运用类HDCA_SDP方法产生子空间上的聚类。

算法的性能较CLIQUE算法有了提升，在聚类结果的精度方面提升明显。

关键词：

数据挖掘；聚类；高维聚类；子空间

Abstract

Dataminingisatechnologyofminingusefulinformationfromdatabase.Thisinformationwhichisminedfromdatabaseisalsocalledknowledge,sodataminingisalsocalledKDD（KnowledgeDiscoveryinDatabases）.Theminedknowledgecanbeusedindecisionsupport,dataanalysisandanyotherfield.Bythedevelopmentofdatabase,datamininghasbeenmoreandmoreimportant.

Bytheincreaseofthesizeofdataindatabases,traditionalclusteringmethodscan’ttakeeffectly.Actually,theoperationofclusteringisjustthemeasurementofsimilaritybetweendifferentdataobjects.Thesedataobjectswhichhavethehighsimilarityshouldbeassignedtoonecluster.Eucliddistancefunctionandanyotherdistancebasedfunctionsareusuallyusedinclusteringonlow-dimensionaldata.Buttheycan’tworkwellonhigh-dimensionaldata,becausetheycan’ttransferbetweendifferentobjects.Andit’sdifficulttodefinethesefunctionsonhigh-dimensionaldata,sonewmeasurementofsimilaritymustbeconsidered.Otherwise,becauseofthehigh-dimension,traditionalalgorithmsalwayshavethehighcomplexityandlimitationintheirapplications.

Inallusiontotheproblemofdimensionalitycursecausedbyhigh-dimensionaldata,weproposedaclusteringalgorithmbasedonsingle-dimensionpartitionwhichiscalledHDCA_SDPinthispaper.Ittakesuseoftherelationshipofsingle-dimensionandmulti-dimension.Transposeofindexonsingledimensionistakentopredigestthemethodofhigh-dimensionaldataprocess.Thisalgorithmworksononedimensionallayereachtime,processeswitheachlayerandfinallyalltheclusterswillbegained.

Wehaveanalyzedandimprovedafewimprovedalgorithmsontraditionalk-meansalgorithm.OnthebaseofHDCA_SDPalgorithm,weproposedDFBCalgorithmwhichissuitforhigher-dimensionaldata.DFBCalgorithmfirstpartitionthewholedimensionstosomecombinationsoflowdimensions,thenclusteroneachcombination.TheprocessissimilartoHDCA_SDPalgorithm.ComparedtoHDCA_SDP,DFBCalgorithmismoresuitableonlargeandhigher-dimensionaldata.TherunningtimeofDFBCalgorithmincreaseslinearitywiththeincreasesofcombinations.It’sactuallyacompromiseoflow-dimensionalandhigh-dimensionalclusteringmethodonitsidea.

Weresearchedsometechnologiesofgridbasedalgorithmsandanalyzedfixed-gridbasedandadapt-grid’sshortages.InallusiontoGCOD’sshortageweproposedanimprovedalgorithm.AmeasureofintersectinggridisadoptedinGCODalgorithmwhichisacompromisemethodoffixed-gridandadapt-gridbasedalgorithms.Butithasn’tlimitedthesizeofintersectinggrids,andthentherewillbesomeirrationalityclustersfinally.Inallusiontothisproblemweproposedamethodtorestrictthesizeofintersectinggridsandmorerationaldensitycomputingmethod.

Someclusteringalgorithmsonsubspaceareresearchedinthispaper.InallusiontotheshortageoftraditionalCLIQUEalgorithm,HIGSCalgorithmwhichisbasedonhalfintersectinggridsisproposed.Itfirstlyclustersonallofthesingledimensionsbasedonhalfintersectinggrids.ThengeneratessubspacebythesimilarruleofApriori.InthecourseofgeneratingsubspaceclusteringaregeneratedbysimilarHDCA_SDPalgorithm.ComparedtoCLIQUE,theperformanceofHIGSCalgorithmisimproved,especiallyontheaspectofprecisionofclustering.

Keywords:

DataMining;clustering;high-dimensionalclustering;subspace

第一章

引言

本论文主要讨论了什么是数据挖掘，什么是高维数据聚类，有哪些传统的聚类技术，针对传统或现有的聚类技术的局限性，讨论如何提升聚类的性能，并将其运用到高维数据空间聚类中。

本章将介绍数据挖掘的发展，数据聚类技术的特点及高维数据聚类技术的发展。

基于这些背景知识的介绍，我们提出本文的主要工作，即运用单维与多维的关系来实现对高维数据的有效聚类，运用相交网格的思想来聚类子空间等，以更好的完成数据挖掘的任务。

本章的最后列出了文章的组织结构。

一.1研究背景

一.1.1数据挖掘的产生与发展

60年代末期以来，随着计算机应用的普及和数据处理在计算机应用中所占比重的上升，数据库技术得到了迅速发展。

数据库技术与计算机网络通信已经成为当前计算机应用中两个最重要的基础领域[1]。

计算机的一些重要应用，如管理信息系统、办公自动化技术、计算机辅助设计、专家系统等，大都离不开这两个基本技术。

在当前流行的数据库管理系统中，采用的数据模型主要有层次模型、网状模型和关系模型三种。

70年代中期，关系数据模型渐渐成为占主导地位的数据模型。

由于关系数据库的模型结构简单，逻辑物理界面清晰，具有较强的集合处理功能，使得数据库应用系统开发的效率大大提高。

数据库的应用己经触及到人类生活的各个方面。

据统计1989年时全世界数据库总量为500万个，而且数量以每20个月翻一番的速度增长着，但是对数据库中数据的开发应用还主要是检索查询，效率很低，往往很多数据还没来得及分析就己经过时了。

90年代地球探测卫星每天产生的数据，超过以前所有航测数据的总和，即使一个人以最快的速度一刻不停地工作，也要花费几年时间才能浏览卫星一天内产生的图片，生物学领域研究的数以百万计的遗传基因，世界各国定期进行的人口普查，国土资源地理信息，铁路动态调度控制，公安司法部门的案件处理，都涉及巨量的数据，相当数量的数据具有很强的时效性，数据的价值随着时间的推移而迅速降低。

数据收集与维护的目的是供人们使用。

简单的数据查询或统计虽然可以满足某些低层次的需求，但人们更为需要的是从大量数据资源中挖掘出对各类决策有指导意义的一般知识。

它们是对大量数据的高度浓缩和抽象，是对数据整体的认识，这些经过智能分析和表示的数据才是有价值和竞争力的社会资源。

数据挖掘技术就是在这样一个时代背景下产生的。

它的宗旨就是在数据库中分析处理大量的数据，发现有用的知识，为用户提供所需问题的答案，又称为数据库知识发现。

目前对数据挖掘比较公认的定义是：

从数据集中识别出可信的、有效的、新颖的、潜在有用的以及最终可理解模式的高级处理过程。

“数据库知识发现”一词第一次出现是1989年8月在美国底特律召开的第11届国际人工智能联合会议的专题研讨会上。

1991年、1993年和1994年又分别举行过数据库知识发现专题研讨会。

由于参加会议的人数逐年增多，所以从1995年开始，每年都要举办一次数据库知识发现国际会议。

一.1.2聚类分析

聚类分析是数据挖掘的主要任务之一[2,3]，用于发现在数据库中未知的对象类。

通过聚类过程形成的每个组称为一个聚类簇。

在数据挖掘之前，对象类划分的数据量与类型均是未知的，因此在数据挖掘后一般需要对数据挖掘结果进行合理的分析与解释。

聚类是现实世界中普遍存在的现象，其应用也非常广泛。

据文献所载，在破产预测、手写体字符的计算机识别、交通管理与塞车状况预测等方面都有过成功应用。

在20世纪70年代，对聚类分析已经有了比较深入的研究。

聚类的方法主要有统计学方法和机器学习的方法。

在统计学中，聚类一般称为聚类分析，主要研究基于几何距离的聚类。

在使用上，首先定义多维空间，在多维空间中计算对象间的距离，然后以距离作为对象间的相似性判别标准。

在机器学习中，聚类称为无监督学习，主要体现在聚类学习的数据对象没有类别标记，需要由聚类学习算法自动计算。

近十年左右，随着数据挖掘技术的兴起，对聚类的研究掀起了新的热潮。

除了统计学和人工智能领域的研究人员以外，数据库领域的人员也加入了研究行列，并取得了可喜的成果。

从数据库知识发现的角度看，对聚类问题的研究是从大量的数据集中智能地、自动地抽取出有价值的聚类知识。

近年来，随着聚类分析应用的领域扩展和深入，高维聚类问题成为当前聚类分析研究的重点。

典型的高维聚类应用如web挖掘、文本聚类、搜索引擎、客户分析等。

在数据维数较高时，传统聚类分析的性能会急骤下降，甚至无法完成聚类任务[4,5]。

这样就产生了“维度困扰”的问题，维度困扰又称维度灾难，它是指随着维度的增长，聚类分析的计算复杂度会呈指数级增长的情况。

同时，高维数据聚类中距离函数难于定义。

聚类操作是数据对象之间相似性的度量，相似度高的对象被归为一类。

低维空间中经常使用欧氏距离等距离函数来度量相似性，但是在高维情况下由于相似性没有传递性，距离函数无法发挥作用。

这样就必须重新考虑新的度量数据对象相似性的标准或准则。

另外，基于距离的聚类方法，经常需要计算簇的均值或近邻，但在高维情况下，按距离计算的簇的均值会很接近，聚类操作由于无法明确区分簇的中心而无法进行。

并且，由于维数很高，传统聚类算法的计算复杂度会很高，其应用受到很大局限性。

一.2课题的引出

聚类分析由来已久，但是国际上对高维聚类算法的研究相对较晚，大致起始于20世纪90年代中期，较早的研究成果是一种基于超图划分的聚类方法[6]，此外是一些基于网格的方法[7]和基于小波变换的方法[8]等。

文献[6]中提出了一种基于超图划分的方法，这种方法将高维数据聚类问题转化为图划分问题，由于图划分问题己经研究得较为成熟，这使得转化后的问题相对易于解决，从而实现了高维数据聚类问题的一种比较有效的解决方法。

对高维聚类研究得较多的另一种方法是基于网格的方法。

基于网格的方法相对比较简单：

它首先通过有限地划分每一维，将数据空间量化为超矩形单元，形成一个网格结构。

然后忽略掉低密度的单元，高密度的区域则代表簇。

最后将相连的相连的高密度单元合并形成一个簇。

这种技术效率较高，但是随着数据维度的增长，单元的数量以指数形式增加。

并且，对分散在不同网格中的，但是原该属于一类的数据作了划分，使得它们不一定被聚为一类，固定网格划分聚类遇到的主要问题被称为聚类边界不明确。

为了解决上述网格在高维空间中的问题，出现了几个改进的网格划分聚类方法，分别是：

WaveCluster[8]，CLIQUE[9]，MAFIA[10]，ENCLUS[11]和OptiGrid[12]算法等。

在美国休斯顿举行的第五届关于数据挖掘的SLAM（InternationalConferenceonDataMining）会议指出，当前许多应用领域都需要进行高维数据分析，数据的维度通常是成百上千，而且非常稀疏，对这样数据进行聚类分析是目前相关研究界面临的一个新兴挑战。

国内对面向数据挖掘的聚类算法研究相对起步较晚，但有着较大的发展空间，目前在空间数据聚类上的研究已取得一些成果。

综上所述，目前高维聚类算法研究正处于发展初期，而随着信息时代的发展，高维数据聚类在许多应用领域逐渐体现出其重要性，因此，对高维数据的聚类算法进行研究并提出高效可行的算法是非常有意义的。

一.3论文的主要工作

在论文中我们首先介绍了数据挖掘的基本原理以及相关数据聚类的方法和应用，展望了当前数据聚类的研究热点和研究现状。

然后对高维数据聚类技术作了具体的介绍，结合相关问题对高维数据聚类算法进行了研究，在借鉴国内外在数据挖掘与高维数据聚类处理方面已有成果的基础上，提出了利用单维与多维的关系来聚类高维数据的方法，并利用相交网格聚类技术与子空间聚类技术来解决维度困绕的难题。

首先在高维数据的完全空间聚类方面，我们介绍了当前存在的传统聚类技术，设计了一种基于单维分割的高维数据聚类技术，从而缓解了维度困绕的问题。

在子空间聚类方面，结合基于相交网格划分的方法与子空间聚类的传统算法，提出了自己的见解和解决方案，为解决高维数据聚类问题提供了实际可用的方法。

1）在高维数据集上使用单维分割的技术

研究高维数据的特点，比如稀疏性等问题，充分利用单维与多维的关系，提出以单维分割高维数据，并将数据进行整合，按维序逐次聚类的技术。

其中，设计了将高维数据进行索引转换，从而达到降低维度的技术，它能快速生成各个维的对象表示，从而简化高维数据处理问题。

该技术由于每次处理只针对一个维，因而可以将维作为层次，经过层层处理，最终就能得到完整数据空间上的聚类。

该算法按照维的增长，计算时间是呈线性变化的，可见维度困绕的问题得到了很好的解决。

2）在更高维数据集上使用维分组技术

研究了在低维数据空间上传统数据聚类算法K-means算法的几种改进算法，并提出了对这几种改进算法的整合，从而形成了比较完善的K-means算法。

在大型高维数据空间上，将维划分为比较低的维组合，在这些维组合的数据空间上运用改进的K-means算法进行聚类，以维组合为层次，聚类过程是逐层进行的，这跟单维分割聚类技术是相似的，所有层处理完之后就得到了最终的聚类结果。

相比于单维分割聚类技术，使用维分组的聚类技术更适用于大型更高维的数据空间。

该算法按照维组层次的增长，计算时间也是呈线性变化的，从算法的思想来看，它是低维聚类与高维聚类技术的一种折衷。

3）利用相交网格进行聚类

对基于网格的聚类技术进行了研究，分析了固定网格划分聚类与自适应网格划分聚类存在的缺陷，并研究了克服这种缺陷的GCOD算法，同时分析了GCOD算法存在的缺陷，提出了一种改进的策略。

GCOD算法主要采用了相交网格划分的措施，对固定网格划分与自适应网格划分技术采取了一种折衷的处理策略。

但是GCOD算法未对相交网格的大小进行限制，使得这其中会存在许多不合理的聚类。

我们针对这个问题提出了对网格大小进行限制的方法，并且提出了更加合理的密度计算方法，从而大大改善了GCOD算法的执行效果与执行性能。

4）利用半相交网格划分技术聚类子空间

研究了高维数据子空间聚类的经典算法，分析了其存在的缺陷，提出了利用相交网格划分的方法HIGSC来改善这些问题。

HIGSC首先利用半相交网格划分方法在单个维上进行聚类，然后利用类Apriori规则来形成子空间，在子空间形成的过程中运用类HDCA_SDP算法产生子空间上的聚类。

HIGSC算法性能比CLIQUE算法有了很大提升，在聚类结果的精度方面提升比较明显。

5）索引转换技术的研究

在单个维上进行聚类往往需要索引转换的预处理，这样能加快算法的处理，这种转换实际上是将关系数据库中的数据记录进行了转置存储。

转置后的数据库与原数据库占用相同的空间，因而，实际应用中，我们可以直接将数据存储为转置数据库的形式以便于利用本文的相关方法进行聚