88

3次元のベクトルの大規模なセットがあります。ユークリッド距離に基づいてこれらをクラスター化し、特定のクラスター内のすべてのベクトルが互いの間のユークリッド距離がしきい値「T」未満になるようにする必要があります。

クラスタがいくつ存在するかわかりません。最後に、空間内のいずれかのベクトルとのユークリッド距離が「T」以上であるため、クラスタの一部ではない個々のベクトルが存在する可能性があります。

ここでは、どの既存のアルゴリズム/アプローチを使用する必要がありますか?

4

6 に答える 6

84

階層クラスタリングを使用できます。これはかなり基本的なアプローチであるため、多くの実装が利用可能です。たとえば、Python のscipyに含まれています。

たとえば、次のスクリプトを参照してください。

import matplotlib.pyplot as plt
import numpy
import scipy.cluster.hierarchy as hcluster

# generate 3 clusters of each around 100 points and one orphan point
N=100
data = numpy.random.randn(3*N,2)
data[:N] += 5
data[-N:] += 10
data[-1:] -= 20

# clustering
thresh = 1.5
clusters = hcluster.fclusterdata(data, thresh, criterion="distance")

# plotting
plt.scatter(*numpy.transpose(data), c=clusters)
plt.axis("equal")
title = "threshold: %f, number of clusters: %d" % (thresh, len(set(clusters)))
plt.title(title)
plt.show()

これにより、次の画像のような結果が生成されます。 クラスター

パラメーターとして指定されるしきい値は、ポイント/クラスターを別のクラスターにマージするかどうかを決定する基準となる距離値です。使用されている距離メトリックも指定できます。

クラスター内/クラスター間の類似性を計算する方法にはさまざまな方法があることに注意してください。たとえば、最も近いポイント間の距離、最も遠いポイント間の距離、クラスターの中心までの距離などです。これらの方法のいくつかは、scipys の階層的クラスタリング モジュール (単一/完全/平均... リンク) でもサポートされています。あなたの投稿によると、完全なリンケージを使用したいと思います。

このアプローチでは、他のクラスターの類似性基準、つまり距離しきい値を満たさない場合、小さな (単一点) クラスターも許可されることに注意してください。

パフォーマンスが向上するアルゴリズムは他にもあり、多くのデータ ポイントがある状況で適切になります。他の回答/コメントが示唆しているように、DBSCANアルゴリズムも見たいと思うかもしれません:

これらおよびその他のクラスタリング アルゴリズムの概要については、このデモ ページ (Python の scikit-learn ライブラリの) も参照してください。

その場所からコピーされた画像：

http://scikit-learn.org/stable/auto_examples/cluster/plot_cluster_comparison.html

ご覧のとおり、各アルゴリズムは、考慮する必要があるクラスターの数と形状についていくつかの仮定を行います。アルゴリズムによって課せられた暗黙の仮定か、パラメーター化によって指定された明示的な仮定のいずれかです。

于 2012-04-13T08:12:55.783 に答える
23

moooeeeep による回答では、階層的クラスタリングの使用が推奨されています。クラスタリングのしきい値を選択する方法について詳しく説明したいと思いました。

1 つの方法は、さまざまなしきい値t1、t2、t3、... に基づいてクラスタリングを計算し、クラスタリングの「品質」のメトリックを計算することです。前提は、最適な数のクラスターを使用したクラスター化の品質が、品質メトリックの最大値を持つことです。

私が過去に使用した優れた品質指標の例は、Calinski-Harabasz です。簡単に言うと、平均クラスター間距離を計算し、それらをクラスター内距離で割ります。最適なクラスタリングの割り当てには、互いに最も離れたクラスターと、「最も密な」クラスターが含まれます。

ところで、階層クラスタリングを使用する必要はありません。また、 k平均のようなものを使用して、各kについて事前に計算し、Calinski-Harabasz スコアが最も高いkを選択することもできます。

さらに参考文献が必要な場合はお知らせください。ハードディスクを調べていくつかの論文を探します。

于 2012-04-13T17:45:37.227 に答える
12

DBSCANアルゴリズムを確認してください。ベクトルの局所密度に基づいてクラスター化します。つまり、それらはε距離以上離れてはならず、クラスターの数を自動的に決定できます。また、外れ値、つまり不十分な数のε近傍を持つ点は、クラスターの一部ではないと見なされます。ウィキペディアのページには、いくつかの実装へのリンクがあります。

于 2012-04-13T09:50:15.020 に答える
0

階層クラスタリングを使用して、moooeeeep の回答に追加したいと思います。このソリューションは私にとってはうまくいきますが、しきい値を選択するのはかなり「ランダム」です。他のソースを参照して自分でテストしたところ、より良い方法が得られ、デンドログラムで簡単にしきい値を選択できました。

from scipy.cluster import hierarchy
from scipy.spatial.distance import pdist
import matplotlib.pyplot as plt

ori_array = ["Your_list_here"]
ward_array = hierarchy.ward(pdist(ori_array))
dendrogram = hierarchy.dendrogram(hierarchy.linkage(ori_array, method  = "ward"))
plt.title('Dendrogram')
plt.xlabel('Customers')
plt.ylabel('Euclidean distances')
plt.show()

このようなプロットが表示さ れます ここをクリック. 次に、距離 = 1 で水平線を引くと、接続詞の数が目的のクラスター数になります。ここでは、4 つのクラスターに対してしきい値 = 1 を選択します。

threshold = 1
clusters_list = hierarchy.fcluster(ward_array, threshold, criterion="distance")
print("Clustering list: {}".format(clusters_list))

これで、cluster_list の各値は、ori_array の対応するポイントの割り当てられたクラスター ID になります。

于 2020-11-11T06:53:49.700 に答える
0

大規模なデータ セットに適したOPTICSを使用します。

OPTICS: クラスター構造を特定するための順序付けポイント DBSCAN と密接に関連し、高密度のコア サンプルを見つけ、そこからクラスターを展開します1。DBSCAN とは異なり、可変近傍半径のクラスター階層を保持します。DBSCAN の現在の sklearn 実装よりも大規模なデータセットでの使用に適しています

from sklearn.cluster import OPTICS
db = OPTICS(eps=3, min_samples=30).fit(X)

必要に応じて、eps、min_samplesを微調整します。

于 2019-03-15T12:00:36.593 に答える