matlab 职坐标,机器学习入门之机器学习实战ByMatlab（四）二分K-means算法
本文主要向大家介绍了机器学习入门之机器学习实战ByMatlab(四)二分K-means算法，通过具体的内容向大家展现，希望对大家学习机器学习入门有所帮助。前面我们在是实现K-means算法的时候，提到了它本身存在的缺陷：
1.可能收敛到局部最小值
2.在大规模数据集上收敛较慢
对于上一篇博文最后说的，当陷入局部最小值的时候，处理方法就是多运行几次K-means算法，然后选择畸变函数J较小的作为最佳聚类结果。这样的说法显然不能让我们接受，我们追求的应该是一次就能给出接近最优的聚类结果。
其实K-means的缺点的根本原因就是：对K个质心的初始选取比较敏感。质心选取得不好很有可能就会陷入局部最小值。
基于以上情况，有人提出了二分K-means算法来解决这种情况，也就是弱化初始质心的选取对最终聚类效果的影响。
二分K-means算法
在介绍二分K-means算法之前我们先说明一个定义：SSE(Sum of Squared Error),也就是误差平方和，它是用来度量聚类效果的一个指标。其实SSE也就是我们在K-means算法中所说的畸变函数：
SSE计算的就是一个cluster中的每个点到质心的平方差，它可以度量聚类的好坏。显然SSE越小，说明聚类效果越好。
二分K-means算法的主要思想：
首先将所有点作为一个簇，然后将该簇一分为二。之后选择能最大程度降低聚类代价函数(也就是误差平方和)的簇划分为两个簇。以此进行下去，直到簇的数目等于用户给定的数目k为止。
二分k均值算法的伪代码如下：
将所有数据点看成一个簇
当簇数目小于k时
对每一个簇
计算总误差
在给定的簇上面进行k-均值聚类(k=2)
计算将该簇一分为二后的总误差
选择使得误差最小的那个簇进行划分操作
Matlab 实现
function bikMeans
%%
clc
clear
close all
%%
biK = 4;
biDataSet = load(‘testSet.txt‘);
[row,col] = size(biDataSet);
% 存储质心矩阵
biCentSet = zeros(biK,col);
% 初始化设定cluster数量为1
numCluster = 1;
%第一列存储每个点被分配的质心，第二列存储点到质心的距离
biClusterAssume = zeros(row,2);
%初始化质心
biCentSet(1,:) = mean(biDataSet)
for i = 1:row
biClusterAssume(i,1) = numCluster;
biClusterAssume(i,2) = distEclud(biDataSet(i,:),biCentSet(1,:));
end
while numCluster
minSSE = 10000;
%寻找对哪个cluster进行划分最好，也就是寻找SSE最小的那个cluster
for j = 1:numCluster
curCluster = biDataSet(find(biClusterAssume(:,1) == j),:);
[spiltCentSet,spiltClusterAssume] = kMeans(curCluster,2);
spiltSSE = sum(spiltClusterAssume(:,2));
noSpiltSSE = sum(biClusterAssume(find(biClusterAssume(:,1)~=j),2));
curSSE = spiltSSE + noSpiltSSE;
fprintf(‘第%d个cluster被划分后的误差为：%f \n‘ , [j, curSSE])
if (curSSE
minSSE = curSSE;
bestClusterToSpilt = j;
bestClusterAssume = spiltClusterAssume;
bestCentSet = spiltCentSet;
end
end
bestClusterToSpilt
bestCentSet
%更新cluster的数目
numCluster = numCluster + 1;
bestClusterAssume(find(bestClusterAssume(:,1) == 1),1) = bestClusterToSpilt;
bestClusterAssume(find(bestClusterAssume(:,1) == 2),1) = numCluster;
% 更新和添加质心坐标
biCentSet(bestClusterToSpilt,:) = bestCentSet(1,:);
biCentSet(numCluster,:) = bestCentSet(2,:);
biCentSet
% 更新被划分的cluster的每个点的质心分配以及误差
biClusterAssume(find(biClusterAssume(:,1) == bestClusterToSpilt),:) = bestClusterAssume;
end
figure
%scatter(dataSet(:,1),dataSet(:,2),5)
for i = 1:biK
pointCluster = find(biClusterAssume(:,1) == i);
scatter(biDataSet(pointCluster,1),biDataSet(pointCluster,2),5)
hold on
end
%hold on
scatter(biCentSet(:,1),biCentSet(:,2),300,‘+‘)
hold off
end
% 计算欧式距离
function dist = distEclud(vecA,vecB)
dist = sum(power((vecA-vecB),2));
end
% K-means算法
function [centSet,clusterAssment] = kMeans(dataSet,K)
[row,col] = size(dataSet);
% 存储质心矩阵
centSet = zeros(K,col);
% 随机初始化质心
for i= 1:col
minV = min(dataSet(:,i));
rangV = max(dataSet(:,i)) - minV;
centSet(:,i) = repmat(minV,[K,1]) + rangV*rand(K,1);
end
% 用于存储每个点被分配的cluster以及到质心的距离
clusterAssment = zeros(row,2);
clusterChange = true;
while clusterChange
clusterChange = false;
% 计算每个点应该被分配的cluster
for i = 1:row
% 这部分可能可以优化
minDist = 10000;
minIndex = 0;
for j = 1:K
distCal = distEclud(dataSet(i,:) , centSet(j,:));
if (distCal
minDist = distCal;
minIndex = j;
end
end
if minIndex ~= clusterAssment(i,1)
clusterChange = true;
end
clusterAssment(i,1) = minIndex;
clusterAssment(i,2) = minDist;
end
% 更新每个cluster 的质心
for j = 1:K
simpleCluster = find(clusterAssment(:,1) == j);
centSet(j,:) = mean(dataSet(simpleCluster‘,:));
end
end
end
算法迭代过程如下
biCentSet =
-0.1036 0.0543
0 0
0 0
0 0
第1个cluster被划分后的误差为：792.916857
bestClusterToSpilt =
1
bestCentSet =
-0.2897 -2.8394
0.0825 2.9480
biCentSet =
-0.2897 -2.8394
0.0825 2.9480
0 0
0 0
第1个cluster被划分后的误差为：409.871545
第2个cluster被划分后的误差为：532.999616
bestClusterToSpilt =
1
bestCentSet =
-3.3824 -2.9473
2.8029 -2.7315
biCentSet =
-3.3824 -2.9473
0.0825 2.9480
2.8029 -2.7315
0 0
第1个cluster被划分后的误差为：395.669052
第2个cluster被划分后的误差为：149.954305
第3个cluster被划分后的误差为：393.431098
bestClusterToSpilt =
2
bestCentSet =
2.6265 3.1087
-2.4615 2.7874
biCentSet =
-3.3824 -2.9473
2.6265 3.1087
2.8029 -2.7315
-2.4615 2.7874
最终效果图
运用二分K-means算法进行聚类的时候，不同的初始质心聚类结果还是会稍微有点不同，因为实际上这也只是弱化随机质心对聚类结果的影响而已，并不能消除其影响，不过最终还是能收敛到全局最小。
$(function () {
$(‘pre.prettyprint code‘).each(function () {
var lines = $(this).text().split(‘\n‘).length;
var $numbering = $(‘‘).addClass(‘pre-numbering‘).hide();
$(this).addClass(‘has-numbering‘).parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($(‘
‘).text(i));
};
$numbering.fadeIn(1700);
});
});
本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标人工智能机器学习频道！
相关文章：
开始整SWF文字高亮显示——第一步：解析PDFToFlex源文件（修改补充版）
为了深入实现PDF转成SWF后的关键字高亮显示的问题，我需要解析PDFToFlex源文件，已经看到Flex 的新类：flash.net.URLStream 和 flash.utils.endian，我会全面学习我遇到的新类的。本来当天晚上就准备把分析的成果与大家分享的&#…
【计算机视觉】EmguCV学习笔记（3）ROI区域图像叠加以及初级图像混合
如果喜欢这里的内容，你能够给我最大的帮助就是转发，告诉你的朋友，鼓励他们一起来学习。 If you like the content here, you can give me the greatest help is forwarding, tell your friends, encourage them to learn together.
优先发展智慧旅游与智慧交通领域
三亚借助互联网技术，经过两个五年的规划建设，智慧城市建设成效初显。今天，三亚通过市长专题办公会议讨论明确，下一步，三亚智慧城市建设将向智慧旅游、智慧交通等领域寻找突破口，将三亚建设成为更高效率的便…
php redis管理系统,php+redis实现小型的用户管理系统
1、redis.php ，用于连接redis数据库//实例化$redis new Redis();//连接服务器$redis->connect("localhost");//授权$redis->auth("lamplijie");2、add.php，用于添加用户用户名：密码：年龄：3…
在虚拟机中 windows 2003 装.net framework 3.5 出现问题.
错误信息: [11/27/09,08:52:50] Microsoft .NET Framework 2.0a: [2] Error: Installation failed for component Microsoft .NET Framework 2.0a. MSI returned error code 1603[11/27/09,08:53:01] WapUI: [2] DepCheck indicates Microsoft .NET Framework 2.0a is not inst…
python——赋值与深浅拷贝
结合python变量存储的特性从内存的角度来谈一谈赋值和深浅拷贝~~~预备知识一——python的变量及其存储在详细的了解python中赋值、copy和deepcopy之前，我们还是要花一点时间来了解一下python内存中变量的存储情况。在高级语言中，变量是对内存及其地址的抽…
【计算机视觉】EmguCV学习笔记（4）分离颜色通道以及多通道图像混合
如果喜欢这里的内容，你能够给我最大的帮助就是转发，告诉你的朋友，鼓励他们一起来学习。 If you like the content here, you can give me the greatest help is forwarding, tell your friends, encourage them to learn together.
oracle的存储过程调试,oracle 运行普通方式及调试debug方式存储过程性能区别
调试某一存储过程时，在plsql developer debug调试执行时，20多分钟都执行不完，后分析如下：1,查询调试会话运行存储过程的对应sqlselect sid,serial#,event,status,sql_id,prev_sql_id,action,module from v$session where suser12…
关于一个无限分类的多选,单选相关的控件
最近在一个项目中需要用到无限分类的平铺多选,单选这些功能,查了一些资料,结果大都是一些用IFrame这样的东西做的,虽然用起来直观,但本人更喜欢集成控件形式的,于是抽了一些时间做了一个.思路是利用控件JS不同的无限分类表,支持一页多控件,支持不同的无限分类表.效果图如下: 当…
ubuntu如何修改字符集编码
系统支持编码的修改如下：1. 使用如下命令查看系统支持的字符集cat /usr/share/i18n/SUPPORTED说明：查看系统支持的字符集，你需要注意的是支持字符集的格式，如对中文会有以下一些显示（我的系统如此，我不知是…
【怎样写代码】小技巧 -- 关于引用类型的两种转换方式
如果喜欢这里的内容，你能够给我最大的帮助就是转发，告诉你的朋友，鼓励他们一起来学习。 If you like the content here, you can give me the greatest help is forwarding, tell your friends, encourage them to learn together.
Oracle中的iot_type,oracle IOT表学习
IOT: Index-Organized Table索引组织表含义即将表结构整体放入索引中，且是按照主键进行排序的。创建：create table emp_iot(emp_no int,emp_name varchar2(100),dept_no int,salary number(10,2),constraint pk_empi primary key(emp_no, emp_name, dept…
如何查询并解决80端口 (转)
转自：http://www.cnblogs.com/chaofan/archive/2009/12/02/1615691.html 今天在使用apache的时候80端口被占用了，解决办法如下 在命令行里输入netstat -aon|findstr "80" 查看使用了80端口的tcp pid pid为1564 在任务管理器中将该进程结束掉即…
深证信息等三方拟联合开展大数据研究
昨日，深圳证券信息有限公司（下称“深证信息”）、泛欧交易所、北京新浪互联信息服务有限公司（下称“新浪网”）联合签署了合作备忘录，三方将基于各自优势在互联网大数据应用研究、股票指数开发、跨境指数产品…
【怎样写代码】小技巧 -- 关于方法中修饰形参的关键词
如果喜欢这里的内容，你能够给我最大的帮助就是转发，告诉你的朋友，鼓励他们一起来学习。 If you like the content here, you can give me the greatest help is forwarding, tell your friends, encourage them to learn together.
oracle schedule stop,Oracle调度Schedule特性（第八部分）-Windows和Window Groups
哈哈，关于schedule的内容还没完，本章讲Windows，通常说的Windows是指盖首富的操作系统，而此处所说的Windows，是指SCHEDULER特性中的一个子项。在SCHEDULER中，WINDOW对应的是一个时间窗口的概念。我们知道普通…
CSS入门-五个简单,但有用的CSS属性
今天说的这5个CSS属性,你可能会很熟悉,但是你可能会很少会去使用.这个教程所讲得不是关于CSS3的属性,而是依旧使用CSS2属性来说明,这些属性广泛的被各种浏览器所支持:clip,min-height,white-space,cursor和display.所以不要错过这个教程,因为你会发现他们是多么的有用.1.CSS Cl…
借助线下渠道逆袭？小米的愿望恐成镜花水月！
小米5的发布，让久未有波澜的中国手机市场又泛起几点涟漪。 而在小米5发布的同时，小米销售方式的改变，也让人眼前一亮。小米，已经由最初的“反传统”，开始向“传统”靠拢了。 小米5发布会上，小米告诉大家&am…
【怎样写代码】函数式编程 -- Lambda表达式（一）：引出
如果喜欢这里的内容，你能够给我最大的帮助就是转发，告诉你的朋友，鼓励他们一起来学习。 If you like the content here, you can give me the greatest help is forwarding, tell your friends, encourage them to learn together.
oracle创建DBA角色命令,oracle常用DBA命令
1.查看用户拥有的数据库对象Sql代码select object_name from user_objects;2.查看约束信息Sql代码select constraint_name from user_constraints;3.查看用户所拥有的表Sql代码select table_name from user_tables;或Sql代码select *from tab;4.查看用户所拥有的视图Sql代码sel…
Ext JS Designer 1.0.5 发布
ExtJS官方Blog上发布了Ext JS Designer新版本，版本号为1.0.5，这个版本添加了不少新特性，如直接修改title，config参数搜索等等。虽然这个版本仍然不支持代码生成，不过另一则文章则让人感觉代码生成的日子也不远了。 此版…
【怎样写代码】函数式编程 -- Lambda表达式（二）：C#常用委托
如果喜欢这里的内容，你能够给我最大的帮助就是转发，告诉你的朋友，鼓励他们一起来学习。 If you like the content here, you can give me the greatest help is forwarding, tell your friends, encourage them to learn together.
前端设计（一）
前端设计（一）
oracle time格式化比较,ORACLE DATE和TIMESTAMP数据类型的比较(二) (转)
ORACLE DATE和TIMESTAMP数据类型的比较(二) (转)[more]原著作者：James KmannTIMESTAMP数据的格式化显示和DATE 数据一样。注意，to_char支持date和timestamp，但是trunc却不支持TIMESTAMP数据类型。这已经清楚表明了在当两个时间的差别极度重要…
模式实例之——外观实例
场景：银行柜员机取钱或存钱描述：从银行的柜员机取了100块钱（一）子系统/// <summary>/// 子系统抽象/// </summary>public interface IDo{void ShowMessage(string strMemo);}（二）各个子系统///…
cnpm install -g generator-gulp-webapp yo gulp-webapp test-gulp-webapp
2019独角兽企业重金招聘Python工程师标准>>> cnpm install -g generator-gulp-webapp yo gulp-webapp test-gulp-webapp 转载于:https://my.oschina.net/yizhichao/blog/1189216
【怎样写代码】函数式编程 -- Lambda表达式（三）：LINQ初步
如果喜欢这里的内容，你能够给我最大的帮助就是转发，告诉你的朋友，鼓励他们一起来学习。 If you like the content here, you can give me the greatest help is forwarding, tell your friends, encourage them to learn together.
oracle触发器初始化,oracle – 触发器无法初始化变量
我有触发审计,它存储了对任何EMP表行执行的操作.这个触发器工作正常,除了在某些情况下(很少发生,我无法确定确切的条件)它给了我Oracle错误：ORA-01400：无法插入NULL(“MY_SCHEMA”.“HIST_EMP”.“操作”)CREATE OR REPLACE TRIGGER HIST_EMP_AIUDAFTER …
翻页导航条页码计算方法
在开发搜索引擎等应用时，提供一个翻页导航条是必须的。我看过网上一些相关的代码，搞得很复杂。晕~~~ 其实其数学计算公式非常简单，本文提供两种最常用的算法。翻页式样式如下。每次显示10个页码，并提供"前十"、"后…
ArcGIS水文分析实战教程（9）雨量计算与流量统计
ArcGIS水文分析实战教程（9）雨量计算与流量统计 本章导读：降水是水文循环中重要的一环，降水包括雨、雪、雾、露、雹等，本章介绍的是降雨的环节。通过雨量站与插值的方式，实现雨量的空间分布就算，…