K-Means聚类下的Anchor优化输出

def distance(box1, box2):
    w1, h1 = box1
    w2, h2 = box2
    S1 = min(w1, w2) * min(h1, h2)
    S2 = w1 * h1 + w2 * h2 - S1

    d = 1 - S1 / S2

    return d

class KMeans:
    def __init__(self, N, K, boxes):
        self.N = N
        self.K = K
        self.boxes = boxes

        self.group = [0 for _ in range(N)]
        self.count = [0 for _ in range(K)]

        self.centers = list(boxes[:K])
        return

    def k_means(self, T, max_error=1.0e-4):
        step = 0
        error = 1.0

        while step < T and error > max_error:
            self.create_group()
            centers_cur = self.cal_center()
            error = self.cal_error(centers_cur)
            self.centers = centers_cur
            step += 1
        return

    def cal_error(self, centers_cur):
        error = 0.0
        for ii in range(self.K):
            error += distance(self.centers[ii], centers_cur[ii])
        return error

    def create_group(self):
        count = [0 for _ in range(self.K)]
        for ii in range(self.N):
            d = float('inf')
            for jj in range(self.K):
                d1 = distance(self.boxes[ii], self.centers[jj])
                if d1 < d:
                    d = d1
                    self.group[ii] = jj
            count[self.group[ii]] += 1
        self.count = count
        return

    def cal_center(self):
        centers = self.centers
        for ii in range(self.K):
            if self.count[ii] > 0:
                w = 0
                h = 0
                for jj in range(self.N):
                    if self.group[jj] == ii:
                        w += self.boxes[jj][0]
                        h += self.boxes[jj][1]
                w = w / self.count[ii]
                h = h / self.count[ii]
                centers[ii] = (int(w), int(h))
        return centers

    def print_centers(self):
        Swh = []
        for ii in range(self.K):
            w = self.centers[ii][0]
            h = self.centers[ii][1]
            S = w * h
            Swh.append((S, w, h))
        Swh.sort(reverse=True)
        for ii in range(self.K):
            print(Swh[ii][1], Swh[ii][2])


def read_in():
    N, K, T = map(int, input().split())
    boxes = []
    for _ in range(N):
        boxes.append(tuple(map(int, input().split())))

    boxes = tuple(boxes)
    return N, K, T, boxes

if __name__ == '__main__':
    readin = read_in()
    km = KMeans(readin[0], readin[1], readin[3])
    km.k_means(readin[2])
    km.print_centers()

import sys

import numpy as np

def cal_d(A,C):
    h1,w1=A
    h2,w2=C
    inter = min(w1,w2) * min(h1,h2)
    over = w1*h1 + w2*h2 - inter
    return 1- inter/over 

# A=[2,3]
# C=[2,4]
# print(cal_d(A,C))
def sorte_centers_by_areas(center_list):
    areas = [c[0]*c[1] for c in center_list]

    areas = np.array(areas)
    center_list = np.array(center_list)
    new_center_list = []

    while max(areas)>0:
        max_item = center_list[np.where(areas==max(areas))]
        areas[np.where(areas==max(areas))]=0
        
        max_item = list(max_item.flatten())

        new_center_list.append(max_item)
    return new_center_list
# sorte_centers_by_areas([A,C])

def Kmeans(N,K,T,Anchors):
    #initial: centers, S={ci: anchors}, R
    # Anchors = np.array(Anchors)
    
    centers = Anchors[:K]
   
    stop = False
    t=0
    # update while not stop
    while not stop:
        # Remain = list(set(tuple(Anchors))-set(tuple(centers)))
        
        Remain = [ ]
        for i in Anchors:
            if not i in centers:
                Remain.append(i)
        S = dict()
        Dist_matrix=[]
        for i in range(K):
            ci=centers[i]
            S[i]=[ci]

            #对remain里的每个元素计算和ci的距离
            dist_to_ci = [cal_d(a, ci) for a in Remain]
            Dist_matrix.append(dist_to_ci)

        Dist_matrix = np.array(Dist_matrix)
        cls_list = Dist_matrix.argmin(axis=0)
        # print(cls_list)
        

        # get new_centers
        new_centers =[]
        for i in range(K):
            si = list(np.array(Remain)[np.array(cls_list)==i])
            S[i].extend(si)

            new_si = np.array(S[i]).mean(axis=0)
            new_si=list(map(int, new_si))
            new_centers.append(new_si)
        
        # print(new_centers)

        output_center = sorte_centers_by_areas(new_centers)

        # sum_move
        d=0        
        for i in range(K):
            d+= cal_d(centers[i],new_centers[i])
        if d<1e-4:
            stop= True
        t+=1
        if t>=T:
            stop = True
       
    return output_center 

def main():
    # ----------input--------

    line_1 = sys.stdin.readline().strip()
    line_1 = line_1.split(' ')
    N,K,T = list(map(int,line_1))
    
    Anchors =[]
    for i in range(N):
        line = sys.stdin.readline().strip()
        line = line.split(' ')
        anchor = list(map(int,line))
        Anchors.append(anchor)

    # ----------input--------
    # N,K,T=9,3,10
    # Anchors=[[100, 50], [30, 20], [10, 10], [102, 49], [98, 52], [29, 21], [31, 19], [11, 9], [9, 11]]
    centers = Kmeans(N,K,T,Anchors)

    for i in centers:
        print(i[0],i[1])
main()

# 9 3 10
# 100 50
# 30 20
# 10 10
# 102 49
# 98 52
# 29 21
# 31 19
# 11 9
# 9 11