Python中k-means聚类实现，内存不足

Question

注意：问题底部有更新/解决方案

我正在开发一个产品推荐系统，想根据用户的产品偏好来对他们进行分类，首先使用的是k-means聚类算法。

我的数据是一个字典，格式如下：

prefs = {
    'user_id_1': { 1L: 3.0f, 2L: 1.0f, },
    'user_id_2': { 4L: 1.0f, 8L: 1.5f, },
}

这里的产品ID是长整型，评分是浮点型。数据比较稀疏。目前我大约有60,000个用户，其中大多数用户只对少数产品进行了评分。为了简化代码，我使用了defaultdict(float)来实现每个用户的评分字典。

我的k-means聚类算法的实现如下：

def kcluster(prefs,sim_func=pearson,k=100,max_iterations=100):
    from collections import defaultdict
    
    users = prefs.keys()       
    centroids = [prefs[random.choice(users)] for i in range(k)]
   
    lastmatches = None
    for t in range(max_iterations):
        print 'Iteration %d' % t
        bestmatches = [[] for i in range(k)]

        # Find which centroid is closest for each row        
        for j in users:
            row = prefs[j]
            bestmatch=(0,0)
            
            for i in range(k):
                d = simple_pearson(row,centroids[i])
                if d < bestmatch[1]: bestmatch = (i,d)
            bestmatches[bestmatch[0]].append(j)
        
        # If the results are the same as last time, this is complete
        if bestmatches == lastmatches: break
        lastmatches=bestmatches
        
        centroids = [defaultdict(float) for i in range(k)]
        
        #  Move the centroids to the average of their members
        for i in range(k):
            len_best = len(bestmatches[i])
                                    
            if len_best > 0:             
                items = set.union(*[set(prefs[u].keys()) for u in bestmatches[i]])
                
                for user_id in bestmatches[i]:
                    row = prefs[user_id]
                    for m in items:
                        if row[m] > 0.0: centroids[i][m]+=(row[m]/len_best)       
    return bestmatches

从我目前的观察来看，算法在处理第一部分（将每个用户分配到最近的中心点）时运行得不错。

问题出现在下一步，计算每个聚类中每个产品的平均评分，并将这些平均评分作为下一轮的中心点。

基本上，在算法甚至还没能完成第一个聚类（i=0）的计算时，就因为这行代码出现了内存错误：

if row[m] > 0.0: centroids[i][m]+=(row[m]/len_best)

最开始的除法步骤是在一个单独的循环中，但效果也不好。

这是我遇到的异常信息：

malloc: *** mmap(size=16777216) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug

任何帮助都将不胜感激。

---

更新：最终算法

感谢这里得到的帮助，这是我修正后的算法。如果你发现有什么明显错误，请留言告诉我。

首先是simple_pearson的实现：

def simple_pearson(v1,v2):

    si = [val for val in v1 if val in v2]
        
    n = len(si)
    
    if n==0: return 0.0
    
    sum1 = 0.0
    sum2 = 0.0
    sum1_sq = 0.0
    sum2_sq = 0.0
    p_sum = 0.0
    
    for v in si:
        sum1+=v1[v]
        sum2+=v2[v]
        sum1_sq+=pow(v1[v],2)
        sum2_sq+=pow(v2[v],2)
        p_sum+=(v1[v]*v2[v])
    
    # Calculate Pearson score
    num = p_sum-(sum1*sum2/n)
    temp = (sum1_sq-pow(sum1,2)/n) * (sum2_sq-pow(sum2,2)/n)
    if temp < 0.0:
        temp = -temp
    den = sqrt(temp)
    if den==0: return 1.0
    
    r = num/den
    
    return r

将simple_pearson转换为距离值的简单方法：

def distance(v1,v2):
    return 1.0-simple_pearson(v1,v2)

最后是k-means聚类的实现：

def kcluster(prefs,k=21,max_iterations=50):
    from collections import defaultdict
    
    users = prefs.keys()
    centroids = [prefs[u] for u in random.sample(users, k)]
    
    lastmatches = None
    for t in range(max_iterations):
        print 'Iteration %d' % t
        bestmatches = [[] for i in range(k)]

        # Find which centroid is closest for each row        
        for j in users:
            row = prefs[j]
            bestmatch=(0,2.0)
            
            for i in range(k):
                d = distance(row,centroids[i])
                if d <= bestmatch[1]: bestmatch = (i,d)
            bestmatches[bestmatch[0]].append(j)
        
        # If the results are the same as last time, this is complete
        if bestmatches == lastmatches: break
        lastmatches=bestmatches
        
        centroids = [defaultdict(float) for i in range(k)]
        
        #  Move the centroids to the average of their members
        for i in range(k):
            len_best = len(bestmatches[i])
                                    
            if len_best > 0:          
                for user_id in bestmatches[i]:
                    row = prefs[user_id]
                    for m in row:
                        centroids[i][m]+=row[m]
            for key in centroids[i].keys():
                centroids[i][key]/=len_best
                # We may have made the centroids quite dense which significantly
                # slows down subsequent iterations, so we delete values below a
                # threshold to speed things up
                if centroids[i][key] < 0.001:
                    del centroids[i][key]
    return centroids, bestmatches

Answer 1

你的 centroids 不一定要是一个真正的列表。

你似乎只用到了 centroids[i][m] 这个部分。如果你只想要 centroids[i]，那么它可能不需要是一个列表；用一个简单的字典就可以了。

    centroids = defaultdict(float)

    #  Move the centroids to the average of their members
    for i in range(k):
        len_best = len(bestmatches[i])

        if len_best > 0:             
            items = set.union(*[set(prefs[u].keys()) for u in bestmatches[i]])

            for user_id in bestmatches[i]:
                row = prefs[user_id]
                for m in items:
                    if row[m] > 0.0: centroids[m]+=(row[m]/len_best)  

这样可能会更好。

Answer 2

并不是所有的观察都直接和你遇到的问题相关，但我想说的是：

a. 为什么在偏好设置中，键是长整型（longs）？除非你有数十亿的用户，否则简单的整数（ints）就足够了，这样还能节省一点内存。

b. 你的代码：

centroids = [prefs[random.choice(users)] for i in range(k)]

可能会出现重复的情况（两个完全相同的中心点），这样会让K-means算法不高兴。建议你使用更快、更稳定的

centroids = [prefs[u] for random.sample(users, k)]

c. 在你发布的代码中，你调用了一个名为simple_pearson的函数，但你并没有在任何地方定义它；我猜你是想调用sim_func，但在不同的问题上同时猜测你发布的代码和实际工作的代码之间的差异，真的很难提供帮助。

d. 还有一个迹象表明你发布的代码可能和实际可用的代码不同：你设置了bestmatch=(0,0)，但却用if d < bestmatch[1]:来测试——这个测试怎么可能成功呢？距离函数会返回负值吗？

e. defaultdict的一个特点是，直接访问row[m]会神奇地在row的索引m处添加一个项（值是通过调用defaultdict的工厂得到的，这里是0.0）。这个项会一直占用内存。你完全不需要这种行为，因此你的代码：

  row = prefs[user_id]                    
  for m in items:
      if row[m] > 0.0: centroids[i][m]+=(row[m]/len_best)

在浪费大量内存，把prefs变成了一个密集矩阵（大部分是0.0值），而不是原来的稀疏矩阵。如果你改成这样：

  row = prefs[user_id]                    
  for m in row:
      centroids[i][m]+=(row[m]/len_best)

就不会再增加row和prefs的大小，因为你是在遍历row已经拥有的键。

可能还有很多其他问题，有的像最后一个那样严重，有的则比较小——比如说，

f. 不要在循环中进行无数次的len_best除法：在循环外计算它的倒数，然后用这个倒数去乘——而且你不需要在循环中做这个乘法，可以在最后单独做，因为每个项乘的都是同一个值——这样虽然不节省内存，但可以避免浪费CPU时间;-)。好吧，这其实是两个小问题，而不是一个;-）。

正如我提到的，可能还有很多其他问题，但考虑到已经显示出的这些六个（或七个）问题的密集程度，加上S.Lott已经提出的建议（我认为这并不能解决你主要的内存不足问题，因为他的代码仍然通过太多不包含的键来访问row的defaultdict），我觉得继续寻找更多问题可能不是很有效——也许先解决这些问题，如果问题仍然存在，再单独发个问题讨论这些……？