（计算机应用技术专业论文）时间序列挖掘算法在槽况判断上的应用与研究.pdf

北方工业大学硕士学位论文 摘要 在现有的铝电解生产过程中，通过控制系统采集了大量的电解槽生产数据，这些数 据反映了电解槽在采样时刻的各种工作状态，并在上位机监控系统中通过图形、报表等 各种形式为用户提供服务。但是，这些海量数据仅向用户提供了各个时期电解槽的工作 状况，用户需要依靠自己的领域知识和丰富的经验才能进行初步的定性分析，以获取图 形、报表等之外的信息。而在这些海量数据中，隐藏了大量的有用信息，如何对这些数 据进行有效的分析，以获得单槽和系列槽的槽况及其发展趋势，并对所有的电解槽进行 分类，在生产中对各种分类进行区别管理，目前还缺少这方面的工作。 本文提出了序列数据基于时间窗口滑动分析算法，用以解决铝电解工业生产中槽况 的分析和预测问题。该算法的核心是根据点的距离构建空间的连通分支，并利用时间窗 口的滑动来判断当前的槽况。文中详细讨论了算法的基本概念，并给出了相应的连通分 支挖掘算法。利用连通分支进行数据的聚类分析，获取系列槽的槽况分类，同时，提出 了时间窗口滑动的方法来分析单槽的当前槽况及其发展趋势。 本文通过对铝电解生产过程产生的海量数据进行聚类和预测分析，获得系列槽和单 槽的槽况分析结果，并进而指导生产，具有积极的意义，也是目前生产实际中急需解决 的问题。通过对实际的生产数据进行实验分析，对实际生产具有较强的指导意义。 关键词：铝电解，聚类分析，距离，连通分支，时闻窗口滑动 北方工业大学硕士学位论文 a b 咖a c t h l 吐l ! e 商s t i n g 芦o d ：幽p r j d c e 豁o f a d l 期蛔髓出动- 0 l y s i s ，al a r g en u m l 描0 f e 捌舛c 础d a 趣w l 五6 h r e 丑删n l es l o 蓬w 饼垴玎g 姗纽位渤p l i n g 幻s t a l l a n d 删d e d u s e 咚硒t h 洲c 嚣也嘶乎a p i l s ，s t 吐1 融鼬纽d0 也钉毓璐a t 也eh o s tc o m 脚m o n i t o i i i 玛s y 她 咖c 0 u 硎b ym e 洲s y s 疏h o w e 吼t h 敷谳d a l a0 m y 呻访d c 螂砌惋 1 0 t w 贸l ( i n g s i nv 乏抵p 舐o d s u s e 疆撇嘶o n 啦e i r m p 鲰s i o 谳鼢l e d g e a n d r i c h 甑p 舐锄c 器t 0 倒巧吡硼洫峋q u 砌 a l i v c 觚由豳幻蛐硎0 n o 啦o f 础， s t a 锄n e n 奴e t c a1 0 to fu s e 如li 玎蠡眦n a 矗o nw e f el l i d 6 d 既瑚1 d e rt 量l e s em a s s i v ed l a l 凯ri s 蛳协删y z e 幽麟纰蝴t o 龇m e s 觚dd e v 幽p 魄蛐o f 渊e s 1 0 t 锄das e r i 鹤o fs 1 咄i ti sa l s o i 】邺r n a i l tt oc l 私s i 矽a l l 也e 础觚dr e a 脑凼| 蚴 m a l ：唧，e 【i 蝴a c 叛她t 0d i 伍觚d 嬲s i 丘c 砥o ni nt h e 芦o ( 咖掣潲a t 髑吼m 鹏i s 虹u a l a c k o f w o r k i n t h i s 撒 t 地p a p 盯鲫嬲如s 耐鹤0 f d a 土ab 必e d0 l ls l i 魄丽i 幽w 锄a l 灿a l 鲥玛t o l v e l e 锄a 1 ) ，s i s 砌缅a s t 咖b 1 锄o f s l o ts t a ：t u si n 舯讪删o no f a d l 珊岫d e c 廿o l 灿mc o f e0 f t h i s 砌a l y s i sa 1 9 0 础n i s 圮c o 删0 l l o f 也e 币e c i m 鲫m 枷v e b m c h b 鹤。d o n 廿l ed i 撇 0 f p c i i i i t s ，锄【d j 咄t l l e 蛐0 f m e 伽r r 哪钒m g h 咖t h cs h d i i 培w 洒d o w0 f 缸砸sp a p 日 廖v e s 删d i s c 嘶0 璐o f b 勰i cc 0 瞰印t so f 此a l 琴时i l l 】【n 锄d 柏t l l ec o m 印o i l d i n gb r a i 】i c h 删、，i 锣i i l i 】【1 i n ga l 触螂曲c o i ：嘲觚协n mm e 蛐0 rc a n y 咖c ：i 咖 a n a l y s i so fd a 殷l o 勃f t a i l lt 量托c i a s s i 6 训o no ft i 圮s t i n l so fs e r i e so fs ：i o t ，a i l db 血g 咖矾6 i n e s h 血培w i i l d 0 1 w 科a c h 幻柚a l y z et h e 蝴锄dd e 叭1 1 0 p i i 培饥m d so fs i 】【1 酉es l o t t p a p | e f 百v e sc ：l u s t 酉a 1 1 a l y s i sa n d 硒喇a n a l y s i st 0t h e 删v e d a ：t aa r i s i i 唱自咖m e p o d ：u c i i 培p n 脯so fa h n i i n ne l e 咖l y s i s ，m e no b 缸l i no u ：t i x 髓eo f l es t i t i l so fs e r i e so fs l o t 狃ds i l l g l c 姒觚酏岫m e 耐慨瓯融i s0 fp 0 蜘s 蛳矗嗽a n d 妇龇 砷b l 锄圾寥n t 幻l v ci nt 量l ea c t u a l 测o n 豇玳 u 庐龇翱：肿铋t a l 锄i a l y s 主so fa c t i 冶l 圳0 n d a 饥慨勰咖n g 溅s i 嘶6 c a r 哟t da c t u a l 删吡 k e yw o r 凼：e k 仃蚺，c l u s 钯ra a l y s 趣，d i 地m ，c 咖钌雠b r 缸c h ，s k d i n g 缸e 妇d o w 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得j 量友王些太堂或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文储签名嘞签字日期：扫晶年炒弓日 学位论文版权使用授权书 本学位论文作者完全了解j e 友王些太堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅。本人授权j e 友王些太堂可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：潞 签字日期：b 晶年5 - 月乃1 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 彩刁 签字日期：v 楫，月巾 电话： 邮编： 北方工业大学硕士学位论文 1 绪论 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来 越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析， 以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计 等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋 势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。于是 以数据仓库为基础的多维分析和数据挖掘技术成为近几年最活跃的领域之一，并得以蓬 勃的发展，广泛应用于各行各业。 1 1 课题背景及研究意义 当今数据容量规模已经达到万亿字节的水平过量的数据被人们称为信息爆炸，带 来的挑战是：一方面规模庞大、纷繁复杂的数据体系让使用者漫无头绪、无从下手；另 一方面在这些大量数据的背后却隐藏着很多具有决策意义的、有价值的信息。要想使数 据真正成为企业的资源，只有充分利用其为企业自身的业务决策和战略发展服务才行， 否则大量的数据可能成为包袱，甚至成为垃圾。因此，面对人们被数据淹没，人们却饥 俄于知识”的挑战，已成为人们迫切需要解决的问题。现在越来越多的企业认识到企业要 想在竞争中取胜，必须利用计算机和网络技术，数据仓库和数据挖掘技术做深层次的挖掘， 分析历史和当前的大量数据。自动获取其中有用的决策信息，为企业提供快速和方便的 决策支持。通过对企业生产和计划的完成情况及相关环境数据进行多角度和深层次的分 析，使企业的决策者即时掌握企业的运行情况和发展趋势。并对制定生产规划和长远计划 提供理论指导，提高企业的管理水平和竞争优势。在此情况下多维分析和数据挖掘技术 成为信息领域研究的重点。 多维分析工具可提供数据多角度和多层面的逻辑视图，用户提出问题和假设，多维 分析提供该问题的详细信息，并将结果呈现给用户。数据挖掘是从大量数据中提取或“挖 掘”知识是在现有的人工智能和统计的成熟技术在特定系统中的运用。电解槽大量在线数 据的采集，为生产的分析和管理提供了先决条件在这些数据中存在我们无法直接知道 的大量规律，它们反映了电解槽当前的状况和未来的趋势。如果能利用这些计算机能发 现的规律，并对铝电解生产过程做出调整，对铝的生产技术和铝厂的经济效益具有不可估 量的作用。 根据以上的分析和铝厂的具体情况，对多维分析和数据挖掘技术的研究具有重要的 理论意义和现实意义。 北方：r 业人学硕十学位论文 1 2 铝电解工艺研究现状 据资料统计，到2 0 0 3 年，我国电解铝的生产量和消费量均居世界第一，铝电解生产 企业1 4 0 家，遍布全国2 6 个省区。各个铝厂均采用了自动化控制系统。在铝电解的生 产过程中( 见图1 1 ) ，采集了海量的反应电解槽状态的数据，如电解槽的工作电压、平 均电压、针振、电压摆、系列电压、系列电流、效应发生时刻、效应电压等；此外，另 外有测量的电解槽的各种工艺数据，如：分子比、氧化铝浓度、温度、两水平等。 圈卜l 铝电解工艺图 目前，铝电解现有的控制系统大都只能根据实时采集的数据进行槽况的监控，调整 工艺参数，显示槽电压、电流等参数变化的实时曲线，统计采集的数据生成报表，然后 将数据存入数据库。作为历史数据后只能用作再现槽状况，而这些数据中可能隐含的大 量的规律或规则是无法被反映出来的。 另外在现有的系统中，生产管理人员对电解槽是参考所测量的部分参数指标，如电 压、分子比、槽温等，根据个人的经验做出定性的分析判断来进行下一步的管理，不能 精确的分析出各种因素之间的相互影响关系，以及不同槽之间、同一台槽的不同时期和 不同状态下，各因素之间的复杂关系以及对槽况的影响。 由于电解槽是一个半定量，反应滞后的体系，许多参数之间有着高度的、滞后的相 关性。铝电解数据具有如下的特点： ( 1 ) 多变量。在生产过程中，已能在线检测许多物理量。研究目标的影响因素相当多， 在多变量数据处理过程中，许多参数之间常是强相关的。 - 2 北方工业大学硕士学位论文 ( 2 ) 非线性。经典的统计方法主要处理线性关系，因为在线性并且噪音极小条件下， 容易用严格的数学模型来描述目标，并得到解析解。但铝电解生产系统中的绝大多数问 题不能简化为线性问题，特别是复杂生产数据的处理问题。 ( 3 ) 高噪音。噪音干扰是研究目标或自变量失真。噪音可能是“白噪音或“有色噪 音，主要由不确定因素导致，甚至是系统的混沌现象( 如铝液的湍流现象) 构成。 基于铝电解行业的生产管理现状，信息化工厂建设和优化管理控制指标的需求，考 虑铝电解数据的特点：不能建立精确的数学描述模型，直观的确定哪些因素与研究目标 有关，所以我们把数据仓库和数据挖掘技术应用到铝电解的数据分析、及生产管理和控 制中来通过对槽状态的分类、判断、发现异常槽及槽况变化的原因分析；分析各工艺参 数之间的相互影响关系，确定最佳的工艺参数组合，提供给专业人员用于有效地指导铝 电解的生产，以获取更好的控制效果，规范铝电解生产管理，为科学化管理提供依据， 同时提高铝电解行业的信息化水平。 本课题来源于北方工业大学和国内某电解铝厂合作的数据挖掘系统。 1 3 课题研究的内容 作者查阅了大量国内外相关资料和书籍，对数据仓库，数据挖掘和时间序列算法做了 深入的研究。从而提出了时间窗口滑动聚类对槽况预测的模型，并应用与宁夏青铜狭铝 厂数据挖掘系统中。具体研究内容如下： 1 3 1 数据仓库 数据仓库是一个环境，而不是一件产品，提供用户用于决策支持的当前和历史数据， 这些数据在传统的操作型数据库中很难或不能得到。数据仓库技术是为了有效的把操作 形数据集成到统一的环境中以提供决策型数据访问，的各种技术和模块的总称。所做的 一切都是为了让用户更快更方便查询所需要的信息，提供决策支持。 数据仓库的组成如下： 数据抽耽数据净化数据载入 信息发布系统 操作型数据和外界数据 数据集市 报表，查询，e i s 工具 o 乙谨工具 数据挖掘工具 - 3 北方1 ：业人学硕+ 学位论文 操纵平台 元数据 管理平台 1 3 2 数据挖掘 数据挖掘( d a t am 是指通过筛选存储在目录库中的大量数据来发现有用的相互 关系、模式和趋势的过程。数据挖掘采用模式识别技术以及统计和数学技术。 1 3 3 聚类算法 1 3 3 1 聚类分析的定义 所谓聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能小， 类内相似性尽可能大。聚类是一个无监督的学习过程，它同分类的根本区别在于：分类 是需要事先知道所依据的数据特征，而聚类是要找到这个数据特征，因此，在很多应用 中，聚类分析作为一种数据预处理过程，是进一步分析和处理数据的基础。例如在商务 中，聚类分析能够帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模 式来刻画不同的客户群的特征。在生物学中，聚类分析能用于推导植物和动物的分类， 对基因进行分析，获得对种群中固有结构的认识。聚类分析也可以用于在泥土观测数据 库中对相似地区的区分，也可以根据房子的类型、价值和地域对一个城市中的房屋进行 分类。聚类分析也能用于分类w e b 文档来获得信息。作为数据挖掘的功能，聚类分析可 以作为一个获得数据分布情况、观察每个类的特征和对特定类进一步分析的独立工具。 通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相 互关系等。 一个能产生高质量聚类的算法必须满足下面两个条件： 类内( i n t r a d a 鼹) 数据或对象的相似性最强 类问( i n t * d a 鼹) 数据或对象的相似性最弱 1 3 3 2 聚类分析中的数据结构 聚类质量的高低通常取决于聚类算法所使用的相似性测量的方法和实现方式，同时 也取决于该算法能否发现部分或全部隐藏的模式。 许多基于内存的聚类算法选择两种有代表性的数据结构：数据矩阵和相异度矩阵。 数据矩阵是一个对象属性结构。它是由n 个对象组成，如：人；这些对象是利用p 个属性来进行描述的，如：年龄、高度、重量等。数据矩阵采用关系表形式或n p 矩阵 来表示，如图1 2 所示。 4 北方工业大学硕士学位论文 相异度矩阵是一个对象对象结构。它存放所有n 个对象彼此之间所形成的差异。它 一般采用n x n 矩阵来表示，如图1 - 3 所示。 蓦习 i x 嗲x 叩、量。1 d ( 3 ，2 ) o i d ( 刀。2 ) ol 其中砸j j ) 表示对象i 和对象j 之间的差异( 或不相似程度) 通常d ( i j ) 为一个非负 数；当对象i 和对象j 非常相似或彼此“接近时，该数值接近o ；该数值越大，就表示 对象i 和对象j 越不相似。由于有砸j 户哟i ) 且酢痧= o ，因此就有上面所示三角矩阵。 在具体的应用中，我们可以根据聚类所采用的算法，选择一种适合该算法的数据矩 阵形式。 1 3 3 3 聚类分析中的数据模型 聚类分析起源于统计学，传统的分析方法大多是在数值类型数据的基础上研究的。 然而数据挖掘的对象复杂多样，要求聚类分析的方法不仅能够对属性为数值类型的数据 进行，而且要适应数据类型的变化一般而言，在数据挖掘中，对象属性经常出现的数 据类型有：区间标度变量，二元变量，标称型、序数型和比例标度型变量以及混合类型 的变量。 区间标度变量 区间标度变量是一个粗略线性标度的连续度量。典型的例子则包括重量和高度，经 度和纬度坐标，以及大气温度等。为了将数据或对象集合划分成不同类别，必须定义差 异性或相似性的测度来度量同一类别之间数据的相似性和不属于同一类别数据的差异 性。同时要考虑到数据的多个属性使用的是不同的度量单位，这些将直接影响到聚类分 析的结果，所以在计算数据的相似性之前先要进行数据的标准化。 对于一个给定的有n 个对象的m 维( 属性) 数据集，主要有两种标准化方法： 平均绝对误差s o 5 ) ) l r i ， ， ， o q p ；研 撼留 i i 1 靠 rlllllill 北方j t ：业大学硕士学位论文 = 莓1 x 驴一聊p l 这里表示的是第i 个数据对象在属性p 上的取值，m ，是属性p 上的平均值，即： 聊p 2 工驷 标准化度量乙 驴孚 这个平均的绝对误差s p 比标准差op 对于孤立点具有更好的鲁棒性。在计算平均绝 对偏差时，属性值与平均值的偏差l ，一朋，l 没有平方，因此孤立点的影响在一定程度上 被减小了。 数据标准化处理以后就可以进行属性值的相似性测量，通常是计算对象间的距离。 对于n 维向量x i 和玛，有以下几种距离函数： 欧氏距离： d ( x ，工_ ，) = 一l 曼哈顿距离： d ( t ，x ，) = i 一l 七= l 一般化的明氏 幽k c l w a l c i ) 距离： d ( x l ，z ，) = 【( x t x 皿) 。】。 当m ：_ 2 时，明氏距离d m 即为欧氏距离；当n l = l 时，明氏距离马即为曼哈顿距离。 对于欧氏距离和曼哈顿距离满足以下条件： ( i ) d ( ，- ) 0 ：距离是一个非负数值； 伍) d ( _ ，x ，) = 0 ：对象与自身的距离是零： ) d ( 毛，x 2d ( 一，而) ：距离函数具有对称性； 6 北方工业大学硕士学位论文 d ( 而，_ ) d ( ，_ ) + d ( 以，x ，) ：x i 到冯的距离不会大于x i 到) 【i c 和到玛的距离 之和( 三角不等式) 。 二元变量 二元变量只有两个状态：0 和l 。其中二元变量又分为对称的二元变量和不对称的二 元变量。前者是指变量的两个状态不具有优先权，后者对于不同的状态其重要性是不同 的。 对于二元变量，度量两个变量的差异度由简单匹配系数( 对称的情况) 和j a 锄融系 数( 非对称的情况) 决定。设两个对象x i 和玛，q 是属性值在两个对象中都为l 的属性 个数，f 是属性值在x i 中为l 而在玛中为o 的属性个数，s 是属性值在x i 中为o 而在玛 中为1 的属性个数，t 是属性值在两个对象中都为0 的属性个数。则简单匹配系数： 讹刚= i j 删系数： d ( 五，工，) = 旦 q + r + s 标称型、序数型和比例标度型变量 标称变量是二元变量的推广，它可以有多个状态值，状态之间是无序的。具有这种 数据类型的属性也称分类( c a 】6 昭耐c a l ) 属性。 它的差异度可用简单匹配法来计算： d ( ，工，) = 生旦 夕 其中，m 是对象】【i 和玛中匹配的属性个数，而p 是全部属性个数。 ， 序数型变量类似于标称型变量，但它的各个状态是有意义的序列。比例标度型变量 再非线性的标度取正的度量值，例如指数标度，近似遵循彳p 皿或彳p 一，其中a ，b 是正 常数。 混合类型的变量 以上讨论了各种数据类型和它们差异度的计算方法，在实际数据库中，对象是由混 合类型的变量描述的。在实际聚类分析中，将不同的类型属性组合在同一个差异度矩阵 中进行计算。设数据包含m 个不同类型的属性，对象x i 和x i 之间的差异度定义为： 7 - 北方工业n 大学硕十学位论文 嘭力印 d ( 工f ，x ) = 上型i 一 嘭力 ，i l 其中如果砩或砩缺失，或砩；嘞= o ，且变量是不对称二元变量，则指示项噶川= o ； 否则掣= 1 。 如果属性p 是二元变量或标称变量：如果砩= 砩，秽= o ，否则，d = l 。 d ( ，)! 垒二塾! 如果属性p 是区间标度变量： 9 m a x 一一蛐n ，这里的h 取遍具有非空属 性p 的所有数据对象。 如果属性p 是序数型或比例标度型变量：将其转化为区间标度变量值对待。 1 3 3 4 对现有聚类算法的研究 目前存在着大量的聚类算法，算法的选择取决于数据的类型、聚类的目的和应用。 从总体上来看，聚类算法可以分为串行算法和并行算法两类。 划分方法 给定一个n 个对象或元组的数据库，一个划分方法构建数据的k 个划分，每个划分 表示一个聚簇，并且k n o 也就是说，它将数据划分为k 个组，同时满足如下的要求： ( a ) 每个组至少包含一个对象；( b ) 每个对象必须属于且只属于一个组。但在某些模 糊划分技术中第二个要求可以放宽。 划分方法首先根据给定要构建划分的数目k 创建一个初始划分，然后采用一种迭代 的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准则是： 在同一类中的对象之间尽可能“接近 或相关，而不同类中的对象之间尽可能“远离” 或不同。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上，绝 大多数应用采用了以下两个比较流行的启发式方法： ( a ) k - 平均值( k m 巳n s ) 算法，在该算法中，每个簇用该簇中对象的平均值来 表示。 ( b ) k - 中心点( k m m d o 玎潞) 算法，在该算法中，每个簇用接近聚类中心的一个 对象来表示。下面详细介绍这两种算法。 k - m e a n s 算法 8 北方工业大学硕士学位论文 k _ m 鲫陷算法首先随机选择k 个对象，每个对象代表一个聚类的质心。对于其余的 每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中。 然后，计算每个聚类的新质心。重复上述过程，直到准则函数会聚。通常采用的准则函 数是平方误差准则函数。 k 棚翩n s 聚类算法的具体步骤如下： 1 ) 从数据集中选择k 个质心c l ，c 2 ，及作为初始的聚类中心； 2 ) 把每个对象分配到与之最相似的聚合。每个聚合用其中所有对象的均值来代表， “最相似就是指距离最小。对于每个点v i ，找出一个质心c ：i ，使它们之间的距离d ( ， c i ) 最小，并把v i 分配到第i 组； 3 ) 把所有的点都分配到相应的组之后，重新计算每个鲴的质心c i ； 循环执行第2 ) 步和第3 ) 步，直到数据的划分不再发生变化。 该算法具有很好的可伸缩性，其计算复杂度为a 炳蛐，其中，t 是循环的次数。k - m e a n s 聚类算法的不足之处在于它要多次扫描数据库，此外，它只能找出球形的类，而不能发 现任意形状的类。还有，初始质心的选择对聚类结果有较大的影响，该算法对噪声很敏 感。 k 棚e d o i d s 算法 k - 蚰e d o i d s 算法的过程和上述k 咖昀璐的算法过程相似，唯一不同之处：k m e d o i d s 算法用类中最靠近中心的一个对象来代表该聚类，而k m 璐算法用质心来代表聚类。 在k - 1 n e a 璐算法中对噪声非常敏感，因为一个极大的值会对质心的计算带来很大的影 响。而k - 】洲d s 算法中，通过用中心来代替质心，可以有效地消除该影响。 k 加e d o 迅算法首先随机选择k 个对象，每个对象代表一个聚类，把其余的对象分 别分配给最相似的聚类。然后，尝试把每个中心分别用其他非中心来代替，检查聚类的 质量是否有所提高若是，则保留该替换。重复上述过程，直到不再发生变化。 常见的k - m 幽d s 算有：p a m 口a m 廿i n g 加伽n dm 。d o i l s ) 算法、c i 。a ra ( c 1 u s t 谢n g l a 增e 舢枇c a 垃0 1 1 ) 算法、c u d 认n s ( c b 阳曲gl a 瑁e 赳咄c a d o nb 鹤e d 叩o nr a n d o m i z e d s 铭池) 算法。当存在“噪声一和孤立点数据时，k 嘲e d o i d s 算法比可k - t n 倒= l s 更健壮，这 是因为中心点不像平均值那么容易被极端数据影响。但是，k - m e d o i d s 算法的执行代价比 k - n 1 啪s 高。 总之，划分方法具有线性复杂度，聚类的效率高的优点。然而，由于它要求输入数 字k 确定结果簇的个数，并且不适合于发现非凸面形状的簇，或者大小差别很大的簇， 9 北方工业大学硕士学位论文 所以这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的 数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。 层次方法( h i 蹦l 删c a lm 咀1 0 d ) 层次方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次的 方法可以分为凝聚的和分裂的【捌。凝聚的方法，也称为自底向上的方法，一开始将每个 对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个( 层 次的最上层) ，或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始 将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终 每个对象在单独的一个簇中，或者达到一个终止条件。 凝聚 觚 初始 步骤l 步骤2 步骤3 步骤4 t t t 一 分裂d 姒) 步骤4步骤3 步骤2 步骤l初始 图l - 3 在数据对象i 莨合 a b 啊 e 上的凝聚和分裂层次聚类 让我们看一个图就可以理解，层次聚类方法。图1 3 描述了一个凝聚的层次聚类方 法a i g n e s ( a 9 9 1 0 n 埘a l i v en 删和一个分裂的层次聚类方法d l 埘a ( d i v i s i v e 知1 a l 河s ) 在一个包含五个对象的数据集合 a ，b ，c 囊e ) 上的处理过程。最初，a i 国厄s 将每 个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。在d i a n a 方法的处理 过程中，所有的对象初始都放在一个簇中p 根据一些原则( 如簇中最临近对象的最大欧 式距离) ，将该簇分裂。簇的分裂过程反复进行，直到最终每个新的簇只包含一个对象。 主要的凝聚聚类算法有c i 瓜e ，c l 啪l e o n ，b i h ，r o c k 等。下面逐一介绍。 b 瓜c h 算法 b h ( b a l a i 硝dr e r a 矗垤r c d u c i i 培dc l 璐t 鲥n g 璐i 1 1 gh i 饿1 1 i i 哟算法使用了一种 叫做c f 树( 聚类特征树，即c l 璐c e f i n gf e a t u 他t r 嘲的分层数据结构，来对数据点进行动 1 0 北方工业大学硕士学位论文 态、增量式聚类。c f 树是存储了层次聚类过程中的聚类特征信息的一个加权平衡树，树 中每个节点代表一个子聚类，并保持有个聚类特征向量c f 。每个聚类特征向量是一个 三元组，存储了一个聚类的统计信息。聚类特征向量a 7 = 州，z s ，船) 中包含了一个聚类 的三个统计信息：数据点的数目n ，这n 个数据点的线性和船，以及这n 个数据点的 平方和s s 。一个聚类特征树是用于存储聚类特征c f 的平衡树，二它有两个参数：每个节 点的最大子节点数和每个子聚类的最大直径。当新数据插入时，就动态地构建该树。与 空间索引相似，它也用于把新数据加入到正确的聚类当中。 b 配h 算法的主要目标是使加时间尽可能小，原因在于大型数据集通常不能完全 装入内存中。b 玎k i h 算法通过把聚类分为两个阶段来达到此目的。首先通过构建c f 树 对原数据集进行预聚类，然后在前面预聚类的基础上进行聚类。该算法的具体过程如下： 1 ) 预聚类( 舯鲥u s 阶段：扫描整个数据库，构建初始聚类特征树，该树保存在内存 中，用简洁的汇总信息或者叶子节点中的子聚类( s u 】划璐唧来代表数据点的密集区域。 2 可选阶段) 重新扫描叶子节点项，来构建一个更小的c f 树。通过本阶段，可以去 除噪声，并从子聚类中得到相对较大的聚类。 3 ) 采用别的聚类算法，对c f 缸优的叶子节点进行聚类。它使用现有的基于质心的聚 类算法或者现有算法的改进形式，把每一个子聚类当作个单一的数据点，对叶子节点 的子聚类进行聚类。b 口w h 算法需要用户输入参数，如期望得到的聚类数目或者聚类的 期望大小阀值( 半径或直径) 。 4 ) ( 可选阶段) 把前一个阶段中找到的聚类的质心，用作种子来创建最终的聚类。其他 数据点根据到这些种子所代表聚类的远近来重新分配到各个聚类中该阶段还可以用于 减少噪声数目。 以上各阶段中，第2 ) 、4 ) 阶段是可选的，它们用来实现聚类过程的优化。 建造c f 树的过程相当于一种预处理，大大减少了总的数据处理量，提高了算法的 处理速度。b 口k h 算法只对原数据集进行一次初始扫描，所以其计算复杂度是0 0 田。不 过，这是在套防 k 的前提下得到的，其中k 是子聚类的数目。当k 接近于n 时，复杂 度就变成o ( 1 屹) ，因此，在第一阶段中选择合适的阀值是非常必要的。b 瓜c h 的主要缺 点之一就是在初始扫描完成之后，它使用基于质心的方法来形成聚类，当聚类的形状不 同或大小各异的情况下，就容易出现伺题。此外，该算法采用直径作为控制参数，所以 当类的形状非球形或不同大小的类时，聚类效果不佳。还有，该算法对数据的输入顺序 很敏感，还需要用户手工设置一些参数。 北方业人学硕士学位论文 a 瓜e 算法 a 服e ( c h l s t 谢n gu s i i 培娜t a 矗v e ) 算法选择基于质心和基于代表对象方法之间 的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具 有代表性的点。针对大型数据库，a 瓜e 采用随机取样和划分两种方法的组合：一个随 机样本首先被划分，每个划分再被部分聚类。该算法的具体过程如下： 1 豚数据对象中抽取一个随机样本s ； 2 ) 将样本s 分割为一组划分： 3 ) 对每个划分局部地聚类； 钔通过随机取样剔除孤立点。如果一个簇增长的太慢，就去掉它； 5 ) 对局部的簇进行聚类。落在每个新形成的簇中的代表点根据用户定义的一个收缩 因子q 收缩或向簇中心移动。这些点代表和捕捉到了簇的形状； 6 1 用相应的簇标签来标记数据。 c i 瓜e 算法中每个簇有多于一个的代表点，使得a 瓜e 可以适应非球形的几何形状； 该算法对孤立点的处理更加健壮，而且能够识别非球形和大小变化较大的簇；q 瓜e 的 复杂性为o ( n ) 。但是，该算法从源数据对象中抽取一个随机样本s ，基于对此样本的划 分进行聚类，如果抽取的样本发生倾斜，则会严重影响聚类结果。 r o c k 算法 c i 瓜e 算法不能处理枚举型数据，而r o c k 算法是在c u 迮基础之上适用于枚举数 据的聚结分层聚类算法。通过把两个聚类的聚集相互连接度( a g g r e g 如j n 由黝加e c 6 啊劬 与用户定义的静态相互连接模型相比较，从而度量两个聚类之间的相似度。其中，两个 聚类的相互连接度是指两个聚类之间的交叉连接数目，而连接l i i 】l ( ，p j ) 是指这两点之间 的共同邻居数。换句话说，聚类相似度是用不同聚类中又共同邻居的点的数目来确定的。 r ( ) c k 算法首先用相似度阀值和共同邻居的概念，从给定的数据相似度矩阵中构建 一个稀疏图，然后对该稀疏图使用分层聚类算法进行聚类。 e l e o n 算法 c ! l l 锄e l e o n ( 变色龙) 是一个利用动态模型的层次聚类算法。算法思想是：首先通过 一个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用一个凝聚的层次聚类 算法通过反复地合并子类来找到真正的结果簇。它既考虑了互连性，又考虑了簇间的近 似度，特别是簇内部的特征，来确定最相似的子簇： c = l l 瞄e l e o n 跟c i 瓜e 和d b s c a n 相比，在发现高质量的任意形状的聚类方面有更强 的能力。但是，在最坏的情况下，高维数据的处理代价可能对n 个对象需要o ( n 2 ) 的时间。 - 1 2 - 北方工业大学硕士学位论文 总的来说，层次的方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能 被撤消，该技术的个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚 类的结果： ( a ) 在每层划分中，仔细分析对象间的“联接一，例如c i 瓜e 中的做法。 ( b ) 综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代 的重定位来改进结果。 基于密度的方法( d 锄s i 白曲勰e dm 锄o d ) 绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状的簇， 而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法，其主要 思想是：只要邻近区域的密度( 对象或数据点的数目) 超过某个阈值，就继续聚类。也 就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的 点。这样的方法可以用来过滤“噪声 孤立点数据，发现任意形状的簇。常见的基于密 度的聚类算法有d b s c a n ，o p t i c s ，d e n c u j e 等 d b s c a n 算法 d b s c a 脚s i 妒b a s e ds p a l i a lc l _ u s t 舒n g0 fa l 叫i 斌姐、玩血奎i o i 嘲是一个基于高密 度连接区域的密度聚类方法。d b s c a n 通过检查数据库中每个点的e 邻域来寻找聚类。 如果一个点p 的邻域包含多于m i l l p t s 个点，则创建一个以p 作为核心对象的新簇。然 后，d b s o 阑反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些 密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。具体过程如下： d b s a 州，酗，m i 1 【l p 哟 岫) u t ：d ：数据对象集合，e p s ：邻域或称为半径，m i i l l 地：密度阈值 1 ) 读取d 中任意一个未分类的对象o ； 2 ) 检索出与。的距离不大于b p 8 的所有对象b 卸s ( 0 ) ； 3 ) 如果| n e p s ( o ) 闩v i i l l p t s ( 即。为非核心对象) ，则将。标记为噪声，并巩，i j 髁- j ； 4 ) 否则( 即。为核心对象) ，给n 印s ( o ) 中的所有对象打上一个新的类标签n e 、v i d ， 然后将这些对象压入堆栈的se e i d s 中； 5 ) 让q i r r 删o c t = s d s t i 叩；然后检索属于n e p s ( c l 盯锄卿j 鳅) 的所有对象；如果 i n 印s ( q 盯朗t o b j 鳅) 眺以训，则剔除已经打上标记的对象，将余下的未分类对象打上类 标签i l e 丽d ，然后压入堆栈； 6 ) s e o d s p o p ，判断s d s 是否为空，是，则执行步骤1 ) ，否则执行步骤5 ) 。 1 3 北方：1 业人学硕士学位论文 从上面的算法中可以分析得到，d b s c a n 算法不仅可以发现任意形状的聚类，对数 据输入顺序不敏感，并且具有处理异常数据( 噪音) 的能力。但是，该算法对用户定义 的参数是敏感的，而参数的恰当选择是需要有相关经验的；同时，该算法的时间复杂性 是c 憎) ，用这种复杂度的算法聚类大型数据库是不太现实的，如果采用空间索引，基于 r 树的d b s c a n 算法的复杂性为o ( m o g n ) ，是相当高效的，此时是忽略建立索引的时 间，而建立索引通常需要消耗大量的时间。 o p l l c s 算法 o p t i c s ( o r d e 血gp o i n t st 0i d d 黟吐圮c l u s t 商n gs 协】c t i 娴通过对象排序识别聚类结 构。o p t i c s 没有显式地产生个数据集合簇，它为自动和交互的聚类分析计算一个簇次 序( c h 卫s t e ro m 醯培) 。这个次序代表了数据的基于密度的聚类结构。它包含的信息，等 同于从一个宽广的参数设置范围所获得的基于密度的聚类。也就是说，对于一个恒定的 参数m i l l p t s 值，可以同时处理一组距离参数值。 o p t i c s 在选择参数方面具有比d b s c a n 较高的灵活性，在采用空间索引时，复杂 度为o ( 1 1 1 0 9 n ) ，和d b s c a n 时间复杂度相同。但是，它需要额外的空间存储每个对象的 核心距离和一个适当的可达距离。 d e n c l u e 算法 d e n c i ，i 甩( d e 船时b 舔e da u s t c 丽n 曲是一个基于一组密度分布函数的聚类算法。它是 对k - m 鲫c l s 聚类算法的一个推广：k - m 锄s 算法得到的是对数据集的一个局部最优划分， 而d e n c l u e 得到的是全局最优划分。 该算法主要基于下面的想法： ( 1 ) 每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点 在邻域内的影响，被称为影响函数( i n 丑u c e 缸蛾i o n ) ； ( 2 ) 数据空间的整体密度可以被模型化为所有数据点的影响函数的总和； ( 3 ) 然后聚类可以通过确定密度吸引点( d e n s 时a l t 唧砘0 r ) 来得到，这里的密度吸 引点是全局密度函数的局部最大。 d e n c l u e 算法有一个坚实的数学基础，概括了其他的聚类方法，包括基于划分的、 层次的、及基于位置的方法；同时，对于有大量“噪声 的数据集合，它有良好的聚类 特征：对于高维数据集合的任意形状的聚类，它给出了一个基于树的存储结构来管理这 些单元，因此比一些有影响的算法( 如d b s c a n ) 速度要快。但是，这个方法要求对密 度参数。和噪声阈值毛进行仔细的选择，如果选择不当则可能显著地影响聚类结果的质 量。 1 4 北方工业大学硕士学位论文 基于网格的方法( 蓟d - b 鹤e dm e 吐：1 0 d ) 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的 聚类操作都在这个网格结构( 即量化的空间) 上进行。基于网格的聚类算法主要有s t 矾g w a 赋c i j q i 旭等。 s t 玳g 算法 s t 烈g ( s t 撕s 垃c a lh 偷姗撕o ng 矗d - 1 赡s c dm e l l l o d ) 是一种基于网格的多分辨率聚类技 术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形 单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关 于每个网格单元属性的统计信息( 例如平均值、最大值和最小值) 被预先计算和存储。 这些统计信息用于回答查询。 s t 玳g 有几个优点：( i ) 由于存储在每个单元中的统计信息提供了单元中的数据不 依赖于查询的汇总信息，所以基于网格的计算是独立于查询的；( i i ) 网格结构有利于并 行处理和增量更新；( i i i ) 该方法的主要优点是效率很高：s n g 扫描数据库一次来计 算单元的统计信息，因此产生聚类的时间复杂度是0 ( n ) ，其中n 是对象的数目。在层次 结构建立后，查询处理时间是。国，这里g 是最低层网格单元的数目，通常远远小于n 。 该算法的缺点：由于s 1 1 n g 采用了一个多分辨率的方法进行聚类分析，s t 烈g 聚类的质 量取决于网格结构的最低层的粒度。如果粒度比较细，处理的代价会显著增加：但是， 如果网格结构最低层的力度太粗，将会降低聚类分析的质量；而且，s t 玳g 在构建一个 父亲单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的形状是i s c 吐l 舐c ， 即所有的聚类边界或者是水平的，或者是竖直的，没有对角的边界。尽管该技术有快速 的处理速度，但可能降低簇的质量和精确性。 w 删啷暗算法 w 踟c c l l l s t a u s t 谢n g 诵t l lw a v e l e t s ) 采用小波变换聚类，它是一种多分辨率的聚类 算法，它首先通过在数据空间上加一个多维网格结构来汇总数据，然后采用一种小波变 换来变换原特征空间，在变换后的空间中找到密集区域。 w 踟搬e r 的计算复杂度是o i ( n ) ，能有效地处理大数据集合；发现任意形状的簇； 成功地处理孤立点；对于输入的顺序不敏感；不要求指定诸如结果簇的数目或邻域的半 径等输入参数；在实验分析中，w a v e a u s t 盯在效率和聚类质量上优于b 瓜c h ，c ia ra n s 和d b s c a n ；实验分析也发现w 鲫e c h l s t c r 能够处理多达2 0