第1章 顾及限定规则的空间聚类
　　从20世纪70年代起，聚类分析广受关注，并开展了大量研究。聚类分析方法可分为统计学方法和机器学习方法两类。在统计学领域，主要研究如何应用几何距离实现聚类。在机器学习领域，因聚类学习的数据对象不需要类别标记，聚类学习由计算机自动完成，一般被称为无监督学习(unsupervised learning)。随着数据挖掘的发展，聚类技术成为数据挖掘的主要技术之一，在知识发现领域发挥着重要作用。
　　1.1 空间聚类限定规则问题
　　空间聚类分析技术的发展为地理分析实际应用提供了有力工具。但在大多数情况下，由于空间中存在着许多的现实约束，聚类分析得到的结果往往与实际情形并不相符。为使空间聚类分析更好地解决现实问题，需对限定规则进行研究，将用户需求与聚类算法和限定规则综合起来考虑，使得到的聚类结果更贴近实际应用需求。
　　1.1.1 限定规则问题
　　1.空间限定规则
　　从GIS空间分析角度考虑，研究附加限定规则的空间聚类，*先想到的可能是空间限定规则。在空间中，自然障碍物如河流、山川等能严重影响空间聚类结果。例如，为更好地服务顾客，银行管理人员规划在图1.1(a)所示区域设置4台自动取款机。一种解决方案便是对空间中所有的人群活动点(图1.1中点所示位置)进行聚类，在活动点的聚类中心设置取款机。而实际上，在此空间区域中有河流存在，若不考虑河流，直接对居民活动点进行聚类将会得到图1.1(b)所示的结果。可以注意到，在此聚类结果中，簇C11分布于河流的两岸，河流两岸的点在空间上距离*近，而实际情况是从河流一边的点到达另一点，需通过桥梁绕行，这会使得两点之间的到达距离加大，甚至会大于河流一边点与其位于河流同侧其他簇中的点，这个聚类结果显然不符合实际。由此可见，空间聚类中考虑空间限定规则的必要性。
　　2.非空间属性限定规则
　　空间聚类分析处理的对象是空间实体，但这些空间实体在大多数情况下都具有非空间属性，在某些情况下，这些非空间属性甚至会主导空间聚类分析结果。如图1.2所示，在不考虑任何非空间属性影响因素而仅考虑目标对象空间位置情况下，可得到河南省各市区位置的聚类结果[图1.2(a)]。但这种聚类结果仅仅告诉用户哪几个市区在空间上距离*近，而不具备任何其他的实际应用意义。这时，将非空间属性因素纳入参考范围，以市区的经济发展状况为例，用各个市区近五年的经济发展指标作为空间聚类参考条件，再次对河南省各市区进行聚类，得到图1.2(b)所示的结果。该聚类结果直观地反映了河南省各市区在经济发展状况上的相似性，呈现出河南省地方区域经济发展水平。该实例说明了非空间属性在空间聚类分析应用中的重要价值。
　　图1.1 自动取款机位置规划
　　图1.2 非空间属性限定规则影响聚类
　　3.方位限定规则
　　对象的空间分布往往存在着地域差异，以中国为例，在经济发展水平上，东部沿海城市要明显高于中西部城市，但人文景观丰富度，中西部城市要明显高于东部沿海城市。在进行职业地点选择时人们会倾向于选择东南部城市，因其经济水平较其他方位城市来说更为发达，发展机会更多。这种方位性特征对空间聚类结果产生影响。
　　1.1.2 限定规则问题定义及相关概念
　　在空间聚类中附加限定规则需要付出代价，而且规则的建模对*终获得一个有效的聚类结果来说也极其重要。为了对限定规则进行模拟，我们采用凸多边形来描述空间中实际存在的障碍物，如河流、湖泊等，并引入可见性以及可见空间的概念扩充对聚类簇的定义。
　　1.障碍物(obstacles)
　　障碍物统一用多边形表示，记为 O(VE)，其中为障碍物的顶点，为障碍物的边，vi和 vi+1为 ei相应的顶点，1≤i≤n；如果i+1＞n，那么。我们规定障碍物皆为凸多边形。
　　2.可视性(visibility)
　　给定点集为连接 di和 dj的线段，且线段，若l与障碍物边界ek无交点，则 di，dj两点可视，反之，则两点间存在障碍物，不可视。
　　3.可见空间(visibility space)
　　现有点集其中，若si和sj间相互可见，则 S为可见空间。若与si不相互可见，则必有且。
　　4.聚类簇(clusters)
　　现有数据集，其中，CD，可用均值ε和均方差 Minpts表达为高斯模型，若集合满足以下条件：①对于任意的，若 i.并且 d在ε和 Minpts约束的高斯模型范围之内，则②对于任意的和皆在ε和 Minpts约束的高斯模型范围之内，且对于任意的，ci和 cj是相互可见的，那么 C是基于ε和 Minpts的一个簇。
　　1.2 附加限定规则的空间聚类
　　一般情况下，聚类过程是根据一定规则将一组对象归为不同类，视应用目的不同，聚类结果会出现差异。*常见的聚类规则是对象间以及对象与所属聚类簇间欧氏距离*短原则。在实际应用中，欧氏距离存在明显不足。如隔河相望的两点 A、B，从 A点到达 B点的实际距离很可能远远大于两点间的直线距离，直接套用欧氏距离得到的聚类结果将与实际情况出现巨大偏差。这种影响空间聚类的空间障碍物称为空间限定规则。
　　除客观世界存在的障碍物外，对于特定应用还应在聚类过程中附加相应限定规则。如应用空间聚类进行选址，需根据应用方向制定相应的选址规则，用选址规则指导聚类，以得到更加符合客观事实的聚类结果。这种用户根据特定需求制定的限定规则称为非空间属性限定规则。
　　另外，实体的空间位置决定了实体间会存在着一定的方位关系，在某些情况下，人们会将方位因素考虑进去，如进行工作城市的选择时，人们会倾向于选择东部城市，因为东部地区气候温和，交通便利，生活舒适。所以在聚类时，会将方位影响因素考虑进去，这种限定规则被称为方位限定规则。
　　1.2.1 附加空间限定规则的空间聚类
　　1.附加空间限定规则的空间聚类实现的数学基础
　　假设有 n点集合及无相关性的障碍集。其中，障碍物 oi表示为一个多边形，其边为，结点为。定义点 p，q间的障碍的距离为在不经过任何障碍物的情况下，由 p到 q的*短欧氏距离。则将附加限定规则的空间聚类定义为将 P依据障碍距离聚为 k个簇的过程。在聚类过程中必须使聚类结果的均方误差限定在之内，其中，ci为簇Cli的中心。
　　1)可视路径计算
　　空间索引是按照空间分布特性来组织和存储数据的数据结构。建立空间索引机制的主要目的是提供数据的访问路径或指针，便于空间对象的查询以及各种空间数据的操作，提高空间数据的搜索速度。因加上空间障碍，空间划分会更加复杂，分割深度增大，经比较筛选，我们在研究工作中采用了BSP树建立空间索引。
　　BSP树又称空间二叉分割树，是二叉树的一种，它可将空间逐级进行一分为二的划分，能很好地与空间数据库中空间对象的分布情况相适应。
　　假设 p、q为空间中两点。如果 p、q两点间连线与任一障碍物皆无交点，则可认为 p到 q通视。如果用BSP树表示从点 p到障碍物各结点的可视性，从 p点开始，对BSP树进行遍历，得到一系列通视的点，直至点 q，表示为 vis(p)，即为在障碍物存在的情况下，点 p到点 q的通视路径。
　　2)障碍距离计算
　　障碍距离的计算借助可视性分析图实施。假设空间中有 m个障碍点可视性分析图，其中 vv.为障碍物结点的集合，当且仅当 V中两结点间相互通视时，构成边 E。如图1.3所示，障碍物结点 v1、v5构成可视化分析图的一条边。给定空间 R内相应两点为其相应的可视性分析图。由图1.3可知，点 p到 q可视路径，必然始于 v1、v2、v3之一，经过 VG的中某一路径，*终通过结点v4或者，其中，为 V中相应结点，为内相互通视的两结点相应边。用于存放点 p到 q所有可视路径。其中*优路径长度即为点 p到 q的障碍距离。
　　图1.3 可视性分析
　　2.附加空间限定规则的空间聚类的实现
　　在附加空间限定规则的聚类中，可以认为障碍物仅影响两点间距离的改变，因而附加空间限定规则的空间聚类的实现仅需改变距离函数，这种方法在 Clarans算法基础上实现。但这种方法并不完善，*明显的是该方法忽略了障碍物本身对聚类结果的影响。为此，我们研究了另一种方法，记为 Raise-Clarans法。
　　Clarans方法采用 k-中心算法实现。首先随机选取 k个对象作为聚类中心，然后将其余对象分配至距其*近的聚类中心的所属簇中，并计算均方误差 E。有学者对 Clarans算法进行了改进，将其应用于具有空间障碍的空间聚类中，提出 COD-CLARANS算法。该算法随机顺序选取聚类簇中心，记为，再随机选择另一对象替代，如果新得到
　　的聚类方案优于现有聚类方案，则用新的聚类中心代替原有的聚类中心，直至所有聚类中心都经过验证*后得到*优的聚类方案。
　　除此之外，Raise-Clarans方法的实现还有一些问题需要解决。首先，因COD-CLARANS是一种迭代寻优算法，每次循环都需计算均方误差 E，计算量巨大，计算过程将会占据大量内存。另外，此算法需要随机选择对象来替换聚类中心，很有可能出现选择的聚类中心不是*优的情况，造成计算资源浪费。在进行海量空间数据聚类时，以上两个问题将会更加明显。为此，采取以下两种策略。
　　第一种策略是参照 BIRCH和 CHAMELEON聚类方法，在聚类之前，先对聚类对象进行预聚类，将对象集合分割为大量小型的簇，小型簇中的对象有*大的相似度，*大可能的属于同一簇。然后再用小型簇中心点来代替此小型聚类簇，这将会大大减少 Raise-Clarans计算过程中的数据量。为更好地实现聚类算法，小型簇中心点需同时存储小型簇的信息，如包含点个数、直径等。
　　第二种策略是计算随机选择对象所对应的聚类均方误差E.，与现有 E进行比对，如果E.大于 E，说明目前的聚类结果已处于较优地位，不必计算 E。计算时用随机选择簇中心cran到小型簇的直线距离 d代替两者间的障碍距离 df，可以证明，d是 df的正确近似代替。同样可以推理出*优解的E.是 E的*小值。
　　下面讨论 Raise-clarans方法的具体实现。
　　1)预聚类(Pre-clustering)
　　(1)将空间区域R划分为 n个子区域互不相交，且与障碍物无交点，并保证，如图1.4所示。
　　图1.4 空间区域划分
　　(2)在每个子区域内进行子聚类，各个子簇中心皆在相应子区域内，彼此间可见，可以确保各个子簇不会与障碍物有交点。
　　(3)构建子簇中心与障碍物结点的BSP树。根结点与终结点皆为子簇中心，在研究过程中要求BSP树无向即可，因此，可将空间区域大致平均分为两部分：一部分作为根结点；另一部分作为终结点。
　　(4)构建可视性分析图。可视性分析图在BSP树的基础上构建生成，因此要求可视性分析图的起点与BSP树的根结点相同，终点与BSP树的终结点相同。
　　(5)构建空间连接索引。空间连接索引是为方便进行障碍距离计算构建的，分为三种类型。
　　VV索引：可视性分析图中任意两个障碍物结点间所有可视连接的索引。障碍距离的计算离不开障碍物结点间可视性距离的计算， VV索引将会大大减少这些距离的计

目录
序
作者序
前言
第1章 顾及限定规则的空间聚类 1
1.1 空间聚类限定规则问题 1
1.1.1 限定规则问题 1
1.1.2 限定规则问题定义及相关概念 3
1.2 附加限定规则的空间聚类 3
1.2.1 附加空间限定规则的空间聚类 4
1.2.2 附加非空间属性限定规则的空间聚类 8
1.2.3 附加方位因素的空间聚类 13
1.3 空间聚类结果分级处理 16
1.3.1 非空间属性的分级处理 16
1.3.2 空间方位因素的分级处理 18
1.4 算法实现及应用 23
1.4.1 实验数据及预处理 23
1.4.2 算法实现 24
1.4.3 算法应用实例 30
第2章 基于人工蜂群算法的空间聚类 34
2.1 人工蜂群算法及改进 34
2.1.1 人工蜂群算法 34
2.1.2 人工蜂群算法改进 38
2.1.3 算法改进测试 39
2.2 人工蜂群聚类算法 47
2.2.1 FCM算法和HCM算法 47
2.2.2 群智能聚类算法 51
2.2.3 算法比较分析 53
2.3 人工蜂群算法的空间聚类应用 56
2.3.1 实验数据 56
2.3.2 数据预处理 58
2.3.3 实验结果及分析 62
第3章 数据流的空间聚类变化检测 65
3.1 数据流相关概念及算法 65
3.1.1 数据流相关概念 65
3.1.2 数据流聚类算法 67
3.1.3 基于动态图的聚类变化挖掘 74
3.2 基于实时聚类快照的空间聚类变化检测 75
3.2.1 基于网格索引的DenStream算法优化 75
3.2.2 在线阶段的实时聚类快照截取 79
3.2.3 基于快照的聚类变化分析 80
3.2.4 实验与结果分析 84
3.3 基于滑动窗口的空间聚类变化检测 89
3.3.1 基于滑动窗口的在线聚类更新 89
3.3.2 基于图的空间聚类变化分析 95
3.3.3 实验与结果分析 97
3.4 应用实例——城市犯罪数据流模拟及聚类演化分析 99
第4章 量化空间关联规则挖掘应用 110
4.1 量化关联规则问题 110
4.1.1 关联规则挖掘相关概念 110
4.1.2 量化关联规则挖掘问题 112
4.2 空间数据预处理 115
4.2.1 基于聚类的空间数据离散化 115
4.2.2 聚类算法优化 117
4.2.3 基于行政区划的空间数据离散化 123
4.2.4 事务数据库构建 124
4.3 量化空间关联规则挖掘 125
4.3.1 包含事务信息的FP-tree 126
4.3.2 FPT-growth算法 129
4.3.3 基于模拟退火的量化关联规则挖掘 131
4.4 实验及分析 138
4.4.1 使用聚类数据进行定量关联规则挖掘 138
4.4.2 使用行政区划数据进行定量关联规则挖掘 143
4.4.3 实验结果分析 145
第5章 基于粒子群的模糊空间关联规则挖掘 147
5.1 基于粒子群的隶属函数优化方法 147
5.1.1 基本粒子群优化算法 147
5.1.2 隶属函数及其优化 149
5.1.3 优化算法描述 154
5.1.4 实验结果及分析 156
5.2 模糊空间关联规则挖掘方法 160
5.2.1 模糊集与模糊关联规则 160
5.2.2 全模糊区域频繁模式挖掘算法 163
5.2.3 基于改进粒子群算法的关联规则提取 167
5.3 模糊空间关联规则应用研究 173
5.3.1 数据准备与数据预处理 173
5.3.2 挖掘结果分析及检验 177
5.3.3 结果检验 178
第6章 本体辅助的空间关联规则挖掘 183
6.1 本体及其构建 183
6.1.1 本体基本概念 183
6.1.2 本体的结构与构建原则 184
6.1.3 基于语义收缩的本体构建 185
6.2 本体辅助的空间关联规则挖掘数据预处理 191
6.2.1 本体辅助的数据清理 191
6.2.2 本体辅助的数据归约 196
6.2.3 实验及评价 200
6.3 基于本体语义约束的空间频繁模式挖掘 207
6.3.1 空间依赖分析 207
6.3.2 基于概念格的空间依赖剔除 211
6.3.3 本体语义应用的实现 213
6.3.4 实验及其评价 214
6.4 本体辅助的空间关联规则挖掘结果优化 218
6.4.1 规则的生成和知识的表达 219
6.4.2 基于规则模式的规则选取 223
6.4.3 基于本体语义相似度的规则过滤 226
6.4.4 实验分析 227
第7章 本体辅助的中文文本自然灾害专题信息挖掘 232
7.1 中文文本时空信息获取及解析方法 232
7.1.1 地名本体、事件本体和灾害本体 232
7.1.2 面向主题的网页信息获取 233
7.1.3 文本中时空信息解析方法 233
7.1.4 文本中事件信息抽取方法 235
7.2 基于地名本体的地名知识表达方法 237
7.2.1 基于地名本体的地名知识建模 237
7.2.2 地名本体定性空间推理机制 243
7.2.3 地名知识库构建 244
7.3 面向事件的自然灾害领域本体构建 248
7.3.1 相关概念与技术方法 248
7.3.2 自然灾害事件领域知识分析 251
7.3.3 自然灾害事件领域本体建模与表达 257
7.3.4 自然灾害事件领域本体评价 260
7.4 顾及本体语义的自然灾害信息主题爬虫 264
7.4.1 主题爬虫技术基础 264
7.4.2 本体语义支持的自然灾害主题爬虫框架 268
7.4.3 基于语义和HTML位置加权的网页文本主题相关度计算 269
7.4.4 基于主题相关度的链接分析改进方法 275
7.4.5 测试与分析 277
7.5 非结构化中文文本自然灾害事件专题信息解析 280
7.5.1 相关技术基础 280
7.5.2 基于规则和推理的中文文本时间信息解析 282
7.5.3 基于本体标注的中文文本地名识别 288
7.5.4 中文文本自然灾害事件时空信息合并 291
7.5.5 基于复合特征的自然灾害事件类型识别 293
7.5.6 基于事件本体和模式匹配的自然灾害事件属性元素抽取 302
7.6 自然灾害事件时空信息匹配与可视化 308
7.6.1 自然灾害事件时空信息匹配 308
7.6.2 地名知识辅助的中文文本地名消歧 308
7.6.3 自然灾害事件可视化表达与分析 313
7.6.4 应用实例——以地震灾害为例 319
第8章 基于出租车轨迹数据的异常事件检测 323
8.1 出租车轨迹数据分析概述 323
8.1.1 轨迹数据相关知识 323
8.1.2 轨迹数据分析 325
8.1.3 聚类分析与异常检测 327
8.2 出租车异常轨迹模式发现 3308.2.1 相关定义 331
8.2.2 异常轨迹模式发现 333
8.2.3 实验与分析 338
8.3 事件检测与分析 342
8.3.1 基于LRT的元事件检测 343
8.3.2 元事件统计分析 348
8.3.3 复合时空事件的提取与分析 352
8.4 异常聚集行为检测 356
8.4.1 聚集行为发现 356
8.4.2 聚集行为模式分析与异常检测 361
第9章 基于出租车数据和POI的城市空间行为特征分析 369
9.1 数据准备与数据预处理 369
9.1.1 研究区域与数据准备 369
9.1.2 出租车数据预处理 370
9.1.3 POI数据预处理 373
9.2 城市功能区识别及主要交通枢纽空间分析 373
9.2.1 基于POI数据的城市功能区识别 373
9.2.2 城市功能区识别结果分析 376
9.2.3 交通用地的服务范围及空间联系强度分析 377
9.3 基于密度聚类的热点路段及区域挖掘 381
9.3.1 密度聚类算法的改进 382
9.3.2 热点路段时空分布与分析 387
9.3.3 热点区域POI热度指数计算与分析 389
9.4 基于时空谱聚类的出行特征挖掘 396
9.4.1 相似性度量方法及其改进 396
9.4.2 谱聚类算法的时空及功能区拓展 398
9.4.3 实验结果与分析 401
第10章 再分析计划气象数据流挖掘 411
10.1 气象数据流挖掘基础知识 411
10.1.1 相关概念 411
10.1.2 气象数据流的组织与管理 414
10.1.3 数据流挖掘基本算法 416
10.2 面向事件的气象数据流滑动窗口查询 417
10.2.1 基于事件的元对象查询 418
10.2.2 气象数据流滑动窗口查询方法 422
10.3 面向异常时空数据模型的气象数据流异常检测 424
10.3.1 面向异常时空数据模型 424
10.3.2 数据流的异常检测 427
10.3.3 气象数据流的异常检测实验 429
10.4 面向异常分类时空数据模型的气象数据流异常分类 438
10.4.1 面向异常分类时空数据模型 438
10.4.2 数据流的异常分类 440
10.4.3 气象数据流的异常分类实验 445
10.5 面向异常频繁时空数据模型的气象数据流异常频繁挖掘 449
10.5.1 面向异常频繁时空数据模型 449
10.5.2 数据流的异常频繁挖掘 452
10.5.3 气象数据流的异常频繁挖掘实验 455
10.6 面向属性分布时空数据模型的气象数据流高维聚类 462
10.6.1 面向属性分布时空数据模型 463
10.6.2 数据流的高维聚类 465
10.6.3 气象数据流的高维聚类实验 469
参考文献 477
后记 485