直接密度可达
O
Q
P
设MinPts=3 图中Q从P出发是直接 密度可达的，反之亦 然；O从Q出发是密度 可达的，反之则不然。
• 如果对象Q在对象P的e-邻域内，而P又是核心对 象，则称对象Q从对象P出发是直接密度可达的。
密度相连
S
U T P O
R
Q
设MinPts=3 图中O-P-Q-R-S是直 接密度可达的，O-TU是密度可达的。U和 S是密度相连的。
6
3.020 1.644 0.778 3.321 2.017 0.602
相似性度量为 cosij Q型聚类
顺序 1 2 3 4 5 连接点群号 1 5 2 2，3 1,4 4 6 3 5，6 2,3,5,6 相似水平 0.991 0.987 0.985 0.981 0.972
1.00 1 0.99 0.98 0.97 0.96 0.95
•引入类间距离下限作为类别是否合并 的标准
Di ,k
2 ( ) ij kj j 1 p
ip kp
(i, k 1,2, m)
i, k代表类别 , 为样本数, p代表变量数或维数 ,
为变量均值, kp代表类别k中变量p的均方差
3.3 空间密度异常的提取方法
3.3 划分聚类

定义


基本算法（K-Means）
实例计算 该算法的特点

改进方法
划分聚类的原理
定义：给定一个大小为N的数据 集，将 其分为m类，使类内具有较高的相似度， 而类间的相似度较低。
计算实例
0.9
0.8
0.7
0.6
0.5 0.9
0.4 0.8
0.3 0.7
0.2 0.6 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.5
2.2 空间数据的来源
来源的形式 1. 记录空间现象 采样数据（主动）、台站记录（被动）、遥感数据（全覆盖） 2. 记录空间对象 签到数据（主动）、射频数据（被动）、手机信令（全程记录）
泛在传感器种类 1、记录仪 2、分析仪 3、监控探头 4、遥感卫星 …
1、短信、微博 2、智能卡、读卡器 3、上网记录 4、GPS …
相似性度量为 cosij R型聚类
1.00 Co Cu
0.80
0.60
0.40
0.20
0.0
Ni
S As
Cr
层次聚类分析流程
空间数据
次选取较大的相似性度量
绘制聚类谱系图
选择分解阈值确定聚类结果
层次聚类的流程
层次聚类特点

呈树型的层次结构 需要计算相似性度量矩阵 聚类过程是从底部向上 需要人为确定划分阈值

直观、易实现且占用内存少 类别数目以及初始类中心的选 择具有较强的主观性 无法处理形状复杂的数据
划分聚类的改进算法
•引入组内变量平均标准差上限作为类 别是否分裂的标准
1 Sk Np
2 ( x ) ijk jk i 1 j 1 N p
(k 1,2, m)
k代表类别 N为样本数 p代表变量数或维数 为变量均值
应用领域 5
空间数据挖掘和知识发现

城市居民的活动模式发现 地球物理和地球化学异常的发现 遥感图象的分类、识别
1.4 数据挖掘的理论基础
粗糙集
概率统计
模糊理论
人工智能
数据挖掘和 知识发现
可视化理论
决策理论
数据库理论
专业知识
1.5 数据挖掘研究的任务
数据挖掘 研究
规则知识
求同 普遍规则 求异 异常模式
4
5 6 2 3
1 2 3 4 5 6
1.000 0.962 0.941 0.991 0.936 0.947 1 1.000 0.985 0.972 0.966 0.981 2 1.000 0.935 0.950 0.962 3 1.000 0.926 0.952 4 1.000 0.987 5 1.000 6
人脸识别（刑事侦察、安保系统）；

动态跟踪（警报系统）；
应用领域 4
生物信息知识发现 DNA的碱基对数目达到30亿 3万到4万个基因 基因和基因组数据库（ GenBank 包含了已知 的核算序列和蛋白质序列） 核算序列数据库（EMBL） 基因组数据库（GDB） 蛋白质数据库（PIR、PSD、SWISS－PROT）
2.3 空间数据的特点
1）海量的数据 2）空间属性之间的关系 3）空间尺度特征
4）空间信息的不确定性等
5）空间维数的增高
2.4 空间数据挖掘的特点
空间数据之间存在的空间关系 距离关系 方位关系 几何关系 拓扑关系 属性关系 变量相关 属性差异 变量分配
… 空间关系
…
2.5 空间数据挖掘研究思路
空间数据挖掘
主 讲：裴 韬 (peit@) 助 教：宋 辞 (songc@)
本课程的主要内容
1、空间点聚类方法
2、Matlab实习 3、轨迹分析及聚类 4、网络分析及聚类 5、学术报告及写作
6、讨论一
7、讨论二
本课程的考核方法
1、实习作业（30’）
2、课程作业（60’） 3、课堂表现（10’）
课程作业的要求

三人一组；分工明确 请根据课堂上讲的数据挖掘方法，结合自 己的专业问题进行研究，可以解决一个应 用问题，也可以提出一个申请。

文字报告、ppt演讲（8分钟演讲+5分钟 答辩）
本讲的主要内容 1、数据挖掘的含义及内容 2、空间数据挖掘的含义及内容 3、空间聚类 3.1 层次聚类 3.2 划分聚类 3.3 密度聚类 4、本讲小结
挖掘方法
求同
Apriori
求异
聚类分析
数据挖掘的方法分类

数据总结与泛化 聚类 分类 相关性分析 关联规则提取 异常分析 。。。
从信息到决策的认知过程
数据 数据挖掘 知识发现 信息
知识
决策分析 决策
1.6 数据挖掘应用的注意点



机械化的思想 机理不清 所需的先验知识少 归纳方法
0.1 0.1
0.4
0.3
0.2
0.1
划分聚类的算法流程
确定聚类数目K 选取K个点作为初始 聚类中心 计算各样本点到各聚类 中心的距离
根据距聚类中心的距离划 分样本点的归属 重新计算各类别的中心 (转入第3步)
一般采用欧氏距离， 也可采用其它的相似 性度量系数
直到聚类中心坐标 不再发生变化为止
实例及算法优缺点
cluster） 划分聚类（partitioning cluster） 密度聚类（density based cluster）
3.2 R型及Q型层次聚类
相似性度量 层次聚类的算法流程
Q型层次聚类及实例
R型层次聚类
相似性度量



距离系数 相关系数 夹角余弦 离差平方和 其它的相似性统计量
空间数据挖掘 研究
空间知识
求同 空间关联 求异 空间异常
挖掘方法
求同 自相关分析 求异 空间聚类
2.6 空间数据挖掘的任务
空间泛化
空间聚类 空间分类 空间相关性分析 空间关联规则提取
空间异常分析
3 点集的数据挖掘
点的空间聚类

空间聚类的含义


空间聚类方法的分类
密度等值线
高密度点群
Density-Based Spatial Clustering of Applications with Noise (DBSCAN)
DBSCAN的基本概念

邻域 核心点 直接密度可达 密度相连
邻域和核心点
O Q
P
e
MinPts=3
• 给定点半径e内的区域为e-邻域 • 如果一个点的e-邻域内至少包含最少数目 （MinPts）的点则该点称为核心点。
* rij
(x
k 1 n k 1 n
n
ki
xi )(xkj x j )
2 2 1/ 2 ( x x ) kj j ] k 1 n
[ ( xki xi )

(x
k 1 n k 1
ki
xkj nxi x j )
n
2 2 2 2 2 1/ 2 [( x 2 n x ) ( x n x kj i j ) ] ki k 1
距离系数
设在m维空间中，点i的坐标为x ， 点j的坐标为x ，那么点i和点j之间 的距离为：
ki kj
* d ij [ ( xki xkj ) 2 ]1/ 2 k 1
m
(i, j 1,2,, n)
d值越小，表明点i和h的距离越近。
相关系数
如果有n块样本，每块样本具有m个属 性，则任意两个属性i，j之间的相关系 数为：
相似性度量 R型及Q型谱系聚类 K－means聚类 密度聚类
3.1 空间聚类的含义
空间聚类是根据研究对象（样本或变 量）的多种特征在数值上可能存在的相似 性程度，将它们聚合为不同的点群的一种 挖掘方法，使得聚类内的对象相似和类间 的对象差异更大。
空间聚类的分类
层次聚类（hierarchical
(i, j 1,2, , m)
夹角余弦
在m维空间中的两个向量i，j其夹角 余弦为：
cos ij
x
k 1
m
ki
xkj
2 1/ 2 kj
[ x
k 1
m
2 ki
x
k 1
m
(i, j 1,2, , m) ]