Lloyd算法

收录时间:2014-04-19
资源分类:Matlab 工具:MATLAB 7.14 (R2012a)

劳埃德算法从样本初始分配开始重复执行步骤

1所有点Voronoi图计算

  2,Voronoi图每个单元被集成形心进行计算

  3,将每一个移动到它的Voronoi单元的质心。

劳埃德算法首先把输入点分成k个初始化分组,可以是随机的或者使用一些启发式数据。然后计算每组的中心点,根据 中心点的位置把对象分到离它最近的中心,重新确定分组。继续重复不断地计算中心并重新分组,直到收敛,即对象不再改变分组(中心点位置不再改变)。
劳埃德算法和k平均通常是紧密联系的,但是在实际应用中,劳埃德算法是解决k平均问题的启发式法则,对于某些起始点和重心的组合,劳埃德算法可能实际上收敛于错误的结果。(上面函数中存在的不同的最优解)
虽然存在变异,但是劳埃德算法仍旧保持流行,因为它在实际中收敛非常快。实际上,观察发现迭代次数远远少于点的数量。然而最近,David Arthur和Sergei Vassilvitskii提出存在特定的点集使得k平均算法花费超多项式时间达到收敛。

Lloyd's Algorithm

Runs Lloyd's algorithm on the particles at xy positions (Px,Py) within the boundary polygon crs for numIterations iterations.

showPlot = true will display the results graphically.

 

Lloyd's algorithm starts with an initial distribution of samples or points and consists of repeatedly executing one relaxation step:

  1. The Voronoi diagram of all the points is computed.

  2. Each cell of the Voronoi diagram is integrated and the centroid is computed.

  3. Each point is then moved to the centroid of its Voronoi cell.

 

Run with no input to see example.

 

Uses http://www.mathworks.com/matlabcentral/fileexchange/34428-voronoilimit,

which requires the Polybool function of the mapping toolbox to run.

文件下载列表
lloydsAlgorithm.zip (3.57KB)  
附件内容(只显示2中的1个)
lloydsAlgorithm.m  
标签: Lloyd算法 
更多

目前尚无评论

用户反馈   关于我们
Copyright (©) ZHIHUISHI.COM 2013 All Rights Reserved.
京ICP备18060134号-3