首页 > 试题广场 >

聚类

[编程题]聚类
  • 热度指数:575 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
铁柱在研究一个区域的小黄车使用分布。他得到了服务器上最近10000个用户的二维位置,现在他想把这些用户聚成K(K<10) 组,每组有一个中心C_i。他想评价聚类算法的好坏,把每个数据点到中心的l1距离作为总距离。即
D = sum_j || X_j - C( X_j ) ||_1
其中C(X_j)代表X_j所属的中心。现在他想找一个尽可能好的聚类算法,使得这个总距离尽可能小。要求你输出K个中心的位置(顺序不限)
比如如果有5个数据点
1 1
1 2
1 4
3 4
3 5
给定2个中心1 2, 3 4的话
总距离就是1+0+2+0+1 = 4

输入描述:
本题总是会有10000个数据点
第一个输入为K,表示需要聚类的个数,
之后10000行,为每个点的x和y
例如:
2
2-5001行 每行都是 0 0
5002-10001行 每行都是 2 2


输出描述:
依次输出每个类中心
示例1

输入

2
2-5001行 每行都是 0 0
5002-10001行 每行都是 2 2

输出

0.00000 0.00000
2.00000 2.00000
题目的预期输出41909.991042应该是损失值,即样本点到对应簇心的距离
实现代码如下
dim = 2      #二维
n_data = 10000    #10000个数据点
iter_times = 10

def l2_dist(x1, x2):          #欧氏距离
    sum = 0
    for i in range(len(x1)):
        sum += (x1[i] - x2[i]) ** 2
    return sum ** (1/2)

#计算中心
def centroid(l):
    res = [0] * dim
    for i in range(dim):
        for a in l:
            res[i] += data[a][i]
    for i in range(dim):
        res[i] /= len(l)
    return res

def CalCentroids(l):
    res = []
    for i in l:
        res.append(centroid(i))
    return res

K = int(input())

data = []
for i in range(n_data):
    data += [list(map(float, input().strip().split()))]

#随机分配
clusters= []
for i in range(K):
    clusters.append([])
for i in range(n_data):
    pos = i % K
    clusters[pos].append(i)

#迭代
for _ in range(iter_times):
    sum_dist = 0
    centroids = CalCentroids(clusters)
    for i in range(K):
        clusters[i] = []
    for i in range(n_data):
        best_c = 0
        best_d = 9999999999
        for j in range(K):
            d = l2_dist(centroids[j], data[i])
            if d < best_d:
                best_c = j
                best_d = d
        sum_dist += best_d
        if len(clusters[best_c]) == 0:
            clusters[best_c] = []
        clusters[best_c].append(i)

print(sum_dist)

# for i in range(K):
#     print(f'{clusters[i][0]} {clusters[i][1]}')
实现出来输出为35380

发表于 2022-03-28 19:16:28 回复(0)
没做出来,马克一下,不让调用包真是吃力啊。
好像还没有通过的人可以借鉴,我来发一个27%正确的结果吧,用K-means做的,有兴趣的来挑挑错。
聚类中心点初始化方法弱爆了,简单调参没出好结果。
k =int(raw_input())
p =[]
minxx =[]
minyy =[]
for i in range(10000): ## Dada loading
    x,y =raw_input().split()
    x =float(x)
    y =float(y)
    minxx.append(x)
    minyy.append(y)
    p.append([x,y])
if k ==1: ##不知道会不会出现只聚类1组的情况,反正先写着。。。
    print sum(minxx)/10000
    print sum(minyy)/10000
else:
    kpx =[0 for i in range(k)] ## 初始化聚类中心点
    kpy =[0 for i in range(k)]
    for i in range(k):
        kpx[i] =(max(minxx) -min(minxx))/(k)*(i+1)+min(minxx)
        kpy[i] =(max(minyy)-min(minyy))/(k)*(i+1)+min(minyy)
    prebelong =[999 for _ in range(100000)] ## 迭代记录初始化
    for_ in range(100): ## 迭代次数上限为100
        belong =[]
        for i in range(10000): ## 每个数据点
            thisbe =[]
            for n in range(k): ## 每个聚类点
                thisbe.append(abs(p[i][0]-kpx[n])+abs(p[i][1]-kpy[n]))## 每个数据点对每个聚类点计算L1距离
            belong.append(thisbe.index(min(thisbe)))## 按照最接近的原则,生成聚类结果
        for n in range(k):
            xx =[]
            yy =[]
            for i in range(10000):
                if belong[i] ==n:
                    xx.append(p[i][0])
                    yy.append(p[i][1])
             
            kpx[n] =sum(xx)/len(xx) # 计算每个聚好的类的x和y的均值,作为新的聚类点
            kpy[n] =sum(yy)/len(yy)
        sumeq =0
        for i in range(10000): # 如果此次聚类和上次结果一致,则算成功,退出主循环,输出结果
            if prebelong[i] ==belong[i]:
                sumeq +=1
        if sumeq ==10000:
            break
        else:
            prebelong =belong
             
    for i inrange(k):
        printkpx[i] , kpy[i]
发表于 2018-09-23 20:03:30 回复(0)
明明输入的第一行数字是6,表明应该是有6个类中心,为什么预期输出会是一行41909.991042?
不应该是6对数吗?这样,错了,通不过,都不知道问题在哪!
发表于 2021-08-10 20:02:44 回复(0)
采用K-Means+L1距离,一直循环到质心不发生改变为止,本地IDE可以通过。
但是提交一直是请检查是否存在语法错误或者数组越界非法访问等情况。
求教各位大神有没有解法
import random
K = int(input())
data = []
for i in range(10000):
    data += [list(map(int, input().strip().split()))]
print(data)
def L1_dis(poi1_x, poi1_y, poi2_x, poi2_y):
    return abs(poi1_x-poi2_x)+abs(poi1_y-poi2_y)
centroids = []
if K <= 0:
    print(-1)
elif K == 1:
    sum_x = 0
    sum_y = 0
    for i in range(10000):
        sum_x += data[i][0]
        sum_y += data[i][1]
    centroids = [sum_x/10000, sum_y/10000]
    print(format(centroids[0], '.5f'), format(centroids[1], '.5f'))
else:
    for j in range(K):
        random_centroids = random.randint(0, 9999)
        while data[random_centroids] in centroids:
            random_centroids = random.randint(0, 9999)
        centroids.append(data[random_centroids])
    flag = 1
    centroids_ori = [0 for j in range(K)]
    while(flag):
        result = [[]for j in range(K)]
        for j in range(K):
            centroids_ori[j] = centroids[j]
        for temp in data:
            min_class = 0
            min_dis = L1_dis(temp[0], temp[1],
                             centroids[0][0], centroids[0][1])
            for j in range(1, K):
                L1 = L1_dis(temp[0], temp[1], centroids[j][0], centroids[j][1])
                if L1 <= min_dis:
                    min_dis = L1
                    min_class = j
            result[min_class].append(temp)
        for j in range(K):
            sum_x = 0
            sum_y = 0
            for re in result[j]:
                sum_x += re[0]
                sum_y += re[1]
            centroids[j] = [sum_x/len(result[j]), sum_y/len(result[j])]
        if centroids == centroids_ori:
            flag = 0
        else:
            flag = 1
    for j in range(K):
        print(format(centroids[j][0], '.5f'), format(centroids[j][1], '.5f'))

发表于 2020-05-29 11:40:49 回复(0)
请求高人指教。。。不能用numpy包,一直通不过
#coding=utf-8
 
import random
import math
     
#计算两个点之间的距离,用的是欧几里得距离
def distEclud(vecA, vecB):
    x1,y1=vecA
    x2,y2=vecB
    return math.sqrt(pow(x1 - x2, 2)+pow(y1 - y2, 2))
 
#随机生成初始的质心(ng的课说的初始方式是随机选K个点)   
def randCent(dataSet, k):
    centroids =[]
    for i in range(k):
        centroids.append([0,0])
    for i in range(k):
        for j in range(2):
            minJ = min(dataSet[:][j])
            rangeJ = float(max(dataSet[:][j]) - minJ)
            centroids[i][j] = minJ + rangeJ * random.random()
    return centroids
     
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    m = 10000
    clusterAssment = []#创建点的归类list
    for i in range(m):
        clusterAssment.append(-1)#初始化为-1
    centroids = createCent(dataSet, k)
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):#为每个点分配一个中心点,即归类
            minDist = float("inf")
            minIndex = -1
            for j in range(k):
                distJI = distMeas(centroids[j],dataSet[i])#计算该点到中心点的距离
                if distJI < minDist:
                    minDist = distJI; minIndex = j#更新该点的距离值,并将中心点索引赋值给minIndex
            if clusterAssment[i] != minIndex: #若该点的分配中心点不为minIndex
                clusterChanged = True
            clusterAssment[i] = minIndex
        for cent in range(k):#重新计算中心点
            hang=[]
            for i in range(len(clusterAssment)):
                if clusterAssment[i]==cent:
                    hang.append(i)
            #ptsInClust = dataSet[hang][:]
            ptsInClust=[]
            for i in hang:
                ptsInClust.append(dataSet[i])
            if len(ptsInClust)>0:
                x=0
                y=0
                for i in range(len(ptsInClust)):
                    x+=ptsInClust[i][0]
                    y+=ptsInClust[i][1]
                
                centroids[cent][0] = float(x/len(ptsInClust)) 
                centroids[cent][1] = float(y/len(ptsInClust))
    print(centroids)
     
def main():
    num=int(input())
    dataMat = []
    for i in range(10000):
        x,y=[float(x) for x in input().split()]
        dataMat.append([x,y])
    kMeans(dataMat,num)
     
     
if __name__ == '__main__':
    main()

发表于 2018-09-07 12:54:51 回复(1)