我正在尝试实现以下(划分)的聚类算法(以下是该算法的简写形式,完整描述可用here):

从样本x(i = 1,...,n)开始,该样本被视为n个数据点的单个群集,并且为所有点对定义了相异度矩阵D。固定阈值T,以决定是否拆分集群。

  • 首先确定所有成对的数据点之间的距离,并选择一个在它们之间具有最大距离(Dmax)的对。
  • 将Dmax与T进行比较。如果Dmax> T,则通过使用所选对作为两个新群集中的第一个元素,将单个群集分为两部分。其余的n-2个数据点将放入两个新群集之一中。如果D(x_i,x_l)
  • 在第二阶段,在两个新群集中的一个内找到值D(x_i,x_j),以在群集中找到对之间的距离最大Dmax的对。如果Dmax
    输出是集群数据记录的层次结构。我恳请寻求有关如何实现聚类算法的建议。

    编辑1:我附加了定义距离(相关系数)的Python函数和在数据矩阵中找到最大距离的函数。
    # Read data from GitHub
    import pandas as pd
    df = pd.read_csv('https://raw.githubusercontent.com/nico/collectiveintelligence-book/master/blogdata.txt', sep = '\t', index_col = 0)
    data = df.values.tolist()
    data = data[1:10]
    
    # Define correlation coefficient as distance of choice
    def pearson(v1, v2):
      # Simple sums
      sum1 = sum(v1)
      sum2 = sum(v2)
      # Sums of the squares
      sum1Sq = sum([pow(v, 2) for v in v1])
      sum2Sq = sum([pow(v, 2) for v in v2])
      # Sum of the products
      pSum=sum([v1[i] * v2[i] for i in range(len(v1))])
      # Calculate r (Pearson score)
      num = pSum - (sum1 * sum2 / len(v1))
      den = sqrt((sum1Sq - pow(sum1,2) / len(v1)) * (sum2Sq - pow(sum2, 2) / len(v1)))
      if den == 0: return 0
      return num / den
    
    
    # Find largest distance
    dist={}
    max_dist = pearson(data[0], data[0])
    # Loop over upper triangle of data matrix
    for i in range(len(data)):
      for j in range(i + 1, len(data)):
         # Compute distance for each pair
         dist_curr = pearson(data[i], data[j])
         # Store distance in dict
         dist[(i, j)] = dist_curr
         # Store max distance
         if dist_curr > max_dist:
           max_dist = dist_curr
    

    编辑2:下面粘贴的是Dschoni的答案中的函数。
    # Euclidean distance
    def euclidean(x,y):
      x = numpy.array(x)
      y = numpy.array(y)
      return numpy.sqrt(numpy.sum((x-y)**2))
    
    # Create matrix
    def dist_mat(data):
      dist = {}
      for i in range(len(data)):
        for j in range(i + 1, len(data)):
          dist[(i, j)] = euclidean(data[i], data[j])
      return dist
    
    
    # Returns i & k for max distance
    def my_max(dict):
        return max(dict)
    
    # Sort function
    list1 = []
    list2 = []
    def sort (rcd, i, k):
      list1.append(i)
      list2.append(k)
      for j in range(len(rcd)):
        if (euclidean(rcd[j], rcd[i]) < euclidean(rcd[j], rcd[k])):
          list1.append(j)
        else:
          list2.append(j)
    

    编辑3:
    当我运行@Dschoni提供的代码时,该算法将按预期工作。然后,我修改了create_distance_list函数,以便我们可以计算多元数据点之间的距离。我用欧几里得距离。对于玩具示例,我加载iris数据。我仅对数据集的前50个实例进行聚类。
    import pandas as pd
    df = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data', header = None, sep = ',')
    df = df.drop(4, 1)
    df = df[1:50]
    data = df.values.tolist()
    
    idl=range(len(data))
    dist = create_distance_list(data)
    print sort(dist, idl)
    

    结果如下:



    一些数据点仍聚集在一起。我通过在actual函数的sort字典中添加少量数据噪声来解决此问题:
    # Add small random noise
    for key in actual:
      actual[key] +=  np.random.normal(0, 0.005)
    

    知道如何正确解决此问题吗?

    最佳答案

    欧氏距离的一个正确的工作示例:

    import numpy as np
    #For random number generation
    
    
    def create_distance_list(l):
    '''Create a distance list for every
    unique tuple of pairs'''
        dist={}
        for i in range(len(l)):
            for k in range(i+1,len(l)):
                dist[(i,k)]=abs(l[i]-l[k])
        return dist
    
    def maximum(distance_dict):
    '''Returns the key of the maximum value if unique
    or a random key with the maximum value.'''
        maximum = max(distance_dict.values())
        max_key = [key for key, value in distance_dict.items() if value == maximum]
        if len(max_key)>1:
            random_key = np.random.random_integers(0,len(max_key)-1)
            return (max_key[random_key],)
        else:
            return max_key
    
    def construct_new_dict(distance_dict,index_list):
    '''Helper function to create a distance map for a subset
    of data points.'''
        new={}
        for i in range(len(index_list)):
            for k in range(i+1,len(index_list)):
                m = index_list[i]
                n = index_list[k]
                new[(m,n)]=distance_dict[(m,n)]
        return new
    
    def sort(distance_dict,idl,threshold=4):
        result=[idl]
        i=0
        try:
            while True:
                if len(result[i])>=2:
                actual=construct_new_dict(dist,result[i])
                    act_max=maximum(actual)
                    if distance_dict[act_max[0]]>threshold:
                        j = act_max[0][0]
                        k = act_max[0][1]
                        result[i].remove(j)
                        result[i].remove(k)
                        l1=[j]
                        l2=[k]
                        for iterr in range(len(result[i])):
                            s = result[i][iterr]
                            if s>j:
                                c1=(j,s)
                            else:
                                c1=(s,j)
                            if s>k:
                                c2=(k,s)
                            else:
                                c2=(s,k)
                            if actual[c1]<actual[c2]:
                                l1.append(s)
                            else:
                                l2.append(s)
                        result.remove(result[i])
        #What to do if distance is equal?
                        l1.sort()
                        l2.sort()
                        result.append(l1)
                        result.append(l2)
                    else:
                        i+=1
                else:
                    i+=1
        except:
            return result
    
    
    #This is the dataset
    a = [1,2,2.5,5]
    #Giving each entry a unique ID
    idl=range(len(a))
    dist = create_distance_list(a)
    print sort(dist,idl)
    

    我编写代码的目的是为了提高可读性,其中有很多东西可以使速度更快,更可靠,更漂亮。这只是为了让您了解如何完成此操作。

  • 10-05 22:43