高维数据聚类（精选3篇）
高维数据聚类 篇1
1 引言
聚类分析是数据挖掘领域中的一项重要的研究课题, 高维数据对象的聚类又是聚类分析的重要研究课题, 也是涉及到聚类算法是否能够有效地应用于各个领域, 例如多属性 (高维) 流数据的聚类分析。高维数据的特点表现为: (1) 高维数据集中存在大量无关的属性使得在所有维中存在簇的可能性几乎为零; (2) 高维空间中数据比低维空间中数据分布稀疏, 其中数据间距离几乎相等是普遍现象。目前, 对高维数据的聚类主要有3种方法:属性转换、子空间聚类、协同聚类、属性转换是通过创建新属性, 将一些旧属性合并在一起来降低数据集的维度的方法。目前, 主成分分析方法 (PCA) 、自组织特征映射 (SOM) 、多维缩放 (MDS) 、小波分析等是普遍应用的降维方法。虽然采用降维技术使得数据的维度大大降低, 但数据的可理解性和可解释性变得较差, 一些对聚类有用的信息也可能会随之丢失, 很难准确地表达和理解结果。在处理高维数据时, 采用属性转换的方法得到的聚类效果并不是很理想, 有一定的局限性, 不能满足当前高维聚类算法发展的需要。
子空间聚类算法对特征选择的任务进行了拓展, 它是在同一个数据集的不同子空间上进行聚类。子空间聚类和特征选择一样使用搜索策略和评测标准来筛选出需要聚类的簇, 因为不同的子空间上存在不同的簇, 因此我们要对评测标准设置一些条件。
协同聚类在数据点聚类和属性聚类之间达到了一种平衡。因为它从对象—属性两个角度同时进行聚类操作。假设X是由数据对象和数据属性构成的矩阵, 一般被叫做关系矩阵、可能性矩阵、影响矩阵、频率矩阵等。一般被应用于反映基因响应的强度、一个Web页面的点击率, 或一个仓库里各项商品的销售数量等。Govaert于1995提出了可能性矩阵表中行列块的同时聚类算法。Dhillon于2001年提出了一种协同代数聚类算法, 它与文本挖掘相关, 是基于二部图和它们的最小切割的。Oyanagi等人于2001年提出了一种简单的Ping-Pong算法, 它能在稀疏二元矩阵中发现相应区域, 该算法能建立矩阵元素的横向联系, 并用此来重新分布列对行的影响, 并反过来进行。
本文在对数据对象间的最大距离和平均距离随维数增加的变化趋势实验基础上, 通过实验研究了聚类算法的聚类精度随数据对象维度的变化特征。同时, 提出了利用复相关系数倒数阈值实现降维的方法。
2 数据对象离散度与维度的关系
2.1 实验数据
实验中所用的数据集均来自UCI数据库, 数据集包括Iris, Wine, Wisconsin Diagnostic Breast Cancer, SPECT Heart和Libras Movement。数据集的详细描述见表1。
2.2 相关定义
为了确定数据对象随维度变化规律, 我们定义了数据对象间的最大距离和平均距离来定量确定数据对象间的离散度。
最大距离:假设数据集D有n个数据对象, 每个数据对象有d个属性 (维) , 即Xi={xk, k=1, …, d}, i=1, …, n。数据对象间的最大距离被定义为:
平均距离:数据对象间的平均距离被定义为:
2.3 实验结果
为了研究维数对聚类精度的影响, 有必要研究对象间的距离随维数增高的变化趋势。根据上面定义的公式 (1) 和公式 (2) , 数据对象间的最大距离和平均距离随维数的增加而增大。我们使用UCI数据库中的Libras Movement数据集, 先对数据集进行最小—最大标准化处理, 然后计算此数据集中数据对象间随维数增高的最大距离和平均距离。实验结果分别显示在图1和图2中。
如图1和图2所示, 随着维数的增加, 数据对象间的最大距离和平均距离逐渐增大。表明数据对象在高维数据空间变得比较稀疏, 很可能导致数据空间中客观簇的消失, 使得基于距离的聚类算法往往不能够取得良好的聚类效果。因此, 为了获得有效的聚类结果, 基于距离、密度和密度可达的聚类算法有必要进行改进或降维。
3 维数对算法聚类精度的影响
3.1 直接聚类
我们给出了确定聚类效果的准确度公式。假设数据集D中有k个类, 即Ci (i=1, …, k) , Oip (p=1, …, mp) 是类Ci中的数据对象。数据集D经过聚类后, 出现了k个类Ci′ (i=1, …, k) , O′ip (p=1, …, mp′) 是Ci′类中的数据对象, 准确度被定义为:
|Ck∩Ci′|是同时属于类Ci和Ci′的数据对象Oip (p=1, …, mp) 和Oip′ (p=1, …, mp′) 的个数;|D|是数据集D中的数据对象的个数。
为了研究维数对算法聚类精度的影响, 我们分别用K-means和层次聚类算法对以上5个不同维数的数据集进行聚类分析, 聚类结果如图3所示。当数据集的维数小于30的时候, 两种聚类算法的性能较好, 当数据集的维数大于30的时候, 聚类算法的精度随维数的增高而降低。实验结果在一定程度上表明, 当数据集的维数小于30的时候, 传统的聚类算法, 如K-means和层次聚类算法, 这种基于距离的聚类算法是有效的, 但是当维数大于30的时候它们的聚类结果很不理想。
3.2 PCA降维聚类
Wine数据集有13维, 经过主成分分析 (PCA) 降维后, 原有的13维变成了3维, 为了比较PCA降维前和降维后的效果, 我们用K-means和层次聚类算法对原有的数据集和经过降维后的数据集进行聚类, 结果如图4所示。
对数据集降维后, K-means和层次聚类算法的聚类精度有所提高, 但是效果不是很明显。此结果也说明了K-means和层次聚类对30维以内的数据集的聚类精度比较高。
Libras Movement数据集有90维, 经过PCA降维后变成了10维, 降维前和降维后的聚类结果如图5所示。
降维前和降维后K-means和层次聚类算法的聚类精度都很低, 结果表明: (1) 以上两种聚类算法不能有效地处理高维数据; (2) PCA降维对聚类算法不总是有效的; (3) 此数据集包含15个类, 对于高维、多类的数据集, 聚类算法不能很好地辨别存在的类 (簇) 。
4 基于复相关系数倒数降维
4.1 复相关系数倒数加权
复相关系数的倒数赋权法是在方差倒数赋权法的基础上提出来的。假设数据对象的某一属性为Xk, 则它的复相关系数记为ρk。ρk越大, 表明Xk与其余的属性越相关, 越能被非Xk代替, 也就是说Xk属性对聚类的作用越小;反之, ρk越小, Xk与其余的属性越不相关, Xk属性对聚类的作用越大。所以可以用|ρi|-1计算数据对象属性权重系数wk。
因此, 数据点密度计算公式中的加权欧式距离公式为:
4.2 降维实验
我们也可以采用复相关系数的倒数赋权法作为一种特征选择方法, 对数据集中数据对象的每个属性加权后, 得到了每个属性的权值, 然后根据权值的大小, 我们设定一个阈值参数σ, 选择权值大于σ的属性, 从而实现了对数据集的降维, 然后对降维后数据集进行聚类。为了说明此方法的有效性, 采用k-means算法、层次聚类算法、CADD (基于密度和密度可达聚类算法) 算法对WDBC数据集和SPECT Heart数据集进行聚类, 来对比降维前和降维后的结果。
WDBC数据集有30个属性, 取权值σ≥0.036时, 该数据集降为3维;取权值大于0.034时, 该数据集降为6维;取权值大于0.033时, 该数据集降为15维。降为3维、6维、15维的数据集和原数据集的聚类精度如图6所示, 实验结果表明该数据集降为6维时聚类效果最好。
SPECT Heart数据集有44个属性, 取权值大于0.024时, 该数据集降为5维;取权值大于0.023时, 该数据集降为18维;取权值大于0.022时, 该数据集降为28维。降为5维、18维、28维的数据集和原数据集的聚类精度如图7所示, 实验结果表明该数据集降为18维时聚类效果最好。
Libras Movement数据集有90个属性, 取权值大于0.0111113时, 该数据集降为10维;取权值大于0.0111111时, 该数据集降为34维;取权值大于0.0111110时, 该数据集降为47维。降为10维、34维、47维的数据集和原数据集的聚类精度如图8所示。实验结果表明聚类算法对该数据集的聚类效果较差, 原因是此数据集包含15个类, 类比较多, 聚类算法不能很好地识别, 但是该数据集降为47维时聚类效果有所提高, 仍能体现出本文降维方法的有效性, CADD算法的聚类效果相对好一些, 从而体现了CADD算法的优越性。
由以上实验结果表明: (1) 采用复相关系数的倒数赋权法作为一种属性选择方法是有效的, 并且计算量较小, 适合处理高维数据; (2) 降维要降到合适的维度, 如果维数太少, 则会丢失对聚类重要的属性信息, 如果维数太多, 则会产生“噪声”, 影响聚类结果; (3) 一般的聚类算法不能很好地处理高维且类比较多的数据集, 因此有待于进一步研究能处理高维且类比较多的数据集的聚类算法。
5 结论
对于传统的基于距离的聚类算法, 当数据对象的维数小于或等于30时, 聚类分析往往能够取得良好的聚类效果;维数高于30时, 聚类效果不佳。甚至使用PCA降维后, 聚类算法对高维数据的聚类效果的改进也不是很明显。用复相关系数的倒数赋权法为差异度加权, 并且把复相关系数的倒数赋权法用作一种属性选择方法, 通过设定属性加权系数的阈值参数对数据对象进行降维也能取得较好的聚类结果。
摘要：虽然经典聚类算法能够有效地处理维度较低的数据对象, 但随着维度的增加, 算法的性能和效率就会明显下降。本文在对数据对象间的最大距离和平均距离随维数增加的变化趋势实验基础上, 对聚类算法的聚类精度随数据对象维度增加的变化特征进行了实验研究。同时, 利用复相关系数的倒数对属性进行加权, 提出了利用复相关系数倒数阈值实现降维的方法, 并取得了良好的实验结果。
关键词：高维数据,聚类效果,复相关系数,降维
参考文献
[1]冯永, 吴开贵, 熊忠阳, 等.一种有效的并行高维聚类算法[J].计算机科学, 2005, 32 (3) :216-218.
[2]王永卿.高维海量数据聚类算法研究[D].南宁:广西大学, 2007.
[3][加]Jiawei Han, [加]Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社, 2001.
[4]G Govaert.Simultaneous Clustering of Rows and Columns[J].Control and Cyberyretics, 1995, 24 (4) :437-458.
[5]Inderjit S Dhillon.Co-clustering Documents and Words Using Bipartite Spectral Graph Partitioning[C]//Proceedings and the7th ACM SIGKDD, New York, NY, 2001.
[6]Shigeru Oyanagi, Kazuto Kubota, Ahihiko Nakase.Application of Matrix Clustering to Web Log Analysis an d Access Prediction[C]//7th ACM SIGKDD, San Francisco, CA, 2001.
[7]宋宇辰, 张玉英, 孟海东.一种基于加权欧氏距离聚类方法的研究[J].计算机工程与应用, 2007, 43 (4) :179-180.
[8]孟海东, 宋飞燕, 宋宇辰.面向复杂簇的聚类算法研究与实现[J].计算机应用与软件, 2008, 25 (10) :32-34.
高维空间数据库聚类算法研究 篇2
聚类分析是数据挖掘的重点研究领域,也是研究的热点之一,当前各种聚类技术层出不穷。随着聚类技术的发展以及工程实践应用的深入,聚类的研究目标渐渐地针对的是大型、高维的空间数据库,这给聚类带来了挑战。实际上,在人们日常生活所接触和利用的现实数据中,大约有80%的数据与地理位置、属性及其空间分布有关[1]。
1 空间数据库聚类的基本概念
空间数据聚类是空间数据挖掘的一个重要分支,它是根据某个相似性准则对空间实体集进行自动分组或类,使空间数据库中的数据达到组内差异最小、组间差异最大的过程[2]。空间数据库聚类就是将空间数据库分成相似的对象集。设X是数据集,即:X=(x1,x2……,xm),将X分割成n个类(簇)C1……,Cn,使其满足下面三个条件:Ci≠,i=1,2...n;C1∪C2∪…∪Cn=X;Ci∩Cj≠;i≠j;i,j=1,2...n;其中聚类Ci中包含的对象彼此“更相似”,与其他类中的对象“不相似”[3,4]。
2 主要的空间数据库聚类算法
目前已经研究出来的空间聚类算法有很多种,采用不同的聚类算法,可能有不同的聚类结果。算法的选择主要取决于具体的数据集、数据类型、聚类的目的以及应用背景。对于高维空间数据库,从数据挖掘的技术角度来看,主要的高维空间数据库聚类算法分为层次方法,划分方法,基于密度的方法,基于网格的方法和基于模型的方法[5]。
2.1 层次方法
层次方法(hierarchical method)(也称系统聚类法,系统聚类法为传统统计学方法)采用距离作为衡量聚类的标准,根据层次分解有“自底向上”和“自顶向下”两种方式,进一步划分为合并的和分裂的两种方法。其中合并层次聚类初始时将每一个对象作为单独的簇,然后合并这些簇成越来越大的簇,直到满足某个条件为止或者所有对象在一个簇中。而分裂层次聚类则是先将所有对象看成在一个簇中,然后把它逐渐细分成越来越小的簇,直到满足某个条件为止或每个对象自成一簇。层次聚类法简单直接并且易于理解和应用,但缺点在于:一旦合并或者分裂执行,则不能修正,也没有办法更正错误;没有良好的伸缩性,时间复杂度是O(n2),为克服这一缺点,有人将层次聚类和迭代重定位等聚类技术进行集成,形成多阶段聚类。代表算法有:BIRCH算法[6],CURE算法[7],CHAMELEON算法[8]。
2.2 划分方法
划分方法也叫分割方法,是将一个包含有n个数据对象的数据库组织成k(k≤n)个划分,其中每个划分表示一个类或簇,而且这k个划分满足2个要求:(1)每一个划分至少包含一个对象;(2)每一个对象属于且仅属于一个划分,图1描述了划分方法的基本框图。
对于事先给定的K,算法首先创建一个初始划分,然后采用反复迭代的方法改变划分,使得每一次迭代之后的分组方案都比前一次好。而好的划分标准就是:同一分组中的对象越“接近”越好,而不同分组中的记录越“远离”越好。最著名的两种划分方法是基于质心的k-means方法[9]和基于粒计算的K-medoids算法。
2.3 基于密度的方法
基于密度的方法与层次方法、划分方法的根本区别是:它不是采用距离来衡量相似性的,而是基于密度的。该方法的核心思想就是:只要在指定空间区域中的点的密度大于某个设定的阈值就把它加到与之相近的聚类中去。其优点是可以发现任意形状的簇,抗干扰能力强,较适合空间数据聚类。代表算法有DBSCAN算法、OPTICS算法、DENCLUE算法[10]、SUBCLUSTER算法等。DBSCAN算法通过不断扩大足够高密度区域来进行聚类,它能处理噪声及发现空间数据库中任意形状的聚类,聚类速度快;此算法将一个聚类定义为一组“密度连接”的点集[11]。OP-TICS算法是为聚类分析生成一个增广的簇排序,并不显性地产生结果类簇,这个排序表示了各样本点基于密度的聚类结构[12]。
2.4 基于网格的方法
基于网格的方法首先把数据空间划分成为一定数目单元的网格结构,所有的聚类操作都是以网格中的单元对象进行的。这样处理的主要优点是处理速度很快,处理时间与目标数据库中记录的个数是无关的,只与把数据空间分为多少个单元有关。缺点是划分网格单元太粗糙时,不同聚类对象会被划分到一起,划分网格单元太细化时,会得到很多小的聚类,所以,基于网格的聚类算法存在如何选择合适的单元大小和数目的问题。另外,此算法不适合处理高维的数据,因为网格单元的数目随着维数的增加而呈指数级增长。代表算法有STING算法[13]、CLIQUE算法[14],WAVE-CLUSTER算法[15]则是基于网格与基于密度相结合的方法。
2.5 基于模型的算法
基于模型的方法给每一个簇假定一个模型,接着去寻找数据对给定模型的最佳拟合。它通过构建反映数据点空间分布的密度函数来定位簇,同时还需要考虑噪声数据和离群点的影响,从而产生比较鲁棒的聚类方法。它的一个潜在的假设是,目标数据集是由一系列的概率分布所决定的,代表算法有:统计方法COBWEB、EM、神经网络等。
3 空间数据库聚类方法比较
理想的空间聚类算法应该具有可扩展性、能发现空间任意形状的聚类、用户输入参数少、对噪声不敏感、能处理高维数据、可解释性和可用性。针对这几方面,对以上几种聚类算法进行了比较,见表1。
4 基于高维空间的聚类算法的改进
DBSCAN是一个典型的基于密度的空间聚类算法。其基本思想是采用一定半径范围内包含的空间对象实体的最小数目来定义空间密度的概念,只要一个区域中实体对象的密度大于某个阈值,就将该数据点加入到与之相近的聚类中去。
DBSCAN从任一对象p开始,根据参数ε和Min Pts提取所有从p直接密度可达的对象,如果p是核心对象,那么从p所有密度可达的对象标记为同一类(簇),并从他们进一步扩展,直至找到一个完整的聚类。如果p不是核心对象,则p标记为噪声,然后再选择一个新的对象进行扩展,得到下一个聚类,直到所有的对象都被标记为止,这个过程可能会合并一些密度可达的簇。当没有新的点可以被添加到任何簇时,算法结束。
DBSCAN的算法描述如下:
输入:ε为邻域半径、min Pts是一个簇中点的最小实体数量、SDB数据集
输出:达到阈值要求(ε和min Pts)的聚类区域。
从SDB中读取一个未被处理过的点;
do{
if(该点是核心对象)
寻找所有从该点密度可达的对象,标记为一个簇;
else
读取的点是非核心对象,不做处理;
读SDB的下一个空间对象;
}while(所有点都被处理过);
未加入任何簇的点标记为孤立点(噪声)。
该算法有两个明显的缺点:当数据量增大时,要有较大的内存支持,I/O开销也大;当空间聚类的密度不均时,聚类间距离大,聚类质量较差。针对这两点不足,下面给出改进后的算法,该算法采用分区的并行方式对其进行改进。先将高维空间内数据库降维为二维,再对二维数据库进行分区,分区后对每个区的数据进行聚类,然后再将聚类后的数据合并。
改进后的聚类算法如下:
输入:ε为邻域半径、min Pts是一个簇中点的最小实体数量、SDB分区后的数据集
输出:达到阈值要求(ε和min Pts)的聚类区域。
算法检索完一个点的邻域后,随机选取另一个未被分类的点,重复以上过程,直至所有的点都被分类或归为“噪声”。算法中,考察q的ε-邻域内的点,是最耗时的部分,在没有空间索引的情况下,时间复杂度为O(n2),如果采用空间索引,时间复杂度约为O(1ogn)。
5 总结及研究展望
目前,空间数据挖掘及其相关问题还是一个崭新的研究课题,有关的研究才刚刚开始还不是很深入,需要研究的问题还很多,如医疗成像,卫星探测,遥感解释,多媒体数据库等众多带有价值信息的空间数据的出现,使得空间数据的挖掘成为一个重要领域。由于空间数据库的规模巨大,数据类型和存取方法复杂,所以探索高效的空间数据挖掘一直是一个富有挑战的难题。本文主要是对空间数据的聚类技术进行研究和比较,并改进了基于高度的DB-SCAN算法,该算法减少了I/O开销,在对空间多维数据经过降维、分区后再进行聚类,提高了算法的效率,使其更适合高维空间数据库的数据聚类。
浅谈高维数据挖掘的现状与方法 篇3
数据挖掘 (Data Mining) 是在20世纪80年代被提出来的, 90年代取得发展, 是当今数据库系统及其应用领域中的一个热点话题。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的原始数据中, 提取隐含在其中的、新颖的、潜在有用的、并且最终可理解的模式的非平凡过程, 并进行数据分析、数据融合 (Data Fusion) 以及决策支持的过程。
数据挖掘是一门交叉学科, 主要包括:数据库技术、人工智能、模式识别、统计学、信息搜索技术、数据可视化和高性能计算等。数据挖掘主要分3个阶段:数据准备、数据挖掘、结果的评价和表达。数据挖掘包括以下几个基本过程: (1) 确定研究目标; (2) 数据的收集与整理; (3) 建立合适的数据挖掘模型; (4) 分析和评价模型; (5) 知识同化, 即将数据挖掘中得到的信息应用到实际问题提出执行方案。数据挖掘方法通常分为两类:描述性方法和预测性方法。常用的方法包括:关联规则、决策树、聚类分析、回归分析、神经网络、预测估计、时间序列、异常分析、描述和可视化法等。
数据挖掘领域的具有十大经典算法:C4.5, k-Means, SVM, Apriori, EM, Page Rank, Ada Boost, k NN, Naive Bayes, and CART。常用的数据挖掘常用软件有:clementine, R软件, Weka软件。
2、高维数据简介
高维数据挖掘是基于高维度的一种数据挖掘, 数据挖掘领域并没有明确定义说维数达到多少称之为高维数据集, 但通常认为当维数增长到使一般的数据处理明显变得异常困难时, 该数据集即可认为是高维数据集。它和传统的数据挖掘最主要的区别在于它的高维度。目前高维数据挖掘已成为数据挖掘的重点和难点。如各种类型的贸易交易数据、Web文档、基因表达数据、WEB使用数据及多媒体数据等, 它们的维度 (属性) 通常可以达到成百上千维。
3、高维数据对于数据挖掘产生的影响
在高维空间中, 一方面引起基于索引结构的数据挖掘算法的性能下降, 另一方面很多基于全空间距离函数的挖掘方法也会失效。总的来说高维数据会对传统意义上的数据挖掘的影响主要存在以下几个方面:
(1) 聚类算法
在高维空间中很多情况下距离度量已经失效。另外在高维空间中索引结构的失效, 网格数随维数呈指数级增长的问题也使得不再有效。
(2) 关联规则挖掘
大多数频繁集挖掘算法都是基于特征计数的, 当维数增加, 特征的组合也呈指数级的增长, 这使得当维数达到一定量级时不可能再在这个空间中进行搜索。
(3) 异常检测
高维数据具有稀疏性, 它的稀疏性使得原来数据挖掘中对于“异常”检测的方法变得无法操作。
4、研究现状介绍
然后正因为高维数据具有“稀疏性”和“异质性”特点。解决的方法可以通过降维将数据从高维降到低维, 然后用低维数据的处理办法进行处理。
基于回归分析的方法当中中正则化方法是进行数据挖掘的最重要方法, 其主要的做法就是在目标函数上增加一个适当的惩罚函数, 利用惩罚参数的调节, 使得最终的估计具有自动的稀疏性, 从而实现变量的选择。实际处理中, 使用线性降维是一个主要研究方向。线性降维方法, 主要包括主成分分析、投影寻踪、线性奇异分析等。针对高维数据集的非线性特性, 近年来发展LLE、ISOMAP、多维尺度分析等非线性局部嵌入方法。近年来Hongyuan Zha和Zhenyue Zhang提出了一种可用于非线性流形学习的局部线性光滑方法;de Silva和Joshua B.Tenenbaum研究了曲线流形的非监督学习问题。L.Saul和S.Roweis提出了局部线性嵌入方法, 等等。
5、总结与展望
随着大数据时代的到来, 人们对数据的研究和利用越来越多。高维数据挖掘是数据挖掘理论研究的一个研究热点, 也是数据挖掘应用必须关注的一个实际问题。本文介绍了在高维数据的研究背景和研究现状, 总结了一些在已有的研究中方法策略。高维数据挖掘并没有一个通用的模型或实现方法, 只有与实际情况相结合并不断地改进模型才具有实际的价值。如果利用常用算法来建立适合的高维流数据挖掘平台, 为高维流数据挖掘的应用提供基础, 将有利于推动研究工作的深化和扩展, 也有利于创造商业价值。
摘要：数据挖掘出现于20世纪80年代后期, 是数据库研究中一个很有应用价值的领域.随着大数据出现, 高维数据的挖掘成为了热点和难点。本文在介绍传统数据挖掘的基础上, 介绍了高维数据的特点以及目前面临的问题, 高维数据挖掘最新研究的情况, 并在此基础上进行了总结和展望。
关键词：数据挖掘,高维数据挖掘,稀疏性
参考文献
[1]李泽安等, Beta回归模型在数据挖掘预测中的应用, 南通大学学报 (自然科学版) 2009, 8 (3) :83-85