首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 移动开发 > 移动开发 >

kmeans算法原理及opencv中的兑现

2012-10-11 
kmeans算法原理及opencv中的实现算法的目的:数据分类,聚类,识别对象和标准:输入:n个数据对象输出:k个类别,

kmeans算法原理及opencv中的实现
算法的目的:
数据分类,聚类,识别

对象和标准:
输入:n个数据对象
输出:k个类别, 且满足方差最小的k个聚类,聚类方差度量

每个对象与聚类的相似度:一般是采用各个对象到聚类中心(一般是均值中心)的距离,距离哪个中心近,就是与哪个类的相似度高。
聚类的紧密度度量(聚类好坏的度量):所有对象到各自聚类中心的方差和。

基本算法步骤:
初始化:从 n个数据对象任意选择 k 个对象作为初始聚类中心;

迭代:
    1. 根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行分类;
    2. 由新的分类数据,重新计算每个(有变化)聚类的均值(中心对象);
    3. 计算标准测度函数,当满足一定条件,如函数收敛时,则算法终止;如果条件不满足则循环执行。如opencv中,每次迭代,最大的聚类中心位移max_center_shift < criteria.epsilon小于精度要求时,就结束迭代。以及迭代次数超过设定的最大值时,也结束 iter >= criteria.maxCount。

结束。计算方差,及labels每个对象的分类结果,返回。

算法的时间复杂度上界为O(n*k*t), 其中t是迭代次数。属于非监督学习方法。

OpenCV中增加了参数:
attempts:使用不同的初始化条件,进行分类的次数
flag: KMEANS_RANDOM_CENTERS, KMEANS_PP_CENTERS, KMEANS_USE_INITIAL_LABELS

增加以上参数的目的,是防止kmeans算法陷入局部最优,即分类的结果不是最好的。局部最优的示例:

kmeans算法原理及opencv中的兑现

横向分类,纵向分类分别是两种分类结果。显然,横向分类是局部最优。


而增加尝试次数,和选取不同的初始化中心可以解决这个问题。

KMEANS_PP_CENTERS是采用Arthur & Vassilvitskii (2007) k-means++: The Advantages of Careful Seeding获取初始化种子点。
其思想是:
在直觉上,k个初始聚类中心应该远离彼此,所以第一簇中心均匀地选择随机从正在群集的数据点,之后,每个后续的群集中心应该从剩余的数据点中选择,且剩余点:
 the remaining data points with probability proportional to its distance squared to the point's closest cluster center.(这句话没理解了)

opencv对新的中心选取,多次尝试,取最好的结果,如下:
            ci是随机获取的新的数据中心。
            for( i = 0; i < N; i++ )
            {
                tdist2[i] = std::min(distance(data + step*i, data + step*ci, dims), dist[i]);
                s += tdist2[i];
            }
            
            if( s < bestSum )
            {
                bestSum = s;
                bestCenter = ci;
                std::swap(tdist, tdist2);
            }

其聚类精度明显优于传统的随机选择种子的方法,且计算速度也比较快。而对于更大型的数据集,kmeans++需要进一步扩展,才能获取更好的表现,即kmeans是高度可扩展的。

KMEANS_USE_INITIAL_LABELS是第一次采用用户自己设置的初始化的中心点进行运算,而后面的尝试则采用随机算法(或半随机)选取的中心。









热点排行