首先分清聚类和分类的区别:
分类——监督学习算法,需要给定训练数据
聚类——无监督学习算法,无训练数据。
聚类分为 层次方法和非层次方法:
层次方法——最后形成一棵tree,每个node或者有k个分支,或者是叶子节点。( 过程似huffman tree)
非层次方法——是一个迭代过程,直至满足某个阀值退出。(主要包括k-mean 和 EM算法)
k-mean算法的步骤:(每个样本只能属于一个聚类)
1)随机选出k个centroid(质心)
2)将每个样本分配给与之距离最近的centroid
3)重新计算centroid
4)重复2) 3)直至centroid所对应的set不变
EM算法:(每个样本可以属于不同的聚类,但概率不同)
理论基础—计算极大似然估计,需要求似然函数的极值。输入是样本,但这个样本并不是完整数据,它只是观测数据。
完整数据(Z)包括观测数据(X)和未知数据(Y)。
log似然函数:ℓ ( θ; Z ) = log p( Z|θ)=log
p( X,Y|θ)-----(1)
它的步骤跟EM所代表的单词有关,
<wbr><wbr><wbr><wbr>E——expectation,<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>已知: 观测数据X,<span style="word-wrap:normal; word-break:normal; line-height:17px; font-size:11pt">参数θ的当前值</span><span style="word-wrap:normal; word-break:normal; line-height:17px; font-size:11pt">θt</span><br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><span style="word-wrap:normal; word-break:normal; line-height:17px; font-size:11pt">未知:Y<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>对公式(1)求Y的期望,</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></span>得表达式Q(<span style="word-wrap:normal; word-break:normal; line-height:17px; font-size:11pt">θ,</span><span style="word-wrap:normal; word-break:normal; line-height:17px; font-size:11pt">θt</span>),
Q中不含有变量Y。<br><wbr><wbr><wbr><wbr>M——maximization,对E步得到的Q(<span style="word-wrap:normal; word-break:normal; line-height:17px; font-size:11pt">θ,</span><span style="word-wrap:normal; word-break:normal; line-height:17px; font-size:11pt">θt</span>)求极大值,<br><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><span style="word-wrap:normal; word-break:normal; line-height:17px; font-size:11pt">即θt+1 =</span>argmax Q(<span style="word-wrap:normal; word-break:normal; line-height:17px; font-size:11pt">θ,</span><span style="word-wrap:normal; word-break:normal; line-height:17px; font-size:11pt">θt
)</span><br><wbr><wbr><wbr><wbr>每次参数更新会增加非完整似然函数值<br><wbr><wbr><wbr><wbr>重复E、M两步,直至似然函数收敛到局部极大值。<br><br>
EM会收敛到局部极值,但不保证收敛到全局最优;对初值很敏感,需要一个好的、快速的初始化过程。<br></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
<wbr></wbr>
<wbr></wbr>
k-mean聚类算法如下:
1.<wbr><wbr><wbr><wbr><wbr><wbr>从数据点中,随机选取k个数据中心作为初始的聚类中心。例如k=3,则选择3个数据点</wbr></wbr></wbr></wbr></wbr></wbr>
2.<wbr><wbr><wbr><wbr><wbr><wbr>分别计算每一个点到k个中心点的距离(本文计算的是欧式距离),如果当前计算的数据点离第i个(i=1,2,…,k)中心点最近,则把当前点归到第i类.</wbr></wbr></wbr></wbr></wbr></wbr>
3.<wbr><wbr><wbr><wbr><wbr><wbr>重新计算k个聚类中心点。计算方式如下,如果第i类有n个数据点,则第i类新的中心为:</wbr></wbr></wbr></wbr></wbr></wbr>
<wbr><a href="http://photo.blog.sina.com.cn/showpic.html#blogid=48b8276f01013us7&url=http://s7.sinaimg.cn/orignal/48b8276ftc1ef8902ca86" target="_blank" style="text-decoration:none; color:rgb(27,113,155)"></a><br><a href="http://photo.blog.sina.com.cn/showpic.html#blogid=48b8276f01013us7&url=http://s3.sinaimg.cn/orignal/48b8276ftc1ef8bcd5472" target="_blank" style="text-decoration:none; color:rgb(27,113,155)"><img src="http://s3.sinaimg.cn/bmiddle/48b8276ftc1ef9044f7c3&690" name="image_operate_65101339134613281" alt="分类与聚类" title="分类与聚类" style="margin:0px; padding:0px; border:0px; list-style:none"></a><br><br><br></wbr>
<wbr><wbr><wbr><wbr>4.如果新的聚类中心跟上一次的聚类中心比较变化小于某值算法结束,否则转到第二步。</wbr></wbr></wbr></wbr>
聚类结果如下:
<wbr></wbr>
代码如下:http://download.csdn.net/source/3374443
load gaussdata; %由于我先前生成好了,直接load进来
maxiter = 50;<wbr><wbr>%设定最大频数</wbr></wbr>
iter = 1;
num = size(X,2);<wbr>%num为数据点个数</wbr>
index = randperm(num); %产生1到num个数字的一个随机排列
center = X(:,index(1:3)); %选择出3个初始的聚类中心
�nter = X(:,1:3);
old = center;<wbr><wbr><wbr><wbr><wbr><wbr>%记录旧的聚类中心</wbr></wbr></wbr></wbr></wbr></wbr>
<wbr></wbr>
hold on ;
plot(X(1,:),X(2,:),'g.');<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>%绘制数据点</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
plot(center(1,:),center(2,:),'ro'); %绘制数据中心
title(num2str(iter));<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>%显示迭代步数</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
hold off;
xnum = size(X,2);
cdim = size(center,2);
while iter<=maxiter
<wbr><wbr>clf;</wbr></wbr>
<wbr><wbr>hold on;</wbr></wbr>
<wbr><wbr>5-39行计算每一个点到k个中心的距离,一个很神奇的技巧,自己想吧,呵呵</wbr></wbr>
<wbr><wbr>sumX = sum(X.^2,1);</wbr></wbr>
<wbr><wbr>sumC = sum(center.^2,1);</wbr></wbr>
<wbr><wbr>XY = (2*X'*center)';</wbr></wbr>
<wbr><wbr>distance = repmat(sumX,cdim,1)+repmat(sumC',1,xnum)-XY;</wbr></wbr>
<wbr><wbr>[v,idx] = min(distance,[],1);<wbr><wbr>%求出数据点到哪一个中心的距离最近</wbr></wbr></wbr></wbr>
<wbr><wbr>Y = idx;<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>%对数据点进行分类</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
<wbr><wbr>idx1 = find(idx==1);</wbr></wbr>
<wbr><wbr>idx2 = find(idx==2);</wbr></wbr>
<wbr><wbr>idx3 = find(idx==3);</wbr></wbr>
<wbr><wbr>%下面三行计算出新的聚类中心</wbr></wbr>
<wbr><wbr>center(:,1) = mean(X(:,idx1),2);</wbr></wbr>
<wbr><wbr>center(:,2) = mean(X(:,idx2),2);</wbr></wbr>
<wbr><wbr>center(:,3) = mean(X(:,idx3),2);</wbr></wbr>
<wbr><wbr>title(num2str(iter));</wbr></wbr>
<wbr><wbr>plot_data(X,Y,center);</wbr></wbr>
<wbr><wbr>hold off;</wbr></wbr>
<wbr><wbr>pause(0.1);</wbr></wbr>
<wbr><wbr>error = sum((center(:,1)-old(:,1)).^2,1);<wbr><wbr><wbr>%计算迭代中止条件</wbr></wbr></wbr></wbr></wbr>
<wbr><wbr>if error<0.000001</wbr></wbr>
<wbr><wbr><wbr><wbr><wbr>break;</wbr></wbr></wbr></wbr></wbr>
<wbr><wbr>end</wbr></wbr>
<wbr><wbr>old = center;</wbr></wbr>
<wbr><wbr>iter = iter+1;</wbr></wbr>
end
分享到:
相关推荐
回归、分类与聚类:三大方向剖解机器学习算法的优缺点
使用数据集选自机器学习存储库UCI,数据集标题为心脏病数据库,数据采集 自克利夫兰诊所基金会、...进行数据的分类与聚类操作,包括各种分类算法的比较、各种聚类算法的实现,以及绘制决策树和神经网络结构图等内容。
文本挖掘中的分类与聚类研究,有意向学习nlp的同学可以学习一下。
数据挖掘大作业-数据探索性分析与预处理,关联规则挖掘,分类与聚类+源代码+文档说明 - 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审...
临床大数据挖掘线下课程 第3章 数据挖掘方法-分类与聚类 共134页.ppt 临床大数据挖掘线下课程 第4章 数据挖掘方法-关联规则与贝叶斯网络 共44页.ppt 临床大数据挖掘线下课程 第5章 数据挖掘方法-列线图的绘制 共28页...
退火软近邻丢失的文本分类与聚类_Text Classification and Clustering with Annealing Soft Nearest Neighbor Loss.pdf
聚类需要解决的问题是将已给定的若干无标记的模式聚集起来使之成为有意义的聚类,聚类是在预先不知道目标数据库到底有多少类的情况下,希望将所有的记录组成不同的类或者说聚类,并且使得在这种分类情况下,以某种...
可靠的方法去判断两个时间序列是否相似,截下来便可以使用k-NN算法进行分类。根据经验,最优解一般出现在k=1的时候。下面就利用DTW欧氏距离的1-NN算法。在该算法中,train是时间序列示例的训练集,其中时间序列所属...
使用了PCA、KPCA、LDA、KLDA四种算法进行数据预处理,使用SVM、逻辑回归、ANN三种方法对预处理与未预处理的数据进行了分类与评估,使用FCM方法对预处理与未预处理的数据进行了聚类与评估,完整地完成了项目的全部...
档摘要本分类、聚类1. 本表示(构建本特征向量)将结构化的本内容转化成结构化的特征向量形式,作为分类或聚类模型的输建特征空间每个档被表示为个特征向量,其特征向量
使用了PCA、KPCA、LDA、KLDA四种算法进行数据预处理,使用SVM、逻辑回归、ANN三种方法对预处理与未预处理的数据进行了分类与评估,使用FCM方法对预处理与未预处理的数据进行了聚类与评估,完整地完成了项目的全部...
C++写的自然语言处理,其中包括聚类和分类两部分。
①文档聚类可以作为多文档自动文摘等自然语言处理应用的预处理步骤,比较典型的例子是哥伦比亚大学开发的多文档文摘系统Newsblaster[20] ②对用户感兴趣的
Spark Mllib学习敲代码
java实现的文本聚类使用了kmeans算法
摘要:随着当今世界信息化时代的迅猛发展,大量的数据信息呈现出爆炸式的增长态势,而且随着互联网的进步,这些海量数据的传播速度也日益加快。对于这些数据的处理是目前亟
使用了PCA、KPCA、LDA、KLDA四种算法进行数据预处理,使用SVM、逻辑回归、ANN三种方法对预处理与未预处理的数据进行了分类与评估,使用FCM方法对预处理与未预处理的数据进行了聚类与评估,完整地完成了项目的全部...
使用了PCA、KPCA、LDA、KLDA四种算法进行数据预处理,使用SVM、逻辑回归、ANN三种方法对预处理与未预处理的数据进行了分类与评估,使用FCM方法对预处理与未预处理的数据进行了聚类与评估,完整地完成了项目的全部...
分类和聚类的区别