《大数据分析与挖掘》课件-04大数据挖掘-聚类算法

大数据分析与挖掘

——04大数据挖掘-聚类——Part

1.聚类算法简介聚类（Clustering）“物以类聚，人以群分”是对于静态数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息聚类（Clustering）聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（Subset），这样让在同一个子集中的成员对象都有相似的一些属性其他分析算法的一个预处理步骤在这一过程中没有监督，因此是一种无监督的分类聚类与分类聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小;聚类中没有任何指导信息，完全按照数据的分布进行类别划分待分类数据训练数据数据挖掘任务通常分为两大类：预测任务，根据其他属性的值，预测特定属性的值。描述任务，概括数据中潜在联系的模式（相关性，趋势，聚类，轨迹和异常）聚类与分类的区别：TrainAndClassification（分类）;NoTrain（聚类）分类属于预测任务，就是通过已有数据集（训练集）的学习，得到一个目标函数f（模型），把每个属性集x映射到目标属性y（类），且y必须是离散的（若y为连续的，则属于回归算法）。为什么需要聚类?对相似的文档或超链接进行聚类，由于类别数远小于文档数，能够加快用户寻找相关信息的速度;聚类的基本要素定义数据之间的相似度;聚类有效性函数（停止判别条件）;在聚类算法的不同阶段会得到不同的类别划分结果，可以通过聚类有效性函数来判断多个划分结果中哪个是有效的;使用有效性函数作为算法停止的判别条件，当类别划分结果达到聚类有效性函数时即可停止算法运行;类别划分策略（算法）;通过何种类别划分方式使类别划分结果达到有效性函数;相似度EuclideanDistance数据表示为向量，向量中某一维对应数据某一特征或属性仅计算了数据向量中属于同一维度特征的权值差距;聚类有效性函数最小误差（）:最小方差:衡量同一类别内数据的平均误差和;衡量属于不同类别的数据与类别中心的的误差和;聚类划分聚类K-meansK-medodisK-modes层次聚类divsiveBIRCHROCKChamelon密度聚类DBSCANOPTICS网格聚类STING模型聚类GMM聚类基本方法聚类（Clustering）-基于密度的方法基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点聚类（Clustering）-基于网格的方法这种方法首先将数据空间划分成为有限个单元（Cell）的网格结构,所有的处理都是以单个的单元为对象的这么处理的一个突出的优点就是处理速度很快聚类（Clustering）-基于模型的方法基于模型的方法给每一个聚类假定一个模型，然后去寻找能个很好的满足这个模型的数据集它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的聚类（Clustering）-划分法给定一个有N个元组或者纪录的数据集，构造K（K

<N）个分组，每一个分组就代表一个聚类（1）每一个分组至少包含一个数据纪录（这个要求在某些模糊聚类算法中可以放宽）（2）每一个数据纪录属于且仅属于一个分组对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好聚类（Clustering）-划分法使用这个基本思想的算法有：K-MEANS算法K-MEDOIDS算法CLARANS算法Clara算法FuzzyC-Means算法聚类（Clustering）-层次法层次聚类，又称为系统聚类（系谱聚类）是一个一般的聚类算法，通过合并或分割类，生成嵌套的集群。算法的层次结构可以以一棵树表示。树的根是一个唯一的类，包含了所有的样本，而树的叶子节点是单独的一个样本。通过树的叶子节点的相互合并，最终合并成为树的根节点。这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止两种方案：即分裂（“自顶向下”）或凝聚（“自底向上”）算法运行到某一阶段，类别划分结果达到聚类标准时即可停止分裂或凝聚;Part

2.三种典型聚类算法K-Means聚类分析

迭代算法步骤适当选取K个类的初始中心

K-means初始参数-类别数&初始类别中心;聚类有效性函数-最小误差;优点：

聚类时间快;缺点：对初始参数敏感;容易陷入局部最优;

K-means原理类圆形数据集（Cluster形状为主）聚类数据集类型蝴蝶型数据集很明确的属于Cluster1很明确的属于Cluster2属于Cluster1or2?系统聚类系统聚类原理系统聚类的的基本思想是先将样本看作各自一类，定义类间距离的计算方法，选择距离最小的一对类合并成为一个新的类。接着重新计算类间的距离，再将距离最近的两类合并，如此最终便最终合成一类。由上图给出了一个系统聚类的例子。首先定义样本间距离的计算方法，计算各个样本点间的距离。先将距离最近的b与c合并，此时有5个类：{a},{b,c},{d},{e}和{f}。为了进一步的合并，所以需要计算类{a}与}{b,c}间的距离。因此还需要定义类间距离的计算方法。按照合并距离最小的两个类的规则，我们按顺序合并{d}与{e}，{d,e}与{f}，{b,c}与{d,e,f}，{a}与{b,c,d,e,f}。最终我们通过类的合并得出上图的结果。整个过程如同生成树的过程，树的层次结构分明。样本间距离的常用定义类间距离的常用定义系统聚类步骤考虑使用系统聚类算法将数据集N中的n个样本划分成k个不相交的类。

如果已经聚为k

类则算法停止，否则重复步骤2继续合并类通过相同的数据，我们使用系统聚类与K-Means算法效果作对比。一般而言，系统聚类使用欧几里德距离（affinity=‘euclidean’）和离差平方和法(linkage=‘ward’)效果最好。代码如下：#聚类数量不正确时的效果y_pred=AgglomerativeClustering(affinity='euclidean',linkage='ward',n_clusters=2).fit_predict(X)#选取欧几里德距离和离差平均和法plt.subplot(221)plt.scatter(X[y_pred==0][:,0],X[y_pred==0][:,1],marker='x',color='b')plt.scatter(X[y_pred==1][:,0],X[y_pred==1][:,1],marker='+',color='r')plt.title("IncorrectNumberofBlobs")#类间的方差存在差异的效果X_varied,y_varied=make_blobs(n_samples=n_samples,cluster_std=[1.0,2.5,0.5],random_state=random_state)y_pred=AgglomerativeClustering(affinity='euclidean',linkage='ward',n_clusters=3).fit_predict(X_varied)plt.subplot(223)plt.scatter(X_varied[y_pred==0][:,0],X_varied[y_pred==0][:,1],marker='x',color='b')plt.scatter(X_varied[y_pred==1][:,0],X_varied[y_pred==1][:,1],marker='+',color='r')plt.scatter(X_varied[y_pred==2][:,0],X_varied[y_pred==2][:,1],marker='1',color='m')plt.title("UnequalVariance")从实验结果分析，系统聚类的结果比K-Means的聚类效果要好，在这两个实验尤为明显。从算法分析,K-Means需要随机选择类的初始中心，给算法带来一定的不稳定，比起K-Means的迭代算法，系统聚类算法更为严谨，每一步合并都是贪心的。DBSCAN聚类DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)是一个有代表性的密度聚类算法。它将类定义为密度相连的点的最大集合，通过在样本空间中不断寻找最大集合从而完成聚类。该算法在带噪声的样本空间中发现任意形状的聚类并排除噪声。首先我们将列出DBSCAN算法涉及的基本定义：DBSCAN聚类步骤

从对象集合D中抽取未被访问过的样本点q

检验该样本点是否为核心对象，如果是则进入下一步