高维数据降维（精选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
所谓数据降维技术, 其实就是通过使用一个线性或者非线性的数学变换, 把数据的样本点从高维空间中映射到一个地位空间中, 这样我们就可以得到原始高维数据集的一个内在的紧致低维表示。流形学习给我们提供了这样一个很好的途径。近年来, 在前人的基础上, 国内外学者对基于流形学习的非线性的降维方法在理论基础和实际应用方面都做了很大的工作, 进一步完善了流形学习的理论, 扩展了流形学习方法的应用范围, 提高了流形学习方法的降维效果, 但是, 这些改进的流形学习算法在运用到现实中的高维数据集时还存在着一些问题, 其中一个最重要的问题就是, 不管是以前的流形学习算法还是改进的流形学习算法, 这些数据降维算法都是假设我们索要处理的高维数据来自于同一个数据流形, 并没有考虑到数据有可能采集于几个分散的不同的高维数据流形上, 然而, 我们在现实中所遇到的高维数据不仅仅都是在同一个高维数据流形上, 还有可能采样与多个不连续的低维非线性流形或者是采样于一个流形上的几个不连续的部分, 比如视频监控中多人脸多表情数据集。
为了学习高维多流形数据集的内在的低维几何结构, 国内外学者提出了相应的监督和无监督的多流形学习算法, 孟德宇等人提出了分解——整合算法, 提出了一种基于切空间扩展的算法, 但是它们在成功展现各个流形的内在几何结构、算法的鲁棒性、泛化能力、准确划分各流形进而有效的判定流形个数等方面的能力还比较欠缺。本文在孟德宇等人的基础上提出了等距离多流形学习的一般过程, 最后提出一种改进的多流形学习算法。
1 等距离多流形学习的一般步骤
多流形同单一的数据流形不一样, 更主要的关心同一数据流形上的信息, 受到分解——整合的算法启发, 本文提出了等距离多流形学习的一般步骤:
1.1 分解过程
对整个数据集进行聚类, 如果高维数据样本点分布在不同的流形上或者同一流形的不同区域, 这些情况都可以通过聚类方法判别出来。即使流形彼此重叠, 它们仍然可以被识别。通过此步骤, 数据集X被分成几个部分, 每个部分被人为是一个单独的数据流行。
估计流行的本征位数。
分别学习单独的数据流形
1.2 组合过程
在低维空间中保持整个数据流集的整体构架I, I可以表示全局结构, 让RY1低维嵌入到I。
通过参照I, 把YmS转换到一个单一的坐标系中, 为了忠实的保持多流行数据之间的关系, 这里可以用欧几里德变换, 最后输出低维嵌入结果。
2 改进的多流形学习算法
基于孟德宇等人提出的切空间扩展算法和等距离多流形学习的一般步骤, 本文提出了一种改进的多流形学习算法, 因为该算法实在Isomap的基础之上, 故本文算法称为M-Isomap算法, 按照我们所提出的等距离多流行学习的一般步骤, 本文算法也分了这两个步骤。
2.1 分解步骤
首先在给定的数据集X上运行基于采样密度和流形弯曲度的动态领域扩展切空间的方法, 这样就可以准确的获得数据集的各个子流行{Xm}=1, 2, …, M。
估计各个子流行的本征维数。假设Xm的本征维数为dm, 领域大小为km或者εm, 令d=max{dm}, 重构Xm的领域图, 新的领域图能够更好的近似整个流形的测地距离。
在各个子流形上分别运行古典的Isomap算法, 可以得到Xm相应的低维嵌入为Ym, 并记Ym=yim, i=1, 2, …, M。
2.2 整合步骤
保持数据集X的整体构架。首先计算不同子流形之间的距离矩阵, 假设∈Xm, ∈Xn, 则它们之间的距离为:
其中dm (, ) 是Xm的领域图中的最短距离, 尽管dm (, ) 有可能不是整个连通图上的最短路径, 上式依然是一种近似各个流形之间的距离的有效方法。
当Dmn被假定为流形Xm和流形Xn之间的距离矩阵, 则各个子流形间的最远距离可以表示为:
假设
其中A为一个正交矩阵, β为一个位移向量。则对于m个数据流形, 可以假设欧式转换为:
一般情况下, 可以写成矩阵的形式:
e为一个单位向量, 通过最小二乘法及正则化等一系列操作, 最终得到:
通过以上, 低维嵌入Ym就可以通过i欧几里德变换转化为全局坐标系统。
2.3 实验结果
通过对瑞士卷数据集进行采样100个样本在MATLAB7.0版本上进行实验其中Isomap领域半径k=4, 本文的=20, ε=0.5实验结果如图1所示。
通过实验能够看出本文算法的有效性及比传统的优越性。
3 总结
本文通过对传统算法的分析, 进行了一定的改进, 取得了较好的结果, 说明了本文算法的有效性, 当然本文算法也存在着不足之处, 如时间复杂度比较大, 怎样提高算法的时间复杂度需要进一步研究。
参考文献
[1]孟德宇.关于流形学习若干基础问题与核心算法的研究[J].2008.
[2]陈省身.微分几何学讲义[M].北京大学出版社, 1983.
高维空间数据库聚类算法研究 篇3
聚类分析是数据挖掘的重点研究领域,也是研究的热点之一,当前各种聚类技术层出不穷。随着聚类技术的发展以及工程实践应用的深入,聚类的研究目标渐渐地针对的是大型、高维的空间数据库,这给聚类带来了挑战。实际上,在人们日常生活所接触和利用的现实数据中,大约有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开销,在对空间多维数据经过降维、分区后再进行聚类,提高了算法的效率,使其更适合高维空间数据库的数据聚类。