掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
宇宙、量子和人類心靈
-
>
氣候文明史
-
>
南極100天
-
>
考研數學專題練1200題
-
>
希格斯:“上帝粒子”的發明與發現
-
>
神農架疊層石:10多億年前遠古海洋微生物建造的大堡礁
-
>
聲音簡史
空間數據挖掘方法與實踐 版權信息
- ISBN：9787030730633
- 條形碼：9787030730633 ; 978-7-03-073063-3
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>>
空間數據挖掘方法與實踐 內容簡介
空間數據挖掘及應用是地理信息科學等相關學科研究的重要方向，其應用領域十分廣泛。該著作從空間聚類、空間關聯規則挖掘、自然災害專題信息挖掘、軌跡數據挖掘、數據流挖掘幾個方面開展了比較深入的研究。其中，空間聚類研究包括顧及限定規則的空間聚類、基于人工蜂群算法的空間聚類、數據流的空間聚類變化檢測等內容；空間關聯規則挖掘包括量化空間關聯規則挖掘、基于粒子群的模糊空間關聯規則挖掘、本體輔助的空間關聯規則挖掘三個方面的研究；自然災害專題信息挖掘包括面向事件的自然災害領域本體構建、顧及本體語義的自然災害信息主題爬蟲、非結構化中文文本自然災害事件專題信息解析、自然災害事件時空信息匹配與可視化等內容；軌跡數據挖掘包括基于軌跡數據的異常事件檢測、顧及POI的城市空間行為特征分析；數據流挖掘包括面向事件的氣象數據流滑動窗口查詢、面向異常時空數據模型的氣象數據流異常檢測、面向異常分類時空數據模型的氣象數據流異常分類、面向異常頻繁時空數據模型的氣象數據流異常頻繁挖掘、面向屬性分布時空數據模型的氣象數據流高維聚類等。
空間數據挖掘方法與實踐 目錄
目錄
序
作者序
前言
第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
序
作者序
前言
第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
展開全部
空間數據挖掘方法與實踐 節選
第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索引將會大大減少這些距離的計
書友推薦
- >
伯納黛特,你要去哪(2021新版)
- >
龍榆生：詞曲概論/大家小書
- >
名家帶你讀魯迅:故事新編
- >
隨園食單
- >
我從未如此眷戀人間
- >
山海經
- >
我與地壇
- >
月亮虎
本類暢銷
