（计算机软件与理论专业论文）区域交通状态聚类分析.pdf

区域交通状态聚类分析 论文题目： 专业： 硕士生： 指导教师： 区域交通状态聚类分析 计算机软件与理论 范先立 印鉴教授 摘要 本文围绕着“区域交通状态聚类分析”，探讨了聚类分析在高速公路交通时 空聚类上的应用。针对经典的共享型最近邻居s n n 聚类算法在“去噪”、孤立点 和代表点的判断、聚类效果等方面的不足之处，提出了改进方案，并给出了一种 改进的多维共享型最近邻居d s n n 聚类算法。经过采用美国高速公路交通时空 监测数据集进行实验，结果表明，d s n n 算法比s n n 算法在多维时空数据集上 具有更好的聚类效果。 关键词：时空聚类，共享型最近邻居，孤立点，s n n 图 区域交通状态聚类分析 t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： r e g i o nt r a f f i cs t a t ec l u s t e r i n ga n a l y s i s c o m p u t e rs o f t w a r ea n dt h e o r y f a nx i a n l i y i l lj i a n a b s t r a c t i nt h i sp a p e r , w i t ht h ec o r ec o n t e n to fr e g i o nt r a f f i cs t a t ec l u s t e r i n ga n a l y s i s ，w e d i s c u s st h ea p p l i c a t i o no fc l u s t e r i n ga n a l y s i so nf r e e w a yt r a f f i cs p a t i o t e m p o r a l c l u s t e r i n g c o n s i d e r i n gt h a tt h e r e a r es h o r t c o m i n g si nt h ec l a s s i c a ls h a r e dn e a r e s t n e i g h b o rc l u s t e r i n ga l g o r i t h m ( s n n ) ，i n c l u d i n gd e l e t i o nf o ro u t l i e r s 、j u d g m e m0 1 1 c o r ep o i n t s 、c l u s t e r i n gp e r f o r m a n c e ，w ep r o v i d er e f i n e m e n ts o l u t i o n s ，a n de v e n t u a l l y b r i n g f o r w a r dt h er e f i n e d h i g hd i m e n s i o n a l s h a r e dn e a r e s t n e i g h b o rc l u s t e r i n g a l g o r i t h m ( d s n n ) a f t e rf i n i s h i n g c o r r e l a t i v e e x p e r i m e n t sw i t ht h ep r a c t i c a l a m e r i c a nf r e e w a yt r a f f i cs p a t i o t e m p o r a ld a t as e t ，w ed r a wac o n c l u s i o nt h a td s n n a k o r i t h mh a sb e t t e rc l u s t e r i n gp e r f o r m a n c eo nm u l t i - d i m e n s i o n a ls p a t i o - t e m p o r a l d a t a s e tt h a ns n na l g o r i t h m k e yw o r d s ：s p a t i o t e m p o r a lc l u s t e r i n g 、s h a r e dn e a r e s tn e i g h b o r 、o u t l i e r 、s n ng r a p h 区域交通状态聚类分析 引言 在过去的数十年中，人们收集数据的能力有了迅速的提高。起作用的因素包 括条码在大部分商业产品中的广泛使用，商务、科学和行政事务的计算机化，以 及由文本和图像扫描平台到卫星遥感系统的数据收集工具的进步。此外，互联网 的流行聚集了海量的数据信息。存储数据的爆炸性增长已激起对新技术和自动工 具的需求，以便帮助人们对海量数据转换为信息和知识。 作为当前计算机科学领域的热门分支，数据挖掘是对海量数据库进行分析， 目的是发现未知的关系和以数据拥有者可理解并对其有价值的新颖方式来总结 数据。聚类分析则主要研究如何将初始数据集进行归类，使得类内相似度和类间 相异度都尽可能高。 聚类分折源于许多研究领域，如数据挖掘、统计学、生物学、以及机器学习 等。在数据挖掘领域，研究工作主要集中在聚类方法的可伸缩性，对复杂形状和 类型的数据聚类有效性，高维数据聚类分析技术，以及针对大型数据库中混合数 值和分类数据的聚类方法等多方面。不同的应用有各自特殊的要求，如可伸缩性、 用于决定输入参数的领域知识最小化、处理噪声数据的能力、对于输入记录的顺 序不敏感、高维性、可解释性和可用性等问题之上。 本文探讨了聚类分析在高速公路交通时空聚类上的应用，详细研究了经典的 共享型最近邻居聚类算法s n n ，并阐述了时空数据类型和高维性特征。针对s n n 算法中的不足之处，提出了改进方案，最终给出了改进的多维共享型最近邻居聚 类算法d s n n 。实验结果表明，d s n n 算法比s n n 算法在多维时空数据集上具 有更好的聚类效果。 区域交通状态聚类分析的核心研究内容主要包括聚类算法的比较研究与改 进、聚类效果评价研究、聚类结果可视化研究。它的研究意义在于：经过对交通 状态历史记录数据进行时空聚类分析，从而把握交通状态的时空规律，为相关交 通管理部门、交通管理员等提供指导，帮助完成后期的交通状态趋势分析和交通 问题排解的解决方案；同时，应用全球定位系统，将区域交通状态信息和相关指 导信息传输给个人数字助理p d a 应用系统，为驾车者提供帮助。 本文共四章，各章主要内容如下： 第一章介绍数据挖掘，包括数据挖掘的产生、应用与当前研究现状，并 着重介绍时空数据挖掘、空间数据立方体和空间o l a p 。 第二章 第三章 第四章 介绍聚类分析，包括聚类分析的数据类型、以及目前主要聚类方 法及其分类。 首先介绍了区域交通状态聚类分析目前国内外的研究现状和所存 在的问题，然后介绍了有关概念，包括时空源数据类型及相关结 构、时空数据高维性特征、数据样本间的相关度量、孤立点，最 后介绍了经典的共享型最近邻居聚类算法s n n 。 针对s n n 聚类算法中存在的不足之处，提出改进方案，并给出一 个改进的多维共享型最近邻居聚类算法d s n n 。实验表明，d s n n 算法比s n n 算法在多维时空数据集上具有更好的聚类效果。 区域交通状态聚类分析 第1 章数据挖掘概述 1 1 数据挖掘背景 随着信息时代的发展，人们收集数据的能力有了迅速的提高，越来越多的 人加入到数字世界中，利用计算机提供的各种工具来获得他们所感兴趣的信息。 条形码在大部分商业产品中的广泛使用，许多商务、科学和行政事务的计算机 化，以及由文本和图像扫描平台到卫星遥感系统的数据收集工具的进步，再加 上作为全球信息系统的万维网的流行，w e b 数据的急剧膨胀，已经将我们淹没在 数据和信息的汪洋大海中。数据的丰富带来了对强有力的数据分析工具的需求， 传统的数据库查询手段已经很难满足人们的需要，大量的数据被描述为“数据 丰富，但信息贫乏”。快速增长的海量数据收集、存放在大型和大量的数据库中， 却由于缺乏将这些数据转换成有价值的信息和知识的新技术和自动化工具，使 得收集在大型数据库中的数据变成了“数据坟墓”难得再访问的数据档案。 人们迫切需要一种能够对庞大的数据进行更高层次处理的技术，从中找出规律 和模式，以帮助人们更好地利用数据进行决策管理和研究，而数据挖掘技7 除一 从大量数据中用非平凡的方法发现有用的知识的出现，引起了人们广泛的 关注，导致了数据挖掘研究的蓬勃发展。 数据挖掘通常又称为数据中的知识发现，就是从存储在大型数据库、数据仓 库或其他信息存储容器中的大量的、不完全的、有噪声的、模糊的、随机的数据 里提取人们感兴趣的知识，这些知识是隐含的、事先未知的、对决策有潜在价值 的有用信息 1 ，2 。还有很多近似的术语，如从数据库中发现知识( k d d ) 、数据 分析、数据融合( d a t af u s i o n ) 以及决策支持等。人们把原始数据看作是形成知 识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系型数据库 中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络 上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演 绎的，也可以是归纳的。知识用概念、规则、模式、规律等方式来表示。发现了 的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数 据自身的维护。 数据库中的知识发现是一个多步骤的处理过程，一般分为： ( 1 ) 问题定义：了解相关领域的有关情况，熟悉背景知识，弄清用户要求。 ( 2 ) 数据提取：根据要求从数据库中提取相关的数据。 ( 3 ) 数据预处理：主要对前一阶段产生的数据进行加工，检查数据的完整 性及数据的一致性，对其中的噪音数据进行处理，对丢失的数据进行填补。 ( 4 ) 数据挖掘：运用选定的知识发现算法，从数据中提取出用户所需要的 知识，这些知识可以用一种特定的方式表示或使用一些常用的表示方式。 ( 5 ) 知识评估：将发现的知识以用户能了解的方式呈现，根据需要对知识 发现过程中的某些处理阶段进行优化，直到满足要求。 由此可见，数据挖掘只是数据库中知识发现的一个步骤，但又是最重要的一 步。因此。往往可以不加区别地使用k d d 和数据挖掘。一般在研究领域被称作 数据库中知识发现的，在工程领域则称之为数据挖掘。 数据挖掘是一门广义的交叉学科，涉及多学科技术的集成，包括数据库技术、 区域交通状态聚类分析 人工智髓、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、 信息检索、知识库系统、图像与信号处理和空问数据分析。机器学习和数据分析 的理论及实践是数据挖掘研究的基础，极大的商业应用前景又是数据挖掘研究工 作的巨大推动力。传统的数据库查询和统计、报表的处理方式都是对指定的数据 进行简单的数字处理，而不能对这些数据所包含的内在信息进行提取，因此只能 够提供用户想要的信息，而数据挖掘技术则可以发现用户没有意识到的未知的有 价值信息。作为一种在海量数据中发现知识的手段，与传统的数据分析( 如查询、 报表、联机应用分析o l a p 等) 的本质区别在于数据挖掘是在没有明确假设的前 提下去挖掘信息、发现知识的，它可以从大型的数据库或数据仓库中提出隐藏的 预测性信息，从浩如烟海的企业信息资料库中挖掘出更有价值的信息，具有广泛 的应用前景。 数据挖掘所能发现的知识有如下几种：广义型知识，反映同类事物共同性 质的知识；特征型知识，反映事物各方面的特征知识；差异型知识，反映不同 事物之间属性差别的知识；关联型知识，反映事物之间依赖或关联的知识；预 测型知识，根据历史的和当前的数据推测未来数据；偏离型知识，揭示事物偏 离常规的异常现象。所有这些知识都可以在不同的概念层次上被发现，随着概 念树的提升，从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。 例如，从一家超市的数据仓库中，可以发现的一条典型关联规则可能是“买面 包和黄油的顾客十有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用 卡”，这种规则对于商家开发和实施客户化的销售计划和策略是非常有用的。 数据挖掘所得到的知识应具有先前未知、有效和可实用三个特征。先前未 知是指该知识是预先未曾预料到的，即数据挖掘是要发现那些不能靠直觉发现 的信息或知识，甚至是违背直觉的信息或知识，挖掘得到的知识越是出乎意料， 就可能越有价值。知识的有效性要求挖掘前要对被挖掘的数据进行仔细检查， 保证它们的有效性，才能保证挖掘所得知识的有效性。最为重要的是要求所得 的知识有可实用性，即这些信息或知识对于所讨论的业务或研究领域是有效的， 是有实用价值和可实现的。常识性的结论，早已被人们或竞争对手掌握的或无 法实现的事实都是没有意义的。 数据挖掘起源于2 0 世纪8 0 年代后期，是信息技术自然演化的结果，9 0 年代 有了突飞猛进的发展。自从1 9 9 5 年第一届知识发现和数据挖掘国际会议在加拿 大召开以来，数据挖掘技术已成为机器学习、数据库系统、人工智能等领域内 热门的研究方向。随后，i e e e 、a c m 、a a a i 等国际权威机构纷纷组织专题会议， 共同讨论有关数据挖掘方面出现的问题和所取得的成果。 1 2 数据挖掘的应用与发展 1 2 1 数据挖掘的方法 近年来，数据挖掘技术引起了信息产业界的极大关注，其主要原因是存在大 量数据可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取 的信息和知识可以广泛用于各种应用，包括商务管理、生产控制、市场分析、工 程设计和科学探索等。而用于发现知识的数据挖掘分析方法包括 1 ，2 ： ( 1 ) 分类( c l a s s i f i c a t i o n ) 区域交通状态聚类分析 分类反映同类事物共同性质的特征型知识以及不同事物之间的差异型 特征知识。它是这样的一个过程，首先找出描述并区分数据类或概念的模型 ( 或函数) ，再使用模型预测类，标记未知的对象类。模型类的个数是确定 的，预先定义好的。一个典型的应用就是银行将信用卡申请者分类为低、中、 高风险来标志申请者的可信度，再根据可信度来给予申请者不同的优惠。 ( 2 ) 估值( e s t i m a t i o n ) 估值与分类类似，不同之处在于，分类描述的是离散型变量的输出，而 估值处理连续值的输出；分类的类别是确定数目的，估值的量是不确定的。 一般来说，估值可以作为分类的前一步工作。给定一些输入数据，通过估值， 得到未知的连续变量的值，然后，根据预先设定的阈值，进行分类。例如： 银行对家庭贷款业务，运用估值，给各个客户记分。然后，根据阈值，将贷 款级别分类。 ( 3 ) 演变分析( e v o l u t i o na n a l y s i s ) 数据演变分析也可以认为是以时间为关键属性的关联知识。是根据时间 序列型数据，描述行为随时间变化的对象的规律或趋势，然后对其建模，并 由历史的和当前的数据去推测未来的数据。分析过程可能包含时间相关数据 的特征化、区分、关联、分类和聚类，这类分析的不同特点包括时间序列数 据分析、序列或周期模式匹配和基于类似性的数据分析。演变分析在医疗上 有很强的应用前景，例如通过分析患者以往的医疗数据，可以根据患者的实 际情况( 如经济水平、既往病史、具体病情) ，使用演变分析来提前预测病 人手术后的康复进度，合理安排康复计划、用药计划等。 ( 4 ) 相关性分组或关联规则( a f f i n i t yg r o u p i n go ra s s o c i a t i o nr u l e s ) 关联规则是当前数据挖掘研究的主要领域之一，主要作用是确定数据集 中不同领域或属性间的联系，找出可信的、有价值的多个域之间的依赖关系。 这些规则可以找出顾客购买行为模式，如在销售食品柜台发现，在购买牛奶 的客户中，有8 0 的人同时也购买了面包和饼干，用规则：牛奶一面包+ 饼 干表示。发现这样的规则可以设计方便顾客购物的商品货架、指导商家进货， 对于确定市场策略是很有价值的。关联规则还可以应用到附加邮递、仓储规 划以及基于购买模式对用户进行分类等方面。 ( 5 ) 聚类分析( c l u s t e r i n g ) 与分类和预测不同，聚类是对记录分组，把相似的记录集中在一个聚类 里，聚类分析数据对象，而不考虑已知的类标记。聚集和分类的区别主要在 于聚集不依赖于预先定义好的类，不需要训练集。聚类分析通常作为数据挖 掘的第一步。例如，“哪一种类的促销对客户响应最好? ”，对于这一类问题， 首先对整个客户做聚类，将客户分组在各自的聚类里，然后对每个不同的聚 类回答问题，可能效果更好。 ( 6 ) 概念描述( c o n c e p td e s c r i p t i o n ) 概念一般是指数据的汇集。而概念描述是指机器自动由现有数据获得需 要描述的概念的定义，即根据数据的微观特性发现其表征的、带有普遍性的、 较高层次概念的、中观和宏观的知识，反映同类事物共同性质，是对数据的 概括、精炼和抽象。例如，对某一个病症，给出一些确诊病人的例子，计算 机自动归纳该病症患者的特征，然后得到一个关于患此类新病症的病人的一 个通用的描述。 区域交通状态聚类分析 1 2 2 数据挖掘的研究现状 数据挖掘技术从一开始就是面向应用的。它不仅仅是面向特定数据库的简单 的检索查询或者调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、 综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用己 有的数据对未来的活动进行预测。例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提出新 的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。美国加州 理工学院喷气推进实验室与天文学家合作开发的s k i c a t 系统通过对几百万个 天体进行分类，已帮助天文学家发现了1 6 个新的类星体。美国n b a 篮球队的 教练，利用某公司提供的数据挖掘技术，临场决定替换队员，一度在数据库界被 传为佳话。最近，还有不少d m k d 产品用来筛选i n t e r n e t 上的新闻，保护用户 不受无聊电子邮件的干扰和商业推销，受到极大的欢迎。这样一来，就把人们对 数据的应用，从低层次的末端查询操作，提高到为各级经营决策者提供决策支持。 这种需求驱动力，比数据库查询更为强大。同时需要指出的是，这里所说的知识 发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定 理和纯数学公式，更不是什么机器定理证明。所有发现的知识都是相对的，是有 特定前提和约束条件、面向特定领域的，同时还要能够易于被用户理解，最好能 用自然语言表达发现结果。 目前，国外数据挖掘的发展趋势主要有：对知识发现方法的研究进一步发展， 如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高；传统的 统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合等。在应用方面包括： k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤 立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。国外很多 计算机公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应的研究中 心进行这方面的工作。很多大公司也对数据挖掘应用的研究投入大量精力，经过 十多年的努力，关于数据挖掘技术应用的研究也取得了丰硕的成果。一些公司已 经开发了多种数据挖掘相关的产品，据不完全统计，目前已经有了数百个数据挖 掘软件产品。如i b m 公司开发的q u e s t 和i n t e l l i o p t tm i n e r ；a n g o s ss o t ! t w a r e 开发的基于规则和决策树的k n o w l e d g es e e k e r ：a d v a n c e ds o f t w a r ea p p l i c a t i o n 开 发的基于人工神经网络的d bp r o f i l e ；加拿大s i m o nf r a s e r 大学开发的d bm i n e r ； s g i 公司开发的m i n es e t 等。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉 及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关 数据挖掘理论方面的研究，大量的文章已经在各级期刊，各种会议发表，应用数 据挖掘技术开发的产品日渐增多，已经有不少含数据挖掘功能的产品问世，如用 于对股票行情进行分析预测的指南针、神光、r m r 等智能股票分析系统。目前 进行的大多数研究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计划、 “九五”计划等。 一份最近的g a r t n e r 报告中列举了在今后3 5 年内对工业将产生重要影响的 五项关键技术，其中k d d 和人工智能排名第一。同时，这份报告将并行计算机 体系结构研究和k d d 列入今后5 年内公司应该投资的1 0 个新技术领域。可以 看出，数据挖掘的研究和应用受到了学术界和实业界越来越多的重视，预计在 2 1 世纪还会形成更大的高潮，研究焦点可能会集中到以下几个方面：研究专门 用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准化； 区域交通状态聚类分析 寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户理解，也便 于在知识发现过程中的人机交互；研究在网络环境下的数据挖掘技术，特别是在 i n t e r n e t 上建立d m k d 服务器，与数据库服务器配合，实现数据挖掘；加强对各 种非结构化数据的挖掘，如文本数据、图形图像数据、多媒体数据。但是无论怎 样，需求牵引与市场驱动是永恒的，d m k d 将首先满足信息时代用户的急需， 大量基于d m k d 的决策支持软件工具产品将会问世。 1 3 时空数据挖掘 数据挖掘主要完成从海量数据中提取潜在的、有价值的、有趣的信息。但当 大量的原始数据保存着交通数据库、地理信息系统、全球气候系统等相关信息时， 传统的经典数据挖掘工具似乎就显得力不从心了。由于这些数据中时空白相关等 问题的存在，从时空数据集中获取有趣并且有用的模式比起从传统的数字型数据 中获取模式要难得多f 3 , 4 1 。 空间数据挖掘的主要目的就是进行部分“自动化”知识发现等，并搜索海量 空间数据中所具有的知识精华。对于那些占有、产生、管理海量时空数据集的组 织而言，能用高效工具从空间数据集中挖掘信息是非常重要的。当前用于解决空 间数据挖掘问题的方案，不外乎就是在实现了不同数据点的空间关系，并假定样 本点的独立性之后，再采用经典的数据挖掘工具来进行挖掘处理。然而，因为空 间自相关的存在，经典的数据挖掘方案通常都不能高效地执行空间数据挖掘。 空间自相关是空间数据样本所固有的属性，它是指空间相关的数据样本影响 了处于邻近区域内的其他样本。这个属性也决定了时空数据集的“第一原则”： 每个数据样本都影响着其他数据样本，但越是邻近的样本对其参考样本的影响就 越大。 显然，忽略了空间自相关性的知识发现技术都不能有效完成空间数据挖掘。 另一方面，空间统计虽然直接考虑了空间自相关性，但是结果建模有着过高的计 算复杂度，并且是通过复杂的数字解算器或基于马尔可夫链蒙特卡洛方案 m c m c 的取样来解决的。 目前，一种流行的做法就是，先通过特征选择，将这些数据中的时空成分转 换为非时空成分，再采用经典的数据挖掘技术处理。而还有一种方法就是，直接 针对时空数据和它们内在的独特性质，探索出薪模型、新目标函数、新模式。 空间数据库存储了大量与空间有关的数据，例如地图，预处理后的遥感或医 学图像数据，以及v l s i 芯片设计数据等。空间数据库有许多与关系数据库所不 同的显著特征。空间数据库包含了拓扑和或距离信息，通常按复杂的、多维的 空间索引结构组织数据，其访问是通过空间数据的访问方法，经常需要空间推理、 地理计算和空问知识表示技术。 空间数据挖掘是指对空间数据库中非显式存在的知识、空间关系或其他有意 义的模式等的提取【3 ，5 ，6 】。空间数据挖掘需要综合数据挖掘与空间数据库技术。 它可用于对空间数据的理解，空间关系和空间与非空间数据间关系的发现，空间 知识库的构造，空间数据库的重组和空间查询的优化。空间数据挖掘在地理信息 系统( g i s ) 、地理市场( g e o m a r k e t i n g ) 、遥感、图像数据库探测、医学图像处 理、导航、交通控制、环境研究以及许多使用空间数据的领域中有广泛的应用。 由于空间数据的海量数据和空间数据类型和空间访问方法的复杂性，空间数据挖 区域交通状态聚类分析 掘面临的主要挑战是研究高效的空间数据挖掘技术。 “空间数据挖掘使用统计技术方法如何? ”统计空间数据分析已经是空间 数据分析中常用的方法。统计方法可以很好地处理数字型数据，并可以对空间现 象提出现实的模型。然而它存在的问题也很多，比如统计方法通常假设空间分布 的数据间是统计上独立的，但现实是空间对象间是相互关联的；大部分统计模型 只有具有相当丰富领域知识和统计方面经验的统计专家才用得起来；统计方法不 适用符号值，或不完整或非确定的数据，对大规模数据库其计算代价也十分昂贵。 空间数据挖掘将对传统的空间分析方法加以扩展，重点解决其高效性，可伸缩性， 与数据库系统的结合，改进与用户的交互，以及新知识的发现。 1 3 1 空间数据立方体和空间o l a p 正如w h i n m o n 在”b u i l d i n gt h ed a t aw a r e h o u s e ，t h u de d i t i o n 书中【7 】所 描述的那样，空间数据仓库是面向主题的、集成的、随时间变化的并且是非易失 性的空间和非空间数据的集合，用于支持空间数据挖掘和空间数据有关的决策过 程。 举例说明： 例在大不列颠哥伦比亚省( b c ) 分布着约3 0 0 0 个气象探测器，每一个记 录指定区域的每日气温和降雨量，并将数据传送到省气象站。通过建立空间数据 仓库，可以支持空间o l a p ，用户可以在地图上按月、按地区、按温度和降雨量 的不同组合观察气象变化模式，可以动态地沿任何一维下钻和上卷，发现所希望 的模式。 构造和使用空间数据仓库存在几个挑战性的问题。首先是从异构数据源和系 统中把空间数据集成起来的问题。空间数据通常存储在形形色色的工业企业和政 府机构中，数据格式各异。数据格式不仅与特定的结构有关( 例如基于光栅向 量的空间数据，面向对象模型关系模型，各式各样的空间存储和索引结构，等 等) ，而且与特定厂家有关( 例如e r s i ， m a p l n f o ， i n t e r g r a p h ， 等等) 。有关 异构空间数据的集成与交换已有很多的研究工作，这为空间数据集成和空间仓库 构造铺平了道路。 第二个问题是如何在空间数据仓库中实现快速而灵活的联机分析处理。其 中，星型模式很适合空间数据仓库，因为它提供了简洁而有组织的仓库结构，便 于o l a p 操作。但在空间数据仓库中，维和度量都包含空间成分。 在空间数据立方体中有三种类型的维【1 1 ： 非空间维只包含非空间数据。如上例可构造数据仓库的非空间维温度和降 雨量，因为他们每一个只包含非空间数据，其概化也是非空间的( 如气温的“热”， 降雨量的“湿”) 。 空间一非空间维是指初始数据是空间数据，但其概化值在一定的抽象级别 则变成非空间的。例如，空间维c i t y 取自美国地图的地理数据。假设此维比如在 西雅图的空间值，概化为字符串“p a c i f i c西北太平洋)”。虽然_northwest( “p a c i f i c _ n o r t h w e s t ”是一个空间概念，但不是一个空间值( 因为在此例中，它 为一个字符串) 。因此它是一个非空间维。 空间一空间维是指无论初始数据还是所有高级别的概他数据都是空闯维 的。例如，e q u it e m p e r a t u r e _ r e g i o n 维包含空间数据，对其所有概化，如 0 5 _ d e g r e e s ( 摄氏1 ，5 1 0 _ d e g r e e s 等的地区，也是空间数据组成。 空间数据立方体中有两类不同的度量。 区域交通状态聚类分析 数字度量仅包含数字数据。例如，空间数据仓库中的一个度量可以为某地 区的月收入，通过上卷可计算出按年，按县等的收入。数字度量可进一步划分为 分布的、代数的和整体的。 空间度量包含一组指向空间对象的指针。例如，上例中的空间数据立方体 中的概化( 或上卷) 中，具有相同温度和降雨量的地区被组合为同一个单元，所 形成的度量包含了指向这一地区的一组指针。 非空间立方体仅包含非空间维和数字化的度量。若一个空间数据立方体包含 空间维但不含空间度量，其o l a p 操作，如下钻或转轴( p i v o t i n g ) ，可以以非空 间数据立方体的方式实现。 在空间数据立方体的构造中至少有三种可供选择的空间度量的计算方法。 在空间数据立方体中收集与存储有关的空间对象指针，但不执行空间度量的 预计算。其实现方法可以是在有关的立方体单元中存储一个指向空问对象指针集 合的指针，必要时可随时执行有关空间对象的空间合并( 或其他计算) 。这一方 法在如下的情况下不失为好的选择：当仅需要空间结果显示( 即无需真的空间合 并) ，或者在任一指针集合中没有太多可以合并的地区，或者联机空间合并计算 速度很快。由于o l a p 的结果经常用于联机空间分析和挖掘，因此一般还是主 张将一些空间上邻接的地区预先合并，这样可以加速此类的分析。 在空间数据立方体中预先计算并存储一个粗略近似的空间度量结果。在假定 所需存储空间有限的情况下，若只需要对空间合并结果的粗略浏览或大致估算， 此方法不失为好的选择。例如，最小边界矩形( m b r ) ，可由两个点表示，它可 以作为合并地区的粗略估算。这类预计算的结果较小，并可快速展示给用户。若 对特定单元需要更高的精度，应用可以选择预计算质量较高的结果，或随时加以 计算。 在空间数据立方体中有选择地预先计算一些空间度量。这是一个较为灵活的 选择，它可以在方体( c u b o i d ) 级进行，即是说或者对选择的方体的每一个单元 预计算并存储每一个可合并的空间地区，或者方体没被选择，则不做任何预计算。 通常方体由很多空间对象组成，因此它可能涉及很多可合并空间对象的预计算和 存储，不过这其中有些可能很少用到。因此选择要在较细粒度的级别上进行：检 查方体中的每一组可合并的空间对象，判定是否需要预计算。这里判定需要考虑 的因素包括合并区域的实用性、可共享性以及空间和联机计算时间代价的权衡。 区域交通状态聚类分析 第2 章聚类分析概述 2 1 聚类分析简介 什么是聚类分析? 将物理或抽象对象的集合分组成为由类似的对象组成的 多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象 与同一个簇中的对象彼此相似，与其他簇中的对象相异。在许多应用中，可以将 一个簇中的数据对象作为一个整体来对待。 聚类分析是一种重要的人类行为。早在孩提时代，一个人就通过不断地改进 下意识中的聚类模式来学会如何区分猫和狗，或者动物和植物。聚类分析已经广 泛地用于许多应用中，包括模式识别、数据分析、图像处理、以及市场研究。通 过聚类，人能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据 属性之间的有趣的相互关系。 “聚类的典型应用是什么? ”在商务上，聚类能够帮助市场分析人员从客户 基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生 物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固 有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的 分组，及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发 挥作用。聚类也能用于对w e b 上的文档进行分类，以发现信息。作为一个数据 挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每个 簇的特点，集中对特定的某些簇做进一步的分析。此外，聚类分析可以作为其他 算法( 如特征和分类等) 的预处理步骤，这些算法再在生成的簇上进行处理。 数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘、统计学、机器学 习、空间数据库技术、生物学、以及市场营销。由于数据库中收集了大量的数据， 聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。 作为统计学的一个分支，聚类分析已经被广泛地研究了许多年，主要集中在 基于距离的聚类分析。基于k - m e a n s ( k 平均值) 、k - m e d o i d s ( k 中心点) 和其他一些 方法的聚类分析工具已经被加入到许多统计分析软件包或系统中，例如s p l u s ， s p s s ，以及s a s 。在机器学习领域，聚类是无指导学习( u n s u p e r v i s e dl e a r n i n g ) 的一个例子。与分类不同，聚类和无指导学习不依赖预先定义的类和带类标号的 训练实例。由于这个原因，聚类是观察式学习，而不是示例式学习。在概念聚类 ( c o n c e p t u a lc l u s t e r i n g ) 中，一组对象只有当它们可以被一个概念描述时才形成 一个簇。这不同于基于几何距离来度量相似度的传统聚类。概念聚类由两个部分 组成：( 1 ) 发现合适的簇：( 2 ) 形成对每个簇的描述。在这里，追求较高类内相 似度和较低类间相似度的指导原则仍然适用。 在数据挖掘领域，研究工作已经集中在为大型数据库的有效和实际的聚类分 析寻找适当的方法。活跃的研究主题集中在聚类方法的可伸缩性，方法对聚类复 杂形状和类型的数据的有效性，高维聚类分析技术，以及针对大型数据库中混合 数值和分类数据的聚类方法。 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的要求。 数据挖掘对聚类的典型要求有：可伸缩性、处理不同类型属性的能力、发现任意 形状的聚类、用于决定输入参数的领域知识最小化、处理噪声数据的能力、对于 区域交通状态聚类分析 输入记录的顺序不敏感、高维性( h i g hd i m e n s i o n a l i t y ) 、基于约束的聚类、可解 释性和可用性。 2 2 聚类分析的数据类型 假定初始数据集合包含1 1 个数据对象，这些数据对象可能表示人、房子、文 档、国家等。许多基于内存的聚类算法选择如下两种有代表性的数据结构【1 】： 数据矩阵( d a t am a t r i x ，或称为对象与变量结构) ：它用p 个变量( 也称 为度量或属性) 来表现1 1 个对象，例如用年龄、身高、体重、性别、种族 等属性来表现对象“人”。这种数据结构是关系表的形式，或者看成n p ( n 个对象p 个变量) 的矩阵。 x 1 1 崩1 j 砸1 相异度矩阵( d i s s i m i l a r i t y m a t r i x ，或称为对象一对象结构) ：存储n 个对 象两两之间的近似性，表现形式是一个n n 维的矩阵。 o d ( 2 a ) 0 d ( 3 ，1 ) d ( 3 ，2 ) 0 d ( n 山d ，2 ) 0 在这里d ( tj ) 是对象i 和对象j 之间相异性的量化表示，通常它是一个非负的 数值，当对象i 和 越相似或“接近”，其值越接近0 ：两个对象越不同，其值越 大。既然d ( i ，j ) = d o ，i ) ，而且d ( li ) = 0 ，我们可以得到上述的矩阵。 数据矩阵经常被称为二模( t w o - m o d e ) 矩阵，而相异度矩阵被称为单模 ( o n e m o d e ) 矩阵。这是因为前者的行和列代表不同的实体，而后者的行和列代 表相同的实体。许多聚类算法以相异度矩阵为基础。如果数据是用数据矩阵的形 式表现的，在使用该类算法之前要将其转化为相异度矩阵。 2 3 主要聚类方法的分类 目前存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的和应 用。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法， 以发现数据可能揭示的结果。应用领域的多变性决定了聚类算法的多样性，但算 法的目的只有一个：将初始样本自然地聚集成簇。 大体上，主要的聚类算法可以划分为如下几类 1 ： p p p脚；砌脚 ， r 旷聊；珂；研 区域交通状态聚类分析 2 3 1 划分方法 给定一个n 个对象或元组的数据库，一个划分方法构建数据的k 个划分，每 个划分表示一个聚簇，并且k n 。也就是说，它将数据划分为k 个组，同时满 足如下的要求：( i ) 每个组至少包含一个对象；( i i ) 每个对象必须属于且只属 于一个组。注意在某些模糊划分技术中第二个要求可以放宽。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用一 种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的 一般准则是：在同一个类中的对象之间尽可能“接近”或相关，而不同类中的对 象之间尽可能“远离”或不同。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际上， 绝大多数应用采用了以下两个比较流行的启发式方法： ( i ) k 一平均算法。处理流程如下：首先，随机地选择k 个对象，每个对象 初始地代表了一个簇的平均值或中心。对剩余的每个对象，根据其与各个簇中心 的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重新， 直到准则函数收敛。通常采用平方误差准则，其定义如下： e = 二腻卜m ：1 2 公式( 2 1 ) 这里的e 是数据库中所有对象的平方误差的总和，p 是空间中的点，表示给 定的数据对象，m i 是簇c 。的平均值。这个准则试图使生成的结果簇尽可能地紧凑 和独立。 算法如下： 算法：k 一平均。划分的k _ 平均算法基于簇中对象的平均值。 输入：簇的数目k 和包含n 个对象的数据库。 输出：k 个簇，使平方误差准则最小。 方法： 1 ) 任意选择k 个对象作为初始的簇中心； 2 ) r e p e a t 3 ) 根据簇中对象的平均值，将每个对象( 重新) 赋给最类似的簇； 4 ) 更新簇的平均值，即计算每个簇中对象的平均值； 5 ) u n t i l 不再发生变化 图2 1k 一平均算法 但是，k 一平均方法只有在簇的平均值被定义地情况下才能使用。这可能不使 用于某些应用，例如涉及有分类属性地数据。要求用户必须事先给出k 可以认为 是该方法的一个缺点。k 一平均方法不适用于发现非凸面形状的簇，或者大小差别 很大的簇。而且，它对于“噪声”和孤立点数据是敏感的，少量的该类数据能够 对平均值产生极大的影响。 k 一平均方法有很多变种。它们可能在初始k 个平均值的选择、相异度的计算 和计算聚类平均值的策略上有所不同。经常会产生较好的聚类结果的一个有趣策 略是首先采用层次的凝聚算法决定结果簇的数目，并找到一个初始的聚类，然后 用迭代重定位来改进聚类结果。 k 一平均方法的一个交体是k 一模方法，它扩展了k 一平均方法，用模来代替类 的平均值，采用新的相异性度量方法来处理分类对象，采用基于频率的方法来修 改聚类的模。k 一平均和k 一模方法可以综合起来处理有数值类型和分类类型属性 的数据，这就是k _ 原型方法。 区域交通状态聚类分析 如果一个对象与某个簇的隶属关系是确定的，则它是可废弃的。如果一个对 象不是可废弃的，但属于某个紧密的子簇，那么它是可压缩的。用一种数据结果 聚类特征( c l u s t e r i n gf e a t u r e ) 来汇总那些可废弃的或者可压缩的对象。 如果一个对象既不是可废弃的，又不是可压缩的，那它就应该被保存在主存中。 为了达到可扩展性，这个迭代的算法只包含可压缩的对象和必须在主存中的对象 的聚类特征，从而将一个基于二级存储的算法变成了基于主存的算法。 ( i i ) k 一中心点算法。不采用簇中对象的平均值作为参照点，可以选用簇中 位置最中心的对象，即中心点。k _ 中心点聚类算法的基本策略是：首先为每个簇 随意选择一个代表对象：剩余的对象根据其与代表对象的距离分配给最近的一个 簇。然后反复地用非代表对象来替代代表对象，以改进聚类质量。 算法如下： 算法：k 一中心点。对基于中心点或者中心对象的划分的典型k 一中心点算法。 输入：结果簇的数目k ，包含n 个对象的数据库。 输出：k 个簇，使得所有对象与其最近中心点的相异度总和最小。 方法： 1 ) 随机选择k 个对象作为初始的中心点： 2 ) r e p e a t 3 ) 指派每个剩余的对象给离它最近的中心点所代表的簇； 4 ) 随机地选择一个非中心点对象0 r 。； 5 ) 计算用o r 。代替0 ，的总代价s ； 6 ) i fs o ，t h e no r 。替换0 ，形成新的k 个中心点的集合； 7 ) u n t i l 不发生变化 图2 2k 一中心点算法 p a m ( p a r t i t i o n i n ga r o u n dm e d o i d ，围绕中心点地划分) 是最早提出的k 一 中心点算法之一。它试图对n 个对象给出k 个划分。最初随机选择k 个中心点后， 该算法反复地试图找出更好的中心点。所有可能的对象对被分析，每个对中的一 个对象被看作是中心点，而另一个不是。对可能的各种组合，估算聚类结果的质 量。一个对象o j 被可以产生最大平方一误差值减少的对象代替。在一次迭代中产 生的最佳对象的集合成为下次迭代的中心点。 这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用，但对大的 数据集合就没有良好的可伸缩性。为了对大规模的数据集进行聚类，以及处理复 杂形状的聚类，可以采用一个基于选择的方法c l a r a ( c l u s t e r i n gl a r g e a p p l i c a t i o n s ) 。 c l a r a 的主要思想是：不考虑整个数据集合，选择实际数据的一小部分作为 数据的样本。然后用p a m 方法从样本中选择中心点。如果样本是以非常随机的方 法选取的，它应当足以代表原来的数据集合。从中选出的代表对象( 中心点) 很 可能与从整个