文章大纲:
聚类概念
聚类应用
聚类目标
相似性计算方法
聚类方法分类
划分方法
1. 概念
按照数据之间的相似性,对数据集进行分组或分类(簇, cluster)的过程;试图使类内差距最小化,类间差距最大化。
利用聚类结果,可以提取数据集中隐藏的信息,对未来数据进行预测和分类。
特点:处理巨大的、复杂的数据集
2. 应用
(1)作为其它算法的预处理步骤:利用聚类进行数据预处理,可以获得数据的基本概况,在此基础上进行特征抽取或分类就可以提高精确度和挖掘效率。也可将聚类结果用于进一步关联分析,以获得进一步的有用信息。
(2)作为一个独立的工具来获得数据的分布情况:聚类分析是获得数据分布情况的有效方法。通过观察聚类得到的每个簇的特点,可以集中对特定的某些簇作进一步分析。
(3)聚类分析可以完成孤立点挖掘:许多数据挖掘算法试图使孤立点影响最小化,或者排除它们。
3. 聚类分析的目标
聚类分析的目标就是形成的数据簇,并且满足下面两个条件:
--一个簇内的数据尽量相似(highintra-classsimilarity);
--不同簇的数据尽量不相似(lowinter-classsimilarity)。
衡量一个聚类分析算法质量,依靠:
--相似度测量机制是否合适。
--是否能发现数据背后潜在的、手工难以发现的类知识。
4. 相似性度量
(1)距离相似性度量
(2)角度相似性度量
Similarity is expressed in terms of a distance function, which is typically metric: d(i, j);
不同类型的数据,距离函数的定义也有所不同。
4.1 数据类型及其类内度量方式
(1)区间标度
区间标度是一个粗略线性标度的连续度量
eg:重量和高度,经度和纬度坐标以及大气温度。
明考斯基距离:
名氏距离If q=1,dis曼哈顿距离(Manhattan distance):
曼哈顿距离If q=2,dis欧几里得距离Euclidean distance:
欧式距离(2)二元变量
两种状态:0、1.
A。 对称型
简单匹配系数:
计算公式 数据表B。非对称型
根据惯例,我们将比较重要的输出结果,通常也是出现几率较小的结果编码为1
给定两个不对称的二元变量,两个都取值1的情况被认为比两个都取值0的情况更有意义。因此,这样的二元变量被认为好像只有一个状态。
Jaccard系数:
计算中,负匹配的数目d认为是不重要的,被忽略;
计算公式(3)标称型、序数型和比例标度型
(4)混合型
4.2 类间度量
设有两个类Ca和Cb,它们分别有m和h个元素,它们的中心分别为γa和γb。设元素x∈Ca,y∈Cb,这两个元素间的距离通常通过类间距离来刻画,记为D(Ca,Cb)。
两个聚类p和q:
(1)最短距离法
(2)最长距离法
(3)重心法
(4)类平均法
4.3 其他影响
特征选取不当---聚类无效
特征选取不足---误分类
模式特征坐标单位的选取也会强烈地影响聚类结果
尺度问题:标准化
标准化1 标准化2 标准化3 标准化44.4 角度相似性度量
角度度量 特点5. 聚类方法分类
(1)按照聚类的标准,聚类方法可分为如下两种:
统计聚类方法:这种聚类方法主要基于对象之间的几何距离的。
概念聚类方法:概念聚类方法基于对象具有的概念进行聚类。
(2)按照聚类算法所处理的数据类型,聚类方法可分为三种:
数值型数据聚类方法:所分析的数据的属性只限于数值数据。
离散型数据聚类方法:所分析的数据的属性只限于离散型数据。
混合型数据聚类方法:能同时处理数值和离散数据。
(3)按照聚类的尺度,聚类方法可被分为以下三种:
基于距离的聚类算法:用各式各样的距离来衡量数据对象之间的相似度,如k-means、k-medoids、BIRCH、CURE等算法。
基于密度的聚类算法:相对于基于距离的聚类算法,基于密度的聚类方法主要是依据合适的密度函数等。
基于互连性(Linkage-Based)的聚类算法:通常基于图或超图模型。高度连通的数据聚为一类。
(4)按照聚类分析算法的主要思路,可被归纳为如下几种:
划分法(Partitioning Methods):基于一定标准构建数据的划分。属于该类的聚类方法有:k-means、k-modes、k-prototypes、k-medoids、PAM、CLARA、CLARANS等。
层次法(Hierarchical Methods):对给定数据对象集合进行层次的分解。
密度法(density-based Methods):基于数据对象的相连密度评价。
网格法(Grid-based Methods):将数据空间划分成为有限个单元(Cell)的网格结构,基于网格结构进行聚类。
模型法(Model-Based Methods):给每一个簇假定一个模型,然后去寻找能够很好的满足这个模型的数据集。
6. 划分方法
给定一个有n个对象的数据集,划分聚类技术将构造数据k个划分,每一个划分就代表一个簇,k<=n。也就是说,它将数据划分为k个簇,而且这k个划分满足下列条件:
a。每一个簇至少包含一个对象。
b。每一个对象属于且仅属于一个簇。
对于给定的k,算法首先给出一个初始的划分方法,以后通过反复迭代的方法改变划分,使得每一次改进之后的划分方案都较前一次更好。
启发式方法: k-平均算法和k-中心点算法
k-均值算法:每个簇用该簇中对象的平均值来表示。
k-中心点算法:每个簇用接近聚类中心的一个对象来表示
k-means算法
(1)步骤
首先将所有对象随机分配到k个非空的簇中
计算每个簇的平均值,并用该平均值代表相应的簇。
根据每个对象与各个簇中心的距离,分配给最近的簇。
然后转第二步,重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。
(2)算法
k-means算法(3)主要优点
是解决聚类问题的一种经典算法,简单、快速。
对处理大数据集,该算法是相对可伸缩和高效率的。
当结果簇是密集的而簇间区别是明显的时,它的效果较好。
(4)主要缺点:
必须事先给出k(要生成的簇的数目),而且对初值敏感,对于不同的初始值,可能会导致不同结果。
不适合于发现非凸面形状的簇或者大小差别很大的簇。
对于“躁声”和孤立点数据是敏感的,因为簇的中心是通过计算数据的平均值得到的,这些数据的存在会使聚类的中心发生很大的偏移。
网友评论