最大最小距离法

最大最小距离法：

import matplotlib.pyplot as plt
import math

# 0 3 2 1 5 4 6 5 6 7
# 0 8 2 1 3 8 3 4 4 5
# 测试集合
# x = [0, 3, 2, 1, 5, 4, 6, 5, 6, 7]
# y = [0, 8, 2, 1, 3, 8, 3, 4, 4, 5]

print("请输入所有点的横坐标")
arr1 = input()
x = [float(n) for n in arr1.split()]
print("请输入所有点的纵坐标")
arr2 = input()
y = [float(n) for n in arr2.split()]

# 将x y复制一份，切片复制不会相互影响
cx = x[:]
cy = y[:]
# 类别判断函数
judge = [-1] * len(x)
# 倍数
Multiple = 0.45
# Multiple = 0.5
# 任意一个模式样本作为第1个聚类中心
i = 0
# 实时跟踪zx zy的下标变化
k = 1
zx = [x[i]]
zy = [y[i]]
# 用于记录类心坐标
cenx = [x[i]]
ceny = [y[i]]

judge[i] = k
# 在原数组中删除该点
x.pop(i)
y.pop(i)
# 得到其余点的个数
length = len(x)
# 用于记录距离
distance = 0
# 用于记录最大值的下标
j = 0
for i in range(0, length):
    # 得到最大距离
    if math.sqrt(math.pow(x[i] - zx[0], 2) + math.pow(y[i] - zy[0], 2)) > distance:
        distance = math.sqrt(math.pow(x[i] - zx[0], 2) + math.pow(y[i] - zy[0], 2))
        # 得到距离最远的一个点
        j = i
# 更新k的值,说明目前存在几个类心
k = k + 1
# 将该点定位新的聚类中心
for l in range(0, len(cx)):
    if cx[l] == x[j] and cy[l] == y[j]:
        judge[l] = k
        cenx.append(x[j])
        ceny.append(y[j])
        break
zx.append(x[j])
zy.append(y[j])
x.pop(j)
y.pop(j)
length = length - 1

# 距离数组
d = [-1.0] * k

# 最小距离数组
mind = []
# 得到目前的剩余坐标
m = 0
while m < length:
    for a in range(0, len(x)):
        for j in range(k):
            d[j] = math.sqrt(math.pow(x[a] - zx[j], 2) + math.pow(y[a] - zy[j], 2))
        # 得到每个点到目前已知点的距离
        mind.append(min(d))
    print("各个距离中最小的点")
    print(mind)

    for a in range(0, len(x)):
        for j in range(k):
            d[j] = math.sqrt(math.pow(x[a] - zx[j], 2) + math.pow(y[a] - zy[j], 2))
        if min(d) == max(mind):
            location = a
            break

    # 判断最小距离与类心间的距离
    if Multiple * distance < max(mind):
        k = k + 1
        d = [-1.0] * k
        # print(d)
        # print("新类心,坐标为：")
        # print(x[i])
        # print(y[i])
        for l in range(0, len(cx)):
            if cx[l] == x[location] and cy[l] == y[location]:
                judge[l] = k
                zx.append(x[location])
                zy.append(y[location])
                cenx.append(x[location])
                ceny.append(y[location])
                x.pop(location)
                y.pop(location)
                length = length - 1
                m = 0

                mind = []
                break
    else:
        # 离谁小就归到谁的类中
        for j in range(0, k):
            if min(d) == d[j]:
                # 此时归到这一类中
                # print("该点的坐标为")
                # print(x[m], y[m])
                # print("该点属于第" + str(j + 1) + "类")
                for l in range(0, len(cx)):
                    if cx[l] == x[location] and cy[l] == y[location]:
                        judge[l] = j + 1
                x.pop(location)
                y.pop(location)
                length = length - 1
                m = 0
                mind = []

print("共分成了" + str(k) + "类")
print("聚类中心分别为:")
print(cenx)
print(ceny)
# 输出每个点应该属于的类别
print("每个点应该属于的类别")
print(judge)

for i in range(len(cx)):
    if judge[i] == 1:
        plt.scatter(cx[i], cy[i], color="red")
    elif judge[i] == 2:
        plt.scatter(cx[i], cy[i], color="green")
    elif judge[i] == 3:
        plt.scatter(cx[i], cy[i], color="pink")
    elif judge[i] == 4:
        plt.scatter(cx[i], cy[i], color="magenta")
    elif judge[i] == 5:
        plt.scatter(cx[i], cy[i], color="cyan")
    elif judge[i] == 6:
        plt.scatter(cx[i], cy[i], color="blue")
    elif judge[i] == 7:
        plt.scatter(cx[i], cy[i], color="yellow")
    else:
        plt.scatter(cx[i], cy[i], color="pink")
plt.show()