当前课程知识点：数据挖掘 > 第8章 聚类 > 8.5 基于网格的聚类 > 8.5 基于网格的聚类
基于网格的聚类方法
使用一种多分辨率的网格数据结构
它将对象空间
量化成有限数目的单元
这些单元形成了网格结构
所有的聚类操作都在该结构上进行
这种方法的主要优点是处理速度快
其处理时间独立于数据对象数
而仅依赖于量化空间中
每一维上的单元数
STING统计信息网格
是一种基于网格的多分辨率的聚类技术
它将输入对象的空间区域
划分成矩形单元
空间可以用
分层和递归方法进行划分
这种多层矩形单元
对应不同级别的分辨率
并且形成一个层次结构
每个高层单元
被划分为多个低一层的单元
如图所示
关于每个网格单元属性的统计信息
如平均值、最大值和最小值
被预先计算和存储
这些统计信息用于回答查询
网格中常用的参数包括
Count 网格中对象数目
Mean 网格中所有值的平均值
Stdev 网格中属性值的标准偏差
Min 网格中属性值的最小值
Max 网格中属性值的最大值
Distribution
网格中属性值符合的分布类型
如正态分布
均匀分布
指数分布
或者分布类型未知
STING算法的基本过程分为以下几步
①在层次结构中选定一层
作为查询处理的开始点
通常
该层包含少量的单元
②对当前层次的每个单元
计算置信度区间
或者估算其概率
用以反映该单元与给定查询的关联程度
不相关的单元就不再考虑
③低一层的处理
就只检查剩余的相关单元
④这个处理过程反复进行
直到达到最底层
⑤如果查询要求被满足
那么返回相关单元的区域
否则
检索和进一步的处理落在
相关单元中的数据
直到它们满足查询要求
此图是一个包含两个簇的二维数据集
下面三个图
是网格划分参数取不同值时的聚类结果
假设当网格单元中
至少包含一个数据点时
就认为它是一个高密度网格单元
图中的阴影区域表示聚类算法得到的簇
从图中可以看到
当网格划分参数k取不同值时
算法得到的聚类结果相差很大
当划分参数过大时
网格单元的粒度太小
同一个簇内的高密度网格单元
可能会不相连
导致算法生成多个小的簇
而当划分参数过小时
网格单元粒度太大
所有的高密度网格单元都连在一起
导致数据中存在的多个簇产生合并
网格划分参数除对聚类结果的影响很大
对聚类算法计算复杂度也有很大影响
因此
选取合适的网格划分参数
对基于网格方法的聚类算法非常重要
STING算法的优点
基于网格的计算是独立于查询的
因为存储在每个单元的统计信息
提供了单元中数据汇总信息
不依赖于查询
其次
网格结构有利于增量更新和并行处理
另外
STING算法效率高
扫描数据库一次来计算单元的统计信息
因此产生聚类的时间复杂度为O(n)
即线性阶
在层次结构建立之后
查询处理时间为O(g)
其中g为最底层网格单元的数目
通常远远小于n
STING算法的缺点
由于采用了一种多分辨率的方法
来进行聚类分析
因此STING的聚类质量
取决于网格结构的最底层的粒度
如果最底层的粒度很细
则处理的代价会显著增加
然而如果粒度太粗
聚类质量难以得到保证
其次STING算法
在构建一个父亲单元时
没有考虑到子女单元和其他相邻单元
之间的联系
所有的簇边界不是水平的
就是竖直的
没有斜的分界线
降低了聚类质量
CLIQUE算法
是基于网格的空间聚类算法
它同时非常好地结合了
基于密度的聚类算法思想
因此既可以像
基于密度的方法发现任意形状的簇
又可以像基于网格的方法
处理较大的多维数据集
并且把每个维划分成不重叠的区间
从而把数据对象的整个嵌入空间
划分成单元
CLIQUE算法使用
一个密度阈值识别稠密单元
如果映射到一个单元的对象
超过该密度阈值
则认为该单元是稠密的
CLIQUE算法需要两个参数值
一个是网格的步长
一个是密度阈值
网格步长决定了空间的划分
而密度阈值用来定义密集网格
并且用网格密度表示网格中
所包含的空间对象的数目
密集网格是指给定阈值σ
当网格g的密度≥σ时
网格g是密集网格
否则是非密集网格
网格密度连通区域是指
设Grids为一个网格集合
若集合中的
所有网格相互邻接
且均是密集网格
则称Grid是网格密度连通区域
CLIQUE算法的基本步骤如下
①首先扫描所有网格
当发现第一个密集网格时
便以该网格开始扩展
扩展原则是若一个网格
与已知密集区域内的网格邻接
并且其自身也是密集的
则将该网格加入到该密集区域中
直到不再有这样的网格被发现为止
②继续扫描网格并重复上述过程
直至所有网格被遍历
CLIQUE算法
首先判断是不是密集网格
如果是密集网格
那么对其相邻的网格进行遍历
看是否是密集网格
如果是则属于同一个簇
CLIQUE算法自动发现最高维的子空间
高密度聚类存在于这些子空间中
并且它对元组的输入顺序不敏感
无需假设任何规范的数据分布
它随输入数据的大小线性地扩展
当数据的维数增加时
具有良好的可伸缩性
CLIQUE算法的优点是
给定每个属性的划分
一次数据扫描
就可以确定每个对象的网格单元
和网格单元的计数
其次
尽管潜在的网格单元数量可能很高
但是只需要为非空单元创建网格
另外
将每个对象指派到一个单元
并计算每个单元的密度的时间复杂度
和空间复杂度为O(m)
整个聚类过程是非常高效的
CLIQUE算法的缺点
像大多数基于密度的聚类算法一样
基于网格的聚类
非常依赖于密度阈值的选择
密度阈值太高
簇可能丢失
密度阈值太低
本应分开的簇可能被合并
其次
如果存在不同密度的簇和噪声
则也许不可能找到
适合于数据空间所有部分的值
再者
随着维度的增加
网格单元个数迅速增加
成指数增长
即对于高维数据
基于网格的聚类倾向于效果很差
-1.1 数据分析与数据挖掘
-1.2 分析与挖掘的数据类型
-1.3 数据分析与数据挖掘的方法
-1.4 数据分析与数据挖掘使用的技术
-1.5 应用场景及存在的问题
-第1章 作业1
-第1章 作业2
-2.1 数据的属性
-- 2.1 数据的属性
-2.2 数据的基本统计描述
-2.3 数据的相似性和相异性
-第2章 作业1
-第2章 作业2
-3.1 数据存在的问题
--数据存在的问题
-3.2 数据清理
--3.2 数据清理
--数据清理
-3.3 数据集成
--3.3 数据集成
--数据集成
-3.4 数据归约
--3.4 数据规约
--数据归约
-3.5 数据变换与数据离散化
-第3章 作业1
-第3章 作业2
-4.1 数据仓库基本概念
--数据仓库基本概念
-4.2 数据仓库设计
--数据仓库设计
-4.3 数据仓库实现
--数据仓库实现
-4.4 联机分析处理
--联机分析处理
-4.5 元数据模型
--元数据模型
-第4章 作业1
-第4章 作业2
-5.1 回归分析的基本概念
-5.2 一元线性回归
--一元线性回归
-5.3 多元线性回归
--多元线性回归
-5.4 多项式回归
--多项式回归
-第5章 作业1
-第5章 作业2
-6.1 概述
--频繁模式概述
-6.2 Apriori算法
-6.3 FP-growth算法
-6.4 压缩频繁项集
--压缩频繁项集
-6.5 关联模式评估
--关联模式评估
-第6章 作业1
-第6章 作业2
-7.1 分类概述
--7.1 分类概述
--分类概述
-7.2 决策树
--决策树
-7.3 朴素贝叶斯分类
--朴素贝叶斯分类
-7.4 惰性学习法
-7.5 神经网络
--神经网络
-7.6 分类模型的评估
--分类模型的评估
-第7章 第一部分作业2（研究生班级）
-第7章 第二部分作业2
-第7章 第二部分作业1
-8.1 聚类概述
--8.1 聚类概述
--聚类概述
-8.2 基于划分的聚类
--基于划分的聚类
-8.3 基于层次的聚类
--基于层次的聚类
-8.4 基于密度的聚类
--基于密度的聚类
-8.5 基于网格的聚类
--基于网格的聚类
-第8章 作业1
-第8章 作业2
-9.1 离群点定义与类型
-9.2 离群点检测
--离群点检测
-第9章 作业1
-第9章 作业2
