电子政务基础教程 第10章 聚类分析

第10章聚类分析10．1概述聚类分析(clusteranalysis)简称聚类，是将数据对象集依其特征属性按“相似者相容”原则划分为不同的类或簇（clusters）的过程。数据聚类分析是根据数据的内容与性质将其分到不同的类或簇中，使同簇数据对象有较大的相似性，不同簇属对象有较大的相异性。聚类分析的过程是：根据数据对象的多个观测指标，找出一些能够测量对象或变量间相似程度的统计值，以其为分类依据，将一些特征相似程度较大的对象（或指标）聚合为一类，将另一特征些相似程度较大的对象（或指标）聚合为另一类，直至将所有对象（或指标）都聚合完毕，形成一个分类系统。聚类分析在许多领域广泛应用，包括机器学习，数据挖掘，模式识别，图像分析，人工智能，用户体验，客户行为分析等。聚类分析在电子政务领域有重要的应用价值，它能发现与揭示许多非定式、非常规、动态变化和问题。如在服务层面上，它可知道何时、何地、何类公众经常求助于职能机构，要求何种服务，解决何种问题？可按公众与政务系统接触的次数、方式、界面所反映的问题；许多貌似不同的问题间有无关联度？他们的意见反馈、满意度等；均能通过聚类分析识别偶发性问题与经常性问题，提示潜在与隐含问题等。由此可刻画不同需求与行为的社会群体，针对不同服务对象提供更具针对性的政务服务，改善公众体验等等。10.2政务数据聚类分析10.2.1政务领域的聚类分析需求政务领域，聚类分析主要用于大数据分析与决策辅助。在网络环境中，政务外网信息形成数据海洋，内网信息也随社会信息和机构业务的发展而呈指数级数增长，内外网信息叠加后常给各级领导层造成“数据爆炸而信息稀缺”的感觉。迄今，人们提出了许多聚类算法试图解决大数据特征归集问题。聚类分析还应用于模式识别、图像处理、计算机视觉、模糊控制等领域，并取得长足的发展。这些技术都是传统的面向业务的电子政务向新型的面向分析预测与决策支持型的电子政务发展所不可或缺的。10.2.2聚类分析的优点聚类分析有许多优点，对电子政务领域，其主要适用优点如下。帮助用户从海量数据中“淘取”有用的资源信号，将其提升为知识资源。从总体上而不是从孤立信源、单一渠道、孤立消息报导角度上建立供决策分析的知识资源，有助于决策者洞察全局，形成大局观与纵深观。自动识别与跟踪各类事件的起始、发展、走势和各类主题此消彼长或与其他因素汇聚壮大的演化历程。帮助决策者在各类看似孤立的事件间建立关联，消除知识断层。优化政府机构资源供给与发布的信息流。及时发现并统计一些关键性的信号词、主题语等，响应各类宏观资源集聚变化，等等。在当前社会经济、产业与科技迅猛发展的环境中，新事物、新现象、新产品与新业态等层出不穷，传统的刚性政务信息资源分类目录体系已不适应于政务大数据的管理与应用需求。聚类分析的信息挖掘、动态资源解析与个性目录生成等就能较好地适应这一发展需求。10.2.3聚类分析的一般方法从统计学观点，聚类分析是通过数据建模来归集对象的一种方法。传统的统计聚类分析法包括系统聚类或层次聚类（hierarchicalcluster）法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。电子政务中，大量信息是非结构型文本，聚类分析通过跟踪各信息源的文本信息，对经扫描检测出的大量核心或主题词划分成若干组类，再统计其特征系列后进行计算处理。几种主要聚类方法有：划分法、层次法、密度法、网格法与基于模型的方法等1）划分法（partitioningmethods）给定具有n个对象的数据集，采用划分法对数据集进行k个划分，每个划分（每组）代表一个簇k≤n，每个簇至少包含一个对象，且每个对象一般只能属于一个组。对给定的k值，划分法一般要做初始划分，然后采取迭代重新定位技术，通过让对象在不同组间移动来改进划分的准确度和精度。好的划分原则是：同簇中对象间的相似性很高(或距离很近)，异簇对象间的相异度很高(或距离很远)。几种算法如下：（1）K-Means算法

又叫K均值算法，是目前最著名、使用最广泛的聚类算法。在给定一个数据集和需要划分的数目k后，该算法可根据某个距离函数反复将数据划分到k个簇中，直到收敛为止。（2）K-Medoids算法

又称K中心点算法，它用最接近簇中心的一个对象来表示划分的每个簇。其算法与K-Means算法的划分过程相似，最大的区别是K-Medoids算法是用簇中最靠近中心点的一个真实数据对象来代表该簇，而K-Medoids算法用计算出来的簇中对象的平均值来代表该簇，此平均值是虚拟的，并无真实的数据对象。2）层次法

层次法（HierarchicalMethods）的思路是：开始时每个样本（或变量）自成一类，聚类分析按某种方法度量所有样本间的亲疏程度，将最相似的样本先聚成一小类；再度量剩余样本和小类间的亲疏程度，将当前最接近的样本和小类聚成一类；接下来，再度量剩余样本与小类间的亲疏程度，并将这时最接近的样本与小类聚成一类；如此反复，直到所有样本各成其类为止。具体做法可描述为：在给定n个对象的数据集后，用层次方法对数据集进行层次分解，直到满足某种收敛条件为止。按层次分解的形式不同，层次方法又可分为凝聚层次聚类和分裂层次聚类。层次方法的缺点在于，合并或分裂点的选择较困难，对局部来说，好的合并或分裂点的选择往往不能保证会得到高质量的全局聚类结果，且一旦一个步骤（合并或分裂）完成，它就不能被撤销了。其代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。层次法不仅需要度量个体与个体间的距离，还要度量类与类之间的距离。类间距被度量出来后，距离最小的两个小类将首先被合并为一类。由类间距离定义的不同产生了不同的系统聚类法。类间距离的一些度量方法如下：①

最短距离法（NearestNeighbor）：定义类与类之间的距离为两类最近样本的距离。2.最长距离法（FurtherNeighbor）：定义类与类之间的距离为两类最远样本的距离。3.组间平均连接法（Between-grouplinkage）：定义类间距离为两组元素两两之间的平均距离。

4.重心法（Centroidclustering）：又称均值法，定义类间距离为两类重心（各类的均值）的距离，即如图10-6所示，每次得到新的簇后，重新计算重心值。其他还有组内平均连接法（Within-grouplinkage）、中位数法（Medianclustering）、离差平方和法（Ward'smethod）等，均各有优缺点。3）密度法以距离为相似性的描述指标进行聚类，只能发现球状类型的数据，对非球状类型的数据集，只根据距离来描述和判断是不够的，就有了基于密度的方法（Density-BasedMethods），其原理是：只要邻近区域内的密度（对象数量）超过了某个阈值，就继续聚类。换言之，给定某个簇中的每个数据点(数据对象)，在一定范围内必须包含一定数量的其他对象。该算法从数据对象的分布密度出发，把密度足够大的区域连接在一起，因此可以发现任意形状的类。该算法还可以过滤噪声数据(异常值)。

密度法的典型算法包括DBSCAN(Density—BasedSpatialClusteringofApplicationwithNoise)及扩展算法OPTICS(OrderingPointstoIdentifytheClusteringStructure)，DENCLUE算法等。其中，DBSCAN算法会根据一个密度阈值来控制簇的增长，将具有足够高密度的区域划分为类，并可在带有噪声的空间数据库里发现任意形状的聚类。尽管此算法优势明显，但是缺点就是，该算法需要用户确定输入参数，对参数十分敏感。4）网格法即基于网格的方法(Grid-BasedMethods)，是将对象空间量化为有限数目单元（cell），这些单元形成网格结构，聚类操作在此网格结构中进行。此算法的优点是处理速度快，与目标数据库中记录的个数无关，只与把数据空间分为多少个单元有关，即其处理时间常独立于数据对象的数目，只与量化空间中每一维的单元数目有关。网格法有STING算法、CLIQUE算法、WAVE-CLUSTER算法等，典型的是STING(统计信息网格StatisticalInformationGrid)算法。该算法是一种基于网格的多分辨率聚类技术，将空间区域划分为不同分辨率级别的矩形单元，并形成一个层次结构，且高层的低分辨率单元会被划分为多个低一层次的较高分辨率单元。这种算法从最底层的网格开始逐渐向上计算网格内数据的统计信息并储存。网格建完后，则用类似DBSCAN的方法对网格进行聚类。5）基于模型法(model-basedmethods)基于模型法是给每一个聚类假定一个模型，然后寻找能很好地满足该模型的数据集。这样的模型可能是数据点在空间中的密度分布函数或者其他分布，其潜在的假定是：目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向：统计方案和神经网络方案。除以上几种外，其他常用的聚类分析法还有：传递闭包法，布尔矩阵法，直接聚类法，相关性分析聚类，基于统计的聚类方法，等等。10.2.4聚类方法特征

聚类方法具有许多特性，以下特征在电子政务领域具有特殊的应用价值。

（1）简单直观。

特别适用于针对一些事态不清、起因不明、因素众多、现象纷繁、关联纠缠、甚至彼此矛盾的现象进行观察分析，这对于宏观决策、趋势分析、进程跟踪、演化历程研判、原因根究等领域，都能起重要的辅助功能。

（2）可用于探索性研究。

聚类结果可提供多个可能的解，既然有主导性现象与问题，也是分枝型问题、甚至极易被忽略的奇点型问题等，关注点的选择和最终的求解需要研究者的主观判断和后续的跟踪分析。

（3）多态性。

不管实际数据中是否真正存在不同的类别，利用聚类分析都能得到分成若干类别的现象、或可能的求解方向。

（4）主观性影响。

聚类分析的解相当程度取决于研究者所选择的聚类变量，增加或删除一些变量对最终解都可能产生实质性的影响。

（5）结果差异性。

研究者在使用聚类分析时应注意可能影响结果的各个因素。异常值和特殊变量对聚类有较大影响，故当分类变量的测量尺度不一致时，需要事先做标准化处理。10.2.4聚类分析的性能电子政务涉及科技、生产、人文与社会等大量形态各异的复杂问题，聚类分析对此有广阔应用空间。同时，也因政务涉及问题的类型的纷繁复杂，需要聚类分析具有以下性能。

1）可伸缩性：许多聚类算法对小于200个数据对象的小数据集工作得很好，但一个普通的政务数据库就可能包含数以百万计的对象，对这样的数据集合样本进行聚类可能会导致结论偏差。故政务应用往往需要有高度可伸缩性的聚类算法，既能保证聚类质量，又能拓展数据处理量的弹性范围，且具有较好的聚类效果等。2）具有处理不同类型数据的能力许多传统算法被设计用来聚类数值类型的数据，但电子政务领域需要聚类其他类型的数据，如二元类型(binary)，分类/标称类型（categorical/nominal），序数型（ordinal）数据，文字型或这些数据类型的混合。3）发现任意形状的聚类许多聚类算法是基于欧几里得或者曼哈顿距离度量来决定聚类的。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇，但政务领域中的一个簇可能是任意形状的。因此，采用甚至提出能发现任意形状簇的算法就是重要的需求。4）用于决定输入参数的领域知识最小化一些算法在聚类分析中要求用户输入一定的参数，例如希望产生的簇的数目等。但聚类结果对于输入参数十分敏感，且参数有时很难确定，特别是对于包含高维对象的数据集，不仅加重了系统与用户的负担与时间成本，也使得聚类的质量难以控制。5）处理“噪声”数据的能力绝大多数实际数据集都包含了孤立点，缺失，或者错误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。6）对输入顺序敏感的去除一些聚类算法对输入数据的顺序较敏感，例如，同一个数据集合，当以不同的顺序交给同一个算法时，可能生成差别较大的聚类结果。开发对数据输入顺序不敏感的算法对大数据环境下的政务分析具有一定的意义。7）高维度（highdimensionality）一个涉及政务应用的数据库可能包含若干维度或对象属性。许多聚类算法擅长处理低维数据，如只涉及两到三维。人眼在三维情况下能很好地判断聚类的质量，而高维空间中聚类数据常具有挑战性，特别这样的数据可能分布非常稀疏，且高度偏斜，但却能发现通常为人忽视的奇点知识。8）基于约束的聚类政务应用往往要在各种约束条件下进行聚类。假设一座城市的主管机构对如何为城市中给定数目的大型环保设施选择最优的安放位置，为作出合理决策，系统需要对全市住宅区进行聚类，但又要同时考虑城市的河流、公路网、每个区域的功能及住户要求等。要找到既满足特定约束，又具有良好聚类特性的数据分组常是一项有难度的任务。9）可解释性和可用性用户希望聚类分析的结果是可解释的、可理解的和可使用的。即聚类分析要和特定的语义解释和应用相联系，应用目标如何影响聚类方法的选择也是一个重要课题。目前在政务领域广泛采用的知识图谱也是聚类分析结果的可视化呈现，它以直观、动态、多因素、平面与立体形式等将结果形象化展示出来，往往取得较好结果。10.2.5聚类分析形式电子政务聚类分析既需要有信息的空间序列，又需要有时间序列。信息空间聚类用于对资源引擎采集的所有内容进行热点聚类，或某个领域的热点、某个垂直系统、综合部门内部等的热点聚类。在许多民生决策中，热点事件、热点问题通常是直接策动因素。因此，发现并分析热点的成因，跟踪其发展性态，对于科学决策、制订政策、采取措施、化解矛盾于初期、促进社会稳定等具有重要意义。从时间序列上看，许多社会事件、产业与经济现象的萌生、初始、发展、壮大到消亡等都具有完整的生命周期，既符合一般的周期规律，又有其独特点。一些重要事件的发生、演化与消亡过程会在各种公众传媒中反映出来，并通过资源引擎进入政务系统。通过信息聚类，决策者就能根据热点信息的走势研判其发展趋势，在恰当的时间环节上采取恰当的措施。

同时，决策者往往还要对历史上相似事件的处理和应对措施的正确性、适合性等进行回顾与参考，以总结经验教训，使当前的决策更加科学、及时、合理。如各国应对非典、疯牛病、高致病禽流感、多种区域性流感等重大疫情的历程、采取的各种措施等都有相互借鉴性。因此，政府决策时往往要对历史上类似事件发生时段的信息流进行切片、聚类，找出其演化脉络、评估当时的各项应对策略、措施与绩效，以降低当前的决策风险。10.3聚类可视化10.3.1聚类可视化的需求聚类技术多与可视化技术结合。如大型政务系统，数据引擎每天从数以百计的网站中采集上千个频道的动态信息后，各级领导往往都想了解今天的热点有哪些？媒体集聚的事件是什么？各大网站热论的议题何在？梳理后的信息如不以直观形象化方式呈现，往往起不到提示预警作用。可视化、形象化的图形，会直观呈现当前的热点与动态演化。系统对监测的不同信源自动采集的信息处理后生成聚类图；社会热点往往发萌于某些信源，随后被各门户转载、社会浏览量提升并被一再转载后而升温，也会反映到热岛图中。10.3.2二维政务资源聚类分析聚类分析结果可通过平面与立体化图形，空间与时间分布等多种形式呈现，以从不同视角、不同领域来观测事件的演化过程。

1）二维信息空间聚类分析实例二维聚类分析的可视化呈现实例如图10-12，以某系统对2008年7月10日汶川地震后近2月，来自不同渠道的报导作回溯聚类分析的结果。2）趋势聚类图图12-12的聚类只反映了某天信息空间的分布，只是一个时域片断，不能反映事件发展过程。聚类分析可加上时间坐标作时域聚类分析并生成图像，此时的聚类图就可反映热点事件的生命周期。如其何时萌生、何时明显、何时走强、何时达峰值、何时衰减、何时湮灭或演化成另一事件等。时序聚类分析对于监测特定事件走势、宏观调整结果分析等更为有用，故称为“趋势聚类图”或“趋势图”。这类图又可分为单一事件趋势图与多事件趋势图等。10.3.3三维政务信息聚类分析三维图像的信息量比二维图像更大，在三维聚类分析中，可根据聚集的文档或信息源数量来做第三维坐标。这样，任一热点受媒体关注的程度以及各热点间的相对热度比较就一目了然。10.4聚类分析的综合应用10.4.1聚类分析嵌入个人作业平台

以上实例皆从后台资源库生成后，供用户观察。先进的政务系统可将聚类功能嵌入常规作业流程中，整合一体并将结果动态推送到桌面，由此可生成许多新应用，尤其是在专题化、个性化信息分析与服务领域，可用图10-16实例说明。图10-16显示了一个政务系统中“分析工具”面板，它将聚类分析系统嵌入作业平台，面板分为分析工具区、标题区与内容区三部分。1）分析工具区右侧为竖直工具条，其中有“聚类操作”块，点击后进入本页面。“分析工具”区上部为各项设置。有聚类的起始与终止日期，相关度阈值设置等，其下为保存标题。用户利用本平台来做定题聚类，即设定一个内容标题，系统检测到各信源内容变化后，就能将符合内容特征的资源不断抓取汇入，本例设定的标题为“性