大数据经典算法Kmeans讲解.ppt

大数据经典算法Kmeans讲解
第一页，共30页
主要内容：
Kmeans实战
聚类算法简介
Kmeans算法详解
Kmeans算法的缺陷及若干改进
Kmeans的单机实现与分布式实现策略
第二页，共30页
聚类算法简介
1
2
3
聚类的目标：将一组向量分成若干组，组内数据是相似的，而组间数据是有较明显差异。
与分类区别：分类与聚类最大的区别在于分类的目标事先已知，聚类也被称为无监督机器学习
聚类手段：传统聚类算法 ①划分法 ②层次方法 ③基于密度方法 ④基于网络方法 ⑤基于模型方法
第三页，共30页
什么是Kmeans算法？
Q1：K是什么？A1：k是聚类算法当中类的个数。
Summary：Kmeans是用均值算法把数据分成K个类的算法！
Q2：means是什么？A2：means是均值算法。
第四页，共30页
Kmeans算法详解（1）
步骤一：取得k个初始初始中心点
第五页，共30页
Kmeans算法详解（2）
Min of three
due to the EuclidDistance
步骤二：把每个点划分进相应的簇
第六页，共30页
Kmeans算法详解（3）
Min of three
due to the EuclidDistance
步骤三：重新计算中心点
第七页，共30页
Kmeans算法详解（4）
步骤四：迭代计算中心点
第八页，共30页
Kmeans算法详解（5）
步骤五：收敛
第九页，共30页
Kmeans算法流程
从数据中随机抽取k个点作为初始聚类的中心，由这个中心代表各个聚类
计算数据中所有的点到这k个点的距离，将点归到离其最近的聚类里
调整聚类中心，即将聚类的中心移动到聚类的几何中心（即平均值）处，也就是k-means中的mean的含义
重复第2步直到聚类的中心不再移动，此时算法收敛
最后kmeans算法时间、空间复杂度是：
时间复杂度：上限为O(tKmn)，下限为Ω（Kmn）其中，t为迭代次数，K为簇的数目，m为记录数，n为维数
空间复杂度：O((m+K)n)，其中，K为簇的数目，m为记录数，n为维数
第十页，共30页