第十一章-聚类

聚类聚类任务距离计算聚类算法性能度量大纲聚类任务距离计算聚类算法性能度量大纲监督学习𝐷=(𝒙1,𝑦1),(𝒙2,𝑦2),…,(𝒙𝑚,𝑦𝑚),𝑋和𝑌都是已知的根据预测的变量是否连续可分为分类和回归无监督学习𝐷=𝒙1,𝒙2,…,𝒙𝑚,𝑋已知,𝑌未知在“无监督学习”任务中聚类是研究最多、应用最广的此外还有密度估计,降维,异常检测回顾样本的标记信息是未知的每个簇对应一个潜在的类别簇的个数预先设定或者自适应的聚类任务Cluster1Cluster2Cluster3Cluster4UnlabeleddataClustering聚类目标：将数据集中的样本划分为若干个通常不相交的子集（“簇”，cluster),使得从某种意义上同一簇的对象间的相似度比不同簇对象间的相似度更高聚类任务聚类不存在客观标准，给定数据集，总能从某个角度找到以往算法未覆盖的某种标准设计出新算法聚类任务形式化描述假定样本集包含个无标记样本,每个样本是一个维的特征向量，聚类算法将样本集划分成个不相交的簇。其中，且。。相应地，用表示样本的“簇标记”（即clusterlabel）,即。于是，聚类的结果可用包含个元素的簇标记向量表示。10个西瓜西瓜重量k=31,2,3对10个西瓜，簇标记向量例如{2,1,2,3,2,1,3,1,3,2}1)商业：帮助市场分析人员从客户基本库中发现不同的客户群，并且用不同的购买模式描述不同客户群的特征。2)生物学：推导植物或动物的分类，对基于进行分类，获得对种群中固有结构的认识。3)WEB文档分类4)图像分割5)其他：如地球观测数据库中相似地区的确定；各类保险投保人的分组；一个城市中不同类型、价值、地理位置房子的分组等。6)聚类分析还可作为其他算法的预处理：即先进行聚类，然后再进行分类等其他的数据挖掘。应用聚类任务距离计算聚类算法性能度量大纲相似性度量是计算两个样本之间的相似度，最常用的方法是距离计算。距离越小，相似度越高；距离越大，相似度越低。距离计算常用距离：闵可夫斯基距离（Minkowskidistance）:距离计算𝑑𝑖𝑠𝑡𝑚𝑘𝑥𝑖,𝑥𝑗=(𝑥𝑖𝑢−𝑥𝑗𝑢𝑝𝑛𝑢=1)1𝑝𝑥𝑖=(𝑥𝑖1;𝑥𝑖2;…𝑥𝑖𝑛),𝑥𝑗=(𝑥𝑗1𝑥𝑗2;…𝑥𝑗𝑛)wherep=1,曼哈顿距离(Manhattandistance)p=2,欧式距离(Euclideandistance)𝑥1=[2,1];𝑥2=[3,3]d=(|2-3|1+|1-3|1)1=3Manhattandistanced=(|2-3|2+|1-3|2)1/2=5Euclideandistance𝑑𝑖𝑠𝑡𝑒𝑑𝑥𝑖,𝑥𝑗=𝑥𝑖−𝑥𝑗2=𝑥𝑖𝑢−𝑥𝑗𝑢2𝑛𝑢=1𝑑𝑖𝑠𝑡𝑚𝑎𝑛𝑥𝑖,𝑥𝑗=𝑥𝑖−𝑥𝑗1=𝑥𝑖𝑢−𝑥𝑗𝑢𝑛𝑢=1距离计算夹角余弦（Cosinesimilarity）几何中，夹角余弦可用来衡量两个向量方向的差异；机器学习中，借用这一概念来衡量样本向量之间的差异。两个n维样本点的夹角余弦为：夹角余弦取值范围为[-1,1]。余弦越大表示两个向量的夹角越小，余弦越小表示两向量的夹角越大。当两个向量的方向重合时余弦取最大值1，当两个向量的方向完全相反余弦取最小值-1。距离计算Hammingdistance(汉明距离)两个等长字符串s1与s2的汉明距离为：将其中一个变为另外一个所需要作的最小字符替换次数。•1011101and1001001is2.•2173896and2233796is3.例如:左右字符串之间的汉明距离分别是：汉明距离在包括信息论、编码理论、密码学等领域都有应用。比如在信息编码过程中，为了增强容错性，应使得编码间的最小汉明距离尽可能大。JaccardsimilaritycoefficientCorrelationcoefficientandCorrelationdistanceInformationEntropy…其它距离计算聚类任务距离计算聚类算法性能度量大纲K-meansAGNESDBSCANMixtureofGaussian聚类算法Demo(K-means)K-means簇划分更新均值向量初始化均值向量K-meansk均值算法实例接下来以下表西瓜数据集为例，来演示k均值算法的学习过程。将编号为的样本称为.类似的，对数据集中的所有样本考察一遍后，可得当前簇划分1、假定聚类簇数,算法开始时，随机选择3个样本作为初始均值向量，即。3k23x,x8,x7,x1014x,x9,x19,x15,x17,x18,x20,x13}1C{,x5,x62C{,x1116x,x12}3C{,x1,x2,x3,x4},x2225x,x21,x92,x26,x72,x82,x2430x3、于是，可以从分别求得新的均值向量4、不断重复2、3步直到终止条件（达到给定的的迭代次数或者均值向量不再变化或者差异小于给定的阈值）2、考察样本，它与当前均值向量的距离分别为0.369，0.506，0.166，因此将被划入簇中。1x3CK-means西瓜数据集上运行k-meansK-means优化目标K-means给定数据集，k均值算法针对聚类所得簇划分最小化平方误差其中，是簇的均值向量。值在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，值越小，则簇内样本相似度越高。然而优化E是一个isNP-Hard的问题.K-means尝试采用迭代的方法，每次簇划分和更新均值向量都是优化E的过程，可以证明在有限步收敛.算法流程（迭代优化）：初始化每个簇的均值向量repeat1.（更新）簇划分；2.计算每个簇的均值向量until当前均值向量均未更新K-means固定均值向量，每个样本重新分到最近的簇中，每个样本的平方距离要么不变要么减小，整体上E要么不变要么减小固定簇划分，优化E，即最小化每个簇的平方距离和，针对每簇来说对均值向量求导，可以得到新的均值向量是簇内样本的平均值优点•简单:容易理解和实现•有效:时间复杂度:𝑂(𝑡𝑘𝑑𝑛),𝑡迭代次数.𝑘簇个数𝑑特征维数𝑛数据集大小t和k都是很小的，k-means被认为是线性的.K-means缺点•容易陷入局部最优.•对初始值敏感K-means可以尝试多次随机初始化，选平方误差最小的那次•用户需指定聚类个数那么我们怎么确定k?先验知识，经验值.Elbow(肘)方法.K-means•对离群点敏感K-means我们可以剔除离群点后再聚类K-means•Thek-means不适用于发现非球状簇Fuzzyc-meansK-medoidsISODATAKenelK-meansK-means的扩展K-meansAGNESDBSCANMixtureofGaussian聚类算法Demo(AGNES)ABCDEFABCDEFBCDEFBCDEFDEABCDEFDendrogramAGNESAGNES算法首先，将样本中的每一个样本看做一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直到达到预设的聚类簇的个数。这里两个聚类簇和的距离，可以有3种度量方式。最大距离（全连接）𝑑𝑖𝑠𝑡min𝐶𝑖,𝐶𝑗=min𝑥∈𝐶𝑖,𝑧∈𝐶𝑗𝑑𝑖𝑠𝑡(𝑥,𝑧)𝑑𝑖𝑠𝑡𝑎𝑣𝑔𝐶𝑖,𝐶𝑗=1𝐶𝑖𝐶𝑗𝑑𝑖𝑠𝑡(𝑥,𝑧)𝑧∈𝐶𝑗𝑥∈𝐶𝑖最小距离（单连接）平均距离（均连接）𝑑𝑖𝑠𝑡𝑚𝑎𝑥𝐶𝑖,𝐶𝑗=m𝑎𝑥𝑥∈𝐶𝑖,𝑧∈𝐶𝑗𝑑𝑖𝑠𝑡(𝑥,𝑧)AGNES生成的树状图AGNES计算距离矩阵每次循环合并两个簇并更新距离矩阵Results(AGNES)•复杂度:𝑂(𝑛2)..•不需要你事先制定聚类个数(但聚完后你得观察，到哪个类结束，也就是你最终给他分类的个数)。AGNESK-meansAGNESDBSCANMixtureofGaussian聚类算法DBSCAN:Density-basedSpatialClusteringOfApplicationsWithNoise.DBSCAN是一个基于密度的聚类算法.(聚类方法大都是基于对象之间的距离进行聚类)。基于密度的聚类是寻找被低密度区域分离的高密度区域。DBSCANDBSCANDBSCAN算法：基于一组“邻域”参数来刻画样本分布的紧密程度。基本概念：邻域：对样本，其邻域包含样本集中与的距离不大于的样本；核心对象：若样本的邻域至少包含MinPts个样本，则该样本点为一个核心对象；密度直达：若样本位于样本的邻域中，且是一个核心对象，则称样本由密度直达；密度可达：对样本与，若存在样本序列，其中且由密度直达，则该两样本密度可达；密度相连：对样本与，若存在样本使得两样本均由密度可达，则称该两样本密度相连。DBSCAN一个例子令𝑀𝑖𝑛𝑃𝑡𝑠=3，则虚线显示出领域。是核心对象。由密度直达。由密度可达。与密度相连。DBSCAN对“簇”的定义由密度可达关系导出的最大密度相连样本集合。对“簇”的形式化描述给定邻域参数，簇是满足以下性质的非空样本子集：连接性：与密度相连最大性：与密度可达实际上，若为核心对象，由密度可达的所有样本组成的集合记为𝑋=𝑥′∈𝐷|𝑥′由𝑥密度可达，则𝑋为满足连接性与最大性的簇。DBSCAN找出所有核心对象随机选一个核心对象生长出一个簇，并在核心对象集合里删去已经被覆盖的核心对象们参数设置：如果对数据足够了解，参数可以由领域专家根据经验值指定.•𝑀𝑖𝑛𝑃𝑡𝑠:一般来说,MinPts≥dim+1,可以取MinPts=2*dim，对于很大的数据有必要取更大的值.•𝜖-neighborhood:ε值的选取可以采用k-distancegraphDBSCAN对于数据中的每个点，计算对应的第k（k=MinPts）个最近邻域距离，并将数据集所有点对应的第k最近邻域距离按照降序方式排序，称这幅图为排序的k距离图，选择该图中第一个谷值点位置对应的k距离值设定为𝜖。DBSCANDBSCAN优点：•不用提前指定聚类个数.•能发现任意形状簇.•对噪声鲁棒缺点：•不能很好地处理密度差异大的数据集.DBSCANK-meansAGNESDBSCANMixtureofGaussianClusteringalgorithm高斯混合聚类（Mixture-of-Gaussian）采用概率模型进行聚类MixtureofGaussian高斯分布多元高斯分布的定义对维样本空间中的随机向量，若服从高斯分布，其概率密度函数为其中是维均值向量，是的协方差矩阵。也可将概率密度函数记作。混合高斯分布高斯混合分布的定义该分布由个混合分布组成，每个分布对应一个高斯分布。其中，与是第个高斯混合成分的参数。而为相应的“混合系数”，。假设样本的生成过程由高斯混合分布给出：首先，根据定义的先验分布选择高斯混合成分，其中为选择第个混合成分的概率；然后，根据被选择的混合成分的概率密度函数进行采样，从而生成相应的样本。混合高斯分布身高分布的例子(高斯混合模型):heightdistribution：𝜇𝜎2𝑃male(𝑥):(1.75,0.15)𝑃female(𝑥):(1.63,0.1)ifα1=0.7，α2=0.3𝑝𝑀𝑥=1.7=0.7*𝑃male(1.7)+0.3*𝑃female(1.7)=0.7*0.4+0.3*0.1=0.311.71.631.750.40.310.1𝑃maleingreen，𝑃femaleinredAndtheirmixturedistrubution𝑝𝑀𝑥inblueP(x)x假设𝑧𝑗∈*1