网络数据挖掘-L7 聚类的应用
title: 网络数据挖掘-L7 聚类的应用
date: 2017-07-26 11:43:29
categories: DataMining
mathjax: true
tags: [WebDataMining]
L7 Applications of Clustering
聚类：类间分离，类内集中
聚类的类型，根据不同的类型应用不同的算法：
- well-separated clusters
Paste_Image.png
- center-based clusters
Paste_Image.png
- contiguous clusters
Paste_Image.png
- density-based clusters
Paste_Image.png
- Property or Conceptual clusters
Paste_Image.png
Described by an Objective Function 目标函数
- 聚类的过程就是maximize或者minimize目标函数的过程
- 通过枚举所有可能的聚类并用目标函数去计算goodness
- 通用与否：
- Hierarchical clustering algorithms针对local object
- Partitional algorithms通用
- 从数据中学到参数
数据挖掘中 聚类的要求
- 大规模
- 不同类型的属性
- 聚类的形状
- 初始化的参数尽量少
- 噪声和极端值
- 对输入数据的顺序不敏感
- 高维数据
- 用户规定的约束
- 可解释性和可用性
相似性
相似性的判断比聚类算法更重要，它表明了对数据的侧重点的不同。
- (Dis)similarity measures 相异性度量
Jagota defines a dissimilarity measure as a function f(x,y) such that f(x,y) > f(w,z) if and only if x is less similar to y than w is to z -
data item的折线图 欧式距离
Paste_Image.png
Paste_Image.png
- 折线图的趋势
皮尔逊线性相关Pearson Linear Correlation PLC- 相似性的计算
Paste_Image.png
* 相异性度量
> 
当其他非线性相关时，用PLC则无法来衡量相似性。
Hierarchical Clustering
参考层次化的聚类
算法：自底向上，一开始，每个数据点各自为一个类别，然后每一次迭代选取距离最近(Average Linkage\Single Linkage两个最近的点\Complete Linkage两个最远的点)的两个类别，把他们合并，直到最后只剩下一个类别为止，至此一棵树构造完成。
作用：
- 确定类别数K
- 利用树，自底向上人工判断类别。直接用k-means等方法无法直接判断出准确的有意义的类别。
缺点：
- 可能无法分出不同的类，或者需要有特定的cutoff values
k-means clustering 和 聚类的质量评估Cluster Quality
之前学习过k-means知道，k-means需要给出k以及一开始的random值。不同的k和随机值会导致结果的不同，而且当数据形状不好时该算法分类并不好。
-
K的问题
因此选择k并且利用Cluster Quality Measures评估CQ就有必要了
Paste_Image.png
如图，计算Q即每个类别的相异性程度的和要尽量小，即越紧凑。该评估强调了分类后的数据的一致性homogeneity
Paste_Image.png
-
初始random的问题
Paste_Image.png
-
对密度分布的处理
Paste_Image.png
Paste_Image.png
density-based clusters
该算法需要数据的形状、处理噪音、一次扫描、需要设置密度的阈值
Several interesting studies:
- DBSCAN: Ester, et al. (KDD’96)
- OPTICS: Ankerst, et al (SIGMOD’99).
- DENCLUE: Hinneburg & D. Keim (KDD’98)
- CLIQUE: Agrawal, et al. (SIGMOD’98)
DBSCAN
核心对象、e邻域、直接密度可达、密度可达、密度相连
算法：
扫描整个数据集，找到任意一个核心点，对该核心点进行扩充。扩充的方法是寻找从该核心点出发的所有密度相连的数据点（注意是密度相连）。遍历该核心点的e邻域内的所有核心点（因为边界点是无法扩充的），寻找与这些数据点密度相连的点，直到没有可以扩充的数据点为止。最后聚类成的簇的边界节点都是非核心数据点。之后就是重新扫描数据集（不包括之前寻找到的簇中的任何数据点），寻找没有被聚类的核心点，再重复上面的步骤，对该核心点进行扩充直到数据集中没有新的核心点为止。数据集中没有包含在任何簇中的数据点就构成异常点。
伪代码:所有点都找密度相连，再选出最大的集合，挖掉该集合。重复算法。
算法描述：
算法： DBSCAN
输入： E——半径
MinPts——给定点在E邻域内成为核心对象的最小邻域点数。
D——集合。
输出： 目标类簇集合
方法： Repeat
1） 判断输入点是否为核心对象
2） 找出核心对象的E邻域中的所有直接密度可达点。
Until 所有输入点都判断完毕
Repeat
针对所有核心对象的E邻域内所有直接密度可达点找到最大密度相连对象集合，中间涉及到一些密度可达对象的合并。
Until 所有核心对象的E领域都遍历完毕
弱点：
密度的差异
数据维度高
Paste_Image.png
对密度和核心对象的确定：
Paste_Image.png
聚类的应用
市场调研：用户基数大的时候，选出每个类的典型用户去调研。
土地使用：开店铺的选址。根据每个地的属性（人流量、人流种类、消费习惯）聚类，然后去找卖的好的奶茶店在哪种类型的地里，然后去其他相同类型的地里开店。可以用百度API
