做网站哪家好,免费网站建设服务,对加强政务门户网站建设的意见,软件外包平台哪家可信赖聚类算法—k-Means实验
k-平均#xff08;k-Means#xff09;#xff0c;也被称为k-均值#xff0c;是一种得到最广泛使用的聚类算法[1]. k-Means算法以k为参数#xff0c;把n个对象分为k个簇#xff0c;使得簇内具有较高的相似度。
实验目的
了解常用聚类算法及其优缺…聚类算法—k-Means实验
k-平均k-Means也被称为k-均值是一种得到最广泛使用的聚类算法[1]. k-Means算法以k为参数把n个对象分为k个簇使得簇内具有较高的相似度。
实验目的
了解常用聚类算法及其优缺点掌握k-Means聚类算法对数据进行聚类分析的基本原理和划分方法利用k-Means聚类算法对数据集进行聚类实验熟悉使用Matlab进行算法的实现。
聚类算法的主要思想
主要思想
给定一个有n个对象的数据集划分聚类技术将构造数据k个划分每一个划分就代表一个簇k≤nk\le nk≤n. 每一个簇至少包含一个对象每一个对象属于且仅属于一个簇。
对于给定的k算法首先给出一个初始的划分方法以后通过反复迭代的方法改变划分使得每一次改进之后的划分较前一次更好。
评价函数
更好的标准是同一簇中的对象越接近越好而不同簇中的对象越远越好目标是最小化所有对象与其簇中心之间相异度之和。
各个簇应该是紧凑的各个簇间的距离应当尽可能远。因此用聚类C的类内差异Within cluster variationw(C)w(C)w(C) 和类间差异Between cluster variationb(C)b(C)b(C) 分别衡量上述两要求。
w(C)∑i1kw(Ci)∑i1k∑x∈Cid(x,xi‾)2w(C)\sum_{i1}^{k}w(C_i)\sum_{i1}^{k}\sum_{x\in C_i}d(x,\overline{x_i})^2w(C)i1∑kw(Ci)i1∑kx∈Ci∑d(x,xi)2
b(C)∑1≤j≤i≤kd(xj‾,xi‾)2b(C)\sum_{1\le j\le i\le k}d(\overline{x_j},\overline{x_i})^2b(C)1≤j≤i≤k∑d(xj,xi)2
其中xi‾\overline{x_i}xi 是类 CiC_iCi 的聚类中心d 为距离函数。聚类C的总体质量可以被定义为 b(C)w(C)\frac{b(C)}{w(C)}w(C)b(C).
k-Means算法原理
k-Means算法用类内均值作为聚类中心、用欧氏距离定义d并使上述 w(C)w(C)w(C) 最小化。
优化目标
argmaxC∑i1k∑x∈Ci∥x−xi‾∥2\mathop{\arg\max}\limits_{C} \sum_{i1}^k \sum_{x\in C_i} \parallel x-\overline{x_i}\parallel ^2Cargmaxi1∑kx∈Ci∑∥x−xi∥2
表示选取合适的C使得所有对象的平方误差总和最小其中x是空间中的点xi‾\overline{x_i}xi 是簇 CiC_iCi 的平均值这个优化目标可以保证生成的结果簇尽可能的紧凑和独立。
算法描述
首先随机选择k个对象每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复直到上述平方误差总和收敛。
k-Means算法分析
优点
对处理大数据集该算法是相对可伸缩和高效率的时间复杂度约为 O(k⋅n⋅t)\mathcal{O} (k\cdot n\cdot t)O(k⋅n⋅t)t是迭代次数。k-Means算法经常以局部最优结束算法尝试找出使平方误差最小的k个划分当结果簇是密集的而簇与簇之间区别明显时k-Means的效果较好。
缺点
若涉及离散属性其平均值无法定义无法使用k-Means聚类必须事先给出参数kk的选取对聚类质量和效果影响很大k-Means算法不适合发现非凸面形状的簇或者大小差别很大的簇。而且对于“噪声”和孤立点数据是敏感的少量的该类数据对平均值产生较大影响。
算法改进
k-模算法将k-Means的应用扩大到离散数据。k-原型可以对离散与数值属性两种混合的数据进行聚类在k-原型中定义了一个对数值与离散属性都计算的相异性度量标准。[2]
k-中心点算法解决了k-Means算法对孤立点敏感的问题不采用簇中的平均值作为参照点而使用簇中位置最靠近中心的对象作为参照点。基本思路是反复用非代表对象来替代代表对象以改进聚类的质量。PAMPartition Around Medoid是最早提出的k-中心点算法之一。[3]
代码
clc;clear;
k 2;
data [1 1; 2 1; 1 2; 2 2; 4 3; 5 3; 4 4; 5 4;];
eps 0.1;
epochs 100;
[n,~] size(data);
% initialize the last column of data as classes
data(:,end1) 0;
% assign initial value for means
rng(default) % For reproducibility
clusters data(randperm(n,k),1:end-1);
% initialize E
E inf;
% save means steps
cnt 0; % counter
cls_steps [];
while epochs0% to save means stepscnt cnt 1;cT clusters;cls_steps(cnt,:) cT(:);% assign each xj to the cluster which has the closet meanD pdist2(data(:,1:end-1),clusters);[~,I] min(D);data(:,end) I;% calculate new means for each classesclusters grpstats(data(:,1:end-1),data(:,end));% calculate criterion function ElastE E;E .0;for i1:nE E pdist2(data(i,1:end-1),clusters(data(i,end),:));endif lastE-Eepsbreakendepochs epochs - 1;
endMatlab2021a
结果验证
结果数据
在data.csv数据集上运行上述代码得到结果如下
Clusters: 聚类中心
x1x21.51.54.53.5
E 5.65685424949238
cls_steps: 聚类中心移动记录
c1x1c1x2c2x1c2x243532.333333332.1666666753.51.51.54.53.5
结果图像 其中蓝色/黄色实心点表示不同分类下的数据点空心橙色/紫色圆环表示k-Means聚类中心的变化情况。
附录data.csv
IndexAttr1Attr2111221312422543653744854
参考
毛国君、段立娟, 《数据挖掘原理与算法》, 清华大学出版社, 2016-01-01, ISBN9787302415817Ramasubramanian P , Kumar S P , Anandam D . Experimental work on Data Clustering using Enhanced Random KMode Algorithm. 2020.Bhat A . K-Medoids Clustering Using Partitioning Around Medoids for Performing Face Recognition. 2014.
