kmeans具有质心约束

Question

我正在为我的数据科学导论课做一个数据科学项目，我们决定解决一个与加州海水淡化厂有关的问题：“我们应该把k工厂放在哪里，以尽量缩短与邮政编码的距离？”在

到目前为止，我们得到的数据是，zip，city，county，pop，lat，long，水量。在

问题是，我找不到任何关于如何迫使质心被限制在海岸上的资源。到目前为止，我们想到的是： 使用一个普通的kmeans算法，但是一旦集群已经稳定下来，将质心移动到海岸（bad） 使用带有权重的普通kmeans算法，使沿海拉链具有无限的权重（我听说这不是一个好的解决方案）

你们觉得怎么样？在

Answer 1

我将通过设置可能成为中心的点来实现这一点，即海岸线。
我认为这接近于Nathaniel Saul's第一条评论。
这样，对于每一次迭代，不是选择一个平均值，而是从可能的集合中选择一个点，这将通过接近集群来选择。在

我已经将条件简化为只有2个数据列（lon。但是你应该能够推断出这个概念。为了简单起见，为了演示，我基于here中的代码。在

在这个例子中，紫色的点是海岸线上的地方。如果我理解正确的话，最佳海岸线位置应该如下所示：

参见以下代码：

#! /usr/bin/python3.6

# Code based on:
# https://datasciencelab.wordpress.com/2013/12/12/clustering-with-k-means-in-python/

import matplotlib.pyplot as plt
import numpy as np
import random

##### Simulation START #####
# Generate possible points.
def possible_points(n=20):
    y=list(np.linspace( -1, 1, n ))
    x=[-1.2]
    X=[]
    for i in list(range(1,n)):
        x.append(x[i-1]+random.uniform(-2/n,2/n) )
    for a,b in zip(x,y):
        X.append(np.array([a,b]))
    X = np.array(X)
    return X

# Generate sample
def init_board_gauss(N, k):
    n = float(N)/k
    X = []
    for i in range(k):
        c = (random.uniform(-1, 1), random.uniform(-1, 1))
        s = random.uniform(0.05,0.5)
        x = []
        while len(x) < n:
            a, b = np.array([np.random.normal(c[0], s), np.random.normal(c[1], s)])
            # Continue drawing points from the distribution in the range [-1,1]
            if abs(a) < 1 and abs(b) < 1:
                x.append([a,b])
        X.extend(x)
    X = np.array(X)[:N]
    return X
##### Simulation END #####    

# Identify points for each center.
def cluster_points(X, mu):
    clusters  = {}
    for x in X:
        bestmukey = min([(i[0], np.linalg.norm(x-mu[i[0]])) \
                    for i in enumerate(mu)], key=lambda t:t[1])[0]
        try:
            clusters[bestmukey].append(x)
        except KeyError:
            clusters[bestmukey] = [x]
    return clusters

# Get closest possible point for each cluster.
def closest_point(cluster,possiblePoints):
    closestPoints=[]
    # Check average distance for each point.
    for possible in possiblePoints:
        distances=[]
        for point in cluster:
            distances.append(np.linalg.norm(possible-point))
            closestPoints.append(np.sum(distances)) # minimize total distance
            # closestPoints.append(np.mean(distances))
    return possiblePoints[closestPoints.index(min(closestPoints))]

# Calculate new centers.
# Here the 'coast constraint' goes.
def reevaluate_centers(clusters,possiblePoints):
    newmu = []
    keys = sorted(clusters.keys())
    for k in keys:
        newmu.append(closest_point(clusters[k],possiblePoints))
    return newmu

# Check whether centers converged.
def has_converged(mu, oldmu):
    return (set([tuple(a) for a in mu]) == set([tuple(a) for a in oldmu]))

# Meta function that runs the steps of the process in sequence.
def find_centers(X, K, possiblePoints):
    # Initialize to K random centers
    oldmu = random.sample(list(possiblePoints), K)
    mu = random.sample(list(possiblePoints), K)
    while not has_converged(mu, oldmu):
        oldmu = mu
        # Assign all points in X to clusters
        clusters = cluster_points(X, mu)
        # Re-evaluate centers
        mu = reevaluate_centers(clusters,possiblePoints)
    return(mu, clusters)


K=3
X = init_board_gauss(30,K)
possiblePoints=possible_points()
results=find_centers(X,K,possiblePoints)

# Show results

# Show constraints and clusters
# List point types
pointtypes1=["gx","gD","g*"]

plt.plot(
    np.matrix(possiblePoints).transpose()[0],np.matrix(possiblePoints).transpose()[1],'m.'
    )

for i in list(range(0,len(results[0]))) :
    plt.plot(
        np.matrix(results[0][i]).transpose()[0], np.matrix(results[0][i]).transpose()[1],pointtypes1[i]
        )

pointtypes=["bx","yD","c*"]
# Show all cluster points
for i in list(range(0,len(results[1]))) :
    plt.plot(
        np.matrix(results[1][i]).transpose()[0],np.matrix(results[1][i]).transpose()[1],pointtypes[i]
        )
plt.show()

编辑以最小化总距离。在

Answer 2

K-K并不意味着距离最小化。在

它使平方误差最小化，这与完全不同。 差别大致是中值和一维数据的平均值。错误可能是巨大的。在

下面是一个反例，假设我们有坐标：

-1 0
+1 0
 0 -1
 0 101

k均值选择的中心为0,25。最佳位置为0,0。 k均值法的距离之和大于152，最佳位置距离为104。所以在这里，质心几乎比最佳值差50%！但是质心（=多元平均值）是k-均值使用的！在

k-均值不最小化欧几里德距离！在

这是“k均值对异常值敏感”的一个变体。在

如果你试图限制它只把“中心”放在海岸上，它不会变得更好。。。在

另外，你可能需要至少使用哈弗斯距离，因为在加州，1度北！=1度东，因为它不在赤道。在

此外，您可能应该假设每个位置都需要自己的管道，而是像树一样连接起来。这大大降低了成本。在

我强烈建议将此问题视为一个通用优化问题，而不是k-均值。K-means也是一个优化，但它可能会针对您的问题优化错误的函数。。。在