Monthly Archives: May 2015

JavaScript版k-means++算法实现

按照维基百科的定义,k-means为:把n个点(可以是样本的一次观察或一个实例)划分到k个聚类中,使得每个点都属于离他最近的均值(此即聚类中心)对应的聚类。 k-means的过程为: 1、随机选取k个中心 2、将数据点依据中心归类为k个聚集 3、选择每个聚集的中心,作为新的中心 4、重复2、3步,直到聚集不再发生变化 k-means的缺陷为第一步的随机选择中心。如果数据点为[1, 5, 6, 9, 10]。k-means的结果可能为[[1], [5, 6], [9, 10]],也可能为[[1, 5, 6], [9], [10]]。从概念上看,这两个结果都是正确的,但后者很明显不是我们想要的。 k-means++改进了第一次选取中心的方法,使得第一次选取的中心之间间距够大。k-means++第一次选取中心的过程为: 1、随机选取一个数据点作为第一个中心 2、计算每个数据点到最近的中心的距离 3、选取上一步最后距离最大的数据点,作为新的中心 4、重复2、3步,直到选取到k个中心 下面是实现,包含了k-means和k-means++。 kmeans函数第三个参数为一个计算数据点权值的函数,用来计算数据点间距离和聚集平均权值。缺点是权值函数会被多次应用于同一数据点上。 exports = module.exports = kmeans; //随机取k个中心 function randomCentroids(points, k, weightFun) { var centroids = … Continue reading

Posted in Uncategorized | Tagged | Leave a comment