マップ上のポイントを距離ごとに同じサイズのグループにグループ化するための最速のアルゴリズムを探しています。k-meansクラスタリングアルゴリズムは単純で有望に見えますが、同じサイズのグループを生成しません。
このアルゴリズムのバリエーションはありますか、それともすべてのクラスターのメンバーの数を等しくすることができる別のアルゴリズムがありますか？
46638 次
18 に答える
17
これでうまくいくかもしれません。ロイドのアルゴリズムを適用してk個の重心を取得します。配列内の関連するクラスターのサイズの降順で重心を並べ替えます。i =1からk -1の場合、他の重心j（i < j≤k）までの距離が最小のクラスターiのデータポイントをjにプッシュし、重心iを再計算します（ただし、クラスターを再計算しないでください）。クラスターサイズはn / kです。
この後処理ステップの複雑さはO （ k²nlg n）です。
于 2011-03-27T21:49:36.350 に答える
6
ELKIデータマイニングフレームワークには、同じサイズのk-meansに関するチュートリアルがあります。
これは特に優れたアルゴリズムではありませんが、チュートリアルを作成し、独自のクラスタリングアルゴリズムのバリエーションを実装する方法を人々に教えるのに十分簡単なk-meansバリエーションです。SSQの品質は通常のk-meansよりも悪くなりますが、クラスターを同じサイズにする必要がある人もいるようです。
ELKI 0.7.5では、このアルゴリズムをとして選択できますtutorial.clustering.SameSizeKMeansAlgorithm。
于 2013-02-16T23:14:59.240 に答える
5
加重グラフの定義として距離を表示できます。かなりの数のグラフ分割アルゴリズムは、グラフの頂点を同じサイズの 2 つのセットに分割しようとすることに明示的に基づいています。これは、たとえば、Kernighan-Lin アルゴリズムや、ラプラシアンを使用したスペクトル グラフ分割に現れます。複数のクラスターを取得するには、パーティショニング アルゴリズムを再帰的に適用できます。スペクトル グラフ パーティショニングのリンクで、これについてのすばらしい議論があります。
于 2011-03-28T10:02:18.570 に答える
5
この k-means バリエーションを試してください。
初期化:
- データセットからランダムにセンターを選択するか
k、kmeans++ 戦略を使用するとさらに良い - 各ポイントについて、最も近いクラスター中心までの距離を計算し、このためのヒープを構築します
- クラスターがすでにいっぱいでない限り、ヒープからポイントを描画し、最も近いクラスターに割り当てます。その場合は、次に近いクラスターの中心を計算し、ヒープに再挿入します
最終的に、クラスターごとに +-1 の同数のオブジェクトの要件を満たすパーティショニングが必要です (最後のいくつかのクラスターにも正しい数があることを確認してmください。最初のクラスターにはceilオブジェクトがあり、残りは正確にfloorオブジェクトである必要があります)。
反復ステップ:
必要条件: 「スワップ提案」(別のクラスターにあることを好むオブジェクト) を含む各クラスターのリスト。
Eステップ: 通常の k-means のように、更新されたクラスターの中心を計算します
Mステップ: すべてのポイントを繰り返します (1 つだけ、または 1 つのバッチですべて)
オブジェクトに最も近いクラスター中心/現在のクラスターよりも近いすべてのクラスター中心を計算します。別のクラスターの場合:
- 他のクラスターが現在のクラスターよりも小さい場合は、新しいクラスターに移動するだけです
- 他のクラスター (または距離が短い任意のクラスター) からの交換提案がある場合は、2 つの要素クラスターの割り当てを交換します (複数の提案がある場合は、改善が最も大きいものを選択します)。
- それ以外の場合は、他のクラスターのスワップ提案を示します
クラスターのサイズは不変のまま (+- 天井/床の差)、オブジェクトは、推定が改善される限り、あるクラスターから別のクラスターに移動するだけです。したがって、k-means のように、ある時点で収束するはずです。ただし、少し遅くなる可能性があります（つまり、反復が増える）。
これが以前に公開または実装されたかどうかはわかりません。それは私が試すものです（k-meansを試すとしたら、はるかに優れたクラスタリングアルゴリズムがあります。）
于 2012-01-10T20:42:31.200 に答える
4
一般に、マップ上のポイントを距離ごとに同じサイズのグループにグループ化することは、理論的には不可能です。ポイントを同じサイズのグループにグループ化することは、ポイントを距離ごとにクラスターにグループ化することと競合するためです。
このプロットを参照してください：
ポイントは次の4つです。
A.[1,1]
B.[1,2]
C.[2,2]
D.[5,5]
これらのポイントを 2 つのクラスターにクラスター化するとします。明らかに、(A,B,C) はクラスター 1 になり、D はクラスター 2 になります。しかし、同じサイズのグループが必要な場合は、(A,B) が 1 つのクラスターになり、(C,D) がもう 1 つのクラスターになります。C は (A,B) の中心に近いが、クラスター (C,D) に属しているため、これはクラスター規則に違反しています。そのため、クラスターと同じサイズのグループの要件を同時に満たすことはできません。
于 2015-11-17T09:51:08.620 に答える
3
クラスター重心が与えられた場合、よりクリーンな後処理があります。NをアイテムのK数、クラスターの数、およびS = ceil(N/K)最大クラスター サイズとします。
- タプルのリストを作成する
(item_id, cluster_id, distance) - 距離に関してタプルをソートする
(item_id, cluster_id, distance)タプルのソートされたリスト内の 各要素について:- 要素数が
cluster_id超過した場合Sは何もしない item_idそれ以外の場合は、クラスターに追加しますcluster_id。
- 要素数が
これは O(NK lg(N)) で実行され、@larsmans ソリューションと同等の結果が得られ、実装が容易になります。疑似pythonで
dists = []
clusts = [None] * N
counts = [0] * K
for i, v in enumerate(items):
dist = map( lambda x: dist(x, v), centroids )
dd = map( lambda (k, v): (i, k, v), enumerate(dist) )
dists.extend(dd)
dists = sorted(dists, key = lambda (x,y,z): z)
for (item_id, cluster_id, d) in dists:
if counts[cluster_id] >= S:
continue
if clusts[item_id] == None:
clusts[item_id] = cluster_id
counts[cluster_id] = counts[cluster_id] + 1
于 2015-08-14T22:10:45.047 に答える
2
最近、それほど大きくないデータセットのためにこれを自分で必要としました。私の答えは、実行時間が比較的長くなりますが、局所最適に収束することが保証されています。
def eqsc(X, K=None, G=None):
"equal-size clustering based on data exchanges between pairs of clusters"
from scipy.spatial.distance import pdist, squareform
from matplotlib import pyplot as plt
from matplotlib import animation as ani
from matplotlib.patches import Polygon
from matplotlib.collections import PatchCollection
def error(K, m, D):
"""return average distances between data in one cluster, averaged over all clusters"""
E = 0
for k in range(K):
i = numpy.where(m == k)[0] # indeces of datapoints belonging to class k
E += numpy.mean(D[numpy.meshgrid(i,i)])
return E / K
numpy.random.seed(0) # repeatability
N, n = X.shape
if G is None and K is not None:
G = N // K # group size
elif K is None and G is not None:
K = N // G # number of clusters
else:
raise Exception('must specify either K or G')
D = squareform(pdist(X)) # distance matrix
m = numpy.random.permutation(N) % K # initial membership
E = error(K, m, D)
# visualization
#FFMpegWriter = ani.writers['ffmpeg']
#writer = FFMpegWriter(fps=15)
#fig = plt.figure()
#with writer.saving(fig, "ec.mp4", 100):
t = 1
while True:
E_p = E
for a in range(N): # systematically
for b in range(a):
m[a], m[b] = m[b], m[a] # exchange membership
E_t = error(K, m, D)
if E_t < E:
E = E_t
print("{}: {}<->{} E={}".format(t, a, b, E))
#plt.clf()
#for i in range(N):
#plt.text(X[i,0], X[i,1], m[i])
#writer.grab_frame()
else:
m[a], m[b] = m[b], m[a] # put them back
if E_p == E:
break
t += 1
fig, ax = plt.subplots()
patches = []
for k in range(K):
i = numpy.where(m == k)[0] # indeces of datapoints belonging to class k
x = X[i]
patches.append(Polygon(x[:,:2], True)) # how to draw this clock-wise?
u = numpy.mean(x, 0)
plt.text(u[0], u[1], k)
p = PatchCollection(patches, alpha=0.5)
ax.add_collection(p)
plt.show()
if __name__ == "__main__":
N, n = 100, 2
X = numpy.random.rand(N, n)
eqsc(X, G=3)
于 2013-11-23T16:26:50.167 に答える
2
何らかの形式の再帰的な貪欲なマージを検討してください。各ポイントはシングルトン クラスターとして始まり、最も近い 2 つのポイントを繰り返しマージして、そのようなマージが max を超えないようにします。サイズ。最大サイズを超える以外に選択肢がない場合は、ローカルで再クラスタリングします。これは、バックトラック階層クラスタリングの形式です: http://en.wikipedia.org/wiki/Hierarchical_clustering
于 2011-03-27T22:12:15.880 に答える
1
2012 年 1 月に追加: 後処理よりも優れているのは、クラスターのサイズが大きくなってもほぼ同じサイズを維持することです。
たとえば、X ごとに 3 つの最も近い中心を見つけ、X を最適な距離 (λ クラスターサイズ) を持つ中心に追加します。
k-means からのクラスターがほぼ同じサイズである場合、k-means の後の単純な貪欲な後処理で十分な場合があります。
(これは、k-means からの Npt x C 距離行列の割り当てアルゴリズムを近似します。)
繰り返すことができます
diffsizecentres = kmeans( X, centres, ... )
X_centre_distances = scipy.spatial.distance.cdist( X, diffsizecentres )
# or just the nearest few centres
xtoc = samesizeclusters( X_centre_distances )
samesizecentres = [X[xtoc[c]].mean(axis=0) for c in range(k)]
...
反復によって中心が大幅に変更された場合は驚かれることでしょうが、それは ™ によって異なります。
Npoint Ncluster と Ndim の大きさはどのくらいですか?
#!/usr/bin/env python
from __future__ import division
from operator import itemgetter
import numpy as np
__date__ = "2011-03-28 Mar denis"
def samesizecluster( D ):
""" in: point-to-cluster-centre distances D, Npt x C
e.g. from scipy.spatial.distance.cdist
out: xtoc, X -> C, equal-size clusters
method: sort all D, greedy
"""
# could take only the nearest few x-to-C distances
# add constraints to real assignment algorithm ?
Npt, C = D.shape
clustersize = (Npt + C - 1) // C
xcd = list( np.ndenumerate(D) ) # ((0,0), d00), ((0,1), d01) ...
xcd.sort( key=itemgetter(1) )
xtoc = np.ones( Npt, int ) * -1
nincluster = np.zeros( C, int )
nall = 0
for (x,c), d in xcd:
if xtoc[x] < 0 and nincluster[c] < clustersize:
xtoc[x] = c
nincluster[c] += 1
nall += 1
if nall >= Npt: break
return xtoc
#...............................................................................
if __name__ == "__main__":
import random
import sys
from scipy.spatial import distance
# http://docs.scipy.org/doc/scipy/reference/spatial.distance.html
Npt = 100
C = 3
dim = 3
seed = 1
exec( "\n".join( sys.argv[1:] )) # run this.py N= ...
np.set_printoptions( 2, threshold=200, edgeitems=5, suppress=True ) # .2f
random.seed(seed)
np.random.seed(seed)
X = np.random.uniform( size=(Npt,dim) )
centres = random.sample( X, C )
D = distance.cdist( X, centres )
xtoc = samesizecluster( D )
print "samesizecluster sizes:", np.bincount(xtoc)
# Npt=100 C=3 -> 32 34 34
于 2011-03-28T09:29:16.330 に答える
0
また、各パーティションのメンバーがアルゴリズムへの入力である BUCKET_SIZE 未満になるまでデータを分割する Kd ツリーも見てください。
これにより、バケット/パーティションがまったく同じサイズになるわけではありませんが、すべて BUCKET_SIZE 未満になります。
于 2015-03-19T01:14:57.807 に答える
-1
z 曲線やヒルベルト曲線などの空間充填曲線を調べたいとします。空間充填曲線を考えて、2 次元の問題を 1 次元の問題に減らすことができます。sfc インデックスは 2 次元データの並べ替えにすぎず、データの完全なクラスタリングではありませんが、ソリューションが完全なクラスターを満たさず、かなり高速に計算する必要がある場合に役立ちます。
于 2011-03-27T21:51:12.707 に答える