Showing posts with label KMeans. Show all posts
Showing posts with label KMeans. Show all posts

Friday, November 21, 2014

K-Means++ | 愈宅屋


K-Means++ | 愈宅屋
根据维基上的说法,K-Means++这个算法步骤大概如下:
  1. 在已有的所有点中随机选取一个点,将其加入初始点。
  2. 对于所有的点,计算出他们的D值,D值就是每个点到距离他们最近的初始点的距离的平方。
  3. 对所有点选取下一个点加入初始点的集合,每个点被选取的概率正比于他们的D值。
  4. 如果初始点集合数目没有达到预定的数目,回到2,否则到5。
  5. 执行K-Means算法

我们考虑二维点集的聚类问题,K-Means算法是随便选择初始点,那么就会有一定的概率在一个Cluster内部出现两个或者更多的初始点,还有一种可能就是初始点出现在两个Cluster的正中间这种,反正就是会导致算法不是很有效,一个最常见的失败的聚类经常就是在某些地方把两类聚为一类,然后在另外一些地方把一类分为两类。但是呢,K-Means++算法可以很有效的避免这种状况,比如我在某一Cluster中间已经出现了一个初始点了,那么这个Cluster的点到这个初始点的距离就很小,平方后D值就更小了,所以这里面的点被选为下一个Cluster的概率就会很小。大部分情况下,K-Means++初始化完成之后每个Cluster就会有一个初始化点,这种时候我们就知道里聚类完成也差不多了。所以呢,K-Means++算法也可以很好地降低K-Means算法的迭代次数,换言之,就是算法的时间消耗。

Code:
http://www.kylen314.com/archives/755
Read full article from K-Means++ | 愈宅屋

Improved Seeding For Clustering With K-Means++ | The Data Science Lab


Improved Seeding For Clustering With K-Means++ | The Data Science Lab
If the target distribution is disjointedly clustered and only one instantiation of Lloyd’s algorithm is used, the danger exists that the local minimum reached is not the optimal solution.

This algorithm comes with a theoretical guarantee to find a solution that is O(log k) competitive to the optimal k-means solution.
  • choose an initial center c_1 uniformly at random from X. Compute the vector containing the square distances between all points in the dataset and c_1: D_i^2 = ||\mathrm{x}_i - c_1 ||^2
  • choose a second center c_2 from X randomly drawn from the probability distribution D_i^2 / \sum_j D_j^2
  • recompute the distance vector as D_i^2 = \mathrm{min} \left(||\mathrm{x}_i - c_1 ||^2, ||\mathrm{x}_i - c_2 ||^2\right)
  • choose a successive center c_l and recompute the distance vector as D_i^2 = \mathrm{min} \left(||\mathrm{x}_i - c_1 ||^2, \ldots, ||\mathrm{x}_i - c_l ||^2\right)
  • when exactly k centers have been chosen, finalize the initialization phase and proceed with the standard k-means algorithm
class KPlusPlus(KMeans):
    def _dist_from_centers(self):
        cent = self.mu
        X = self.X
        D2 = np.array([min([np.linalg.norm(x-c)**2 for c in cent]) for x in X])
        self.D2 = D2
 
    def _choose_next_center(self):
        self.probs = self.D2/self.D2.sum()
        self.cumprobs = self.probs.cumsum()
        r = random.random()
        ind = np.where(self.cumprobs >= r)[0][0]
        return(self.X[ind])
 
    def init_centers(self):
        self.mu = random.sample(self.X, 1)
        while len(self.mu) < self.K:
            self._dist_from_centers()
            self.mu.append(self._choose_next_center())
 
    def plot_init_centers(self):
        X = self.X
        fig = plt.figure(figsize=(5,5))
        plt.xlim(-1,1)
        plt.ylim(-1,1)
        plt.plot(zip(*X)[0], zip(*X)[1], '.', alpha=0.5)
        plt.plot(zip(*self.mu)[0], zip(*self.mu)[1], 'ro')
        plt.savefig('kpp_init_N%s_K%s.png' % (str(self.N),str(self.K)), \
                    bbox_inches='tight', dpi=200)

 Then, the successive centers are picked, stopping when we have K=5 of them. The procedure to choose the next most suitable center is coded up in the _choose_next_center() function. As we described above, the next center is drawn from a distribution given by the normalized distance vector D_i^2 / \sum_j D_j^2. To implement such a probability distribution, we compute the cumulative probabilities for choosing each of the N points inX. These cumulative probabilities are partitions in the interval [0,1] with length equal to the probability of the corresponding point being chosen as a center, as explained in this stackoverflow thread. Therefore, by picking a random value r \in [0,1] and finding the point corresponding to the segment of the partition where that r value falls, we are effectively choosing a point drawn according to the desired probability distribution. On the right is a plot showing the results of the algorithm for 200 points and 5 clusters.
Read full article from Improved Seeding For Clustering With K-Means++ | The Data Science Lab