数据聚类分析（精选12篇）
数据聚类分析 篇1
摘要：随着近几年我国经济的不断发展, 其数据量也越来越大, 大数据的出现使得数据挖掘技术得到了广泛重视, 而聚类分析作为数据挖掘的核心的也越来越受到关注。本文主要介绍聚类分析的具体含义, 并分析聚类分析的种类以及聚类分析进行划分时其簇的类型来对聚类分析算法进行详细描述, 并通过聚类算法在实践中的应用, 为数据挖掘在具体实践中的应用提供依据。
关键词：数据挖掘,聚类分析,簇
0 引言
数据挖掘是一个涉及到很多领域的学科, 因为大数据的出现使得数据挖掘需要运用统计学, 人工智能等等来对数据进行处理分析。而聚类算法作为数据挖掘的核心方法之一, 已经在科研和具体实践中得到了广泛的应用。聚类算法是数据挖掘中相对而言较复杂的算法, 比分类算法在理解和处理上都有难度。聚类算法在实践中, 要想有意义, 就必须具有可伸缩性, 即对不同大小的数据集合, 处理效果要是一致的;聚类分析可以处理不同类型的数据, 并且对于不同形状的簇, 也要有合理的效果;聚类算法还可以识别其噪声数据, 抛弃不相干的的噪声, 聚类结果有逻辑上的意义, 有可解释性;聚类还可以处理高纬度的数据, 而且在合理的时间内处理完成。
1 聚类分析
1.1 聚类分析概念
所谓聚类就是将一些数据集合进行分组, 每一组的对象之间是有相似的属性。聚类分析就是将给定的数据对象集合分成不同的簇, 所谓的簇即是聚类产生的对象的集合, 而簇的特点是每个簇内其属性相似, 簇间属性不同。目标就是使类之间差异尽可能大, 类内部的相似度尽可能大。
聚类和分类是完全不同的, 分类的目标类别是已知的, 而聚类的结果是未知的, 需要不停的尝试聚类的结果类别数 (除特殊情况, 如已知总共的类别数) 。聚类分析可以通过建模的方式简化数据, 建模方法有分解法, 模糊聚类等方法。从数据挖掘的角度来说, 聚类算法是一种无监督学习的方式, 所产生的簇是隐含的, 这是与分类算法最大的不同点。在无监督学习中, 用来训练的样本是没有进行标记的, 事先不知道类别, 通过聚类算法后, 每个元素被分到某个类中, 才有了类别。
聚类分析的过程是不断探索的, 因此开始时, 不必事先确定分类标准, 聚类算法能够从样本自身中进行挖掘, 进行分类。使用不同的聚类方法, 其结果往往不同, 同样的聚类算法, 对不同的数据, 聚类结果也可能不同。
在运用到实际生活中, 其聚类分析是数据挖掘的核心, 聚类可以独立获得其散布, 观察其数据的特点, 对其进行分析。
1.2 聚类的类型
传统的聚类分析计算方法有以下几种类型:
(1) 划分法
对于一个数据集, 其大小为M, 划分结果为K个类, K小于M。结果中每个类至少包含一个元素;每一个元素仅属于一个类。一般情况下K未知, 算法首先给出一个初始的分组 (有时为随机划分) , 然后通过某种确定的方法, 衡量分组的好坏。得到一个衡量值。再通过迭代的方法改变分组里的元素, 再次计算衡量值, 选择其中最大衡量值的分组方式, 思想是:同一组中的元素距离尽可能的近, 而不同分组之间的距离尽可能的远。使用这种思想的最简单易懂应用最广泛的的算法是K-MEANS算法。
(2) 层次聚类
有些数据可以进行层次分解, 这种聚类方法要求数据满足层次性。不是所有的数据都适应。划分层次时, 需要设定一个停止条件。在实际执行中, 层次聚类可分为“自底向上”和“自顶向下”两种。“自底向上”算法的意思是, 每一个元素刚开始都是一个单独的类, 在下一轮迭代中, 算法把最相近的元素归为一个类, 此处需要事先设定好一个相似度, 大于此相似度的才归类, 否则仍然自己单独一类, 如果不满足要求, 则继续进行迭代。再次迭代时, 相似度要相应的降低, 以便聚类, 直到所产生的类满足要求。这种思想的典型算法是BIRCH算法。
(3) 基于密度的聚类
以上两种方法, 在度量相似度时候, 都是基于各种距离的, 而基于密度的聚类不考虑元素之间的距离。基于距离的算法, 其缺点是只能发现“类圆形”的簇, 对于特殊形状的簇效果很差。基于密度的算法的思想是, 只要某一个区域中点的密度大于事先设定好的值, 就把这个点归到和它最相近的类中。基于密度的典型算法有DBSCAN算法等。
2 聚类分析算法
(1) K原型算法
该算法通过改进其K均值算法, 使得该算法能够处理符号属性的数据。
(2) 层次算法 (CURE)
CURE算法选择类是以数据点作为依据, 合并类是按照距离最近的类将其合并, 直到其合并的个数满足要求位置。层次算法不在使用半径或所有点表示类别, 而是从了类别选择数量一定并且分布比较好的点来描述该类别, 并且为了使这些点更加靠近中心, 乘以一个因子, 而这个因子还可以将噪音的影响降到最低。将一个类用代表点来表示, 使得类在扩展时, 并不一定要按照球形的方式来扩展, 采用随机抽样的方法提升空间, 可以调整类的形状, 来表示更大形状范围的簇。
(3) 划分算法 (CLARANS)
划分算法的过程是, 先随机选一个点, 随机对周围设定不超过最大邻居的邻接点, 假如找出一个比它更好的点, 就将其移入到该点中, 如果没有更好的点则该点就作为其局部最小量。然后再随机选择一个点, 去寻找另一个局部最小的点。
(4) 基于密度算法
这种方法也叫DBSCAN算法, 主要是利用类的密度连通性对类进行研究分析。其思想是, 对于任意一个对象, 在其给定的半径空间内, 含有的对象数不能少于某一数值。只要区域的密度符合要求, 就归为一类 (一簇) , 而不关心类的形状和大小, 其优点的其聚类的速度快, 能够处理噪声, 能够处理各种奇形怪状的簇。但其缺点也比较明显, 一旦遇到大数据的样本则需要的内存也随之增加, 其很消耗I/O。如果簇的密度不均匀, 则效果也不够好。
3 聚类分析在数据挖掘中的应用
在商业领域内, 聚类较早的应用时发现客户群, 对客户进行聚类, 每个类之间的购买模式不同, 针对不同客户群, 采取不同的措施。
聚类算法可以用来细化细分市场, 用来分析消费者的消费特点, 归纳出新的潜在市场。互联网公司纷纷研究大数据和聚类分析, 就是为了研究客户的行为特点, 提高用户体验。
聚类算法还可以进行动植物分类, 基因工程的大幅度进展, 也跟大数据技术, 分类聚类技术有关, 对基因进行分类和聚类, 是当前研究的热点。
聚类分析应用在保险领域, 可以通过消费水平来对购买了汽车保险的人进行分组, 或者根据住宅的类型, 住宅的位置, 住宅的价值等属性, 来对一个城市的房产所有人进行分组, 针对不同的分组, 推荐不同的保险措施。
聚类分析在Internet上广泛用来文本归类。
聚类分析在电子商务中也有更加广泛的应用。数据挖掘通过用户浏览网页所产生的互动数据, 如点击, 购买, 加入购物车等行为, 对客户进行聚类分析。对不同类别的客户, 给以不同的推荐和激励措施, 极大的提高了用户体验, 极大帮助了电子商务的发展。
4 总结
数据挖掘是现如今广泛研究的热点课题, 数据挖掘可以从大量的数据中挖掘有价值的数据, 并制定用户可以理解的模式。聚类分析做为数据挖掘的核心功能之一, 本文对聚类分析做出了深入的分析, 通过分析几种聚类算法在数据挖掘中的应用, 可以对大数据进行处理, 并可以将其运用到各行各业当中。
参考文献
[1]Margart H.Dunham, DATA MINING Introductory and Advanced Topics, 北京:清华大学出版社, 2011.
[2]郭军华, 数据挖掘中聚类分析的研究:[硕士学位论文], 湖北:武汉理工大学, 2012.
数据聚类分析 篇2
以TM数据为基础数据源,经解译分类后,将珠江三角洲景观分为10个景观类型,并在两种空间层次下将珠江三角洲分别划分为9个和23个景观生态子区.在GIS与景观斑块分析软件Patch Analyst 3.0支持下计算各子区的`景观特征指数.通过各子区的景观指数对比分析,探讨研究区范围内景观格局的空间差异,揭示人类活动、自然干扰等各种景现生态机制对区域景观生态的影响.
作 者：徐小飞 高杨 XU Xiao-fei GAO Yang 作者单位：徐小飞,XU Xiao-fei(广东省水利水电科学研究院,广东,广州,510610)
高杨,GAO Yang(广东省生态环境与土壤研究所,广东,广州,510650)
数据聚类分析 篇3
关键词：微博；聚类；负载均衡；一致HASH算法
中图分类号：TP212.9 文献标识码：A文章编号：1007-9599(2012)03-0000-02
Application of Clustering-based Dynamic Load Balancing in the Data Collection
Liu Dezhi
(Faculty of Computer,Guangdong University of Technology,Guangzhou510006,China)
Abstract:To build social networks based on microblog,we need to provide large microblogging data source,however how to efficient access to the microblogging information is to build social networks of the major challenges facing.this paper presents dynamic load balancing method of data collection based on clustering,combined with clustering and dynamic load balancing is a new attempt,the tests show that it can meet the demand for microblogging data collection.
Keywords:Microblog;Clustering;Load balance;Consistency HASH algorithm
一、引言
随着web2.0技术的快速发展，微博的出现,使人们进入了网络全民媒体的生活方式[1]。面对大规模规模的数据，如何将任务均衡的分布在每台爬虫机上，是一个具有挑战性的问题。本文提出基于聚类的动态负载均衡的方法，将负载率过高的处理机进行任务转移，达到动态负载均衡的目的。
二、动态负载均衡模型
采集系统的逻辑架构结构如图1所示，任务管理节点将任务分配到任务数据节点上，然后由管理节点将任务结果的相关信息通知客户端，客户端再从相应的任务节点中提取结果。
图1 系统结构图
（一）处理机聚类
将处理机的权重定义为一组向量，公式如下：
其中：L(C)_M为CPU利用率的阀值，L(M) _M为内存利用率的阀值，L(D) _M为磁盘I/O量的阀值，L(P) _M为运行态进程数量的阀值。
根据权值向量，将具有同类性能的处理机划分为同一个类别。结合本系统的特点，采用启发式聚类算法比较适合。
（二）动态反馈调整
处理机的负载率R(i)定义如下：
其中L(Ci)、L(Mi)、L(Di)、L(Pi)分别为处理机i当前CPU的利用率，内存的利用率，磁盘I/O量，运行态进程数量。
在该系统中采用一种局部优先的原则，即优先对类的内部处理机进行动态负载调整。
三、算法描述
（一）聚类算法
处理机聚类采用经典的k-means[5]算法，分成K个类别，并将类别信息保存在任务管理节点上。为了方便算法描述，进行如下定义：
定义 1（处理机之间的距离）设处理机中集合中的Pi和Pj的权重分别为W(pi)和W(pj)，则Pi和Pj的距离为
定义 2（处理机到类的距离）设处理机类为C，聚类的中心点为Pi，Pi∈C则设备Pj到类C的距离等于Pj到Pi的距离。
得到类别集合后，将任务按照W(Cj)的比例分配到各个类别中，类内部采用一致hash布局机制。
（二）负载调整
对于每个类Dm的处理机而言，每隔时间t动态获取负载信息，设H为负载率最高的处理机，L为负载率最低的处理机。设处理节点的虚拟机节点为VP1 ,… ,VPm，RAVG 为类中处理机所有虚节点的平均负载率。具体的伪代码如下：
(1) while(RH - RL ≥R_in)
(2) Sort(VH,VL);//将虚节点按照负载率的大小进行降序排序
(3) ΔNUM=min{(RAVG –Rz), (RH –RAVG)};//需要转移的数量
(4) Δnum=0;
(5) while((Δnum<ΔNUM)&& RH > RL)
(6)int_Transmit(VHi , VLj);//类内部负载转移
(7) i++，j--;
(8) Δnum+= VHi ;
(9)R_update(H,L);//将H和L的负载率更新
(10) end while
(11) R_update(Dm);//将Dm类中的负载率更新
(12)if(RAVG≥R_out)then//启动类间负载转移算法。
(13)out_Transmit(H);// 类间负载转移。
(14)endif
(15)getR _MAX_MIN(D,H,L);//更新H、L
(16)end while
该算法采用由内向外的负载调整策略，在内部通过反复执行int_Transmit(VHi , VLj)函数同时更新H和L，将负载率之差缩小在R_in的范围内。如果Dm中负载率的平均值超过R_out，将执行out_Transmit(H)函数，将警告信号发送给任务管理节点，H的负载转移去向由ManageNode决定，通过类间负载转移后，可以使得(RH - RL)的值维持在R_in内。
（三）类内任务迁移
当增加处理机时，首先与每个类D的中心点C进行距离比较，找到最近距离的类别，找到类别之后，采用一致hash原则。删除旧的处理机比较简单，不在描述。
四、实验与结果分析
利用20台Dell R510服务器虚拟出100台不同性能的处理机。在开始进行实验时需要设置参数，配置参数如表1所示。
表1配置参数
从实验的结果来看，没有出现那台处理机的负载率过高或者过低。然而该模型的稳定性比较依赖初始参数值，由对比图2可以看出，反馈时间间隔和聚类个数k的大小对系统的负载性能都会比较大的影响。
图2不同参数的负载性能对比测试
五、结束语
本文提出一种大规模的面向微博数据的采集模型，结合传统的一致hash数据布局机制，引进k-means聚类算法，并同时对所有处理节点进行动态负载调整，从实验结果数据来看，能达到实时负载平衡。但该模型仍然存在一定的缺陷，聚类个数K以及反馈时间间隔的设定，对系统负载平衡效果有比较大的影响，如何寻找最佳的参数值是下一步研究的重点。
参考文献：
[1]Smith B G. Socially Distributing Public Relations：Twitter，Haiti，and Interactivity in Social Media[J].Public Relations Review，2010，36(4)：329-335
[2]Karger D,Lehman E,Leighton T,Levine M, Lewin D. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web.In:Proc.of the 29th Annual ACM Symp. on Theory of Computing (STOC’97).El Paso:ACM Press,1997,654-663
[3]邓成玉,章剑涛,刘永山.动态负载均衡策略及相关模型研究[J].计算机工程与应用,2011,47(8):131-134.
[4]贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究，2007,24(1):10-14
[5]Jain A K,Dubes R C. Algorithms for clustering data[M].Englewood Cliffs,New Jersey:Prentice Hall,1998
[作者简介]
刘德志（1988-），男（汉族），湖南省衡阳市人，在读硕士研究生，主要研究方向为网络监控与智能决策
高维数据对象聚类算法效果分析 篇4
聚类分析是数据挖掘领域中的一项重要的研究课题, 高维数据对象的聚类又是聚类分析的重要研究课题, 也是涉及到聚类算法是否能够有效地应用于各个领域, 例如多属性 (高维) 流数据的聚类分析。高维数据的特点表现为: (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.
数据聚类分析 篇5
目前，随着经济改革的不断深人，居民的生活水平改善的同时，结构也在逐步级。如何有针对性增强经济发展，这就需要我们分析每个城市的经济发展水平，有的放矢地制定经济发展计划。
二、实证分析
数据来源及处理：
根据数据的可获得性、权威性和统一统计口径原则，本文从国家统计局中得到关于全国各地区31个省市自治区城镇生活费支出的相关数据。主要包括居民家庭平均每人食品、衣着、居住、家庭设备及用品、医疗保健、交通通信、文教娱乐以及其他消费支出共分为八大类，这些指标分别记为X1、X2、X3、X4、X5、X6、X7、X8。
(一)因子分析
1.模型检测
一般，满足线性相关性的变量才可以做因子分析。由上图可知，这八个指标间相似性的相关系数矩阵中绝大多数系数值都较高，说明原始数据适合做因子分析。
由KMO抽样适度测度值可知：kaiser-MSA=0.77294558，大于0.5，一般认为此值越大，做因子分析的效果越好。
其次，我们依据据旋转前的先验共同度估计结果λ>1，且累积方差贡献率大于或等于85%的变量作为公因子的要求，所以特征根λ1λ2λ3符合要求，三者累积方差贡献率达到90.80%，大于85%，说明前三个公因子可以解释原始变量的大部分信息量，因此提取前三个公因子是比较科学的。
从最初公因子载荷来看，八个变量在第一个公因子F1上的载荷都很高，这些变量同第一个公因子高度相关。但是，一般情况下，我们对所提取的公因子之间的相关性较低，或者不具有相关性。我们将采用方差最大化来进行对因子进行旋转增强公因子解释性。
由旋转后得到的因子负荷矩阵可知，食品、家庭、其他商品和服务这六项指标在第一个公因子F1上的载荷很高，说明第一个公因子主要体现居民生活的必要需求，同时也存在享受型的生活支出，如接受娱乐服务。因此，我们把第一个公因子定为日常生活因子。其次，衣着、交通与通信等指标在第二个公因子上的载荷很高，表明反映了外在生活因子。第三个公因子可以被定义为居住因子。
2.提取因子
为了比较分析各地区消费差异，我们需进一步计算各地区城镇居民消费支出状况的综合得分情况。我们需要先得到三个公因子计算公式，然后在以每个公共因子的贡献率作为权值，进而计算综合因子得分值。于是可以得到：
公共因子的计算公式为：
F1=0.93390*X1+0.22475*X2+0.63973*X3+0.85063*X4+0.10249*X5+0.91364*X6+0.84928*X7+0.84313*X8
F2=0.07529*X1+0.20548*X2+0.71759*X3+018865*X4+0.81880*X5+0.24581*X6+0.33126*X7+0.18732*X8
F3==0.00141*X1+0.093796*X2-0.01870*X3+0.30345*X4+0.51308*X5+0.12583*X6+0.24042*X7+0.38424*X8
將这三个公因子以各自的方差贡献率占累积方差贡献率的比重为权重来加权计算综合得分
F=4.3328965*F1+1.4740923*F2+1.4567295*F3
3.综合得分比较
由上图分析可知：对第一公因子日常生活因子来讲，东部地区发达的得分普遍较高，东北和中部地区得分一般，而偏远边界地区较低;第二个公因子外在生活因子得分：北方地区普遍偏高，南方地区相对较低，这可能与天气相关，一般来说，较冷的地区用于衣着比例较高，而天气更温和的南方地区反而交通与通讯的支出占消费支出总额的比重较高，这可能与发达的南方交通设施有关。从公因子居住因子F3得分来看，北京山西上海得分较高，原因可归纳为发达地区经济发展吸引了更多的人，所以相对来说住房需求较大，房价普遍较高。
最后分析31个地区的综合得分：其中上海得分最高为14.1972，上海为11.0372，;而贵州为-4.3822，青藏为-4.1430，黑龙江为-3.9581;可以看出北上广津超一线发达地区得分普遍较高，这与他们的经济发展密不可分，其次沿海二线城市欠发达地区得分一般，最后相对落后地区综合得分则较低。
(二)聚类分析
为了进一步验证结果;我们将采用聚类分析将八个指标重新聚类成三部分如下图所示，可以看出第一类包含5个指标解释方差4.4360173，第二类指标包含两个指标，解释了1.65552的.方差，最后一类只有一个指标包含了1的方差。总共解释了7.015692的方差，占总体方差的87.70%。
由上图标准化的回归系数阵，我们可知
C1=0.21026*X1+0.21091*X4+0.21993*X6+0.21681*X7+0.21278*X8
C2=0.54956*X2+0.54956*X5
C3=X3
分析可知：第一类包含了食品，家庭设备及用品，文教娱乐，医疗保健和其他消费，我们可以归类为日常生活因子;第二类外在因子包含了衣服和交通;最后一类也可以归纳为居住因子。
最后我们通过聚类分析的树状图可知，北上广江津发达地区可以聚为一类，因为这些城市居民的收入较高，因此有较强的消费能力。而吉林西藏青海可以聚为一类，这是因为落后的中西部地区，消费能力较弱;其他的聚为另一类。这与我们上述因子分析的结果基本一致。当前我国国民经济运行的主要问题之一是需求不足，消费需求是整个总需求的一个重要方面。
上述分析表明，我国的消费需求呈现出极大的地区不平衡性。而这种三梯度的地区性消费不均现象是与经济发展相关的。因此，我们需大力改善的第三梯度经济，扶持第二梯度地区经济，才能从根本上解决我国消费需求不均衡现象。
三、统计结果分析
通过因子分析和聚类分析可知：我国经济依地区划分主要分为三个梯度，居民消费支出的规模主要受地区经济发展水平影响。首先第一梯度经济发达地区要继续保持领头羊的作用，帮助他们摆脱经济发展怪圈，政府有重点地引导具有地方特色第二梯度地区要持续健康发展的同时，我们要大力增加科技引进，不断为经济发展注入新鲜血液。同时，政府需要大力挖掘文化休闲娱乐等建设。对于第三梯度经济欠发达地区，我们要从根本上解决需求不足，发展落后的问题，可以从减少消费税收的形式刺激一般消费需求，以此进一步提高经济落后地区城镇居民的消费水平。同时政府需要加大交通设施建设改善交通不便现象。
总之，国家实现“刺激消费，扩大内需，刺激经济增长”的目的，需要有的放矢地根据地区发展有针对性的提出发展策略。
参考文献：
[1]孙彩虹.我国城镇居民消费结构变动的因子分析[J].重庆工商大学学报(西部论坛)，(1).
[2]余明江，季丽，胡云霞.我国城镇居民消费结构的因子分析[J].安徽工业大学学报，(25).
[3]国家统计局.中国统计年鉴[M].北京：中国统计出版社，.
聚类分析在学习评价中的应用 篇6
关键词 有监督分类 无监督分类 模糊聚类分析
目前在我国教育各个环节中,对学习参与者,如:学生,的学习效能,主要采用考试的方式进行评测,即根据学习参与者在考试中获得的成绩进行学习效能检测。可表示为:学习参与者S学习课程P,在S学习课程P的过程中,会参与1,2,3……,n次测试,获得X1,...,Xn个测试成绩,S在学习课程P的过程中获得的全部成绩T记做(X1,...,Xn)T为一个n维的向量。记为:。
在中学阶段对学生S的学习效能评价是基于T(X1,...,Xn)T中各元素的算术平均值进行,即,X=∑Xi,而对学生S在课程P的第n+1次测试中,所应获得的成绩的预期是基于|Xn+1-|≤ε进行的,ε:为学习参与者第n+1次测试成绩偏差预测,基于教师的经验和测试的难度。这种评价方法,在中学阶段,能有效的评价和预测学生成绩的发展,然而将这种评价方法应用在大学教育中,就会不完全适用。
一、问题提出
首先,大学教育采用学分制,学科单科结业方式,基本不存在课程学习过程中反复测试的情况,课程结业考试往往就是课程学习的唯一测试,即:学生S在学习课程P的过程中获得的全部成绩T为:T(X1)T =X1 这种情况下,由于原始数据的不足,使用算术平均值方法,已经没有任何意义。如下表所示数据:
在结业考试中,学生1、学生2、学生3的考试总成绩是一样的,我们无法使用算术平均值方法,分析出学生1、2、3之间的学习差异。但从具体的知识点分析,学生1成绩记为(5,5,3,2,5,5,10,10,10,10)T;学生2成绩记为(0,0,5,5,6,4,10,10,10,15)T;学生3成绩记为(5,0,3,2,5,5,0,15,15,15)T,形成3个并不等价的单独向量,这三者在他们存在的线性空间中并不相等。自然这3个单独向量所代表的3个学生的成绩也不相等了。
所以,当我们将中学阶段的学生成绩评价方法,推广到大学阶段时,就会出现如下情况:
(一)对任意一门课程,在课程学习过程中,不存在多次测试成绩X1,...,Xn,从而也就无法用统计的方法求出。
(二)当只存在单次测试成绩X1时,X1中存在n个知识点,n个知识点构成一个(X1,...,Xn)T的n阶向量。
(三)对于任意一门课程,学生成绩评价的实质是对m个参加测试的学生,所获得的m个n阶向量的比较和分类。
二、问题解决
(一)我们知道数学是从量的方面,研究客观世界的一门科学。
一提起数学人们自然想到它是精确的,然而精确的数学有时不能描述现实世界中存在的大量模糊现象,如:好与坏,长与短,热与冷。在学生成绩评价过程中,学生成绩的好与坏,就是一对模糊量,很难说成绩超过90分的就是好学生,而89分的就是学的不好的学生,这时模糊数学就派上用场。模糊数学是指将传统的真值值域从{0,1}扩展到[0,1]区间的有理数,并利用真值函数t:{命题}→[0,1]来表达连续或者“模糊”逻辑。应用模糊数学判断学生成绩“好与坏”,就会得出好、有点好、不好不坏、有点坏、坏等多值判定,而这种判定,更符合教师对学生成绩的分析。
(二)对学生成绩的分析实质是一个模式识别的过程,模式识别又称模式分类,从处理问题的性质和解决问题的方法,模式识别可分为有监督分类和无监督分类。
有监督分类,又称有教师分类或有指导分类,在这种分类中,已知模式类别和某些样本的先验属性,首先用具有类别标记的样本对分类系统进行训练,使该分类系统能够对所有已知样本进行分类。如:m个学生参加考试,在考试之前我们已经知道第i个学生Si是好学生,在本次考试中学生Si的成绩是Xi,则根据有监督分类,在本次考试中所有成绩超过Xi的都是好学生,反之,则是学习成绩较差的学生。有监督分析方法缺点:
1.无法解决“90分是好学生,89分是学习较差学生”这一传统困境。
2.很难预先获得有标识的样本,在每次考试前很难确定好学生一定在本次考试中取得好成绩,即“好学生并不总能获得好成绩”。
3.“好学生”往往不是一个人,而是一群人,判定规则的制定是个难题。
无监督分类,又称聚类分析,是指在没有先验知识的情况下,对已有的全体无标识样本进行分类,聚类就是按照一定的要求和规律对事务进行区分和分类的过程。在这一过程中,没有任何先验知识,没有任何教师指导,仅仅依靠事物间的相似性作为类属划分准则。无监督分析,可以轻松解决“难于预先获得有标识样本”和“判定规则制订困难”等难题,然而仍无法解决“90分是好学生,89分是学习较差学生”这一传统问题。
(三)模糊聚类分析:
传统的聚类分析是一种硬划分,它将每个待辨识的对象严格的划分在某类中,具有“非此即彼”的性质,因此这种类别划分的界限是分明的,而实际上大多数对象并没有严格的属性,它们在性质和类属上存在中介性,具有“亦此亦彼”的性质
如上表,4号样本即可划入(92,94,90,89,88)这一集合中,也可以划入(89,88,86,87,84,85)这一集合中,这种划分轻易地解决了“90分是好学生,89分是学习较差学生”这一传统困境。使用模糊数学的模糊集理论的提出,为这种划分提供了有力的分析工具,并将之称为模糊聚类分析,由于模糊聚类分析更容易反映问题的实质,从而成为聚类分析的主流。
(四)结论:
使用模糊聚类分析方法可以有效解决大学教育中学科单科结业方式,缺少足够多的原始数据,而导致的学生学习效能评测中的算术平均值方法失效问题。
三、算法描述
设:一次测试中n名学生参加,测试m个知识点,则任意学生{Si|i∈[1,n]}的测试成绩T(X1,...,Xm)T,{Sj|j∈[1,m]}为学生Si在本次测试中第j个知识点上获得的成绩,从而在本次测试中,全体学生成绩可描述为n个m阶向量T(X1,...,Xm)T。
1.初始化:
令n个m阶向量自成一类,即建立n个子集,T1(0),T2(0),...,Xn(0),使用模糊聚类方法计算各子集之间的距离,即可得到一个n×n维的距离矩阵D(0),其右上角标号代表模糊聚类运行的迭代次数b ,初始运行时迭代次数b=0,记为(0)。
2.运算一:
求距离矩阵D(b)中的最小元素(对角线元素除外),如果该最小元素为Di,j,则是子集Tjb与Tib的距离,将Tjb与Tib合并为一新子集,记为:Ti,j(b+1),并构建新的分类T1(b+1),T2(b+1),T3(b+1)...。
3.运算二:
计算合并后新分类子集中Ti,j(b+1)与其它没有合并的T1(b+1),T2(b+1),X3(b+1)...间的距离,得到新分类的距离矩阵D(b+1)。
4.运算三:
令迭代次数b=b+1,跳转到运算一,重复计算和合并。预先指定一阈值Q,当迭代获得的距离矩阵D(b)中的最小元素超过阈值Q,迭代中止,所得到的结果即为聚类分类结果。
四、结论
数据聚类分析 篇7
目标航迹数据聚类挖掘分析能够从纷杂的航迹数据中发现目标的潜在运动轨迹,可以用于态势数据挖掘、目标行为意图分析和空中交通流量分析等领域[1,2,3,4,5]。现有的航迹数据挖掘算法大多数是针对整个航迹设计的,但在实际数据中,整条航迹具有相似性的情况不多,大多数情况是不同航迹之间在部分航迹线段上具有相似性,以整条航迹为研究对象的聚类算法往往不能发现局部航迹线段的聚集特性[6,7]。本文给出一种新的目标航迹数据聚类分析算法,以航迹线段为对象设计聚类挖掘算法,并按照垂直距离、平行距离和角度距离计算航迹线段之间的距离,这种方法既能发现局部的航迹线段聚集特征,也能发现全局的航迹聚集特征。
1问题描述
借助传感器侦察手段,能够获取受关注区域内移动目标运动轨迹的海量信息,这些信息中隐含着目标运动的特征规律,特征规律表现为相同或相似目标运动轨迹的反复出现,这些轨迹规律有助于推测目标的行为意图,但这些轨迹规律往往被淹没在大量的噪声航迹点数据中,不易被觉察发现,需要设计相关聚类分析算法帮助人们进行分析。
2算法分析
运动目标航迹聚类分析方法用于对一批累积目标航迹数据进行聚类分析,将相似航迹线段聚在一起,从杂乱无章的众多航迹线中发现目标运动潜在的运动模式。
本文提出了一种目标航迹聚类分析算法,其输入包括:
输入1: 航迹集合T = { t1,t2,t3,……tnum} ,其中,ti( i = 1,2,…,num) 代表目标航迹;
输入2: 指定ε( 辐射距离) 和support( 辐射距离范围内的线段数) 2个参数。
其输出为航迹( 线段) 聚类结果,算法具体执行步骤描述如下:
第1步: 对T中整条航迹按照航迹点进行分割处理,航迹被分割成若干航迹线段,所有航迹线段组成集合D;
第2步: 利用算法Line-Segment-Clustering算法对航迹段进行分析,得到航迹段聚类结果。其中,Line-Segment-Clustering算法描述为:
1设置变量cluster ID初始值为0;
2初始时,将集合D中每条航迹线段都标记为“未分簇”,即未做归簇处理;
3对于集合D中的每一条航迹线段Li( Li∈D) 逐个进行处理,首先判断航迹线段Li是否已被归到某个簇,具有了簇标识,若航迹线段已有了簇标识,则不做处理,若没有簇标识,则进行如下处理过程;
4计算航迹线段Li邻域范围内与其距离小于阈值ε的航迹线段的集合Nε( Li) 所含航迹线段的数量,| Nε( Li) | = { Lj∈D | dist( Li,Lj) ≤ε} ;
5如果Li邻域范围的航迹线段数量大于或等于阈值support,则将集合Nε( Li) 中的每一个线段都分配一个簇标识cluster ID; 否则,直接转到第9步;
6将Nε( Li) 中的成员线段放入队列Q中;
7利用扩展处理函数( 见表2的说明文字) 对Q进行处理;
8让变量cluster ID增加1;
9如果Li邻域范围的航迹线段数量小于阈值support,则将Li标记为噪声;
10经过上述步骤之后,集合D中的每一个元素都被赋予了簇标识;
瑏瑡D中的航迹线段按照其簇标识分配到相应的簇中;
瑏瑢对于每一个簇,通过线段与原始航迹之间的映射关系,找出cluster中包含的原始航迹数量,如果航迹数量大于某一个预定值,则保留这个簇,否则,删除这个簇。
算法的伪代码如表1所示。
扩展处理函数的算法描述为:
1接收参数Q,cluster ID,ε和support,以循环方式对Q中的每一个成员航迹线段进行处理;
2计算Q中成员线 段M的领域线 段集合Nε( M) ;
3如果Nε( M) 所含线段数量大于或等于support,则把集合Nε( M) 中的每一个未分簇或噪声线段都标识为cluster ID; 否则,什么都不做,进入下一次循环,处理Q中的下一个成员线段。
扩展处理算法的伪代码如表2所示。
3实验计算结果分析
采用仿真数据对航迹聚类分析算法进行了测试,仿真数据分为6组,分别包含了2 000、4 000、6 000、8 000、15 000和25 000个航迹点,每个航迹点关联了目标出现时间、位置经度和位置纬度信息。
在一台配置为Pentium CPU 3. 00 GHz、2 GB内存、250 GB硬盘的PC上开展了航迹聚类分析实验。聚类分析的执行时间如图1所示,聚类算法的执行时间随着航迹中所含航迹点的数量增大而增加。
航迹聚类结果如图2所示,图中浅灰色细线段是通过传感器观测到的飞机运动形成的航迹线段,黑色粗线段是聚类生成的航迹簇的标识性线段。实验结果表明算法能排除零星散布航迹线段的干扰,准确地将邻近密集分布的航迹线段归为一簇。
4结束语
数据聚类分析 篇8
关键词：电力系统,不良数据辨识,模糊等价矩阵,聚类分析,传递闭包
0 引言
电力系统不良数据的检测与辨识是电力系统状态估计的重要功能之一,其目的在于排除量测采样数据中偶然出现的少量不良数据,提高状态估计的可靠性[1]。迄今为止,国内外用于不良数据检测与辨识的方法主要有目标函数极值检测法、加权或标准化残差检测法、量测量突变检测法、残差搜索法、非二次准则法和估计辨识法等[2]。这些方法的缺点是很可能出现残差污染和残差淹没现象,从而引起不良数据的误检和漏检。
近年来,许多学者尝试用新理论解决不良数据的处理问题,将很多新方法引进了电力系统不良数据辨识当中。文献[3-5]利用模糊数学中的ISODATA方法和隶属度概念来判定不良数据,有效地克服了残差污染和残差淹没现象。文献[6]用反向传播神经元网络进行估计前的滤波,用典型工况的正确量测作为训练样本,以便在实时监控时能正确辨识不良数据。文献[7-9]在不良数据处理过程中引入GSA算法,并提出利用肘形判据判断最佳聚类个数,得到了较好的检测效果。另外,运用抗差估计理论处理不良数据,也是目前不少学者研究的课题[10,11]。
自从美国著名控制论专家、加利福尼亚大学L.A.Zadeh教授于1965年建立模糊集理论,模糊数学已在实践中证明是现代智能技术中最重要的技术之一,是处理不确定性问题的有效方法,在电力系统中也有广泛的应用前景[12]。利用模糊数学理论对不良数据进行处理是一种有效的尝试,但其在具体实施过程中仍有许多课题需要研究。
本文利用基于模糊等价矩阵的动态聚类分析方法,采用标准残差RN和两相邻采样时刻的量测数据差值ΔZ,作为特征值进行模糊聚类分析,通过寻找最佳阈值λ,对量测项目进行聚类,根据个别已知的良数据和“数以类聚”的原则,得到全良数据的分类,进而辨识出不良数据。仿真分析表明该方法能快速准确地辨识出不良数据,有效地避免残差污染和残差淹没现象,并能灵活选择动态聚类结果,更适合实际电网的计算要求。
1 标准化残差RN检测的原理
所谓标准化残差RN检测,是将残差方程进行标准化,得到标准残差,在一定的误检概率下,确定检测门槛值,与量测点的标准残差比较,超过检测门槛值即被判为可疑数据而予以检测出。
设正常量测条件,在某误检概率Pe下由标准化残差灵敏度矩阵和残差方程,得到检测门槛值γN。按下述的假设检验方式对逐个量测点的标准残差进行检测。
式中:RN,i为第i个量测点的标准化残差;γN,i为第i个量测点标准化残差的检测门槛值。
2 模糊聚类分析法
对事物按一定要求进行分类的数学方法,就是聚类分析,它属于数理统计多元分析的一支。由于现实的分类往往伴随着模糊性,聚类问题采用模糊数学语言描述有其方便之处。
设被分类对象的集合为U={u1,u2,…,un},每一个对象ui由一组特征数据(ui1,ui2,…,uim)来表征,其中uij表示第i个对象的第j个特性指标,记作
称U*为U的特性指标矩阵。
由于m个特性指标的量纲和数量级不一定相同,要对U*进行数据规格化处理,常用的方法有数据标准化、极差规格化和对数规格化等[13]。根据实际系统的计算要求,用多元分析的方法来确定对象ui和uj之间的模糊相似度,建立模糊相似矩阵,即:
此时得到矩阵R=(rij)n×n,一般来说只具有自反性和对称性,不一定具有传递性,未必是模糊等价矩阵[14]。因此,还要由模糊相似矩阵R出发,构造模糊等价矩阵,并以其为基础,进行动态聚类,得到各个阈值λ下的分类。最后根据实际需要选择最佳阈值λ,确定符合系统要求的最佳聚类结果。
3 基于模糊等价矩阵的不良数据辨识
根据模糊数学的理论,考虑不良数据的特点,本文采用标准残差RN和两相邻采样时刻的量测数据差值ΔZ作为特征值,得到原始样本数据集,见表1。对于量测项目集U={u1,u2,…,un},形成特性指标矩阵U*,特性指标m=2。
3.1 模糊相似矩阵的形成
利用Fortran6.5软件编程,本文对比了极差规格化、最大值规格化和数据标准化三种方法,根据数据处理的效果,决定采用数据标准化方法对U*进行规格化处理。
对特性指标矩阵U*的第j列,计算
得到标准残差RN和量测差值ΔZ的平均值和标准差,然后通过变换
得到服从标准正态分布的规格化矩阵U0=(u'ij)n×2。
此系统中量测项目的特征指标偏少,通过试算对比相关系数法和最大最小法的处理效果,选用最大最小法来确定量测项目ui和uj之间的相似关系。
由最大最小公式,计算
得到相似系数rij,其中i,j=1,2,…,n,进而构成模糊关系矩阵R=(rij)n×n。
3.2 基于模糊等价矩阵的聚类
显然,式(6)得到的矩阵R具有自反性和对称性,没有传递性,不能直接用于动态聚类,故必须对其改造,求得相应的模糊等价矩阵,再进行动态聚类。本文采用模糊传递闭包法解决上述问题。
(1)利用平方自合成的方法求出模糊相似矩阵R的传递闭包t(R),即
其中,k≦[㏒2n]+1。t(R)就是所需的模糊等价矩阵R'。
(2)适当选取阈值λ∈[0,1],求出t(R)的λ截矩阵t(R)λ,并对其聚类,具体原则如下:
设t(R)=(r'ij)n×n,t(R)λ=(r'ij(λ))n×n,则
对于ui,uj∈U,若r'ij(λ)=1,则在λ水平上将量测项目ui和uj归为一类。
(3)当λ在[0,1]中取不同值时,相应分类也随之改变。将λ按照从1到0的顺序,对t(R)所得分类逐步归并,得到t(R)λi的一系列分类Sik,其中i=1,2,…,h,h为阈值λ的个数,S为聚类集,k为聚类个数。为了能直观地看到量测项目间的相关程度,文中让λi按照步长0.1逐次递减,得到系统的动态聚类,至此量测项目的动态聚类过程结束。
3.3 最佳聚类结果的确定
可以预见,不良数据辨识的理想聚类数k=2,即全部数据分为良数据和不良数据两类。因此,选取动态聚类中聚类数为2的聚类集S2,便得到系统的最佳聚类。实践表明,这种方法对于偏差较小的不良数据辨识,具有较好的效果,但对于偏差较大的不良数据辨识,则不能保证较高的辨识精度。
本文通过合理选择最佳阈值λ,确定最佳聚类结果。阈值λ的选择,是不良数据动态聚类的关键环节。阈值越大,则辨识精度越高,聚类个数越多,误判的可能性就越大;阈值越小,则辨识精度越低,聚类个数越少,漏检的可能性就越大。
在兼顾辨识精度和聚类稳定的条件下,考虑阈值λ和聚类数k的变化率
其中:i为λ从大到小的聚类次数;ki和ki+1分别为第i次和第i+1次聚类的个数;λi和λi+1分别为第i次和第i+1次聚类时的阈值。如果
则认为第i次聚类的阈值λ为最佳阈值。
在不良数据的辨识过程中,式(10)保证了在取得较高辨识精度的同时,选取具有较好稳定性的聚类集,由此得到的最佳阈值,所对应的聚类结果即为最佳聚类结果。通过对大量数据的分析,发现聚类集Sk在λ在(0.7,0.4)之间时具有较好的稳定性。
3.4 不良数据辨识系统
对于实际系统中存在的不良数据,为了保证较好的辨识精度,最佳聚类结果可能不是理想聚类结果,即k≥2。这时,我们就需要利用个别确定为良数据的量测量,比如电网电压等级V等,根据聚类后“数以类聚”的原则,判断出全良数据的一类,进而得到不良数据的分类,完成不良数据的辨识。
综上,不良数据辨识系统的简要流程,见图1。
4 算例仿真与系统测试
为了验证算法的有效性,本文利用Fortran6.5软件编制了不良数据辨识系统,对传统的4节点模型进行了仿真分析,最后采用某地区电网的实时数据,进行了系统测试。
4.1 仿真算例分析
传统4节点模型接线图如图2所示,其量测配置如表2所示,量测项目总数为16。
对节点1的注入有功功率P1,先后两次分别设置不良数据值ΔP1=10 MW和ΔP1=50 MW,节点1和节点3的电压量测值作为已知的良数据,并在其他量测点设置服从N(0,1)正态分布的随机干扰,最佳阈值由式(10)确定,检测分析结果如表3所示。
对节点1的注入有功功率P1与线路12的有功功率P12,设置不良数据ΔP1=25 MW和ΔP12=20MW,其他计算和实验条件同上,检测分析结果如表4所示。
对节点1的注入无功功率Q1与线路12的无功功率Q12,设置不良数据ΔQ1=25 MW和ΔQ12=20MW,其他计算和实验条件同上,检测分析结果如表5所示。
分别采用方法1(标准化残差RN检测法)、方法2(加权残差RW检测法)和本文方法处理以上四种情况,检测结果见表6,其中标准残差门槛值γN=2.81,本文方法中1表示不良数据、0表示良数据。将三种方法的辨识效果进行对比,如表7所示。
由表6和表7可以看出,在单不良数据的情况下,采用传统方法时出现了残差污染现象,并且随着不良数值的增大,检测出的不良数据增多,说明残差污染现象加重,增加了辨识的困难,而本文方法的检测结果则比较理想。在多不良数据的情况下,由于不良数据的相互作用,导致部分或全部不良数据点上的残差接近于正常残差,同时部分正常测点的残差超过门槛值,故采用传统方法时不仅出现了残差淹没,而且伴随着残差污染,直接造成了漏检和误检,而本文方法的检测结果则更加准确。
算例表明,该算法能够快速准确地辨识出不良数据,并有效克服残差污染和残差淹没,避免误检和漏检情况的出现。另外,通过对不良数据偏差较大的情况处理,说明这种方法可以方便、灵活地在辨识精度和动态聚类结果上做出选择,从而得到更符合实际工况的辨识结果。
4.2 实时数据系统测试
本次系统测试的数据采用某地区电网中3个发电厂、1个升压站和16个变电站的实时运行数据。从此系统共获取186个量测值,取自2010年3月27日的运行情况,其中包含14个节点电压值,15对发电机组出力的有功和无功,23对负荷潮流,16对变压器输入有功无功和32对线路潮流,并对各个量测点都分配各自的标号。各量测点的标准残差均采用适应计算要求的经验值。
由于无法得到原始的生数据,本文利用电力系统SCADA状态估计处理后的数据进行测试。假设量测数据中共出现4个不良数据,分别是第67号(贾庄变168号联络线有功),第104号(香王线1979号有功),第121号(姚程线2320号有功)和第152号(香山变#1主变有功)量测量,其超过正常值在15%~30%之间。测试结果见表8。
5 结论
数据聚类分析 篇9
随着信息技术的飞速发展以及信息获取的便利,人们已被大量的信息淹没。如何从信息的海洋中提取出人们感兴趣的知识,以帮助人们完成特定的任务成为了一个迫切需要解决的问题,基于这样一种需求,用来帮助用户从这些海量数据中分析出其间所蕴涵的有价值的模式和知识的技术——数据挖掘就应运而生了。
所谓数据挖掘,就是从大量的、不完全的、有噪声的、模糊的、随机的、无序的数据中提取隐含在其中的有效的、有价值的、可理解的模式,进而发现有用的或是潜在有用的知识,并得出时间的趋向和关联,为用户提供问题求解层次的决策支持能力。
聚类分析是数据挖掘中一种很重要的技术。所谓聚类,就是把拥有大量数据的集合分成若干簇,在同一个簇中的数据对象之间最大程度的相似,而在不同簇中的数据对象之间具有最大程度的不同。在实际应用中,一个聚类结果会影响到数据挖掘的后续工作,通常一个好的聚类结果会使数据分析工作变得简单清晰,比较容易得到用户想要的知识,而一个糟糕的聚类结果却正好相反,甚至得不到用户想要的结果。因此聚类分析成了数据挖掘中的最为关键的部分,发展成为一个很活跃的研究方向。
1 对聚类分析研究成果的概述
对于数据挖掘中聚类分析的传统方法,根据其基本的思想,可以分成以下几类:划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法。
(1)划分方法
划分方法的基本思想是:给定具有N个对象或元组的数据库,指明想要得到的簇的数目k,一个划分方法利用采取的算法将这N个对象划分成k个分组,其中k
K-means方法:在具有n个对象的数据集中,随机选择k个对象,每个对象初始的代表一个簇的中心,根据所采用的距离度量(如欧几里得距离度量)计算剩余的每个对象与这k个初始簇中心点的距离,将对象分配到与其具有最小距离的簇中,这样具有n个对象的数据集被划分成k个簇,然后重新计算每个簇的平均值。该过程不断的循环迭代,直到新计算的平均值与上一次的平均值相比没有变化。
从该方法的过程可以看出,当结果簇间具有明显的区别时,k-means方法具有很好的效果,但是当存在孤立点时,孤立点对k-means方法会产生很大的影响,因为平均值对孤立点很敏感。另外,k-means方法需要事先指定聚类的数目。
K-medoids方法与k-means方法的过程类似,只是该方法用簇中一个实际的对象代替簇的平均值,所以相比较k-means方法而言,其不易受孤立点的影响。但是该方法要进行不断的对比和比较,其计算代价很高,而且不太适合于大型数据集。K-medoids方法需要事先指定要得到的簇的数目。
k-means方法和k-medoids方法是目前最为流行的聚类方法,当前发展的许多聚类技术都是在这两种方法的基础上进行拓展(如模糊k-means聚类方法),以及在这两种方法的基础上进行的改进。
(2)层次方法
层次聚类方法通过将数据组织成若干组并形成一个相应的树状图来进行聚类。根据其聚类的过程是自下而上还是自上而下,层次聚类方法又分成了聚合聚类和分解聚类两种。其主要思想如下:
聚合聚类方法:将数据集中的每一个对象看作是一个单独的簇,然后根据某个给定的原则将这些簇进行合并,直到数据集中的对象形成一个簇或者是满足事先定义的某个终止条件。
分解聚类方法:与聚合聚类方法恰好相反,将所有的数据集看成是一个大的聚类,根据某个给定的规则对这个簇进行划分,细化成越来越小的簇,直到每个数据对象自成一个簇或者达到某个终止条件。
几种典型的层次方法有BIRCH,CURE等。
BIRCH方法是一种综合性的层次聚类算法,它利用聚类特征(CF)和聚类特征树(CF tree)来描述聚类过程。CF是一个三元组,它对对象子类的信息给出了总结性描述;一个CF tree是高度平衡的树,它有两个参数:分支因子和阈值,它存储了层次聚类的聚类特征。分支因子定义为每个非叶节点孩子的最大数目,而阈值是指存储在树的叶子节点中的子聚类的最大直径。
BIRCH方法由于采用了CF tree汇总一个类的有关信息,从而使一个类可以用对应的CF表示,而不必用具体的一组数据点表示,因此大大提高了聚类算法对大型数据库的高效性和可扩展性,具有良好的聚类质量。但该方法又受到了CF tree节点大小的限制,CF tree节点并不总是与用户所认为的自然聚类相对应。而且,如果簇不是球形,BIRCH算法则不能很好地工作。
CURE采用了一种新的层次聚类方法,对k-means方法和k-medoids方法进行了折中,选择了位于基于质心和基于代表对象方法之间的中间策略。由于CURE方法选择数据空间中一定数目的具有代表性的点来代表一个簇,因此该方法可以识别复杂形状和大小不同的簇,而且能很好地过滤孤立点。然而该方法对用户输入的参数(如样本大小、收缩因子a)具有敏感性,同时也需要用户事先指明想要得到的聚类的数目。
(3)基于密度的方法
对于非球形的簇,用对象之间的距离来度量相似性是不够的,因此为了发现任意形状的簇,利用密度(数据或对象点的数目)来代替距离,提出了基于密度的聚类方法。该方法从数据对象的分布密度出发,将簇看成是由低密度区域分割开的高密度对象区域。
DBSCAN是一种典型的基于密度的方法,它通过检查数据库中每个点的e邻域来进行聚类。其基本思想:检查一个对象p的e邻域的密度是否足够高,即一定距离e内数据点的个数是否超过临界值minpts(minpts由用户事先指定),如果p的e邻域内的数据个数多于minpts个点,则创建一个以p为中心点的新簇。然后DBSCAN反复的寻找从这些中心点直接密度可达的对象并将其添加到簇中,当没有新的对象可以添加到任何簇中时,该过程结束。
DBSCAN用对象或数据点的数目表示类的密度,利用密度可达性来进行聚类,因此能很好的处理噪声,此外该方法能发现空间数据库中任意形状的密度连通集,对数据的输入顺序也不太敏感。但是该方法中使用的e邻域和阈值需要事先指定,参数的设置依赖于具体的应用。
(4)基于网格的方法
该方法采用一个多分辨率的网格数据结构,它首先将数据空间划分成有限数目的单元,形成一个网格结构,所有的处理都是以单个的单元为对象。处理速度通常与目标数据库中记录的个数无关,它只与单元的个数有关,故这种方法的一个突出优点就是处理速度很快。代表性算法有STING。
STING算法将空间区域划分为矩形单元。针对不同级别的分辨率,通常存在多个级别的矩形单元,这些单元形成了一个层次结构:高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易地从低层单元的计算得到。
STING的执行效率比较高,而且利于并行处理和增量更新。但是如果数据粒度比较细,算法处理的代价会明显的增加;而且该算法没有考虑子单元和其他相邻单元之间的关系,尽管该算法处理速度较快,但是可能会降低簇的质量和精确性。
(5)基于模型的方法
基于模型的方法为每个簇都假定了一个模型,并寻找数据对给定模型的最佳拟合。该方法通过构建反映数据点空间分布的密度函数来实现聚类。这种聚类方法试图优化给定的数据和某些数学模型之间的适应性。
人工神经网络就是一种基于模型的聚类方法,是模拟生物神经网络的结构和功能而设计的一种信息处理系统。人工神经网络方法将每个簇描述为一个标本,标本作为簇的原型,不一定对应特定的数据实例和对象。根据某些距离度量,新的对象可以被分配给标本与其最相似的簇。被分配给一个簇的对象的属性可以根据该簇的标本的属性来预测。
2 目前聚类分析研究的主要内容
对聚类进行研究是数据挖掘中的一个热门方向,由于以上所介绍的聚类方法都存在着某些缺点,因此近些年对于聚类分析的研究很多都专注于改进现有的聚类方法或者是提出一种新的聚类方法。以下将对传统聚类方法中存在的问题以及人们在这些问题上所做的努力做一个简单的总结:
(1)从以上对传统的聚类分析方法所做的总结来看,不管是k-means方法,还是CURE方法,在进行聚类之前都需要用户事先确定要得到的聚类的数目。然而在现实数据中,聚类的数目是未知的,通常要经过不断的实验来获得合适的聚类数目,得到较好的聚类结果。
(2)传统的聚类方法一般都是适合于某种情况的聚类,没有一种方法能够满足各种情况下的聚类,比如BIRCH方法对于球状簇有很好的聚类性能,但是对于不规则的聚类,则不能很好的工作;K-medoids方法不太受孤立点的影响,但是其计算代价又很大。因此如何解决这个问题成为当前的一个研究热点,有学者提出将不同的聚类思想进行融合以形成新的聚类算法,从而综合利用不同聚类算法的优点,在一次聚类过程中综合利用多种聚类方法,能够有效的缓解这个问题。
(3)随着信息时代的到来,对大量的数据进行分析处理是一个很庞大的工作,这就关系到一个计算效率的问题。文献提出一种基于最小生成树的聚类算法,该算法通过逐渐丢弃最长的边来实现聚类结果,当某条边的长度超过了某个阈值,那么更长边就不需要计算而直接丢弃,这样就极大地提高了计算效率,降低了计算成本。
(4)处理大规模数据和高维数据的能力有待于提高。目前许多聚类方法处理小规模数据和低维数据时性能比较好,但是当数据规模增大,维度升高时,性能就会急剧下降,比如k-medoids方法处理小规模数据时性能很好,但是随着数据量增多,效率就逐渐下降,而现实生活中的数据大部分又都属于规模比较大、维度比较高的数据集。文献提出了一种在高维空间挖掘映射聚类的方法PCKA(Projected Clustering based on the K-Means Algorithm),它从多个维度中选择属性相关的维度,去除不相关的维度,沿着相关维度进行聚类,以此对高维数据进行聚类。
(5)目前的许多算法都只是理论上的,经常处于某种假设之下,比如聚类能很好的被分离,没有突出的孤立点等,但是现实数据通常是很复杂的,噪声很大,因此如何有效的消除噪声的影响,提高处理现实数据的能力还有待进一步的提高。
3 总结与展望
通过以上的分析可以看出,目前对于聚类的研究虽然成果很多,但是还不够成熟,基本的理论方法还不够完善,对实际的应用也还不够广泛,还需要对其作进一步的研究:
(1)继续进行理论上的研究,寻求在理论上的改进和完善,提高各种方法的性能以及对现实数据的应用能力。
(2)寻求与其他学科的结合,寻找各学科之间的接口,完善现有的方法;并从其他学科获得一些启发,提出一些新方法,比如可以从代数拓扑中有关拓扑空间同伦等价的概念来研究聚类分析。
(3)增强聚类分析的应用能力,将其更广泛的应用于实践,为我们的生产生活提供便利,真正发挥其效能。
摘要：聚类分析是数据挖掘的一种重要技术,在本文中,回顾了几种现有的聚类分析的方法,指出了这些方法的优劣并且总结了聚类分析的主要研究方向并对聚类分析进行了前景展望。
关键词：聚类分析,数据挖掘
参考文献
[1]贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究.2007.
[2]胡庆林,叶念渝,朱明富.数据挖掘中聚类算法的综述[J].计算机与数字工程.2007.
[3]Jiawei Han,Micheline Kamber.Data Mining:Concepts and Techniques[M].机械工业出版社.2007.
数据聚类分析 篇10
用于数据挖掘的数据集维数众多时, 容易陷入“维灾难”, 影响数据挖掘算法的效率和可靠性, 因此往往在数据预处理阶段需要对数据进行特征归约, 去除弱相关特征和冗余特征。同时, 为了数据挖掘的最终结果易于理解, 有时需要对数据进行值归约, 减少已知特征的离散值数目或使连续值离散化, 从而简化对数据的描述。
各高校建立的学生信息管理系统中累积有大量数据, 除了记录和查询, 还需要对数据中隐含的知识加以利用为决策提供数据依据。以成绩管理系统为例, 按培养计划要求, 各学生每学年应选修多门课程, 包括公共基础课、专业基础课、专业选修课、实践课程和学院任选课等各种类型课程, 大学四年完成学业需要选修共平均多达65门课程, 每门课程有一个成绩。其中至少三分之一学生在某些课程修读获得学分过程中有补考或重修多次的经历, 在数据库中将产生同一门课同一个学生的多个成绩数据。如此累计下来的成绩数据数量巨大, 进行数据挖掘得到的隐含知识, 可将学生成绩数据作为评定学生素质的依据。若直接应用如此维数众多的成绩数据, 数据挖掘算法的执行效率将受到很大影响, 因此需要先进行特征归约和值归约。本文讨论在weka平台下使用主成分分析法对学生成绩进行特征归约实现降维, 并对降维后的成绩数据进行聚类从而实现值归约, 以便进一步进行其他数据挖掘工作。
本文中数学公式符号基于下述数据模型定义:
设给定数据集C中有n个样本, 每个样本有p项变量:X1, X2, …, Xp组成原始数据矩阵:
1 主成分分析方法
1.1 简介
主成分分析法是较为常见的一种特征归约方法, 其目的在于以各变量的线性组合代替原有变量, 生成的线性组合之间相互独立, 数量少于原有变量, 并包含有原变量大部分的信息, 从而实现合理的特征归约。
1.2 步骤[1]:
第一步:对样本数据进行标准化, 以便统一量纲[2]。
第二步:计算变量协方差矩阵S, 矩阵S定义为:
第三步:计算上述协方差矩阵Sp×p的特征值λ1, λ2, …, λp (有λ1≥λ2≥…≥λp≥0) , 以及对应的正交化单位特征向量ζ1, ζ2, …, ζp。
上述Sp×p中与前m个最大特征值对应的m个特征向量将定义原数据由p维空间向m维空间的线性转换, 且转换后的m维空间中的特征之间互不相关。
第四步:为了确定上述值, 计算前个最大特征值之和与所有特征值 (方差) 之和的比值,
该比值用百分比表示, 称为累计方差贡献率, 其值反映前m个主成分在方差总和上的投影。当该投影比率足够大 (大于阈值) 时, 包含m个特征的子集的所有分析就是p维空间合适的初步估计[3]。
第五步:得到以上述特征向量值作为系数的m个主成分表达式:
根据主成分表达式计算每个样本在各个主成分上的得分, 得到新的特征归约数据矩阵。
2 k均值聚类方法
2.1 简介
聚类分析在没有先验知识样本没有分类标签的情况下, 依据样本间关联的量度标准将样本自动分成合理的几个群组 (簇) , 目标是分簇后在同一群组中的样本相似度高, 不同群组中的样本相似度低。聚类分析有基于层次、基于划分、基于密度等算法, 其中用于n维连续空间的k均值算法是一种经典的基于划分的迭代型算法, 因为实现运行简单高效等优点被广泛应用。
2.2 步骤:
第一步:随机选取个数据点启动算法。k为预期的聚簇个数。
第二步:通过距离函数的计算将每个数据点分配给当前与之最近的聚簇代表所在的群组中, 同时取消上次迭代确定的归属关系。这一步将对全部数据进行新的划分。
第三步:通过重新计算所有分配给该聚簇代表的所有数据的中心 (如算数平均值) , 从而重新确定每一个群组的新的聚簇代表。
第四步:重复执行第二步和第三步, 直至群组的成员稳定, 聚簇代表未变更, 算法收敛。
应用k均值算法进行聚类分析有三个关键问题需要解决。
1、初始聚簇代表的分布:聚簇代表的初始化不同, 最终获得的聚簇可能会差异很大。为了避免过早收敛于局部最优解, 可以基于不同的初始聚簇代表多次运行该方法, 从中挑选最好的结果[4]。
2、聚簇的个数:需要人工给定, 可能偏大或偏小, 可以根据先验知识指定, 也可以尝试使用多个不同的k值多次运行算法, 使用一些判别函数作为准则进行选择。
3、距离函数:即样本间关联的量度标准, 表示样本间的相异度, 通常用d (x, x′) , 坌x, x′∈X表示样本x和x′之间的距离。如果样本x和x′越不相似, d (x, x′) 越大。对于连续特征样本, 常用的距离函数有欧式距离、曼哈顿距离、方差加权距离、余弦距离、Pearson相关系数等, 可根据样本数据结构特点进行选择。
2.3 评估聚类结果
2.3.1 评估准则的作用
评估准则用于确认识别数据集中是否实际存在非随机结构、聚簇的个数是否正确, 分析聚类结果对数据的拟合情况[5]。常见的非监督簇评估准则有基于凝聚度和分离度的度量, 如类间平方误差和 (Within cluster sum of squared errors, WCSSE) 、加权平均平方距离和、轮廓系数 (Silhouette Coefficient指标) 、类间类内差异比[6]等, 也有基于邻近度矩阵的技术, 如可视化邻近矩阵等方法。
2.3.2 WCSSE
基于欧式距离的聚类, 可以使用WCSSE作为评估聚类质量的准则, 值越小, 说明聚类的聚簇代表能更好的表示簇。WCSSE可定义为:
其中表示第i个群组的聚簇代表 (该群组有mi个样本) , d (ci, x) 代表样本ci与样本x的平均距离, 如表示相异度的欧式距离或表示相似度的余弦距离。
2.3.3 Silhouette指标[7]
数据集C中的一个样本t的Sil指标计算公式为:
其中, 表示t样本和同一群组内其他样本间的距离平均值, 反映簇内凝聚度;, j=1, 2, …, k, 表示t样本和其他群组中样本的最小平均距离, 反映簇间分离度。所有样本的平均Sil值越大, 反映聚类效果越好。
3 使用WEKA实施方法
WEKA简介
Waikato Environment for Knowledge Analysis (WEKA) 是Waikato大学开发的开源数据挖掘平台, 集成了多种机器学习算法, 能实现数据预处理、分类、关联分析、聚类分析等数据挖掘任务及挖掘过程和结果的可视化和性能评估[8]。比较其他商用数据挖掘平台, WEKA允许扩展, 支持用户根据需要使用java语言调用其中封装的算法或进行二次开发。
使用WEKA进行主成分分析聚类
根据上述方法, 在Eclipse集成环境下, 导入WEKA的jar包, 使用JAVA语言编写图1所示流程的程序。本程序调用weka包中weka.core和weka.clusterers的类实现数据预处理和k均值聚类方法。weka.core负责实现数据的获得, 通过调用其中的Instances类进行数据导入和数据集预处理, Instance类获得每条记录的数据。Simple KMeans类负责实现k均值聚类, 其中set Seed接口实现生成随机初始聚簇代表的seed值, set NumClusters接口设置期望的聚簇个数 (Cluster Number) , build Clusterer进行数据集的分簇操作, get Squared Error获得build Clusterer后的聚簇结果。代码实现了各个期望聚簇个数下的各个seed的WCSSE遍历, 并得出WCSSE最小时的seed值, 以及基于该seed值的聚簇结果, 该聚簇结果是相同聚簇个数的最优解。
其中调用Simple KMeans类实现寻找最优解的seed值的核心代码如下:
4 实例分析
4.1 原成绩数据描述
以本学院成绩数据库中2007级计算机专业154个学生的每生必修的46门课程成绩为例。至少有三分之一的学生在某些课程获得学分之前至少补考一次甚至重修多次, 将这部分学生获得学分前的历次考试成绩取平均分作为其该门课程的修正成绩, 生成一个学生一门课仅有一个成绩的数据集, 该数据集有154个样本46个变量。为了了解学生在不同课程的学习情况, 现将学生成绩按课程类型分成公共基础课 (22个变量) 、专业课 (14个变量) 和实践环节课 (10个变量) 三个数据集分别进行以下试验。
4.2 试验与分析
4.2.1 特征归约
使用WEKA数据预处理功能中Principal Components Filter实现数据集的特征归约, 以累计方差贡献率85%作为阈值提取主成分。以专业课成绩为例, 由专业课的主成分分析 (表1) 可见前7个主成分累计方差贡献率达到86.207%, 可以用这7个主成分代替原14个变量来评价学生在专业课程方面的学习情况, 即实现14个变量降维为7个新变量。同法可将公共基础课数据集的22个变量降维为11个新变量, 实践环节数据集的10个变量降维为7个新变量。
4.2.2 值归约
使用前述JAVA程序对特征归约后的数据集 (表2中为PCA得分) 按课程类型分别以3类、4类、5类和6类为期望聚簇个数进行四次k均值聚类, 均选择类内平方误差和 (WCSSE) 最小的结果为该聚簇个数的最佳聚类结果。对未降维数据集按课程类型计算每个学生的平均分和学分绩点成绩, 并分别使用前述JAVA程序进行3类~6类四次k均值聚类。
以专业课成绩为例, 表2表明平均分和学分绩点成绩的聚类效果均不如未降维和PCA得分的聚类效果好, 虽然PCA得分的聚类效果次于未降维的聚类效果, 但因参与聚类的特征维数比未降维少, 聚类的效率比未降维的聚类效率高, 因此使用主成分分析聚类的方法对成绩进行特征归约和值归约是合理可行的。
4.3 结果分析
以专业课成绩为例, 将原数据集按上述方法进行特征归约和值归约后可分为三个群组。
图2表明归属于第一群组的成绩比较好, 第二群组的成绩次之, 第三群组的成绩比较差, 从而将学生专业课成绩离散成“强”、“一般”及“弱”三个值, 对应表示学生的专业学习能力为“强”、“一般”及“弱”。
5 结束语
直接使用绩点成绩或平均分成绩将忽略学生在各科目的学习情况, 对一个学生学习能力的评价不够合理, 而使用传统的五分制或统一的区间硬性划分可能使离散化后的值多数集中在某个区间, 不能很好的区分描述学生的学习情况。使用主成分聚类的方式既保留了学生在各方面的学习情况, 又能合理的将一个学生的成绩进行归类, 因此对学生成绩数据进行降维处理是可行的合理的, 可以此结果作为数据预处理结果进一步进行其他数据挖掘。
参考文献
[1]刘影.多元统计分析在高校教学中的应用:[硕士学位论文].东北师范大学, 2006
[2]林海明杜子芳.统计研究.2013, 08
[3][美]Mehmed Kantardzic著王晓海吴志刚译数据结构:概念、模型、方法和算法 (第2版) .北京:清华大学出版社, 2013
[4]Xindong Xu Vipin Kumar编著李文波吴素研译.数据挖掘十大算法.北京:清华大学出版社.2013
[5][美]Pang-Ning Tan Michael Steinbach Vipin Kumar著范明范宏建等译数据挖掘导论 (完整版) .北京:人民邮电出版社.2011
[6]刘磊.基于k_means的自适应聚类算法研究:[硕士学位论文].北京邮电大学, 2009
[7]王开军.基于有效性指标的聚类算法选择.四川师范大学学报.Nov., 2011 Vol.34, No.6
数据聚类分析 篇11
〔关键词〕因子分析；聚类分析；数据挖掘；专利评价
〔中图分类号〕G250.252 〔文献标识码〕A 〔文章编号〕1008－0821（2012）09－0172－06
工业革命之后，世界上的创新发明越来越多，而专利的诞生，是为了保证发明人的创造活动得到一定量的回报，以激励更多的发明研究工作。1624年英国颁布了《垄断法》，这是早期专利制度的雏形，我国也于1985年颁布了《专利法》[1]。我国经济经过30多年的发展，目前正经历着从劳动密集型向高科产业型的方向发展，而判断是否转型成功的标尺之一就在于专利的发展状况，专利是企业或国家在各种竞争中取得优势的关键因素。广东省一直处于全国经济发展的前沿，但各地之间的专利发展情况不均，为了能找出地区间的差距并有针对性地采取措施，对广东省各地区的专利综合评价应客观、全面、科学，为此，本文选用目前较为权威、科学的专利评价指标体系，在此基础上对广东省2010年的专利统计数据进行因子分析和聚类分析，以期有效促进广东省各地区专利水平的提高和发展。
1 专利评价指标体系
对专利评价指标体系的选用也是对专利综合实力进行评价的一个关键步骤，专利评价指标是相对于原始数据的二次数据，用来进行分析的二次数据是否准确、客观、全面，影响着分析结果的好坏。
我国专利制度实施得比较晚，对专利指标的研究还处于初期阶段，目前的研究热点不仅仅只注重专利数量，同时也重视专利质量以及专利综合评价，如黄庆[2]（2004）等的《专利评价指标体系——专利评价指标体系的设计和构建》，肖国华等[3]（2008）《专利分析评价指标体系的设计与构建》，张冬梅[4]等（2006）《专利情报分析指标体系——分析方法与技术》，阮梅花[5]等（2011）《企业自主创新能力评价的专利指标体系构建初探》等等，结合国外Huang Z[6]的研究来总结以上所有文献，本文在选取专利评价体系遵循以下几个方面：
（1）较客观、科学、全面、准确地表现我国在世界上、我国不同地区或者各个行业乃至企业的专利综合实力；
（2）“量”和“率”结合的平衡。“量”指的是总量，用来评价总体实力情况；“率”用来评价相对强度情况。
（3）实用并具有指导性。
最终，本文选取的地区专利综合评价指标由表1所示：
2 专利综合评价的方法
在进行数据分析之前，首先对本文运用的因子分析、聚类分析进行介绍和说明。
2.1 因子分析法
因子分析法是指从研究指标相关矩阵内部的依赖关系出发，把一些信息重叠、具有错综复杂关系的变量归结为少数几个不相关的综合因子的一种多元统计分析方法，基本思想是：根据相关性大小把变量分组，使得同组内的变量之间相关性较高，但不同组的变量不相关或相关性较低，每组变量代表一个基本结构——即公共因子[7]。即用较少的综合指标分别综合存在于各变量中的各类信息，而综合指标之间彼此不相关，各指标代表的信息不重叠。根据因子分析的目的得知，综合指标应该比原始变量少，但包含的信息量应该相对损失较少[8]。
因子分析的基本原理[9]是：选择i个主分量Z1，Z2，……，Zi，其中Zi=ai1*F1+ai2*F2+……+aim*Fi+ε，F1、F2 、…、Fi称为公共因子，ε称为以Zi的特殊因子，aim是第i个变量在第m个因子上的负荷，它一方面表示Zi对Fi的依赖程度，绝对值越大，密切程度越高；另一方面也反映了变量Zi对公共因子Fi的相对重要性，把aim称为因子荷载。该模型中的因子载荷矩阵需要用适当的方法进行估计，使得各个公共因子之间相互独立；然后，分别计算出公共因子Fi的得分：F=f1*Z1+f2*Z2+……+fi*Zi，fi作为每个主分量Zi的方差贡献率的权数（即因子得分系数）。最后利用此综合评价函数进行综合评价，即以每个因子的方差贡献率占因子总方差贡献率的比重作为权数进行加权计算综合得分。
本文使用因子分析的主要目的是可以通过因子分析对各因子进行客观赋权，以便确定综合评价的重要因素——权重，权重反映不同评价指标对地区专利的影响程度大小，引入权重的综合评价可以更科学合理地评价地区专利发展状况。
2.2 聚类分析法
聚类（Clustering）就是将数据分组成为多个类（Cluster），在同一个类内对象之间具有较高的相似度，不同类之间的对象差别较大，聚类分析师一种无监督数据挖掘方法，它基于观测之间的相似度或距离将观测（数据）分组[10]。一个好的聚类方法会产生高质量的聚类结果，使同一类别内的观测相似度高，而不同类的观测差异大。
3 专利综合评价的实证分析
本文选取了广东省21个市作为样本，并对样本进行因子分析与聚类分析。样本数据根据广东省知识产权局网站2006－2010年的专利统计报表计算得出，其中主要数据来源于2010年，个别数据根据2006－2010年统计计算得出，计算与统计过程使用EXCEL与SPSS统计分析工具完成。
3.1 基于因子分析的实证研究
（1）采用SPSS因子分析统计得出公因子特征值与贡献率表以及公因子得分系数矩阵如表1、表2所示：
按特征值大于1的原则提取公因子，最终提取了6个公因子，第一个公因子的特征根为11.108，解释了总变异的46.285%，以此类推，6个公因子的累积贡献率达91.425%，信息损失为8.575%，能较为全面地反映信息。
（2）此时，用回归法计算出得分，并按系数大小加权进行排序，从而得出公因子得分系数矩阵，如表3所示：
由表2可知，第一公因子Z1的特征值最高，贡献率也最高，并且由表3可知，第一公因子Z1得分大都为正，且数值都很高，因此可以认为Z1代表地区专利发展水平，Z1越高表明地区综合专利发展水平实力越强。实用新型授权量X6，实用新型申请量X2，工矿企业授权量X18，工矿企业申请量X13，发明专利申请量X1，机关单位授权量X19在Z1上有高荷载；大专院校申请量X11，大专院校授权量X16，科研机构授权量X17，科研机构申请量X12在Z2上有高荷载；外观设计授权率X9，实用新型授权率X7，发明专利授权率X5在Z3上有高荷载；技术衰老系数γ在Z4上有高荷载；年专利申请增长率X20，年专利授权增长率X21在Z5上有高荷载。
因此，可以认为公共因子Z1包括以下几个方面的指标：一是反映专利质量情况的指标；二是反映专利数量情况的指标；三是专利来源的指标，这三者被聚合为一个因子的原因之一，是所选择的数量类指标、质量类指标与专利来源指标之间有密切的相关关系，三者之间相互影响，并代表着地区专利发展的关键因素。因子Z2包括专利来源的授权量和申请量指标，这说明专利来源的各种情况也反映着地区专利发展的情况。因子Z3包括专利质量类指标，原因是该类指标是靠比例计算得出，因此聚合在一个因子中，该因子的贡献率在10%以上，专利质量对地区专利的发展情况起着至关重要的作用。因子Z4包括技术发展程度指标，该类指标都是反映专利的发展趋势，其贡献率为9.6%。因子Z5包括专利发展情况指标。根据各因子包含的反映地区专利发展情况的各个维度的指标类型对各个因子进行命名，命名原则是贡献率因子，以载荷大的因子来命名。
（3）得出公因子得分系数矩阵后，以各公因子的方差贡献率fi占其总方差贡献率的比重作为权重进行加权汇总[11]，得出专利综合得分F，专利综合评价函数为：F=（f1*Z1+…+fi*Zi）／∑fi。在该案例中的公式为：F=(0.46285*Z1+0.14518*Z2+…+0.04386*Z6)/0.91425，按此公式，根据表1与表2的数据，计算出每个城市在每个公因子下的得分并计算出综合得分，得出表5。
根据表5的得分，按综合评价得分F可将广东省专利综合实力分为6个阶梯：第一阶为深圳和广州，两者为广东省专利综合实力最突出的地区，由于深圳和广州是广东省重点发展的地区，并且人才更集中，其地理环境优越、交通便捷、人才资源丰富、经济基础雄厚，这是深圳与广州专利综合实力处于领先地位的重要因素。第二阶梯为佛山、东莞、中山，这些地区专利综合实力也很雄厚，源于地处深圳与广州附近，并且工业发达。第三阶梯的惠州、清远、珠海等，其专利综合实力较好。第四阶梯的韶关、肇庆等专利综合实力一般。第五阶梯为云浮、茂名等，专利综合实力较差。第六阶梯为阳江、潮州，专利综合实力很差。
进一步分析，广州市与深圳市遥遥领先于其他各市，其主要原因在于两者的综合因子得分都很高，并且广州市与深圳市之间也有区别，广州市的专利来源因子得分很高，说明广州市的专利来源分布均匀并且在数量与质量上都占据绝对优势，相对来说，深圳市的专利质量因子、专利发展情况因子以及技术发展程度因子都要优于广州市，这情况说明广州市聚集了各大高校以及研究所等，科研人才相较于深圳市来说有绝对的优势，而由于深圳市的政治经济因素，使其专利质量以及发展情况更优于广州市。东莞市、佛山市与中山市的专利综合因子得分相近，并且实用新型与外观设计因子得分都较高，三者之中只有中山市的专利来源因子以及专利发展情况因子较优，说明这3个城市主要注重于加工制造业，真正的发明创新较少，其中中山市的专利发展结构较为合理并长久发展的可能。清远市、惠州市、珠海市等专利综合因子得分较低，但专利来源因子、专利质量因子等得分都较高，说明其专利各项发展水平都良好，但是无法成为一个系统发挥促进专利综合发展的作用，为此，这些城市需协调各项专利因素之间的联系与影响。其他的分析也同上文相似，比如各个市之间排名的比较与该市专利开发的分布情况等，都可以依据上述描述，根据表4的数据分析出来，并可以据此看出各市的不足与优势，分析各市的发展重点以及需要进行的改进等。在此不再探讨。
3.2 基于聚类分析的实证研究
为看出各市专利发展水平的相似程度，本文在因子分析的基础上再运用聚类分析方法对各市进行分类。
根据因子分析中得到的6个因子对21个城市进行分层聚类，分别用4类、6类、8类进行聚类，发现分为8类较为合理，最后得到各市在8类中的属类，即表4最后一列。图2是反映聚类过程的树状图，该图各市右边的序号为该市的综合实力排名。
图1的树状图给出了每一步中被合并类的过程，因此可以进一步分析类之间的关系和同一类的差别，以下将进一步探讨。第一类为广州，是因为广州专利综合因子、专利来源因子得分最高，专利综合总得分也遥遥领先于其他城市；第二类是深圳，深圳专利综合因子、专利质量因子、技术发展情况以及专利发展情况得分很高，专利综合评价总分也很高；第三类为佛山和东莞，两个城市的专利发展水平相似，故聚为一类；第四类为中山、汕头、江门，这3个城市专利总综合得分虽然在排名上差距较大，但绝对值差较小，在利综合因子、专利来源因子、专利质量因子、技术发展情况因子的得分上结构相似，因此聚在了一类；以此类推，第五类为清远与韶关，专利综合因子得分相似，专利来源因子与专利发展情况因子得分较高；第六类为湛江、珠海等；第七类是阳江，专利综合评价很差，但技术发展情况因子得分很高；第八类是潮州，专利综合评价以及各方面因子都很差。
参考文献
[1]邵勇.专利指标及其经济效益研究[Ｄ].暨南大学，2003:1-2．
[2]黄庆，曹津燕，瞿卫军，等.专利评价指标体系——专利评价指标体系的设计和构建[J].知识产权，2004，（5）:25-28．
[3]肖国华，王春，姜禾，等.专利分析评价指标体系的设计与构建[J].图书情报工作，2008，(3):96-99．
[4]张冬梅，曾忠禄.专利情报分析指标体系——分析方法与技术[J].情报杂志，2006，(3)：55-57．
[5]阮梅花，肖沪卫.企业自主创新能力评价的专利指标体系构建初探[J].大学图书馆情报学刊，2011，（2）：85-89．
[6]Huang Z，Chen H，Yi PA，et al.Longitudinal patent analysis for nanoscale science and engineering:Country，institution and technology field[J]．Journal of Nanoparticle Research.2003，5(3):333－363．
[7]白思俊，等.系统工程[M].北京：电子工业出版社，2006:25-50．
[8]宇传华.SPSS与统计分析[M].北京：电子工业出版社，2007:459-513．
[9]龚光明，张柳亮.基于因子分析的湖南省上市公司绩效评价[J].会计之友，2012，(1):36-39．
[10]张俊妮.数据挖掘与应用[M].北京：北京大学出版社，2009:70-79．
[11]戴维 F.格罗布纳.商务统计（第六版）[M].北京：机械工业出版社，2008:355-367．
数据聚类分析 篇12
目前在国内及国际上污水处理领域故障诊断和现场监控技术很多采用基于知识的专家系统[1,2,3,4,5],然而开发一个基于知识的系统最大的难点就是建立知识库。知识的获取主要是依靠专家的经验知识,存在知识获取瓶颈问题。本文以城市污水处理中的活性污泥法污水处理为研究对象,利用聚类分析技术挖掘污水处理历史数据中的隐藏知识。聚类分析的目的主要是找到数据中的异常类别,通过分析异常类别的数据,来进行故障规则的建立。在污水处理过程中,绝大多数时候是处在正常状态,而故障状态表现为个别状态,因此,获得正常状态的数目要远大于故障状态的数目,且正常状态数据具有“抱团”的性质,因此采用异常检测方法来发现数据集中的异常数据。
近年来,很多方法被用来进行异常检测,如基于统计方法的异常检测[6]、基于距离的孤立点检测[7]、基于聚类的异常检测[8,9]。文献[6]中假设数据的每一个属性维是符合正态分布,对数据有一定的要求。文献[7]中方法首先计算数据集中对象两两之间的距离,然后累计每个对象与其他对象的距离,距离值从大到小排序,距离值大的被认为是异常数据。文献[9]提出的异常检测过程采用最近邻聚类—遗传优化两个阶段进行异常数据检测。该算法先采用最近邻聚类算法对数据进行初步聚类,形成初始的聚类集,再使用遗传算法进行优化,实现聚类合并,算法结果把包含实例最多的类标为正常活动类,其他的类则标为异常数据类。并将该算法应用于网络入侵检测,实验结果表明该算法可以有效地进行入侵检测。本文提出采用最近邻聚类和遗传优化算法对污水处理运行数据进行聚类分析,然后采用基于距离和的异常因子来度量异常点的异常程度,从而筛选出样本集中最为异常的样本。通过分析异常样本所对应的故障问题,然后对污水处理中的故障规则的建立作了初步探讨。
1最近邻聚类
最近邻聚类算法的基本思想是:空间中的每一点和与之最近的点属于同一类的可能性最大。如果两个距离最近的点之间的距离小于设定的距离阈值d,那么就认为它们属于同一类。最近邻聚类算法试图把两个最近邻的点归为一类。最近邻聚类算法:首先把第一个数据作为第一个聚类中心,接下来,检测其它数据点到该聚类中心的距离,如果该距离小于阈值d就把这个数据放到此类中,否则,把该数据设为一个新的聚类中心;如此直到把所有的数据归类为止。算法描述如下:
给定数据集X={X1,X2,…,Xn}⊂Rm。
Step 1 对于对象实例Xj(j=1,2,…,n),计算其与最近邻对象Xt(t=1,2,…,n且j≠t)之间的相似度,dj=min‖Xj-Xt‖。其中
Step 2 从第一个样本点X1开始,把X1设为第一个聚类中心c1,设定半径d。d=w×(1/n)×∑
Step 3 考虑第k个样本点Xk,己经存在N个聚类中心,分别为c1,c2,…,cN。计算Xk到N个聚类中心的距离dik(i=1,2,…,N),找出其中最小的一个距离dik,如果dik小于d,则把Xk归入第i类,否则把Xk作为一个新的聚类中心,且cN+1=Xk。
Step 4 重复Step 3,直至所有的样本点都归类为止。
Step 5 形成初始聚类集C={c1,c2,…,cK}。具有最多实例数据的类记为cm。
2遗传优化阶段
遗传算法的具体过程描述如下:
1) 编码方式及初始化
个体采用二进制编码。个体的长度等于上个阶段得到的初始聚类集中类的数目K。假设上阶段得到的初始聚类集为C={c1,c2,…,cK},则一个随机产生的个体
随机产生一个长度为K的二进制串作为一个个体的编码。重复进行这个操作,直到psize(种群的大小)个个体全部被初始化。
2) 适应度函数设计[9]
(1) 创建新的聚类。随机选择一个个体S,产生新的聚类过程如下所示:
Sr=s
其中P为种群的大小,s
合并初始聚类。如果‖ci-cm‖≤‖ci-ck‖,s
(2) 适应度的计算。
同时考虑了类内距离INTRA-Cluster距离(INTRACD)和类间距离INTEL-Cluster距离(INTELCD) ,其中INTRACD用来计算在类c
其中
Fc是预先定义好的一个非常小的适应度值。dINTRACD表示c
3) 遗传操作
选择操作采用比例选择法和最优策略保存法相结合,最优保存策略是指当前个体群体中适应度最高的个体不参与交叉运算和变异运算,而是用它换掉当前种群中经过交叉、变异操作后所产成的适应度最低的个体。交叉操作采用单点交叉。按照一定的变异概率pm进行多点变异操作。随机产生多个变异点。对变异点上的值进行“非”运算。
4) 终止条件
采用给定进化代数来终止遗传算法的运行。
5) 解码
将具有最大适应度值的个体的相对应分类情况作为结果输出。
3异常数据的确定
在遗传优化阶段结束后,将具有最多实例的簇视为主簇(定义1),在比较其他簇到主簇的距离,将距离主簇距离较远的簇视为异常簇(定义2)。最后累计异常簇中每个对象与其他对象的距离,并按累计和的大小从大到小排序输出。
定义1 主簇,假设C={c1,c2,…,cK}为聚类算法获得簇的集合,如果簇cm满足
定义2 异常簇,如果d(ci-cm)(i≠m,i=1,2,…,n)大于N×d,则认为ci为异常簇。其中
4实验结果及规则生成
4.1实验数据
数据来自UCI[12]数据库,是搜集了Manresa城市污水处理厂1990～1991年期间的日常监控数据。整个数据集包括不完整记录在内一共有527个样本。每个样本的样本维数为38(即38个属性)。在这38个属性中,有29个属性是从工厂的不同点测量得出的,而其他9个属性是根据整个工厂的初次处理和二次处理的性能计算得出的。数据中存在数据缺失或数据属性值不全的数据,采用了序列平均值方法来填充空缺值。然后使用零—均值规范化方法来规范化城市污水处理厂的日常监控数据。零-均值规范化中,属性A的值基于A的平均值和标准差规范化。A的值v被规范化为v′,由下式计算:
其中,
4.2实验结果
最近邻聚类阶段距离阈值d=w×(1/n)×∑
遗传算法中的参数为:交叉概率pc=0.75,变异概率pm=0.005,种群大小psize=100,最大迭代次数为200。遗传优化阶段过后,又有子类合并到类m中。遗传算法阶段输出合并后的类m。合并后的类m含有454个实例对象。然后根据定义1和定义2来找出异常样本,下面是N不同取值时所对应的情况。
N=1时,得到51个异常样本,N=2,得到15个异常样本。N=3时,得到8个异常样本。N=4,得到3个异常样本。N=5,6,7时,都是得到2个异常样本,N>7时,没有异常样本。
N=1时所得异常样本包含后面所得到的异常样本。累计异常样本与其他数据的距离[7],并按累计和的大小从大到小排序输出。
结果表明,N=2时得到的异常样本与N=1时前15个异常样本比较一致。在文献[10]中,使用基于平行坐标法的可视化工具对同一个样本集进行可视化时,得到的异常样本与本文聚类分析后所得的结果比较一致。该文中,识别出17天异常,8天可能异常,14天处于正常与异常的边界,与本文N=1时,前面的40个异常日基本一致。平行坐标法需要用户根据自己的领域知识和主观判断对数据进行定性分析,可以帮助用户在进行数据挖掘之前对聚类大致情况有所了解,并在算法挖掘之后帮助用户判断数据挖掘算法的正确性,对聚类分析有很大的辅助作用,但这种方法并未对异常数据的异常度进行定量分析。在文献[11]中,要求指定聚类数,当聚类数K=13时,使用聚类算法得到了14个异常样本,与本文的N=2时所得情况比较相似。但文献[11]中在聚类之前要先指定聚类数,这对用户来说,具有一定的难度。表1给出了异常度比较高的日期状态的相关解释。
4.3规则的生成
规则生成的关键就是生成规则的前件部分。规则一般分为析取式规则和合取式规则,但是合取式规则更容易生成,也更容易被大家所理解,所以这里主要讨论如何生成合取式规则。不过规则生成之后要得到专家的接受和认可才可以使用。
生成合取式规则前件的算法如下:
(1) 取出一个异常样本,判断样本的单个属性值。
(2) 如果样本的某一个属性值较大或较小,则把这个属性相关信息作入规则前件的一个项,并把该项加入规则前件中去。重复判断样本的每个属性值。
(3) 重复(1)、(2),直到所有异常样本进行过规则生成。
规则的前件可以是定性的描述也可以是定量的描述,如“COD-D值高”定性描述,或者描述成“COD-D>323.0”定量描述。
以日期13/3/90为例,得出定性描述得到的规则如下:
IF出水pH值“高” and 出水BOD“高”and 出水挥发性悬浮固体量“高” and 出水沉淀物量“高”
THEN二沉池故障
使用定量描述得到的规则如下:
IF出水pH值>152.0 and 出水BOD>306.0 and 出水挥发性悬浮固体量>131.0 and 出水沉淀物量>3.50
THEN二沉池故障
5结语
本文使用基于最近邻聚类和遗传优化算法的异常检测算法对污水处理历史数据进行了分析,使用基于距离和的异常度量因子,筛选出样本集中最为异常的样本。对这些异常样本进行了分析,根据异常样本所对应的故障问题,对使用异常样本生成故障规则进行了初步的探讨,对污水处理工艺故障诊断系统知识库的建立具有一定的实用意义。
摘要：为了识别污水处理数据中的异常数据,应用了一种基于最近邻聚类和遗传优化算法的异常检测算法。算法采用基于距离的异常因子来度量异常数据的异常程度。通过分析异常类别的数据,建立故障诊断的规则。实验结果表明,该方法能够有效地检测中污水处理数据中的异常数据。
关键词：最近邻聚类,遗传算法,异常因子,故障规则,污水处理
参考文献
[1]Barnett M W.Knowledge based expert system applications in wastetreatment operation and controll[J].ISA Transactions,1992,31(1):55-60.
[2]施汉昌,王玉珏.污水处理厂故障诊断专家系统[J].给水排水,2001,27(8):88-90.
[3]李振宇,杨昌柱,章北平,等.污水生物处理故障诊断专家咨询系统[J].化学与生物工程,2005,39(3):39-41.
[4]Baeza J.A improving the nitrogen removal efficiency of an A2/O basedWWTP by using an on-line knowledge based expert system[J].WaterResearch,2002(36):2019-2133.
[5]Kang Jiayu,Mi Linan.An Expert System for Anaerobic WastewaterTreatment Process[C]//IEEE International Conference on InformationAnd Automatic,ICLA,2009:422-425.
[6]Randy J Pell.Multiple outlier detection for multivariate calibration u-sing robust statistical Techniques[J].Chemometrics and IntelligentLaboratory Systems,2000(52):87-104.
[7]陆声链,林士敏.基于距离的孤立点检测研究[J].计算机工程与应用,2004(33):73-75.
[8]Zengyou He,et al.Discovering cluster-based local outliers[J].Pat-tern Recognition Letters,2003(24):1641-1650.
[9]Yongguo Liu,Kefei Chen,Xiaofeng Liao,et al.A genetic clustering meth-od for intrusion detection[J].Pattern Recognition,2004(37):927-942.
[10]Hamza Albazzaz,et al.Multidimensional visualization for process his-torical data analysis a comparative study with multivariate statisticalprocess control[J].Journal of process control,2005:285-294.
[11]Miquel Sanchez,Ulises Cortes,Javier Bejar.Concept formation inWWTP by means of classification techniques:a compared study[J].Applied Intellgence,1997(7):147-165.