python聚类评价,聚类分析谱系图表,python聚类评价,聚类分析谱系图怎么做
个人资料
介绍了谱聚类的基本算法及其在matlab中的代码实现。介绍如下
从图表分割的角度直观理解谱聚类
谱聚类算法
和数据实现代码。
本文不涉及详细的证明和推导。有兴趣的可以参考七月大神的文章,提到来自pbdmg矩阵的谱聚类。
了解谱聚类
本节从图分割聚类的角度直观地理解谱聚类。但我是从事社交媒体分析的,所以我会从一个社交网络的角度介绍把一个网络图分成多个子图的概念。
分裂图
首先,社交网络被视为一个整体,每个个体(用户)就是网络中的每个节点,每个节点之间的边连接着个体)。在不同性质的网络中,边的定义可能不同,但在这里可以简单地看作是个体之间关系的亲密程度。如图1所示。
图一。
每个个体与其他个体之间的亲密度(也称为权重,设定范围为[0,1])在用户1、2和3之间,以及用户4、5和6之间具有紧密的关系,两个小部分由用户2和6组合。以现实生活为例,123是A班同学,456是B班同学,2和6只是认识而已,关系一般,所以通过直观切割2和6之间的边,形成两个不相关的子图。
图的泛化意义
在很多情况下,“图”模型无法表达现实生活中的网络。图模型是一种解题模型,对象可以在图模型和非图模型中求解。比如在聚类中,针对K-means聚类算法及其代码实现,我们讨论了如何将数据点视为坐标系中的一个点,通过迭代找到聚类的中心点。从另一个角度来看,我们坐标系中的每一个点都被视为图的节点,点与点之间的相似度被视为边的权重,我们也构成了图的模型。所以,图与非图,看哪一个更容易解决问题。
谱聚类的重要性
谱聚类是图分割的完成。然后希望找到最好的分割方法来分割图形。这个图的划分取决于这个图是如何定义的。比如图中的点是什么?边缘是如何决定的?最好的分割标准是什么?等一下。因为图本身定义的不同会导致分割结果的不同,为了明确这些,基于实际定义,这里声明使用目前常用的相似矩阵图模型,虽然图的定义可以是其他方式。
要解决的问题是给定数据{x1,x2,x3,xN},并把它分成K类。
这些数据点被视为数据节点,它们之间的相似度被定义为边的权值。相似度矩阵为W={wij1iN,1jN},其中相似度为
wij=exixj222(1)
根据kkdxgz的相似度。在…之中
是超参数。当然,余弦相似度等其他相似度也是如此。知道相似矩阵
w是对称矩阵。为了不轻易删除单个节点,考虑归一化对角矩阵。
d(数字),对角线上的元素是一行相似矩阵中所有元素的和(因为列,对称矩阵之类的),也就是
d(I,I)=j=1nxij(2))))))))d))I))I))I))I))I))I))j))652)
这样算。
由于没有给出截断的概念,优化函数的形式无法表达。详见pbdmg矩阵到谱聚类。
谱聚类算法
本节提供了谱聚类算法的步骤。一般来说,谱聚类算法首先求解相似度矩阵,然后归一化矩阵,再求解前K个特征向量,最后使用K-means算法进行分类。
其实谱聚类要做的就是把高维数据简单的用特征向量的形式表示出来,这是一个降维的过程。本来k-means不能很好划分的高维的点,经过线性变换降维就可以轻松解决。步骤如下。
1.根据公式(1)计算相似度矩阵W
2.W对角线的值,即w[I,I]=0,是为了排除自身的相似性。
3.根据公式(2)计算归一化矩阵D
4.计算标准化的pbdmg图矩阵L
5.计算L的特征向量,将前k个特征值最大的向量按列放入矩阵X中,即
X=[v1,v2,vk](4))))))))x))x))x)v1,v2,vk ) (4))
按照v1、v2和vK的顺序。
具有最大k个特征值的特征向量
6.正则化X形成矩阵y。
7.通过k-means将矩阵Y与每行中的一个数据点分组,并且第二个矩阵Y
我所属的班级是meta。
xi所属的阶级。
这样,所有的谱聚类过程就完成了。然而,我们实际上忽略了重要的参数。这个参数需要初始化。如何选择?请参见下一节中的示例分析。
光谱聚类代码分析
本节介绍如何用matlab实现谱聚类算法。数据代码可以在我的github上下载。
解锁密码
关键问题是如图(2)所示的分类问题。
图(二)
从上图我们可以看到,这个数据有两个环,外环是第一类,内环是第二类。这个分类问题是普通k-means算法无法解决的。因此,我们将使用代码来实现上一节中介绍的步骤。
首先我们的数据是存在的。
数据,导入数据。
满分。
计算相似度矩阵W,其中矢量化是一个运算,可以用公式(5)来理解。
X=allpts
n=大小(X,1);
squared_X=sum(X.*X,2);
transi _ X=X * X ;%x_j*x_i^t;X_i=repmat(squared_X,1,N);% samevalueinrowX _ j=repmat(squared _ X ,N,1);% samevalueincolE=-(X _ I X _ j-2 * transi _ X);
w=exp(E/(2 * sigsq));
Xi XJ 2=(Xi XJ)(Xi XJ)T=xixTi xjxTi xixTj xjxTj(5)
2.将对角线设置为零
W=W-diag(diag(W));
Diag()既可以取出对角元素,也可以从向量生成对角矩阵。
3.计算归一化矩阵D:
d=diag(sum(W ));
4.计算pbdmg矩阵l。
l=d^(-.5)*w*d^(-.5);
5.求特征值的特征向量并排序,求第一个k。
k=2;[X,di]=EIG(L);[Xsort,Dsort]=eigsort(X,di);
Xuse=Xsort(:1:K);
因为我这里只想分成两类,K=2。同时,eigsort是另一个定义1的函数,如下所示
%[Vsort,Dsort]=eigsort(V,D)% % sortsamatrixeigenvectorsandmatrixofeigenvaluesinorder % of igenvaluesize,largestegenvaluefirstandsmallestegenvaluefunction[Vsort,Dsort]=eigsort(V,D);EIG vals=diag(D);% sortheigenvaluesfromlagesttosmalest。将排序的%特征值存储到columnvectorlambda中。[lohival,loh iindex]=sort(EIG vals);
lambda=flip ud(lo hival);
index=flip ud(loiindex);
dsort=diag();% sortyfestingstocorrespondtoerderedegenvalues。store sorted % intfessionassacolumnsofthematrixvsort。m=长度();
Vsort=zeros(M,M);1:M
Vsort(:i)=V(:index(I));结束;
我删除了一些不必要的评论。
6.归一化X得到矩阵y。
Xsq=Xuse。* Xuse
divmat=repmat(sqrt(sum(Xsq )),1,2)Y=Xuse。/divmat
归一化是将特征向量长度改为1。
7.实现k-means聚类算法
[c,Dsum,z]=kmeans(Y,2)
kk=c;
C1=find(kk==1);
C2=find(kk==2);
在kmeans聚类之后,找到类别标签,最后简单的画一个图(3)来展示我们的分类结果。
图(三)
这里,我们用两种颜色来代表两个不同的类别。这
适马可能不同,这将导致不同的结果。这不是我给的。每个人可以根据问题设置0.1到10,具体可以去。
在我的github上下载完整的代码和数据。
摘要
至此,所有对谱聚类算法的理解,算法的具体步骤,以及实际的实现代码都已经完成。谱聚类可以完成k-means做不到的工作。其基本思想是线性空间变换,可以提取特征向量降维来表示原始的复杂数据。k-means总是用于简单的聚类。涉及特征向量的算法,还有后面会继续写的PCA算法。
参考
Ng,A. Y .M. I. Jordan和Y. Weiss (2001年)“关于谱聚类:
史,j .和j .马利克(1997)“规范化切割和图像分割”
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。