kmeans с расстоянием L1 в питоне

Question

С учетом векторов признаков NxM в виде матрицы с пустым пространством.Есть ли подпрограмма, которая может кластеризовать ее по алгоритму Kmeans, используя расстояние L1 (расстояние Манхэттена)?

Answer 1

Вот один алгоритм Kmeans, использующий расстояние L1 (расстояние Манхэттена).Для общности вектор признаков представлен в виде списка, который легко преобразовать в пустую матрицу.

    import random
    #Manhattan Distance
    def L1(v1,v2):
      if(len(v1)!=len(v2):
        print “error”
        return -1
      return sum([abs(v1[i]-v2[i]) for i in range(len(v1))])

    # kmeans with L1 distance. 
    # rows refers to the NxM feature vectors
    def kcluster(rows,distance=L1,k=4):# Cited from Programming Collective Intelligence 
        # Determine the minimum and maximum values for each point
        ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows])) for i in range(len(rows[0]))]

        # Create k randomly placed centroids
        clusters=[[random.random( )*(ranges[i][1]-ranges[i][0])+ranges[i][0] for i in range(len(rows[0]))] for j in range(k)]

        lastmatches=None
        for t in range(100):
            print 'Iteration %d' % t
            bestmatches=[[] for i in range(k)]
            # Find which centroid is the closest for each row
            for j in range(len(rows)):
                row=rows[j]
                bestmatch=0
                for i in range(k):
                    d=distance(clusters[i],row)
                    if d<distance(clusters[bestmatch],row): 
                        bestmatch=i
                bestmatches[bestmatch].append(j)
            ## If the results are the same as last time, this is complete
            if bestmatches==lastmatches:
                break
            lastmatches=bestmatches

            # Move the centroids to the average of their members
            for i in range(k):
                avgs=[0.0]*len(rows[0])
                if len(bestmatches[i])>0:
                    for rowid in bestmatches[i]:
                        for m in range(len(rows[rowid])):
                            avgs[m]+=rows[rowid][m]
                    for j in range(len(avgs)):
                        avgs[j]/=len(bestmatches[i])
                    clusters[i]=avgs
        return bestmatches

Answer 2

Существует код под «можно ли указать свою собственную функцию расстояния с использованием scikits-learn-k-средних» , который использует любую из 20 с лишним метрик вscipy.spatial.distance.См. Также L1-или-L.5-метрики для кластеризации ;не могли бы вы прокомментировать ваши результаты с L1 против L2?

Answer 3

Я не думаю, что это предлагается явно в scipy, но вы должны взглянуть на следующее:

http://projects.scipy.org/scipy/ticket/612