k表示在python中实现集群,内存不足

注:本问题底部的更新/解决方案

作为产品推荐引擎的一部分,我试图从使用k均值聚类算法开始,根据用户的产品偏好对其进行细分。

我的数据是一本字典的形式:

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

其中,产品ID是长整型,额定值是浮动的。数据稀疏。我目前有大约60000个用户,其中大多数只对少数产品进行了评级。使用defaultdict(float)实现每个用户的值字典,以简化代码。

我对k均值聚类的实现如下:

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

任何帮助都将不胜感激。

更新:最终算法

多亏了这里的帮助,这是我的固定算法。如果您发现任何明显错误,请添加评论。

首先,简单的皮尔逊实现

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

将简单皮尔逊转换为距离值的简单方法:

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