k-means在python中实现集群实现,内存不足

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)进行计算之前,该算法会在此行中使用MemoryError进行轰炸:

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 = [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]:- 测试怎么会成功？距离函数是否返回负值？

即 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所以不会有增长.prefsrow

可能还有许多其他类似问题,例如最后一个或次要问题 - 作为后者的一个例子,

F.不要划分数万亿次len_best:计算其在循环外的逆矩并乘以该逆 - 你也不需要在循环内进行乘法运算,你可以在最后单独进行,因为它是相同的值乘以每个项目 - 这样可以节省内存但避免浪费大量的CPU时间;-).好吧,这些是两个小问题,我猜,不只是一个;-).

正如我所提到的,可能还有很多其他问题,但这六个(或七个)已经显示的问题密度加上S.Lott已经提出的单独建议(我认为这不会解决你的主要内存不足问题) ,因为他的代码仍然row通过太多的密钥解决了defaultdict,它不包含),我认为继续寻找更多的东西并不是很有效率 - 可能从修复这些代码开始,如果问题仍然存在,请发布一个单独的问题那些......？