7

サンプリングされたデータからグリッドを構築したいと考えています。k-means などの機械学習クラスタリング アルゴリズムを使用できますが、中心がほぼ均一に分布するように制限したいと考えています。

私は、scikit-learn の最近傍検索を使用するアプローチを思いつきました。ポイントをランダムに選択し、半径 r 内のすべてのポイントを削除してから繰り返します。これはうまくいきますが、これを行うためのより良い（より速い）方法があるかどうか疑問に思っています。

コメントに応えて、私は2つの代替方法を試しました.1つははるかに遅く、もう1つはほぼ同じです...

方法 0 (私の最初の試み):

def get_centers0(X, r): 

    N = X.shape[0]
    D = X.shape[1]
    grid = np.zeros([0,D])
    nearest = near.NearestNeighbors(radius = r, algorithm = 'auto')

    while N > 0:
        nearest.fit(X)
        x = X[int(random()*N), :]
        _, del_x = nearest.radius_neighbors(x)
        X = np.delete(X, del_x[0], axis = 0)
        grid = np.vstack([grid, x])
        N = X.shape[0]

    return grid

方法 1 (事前計算されたグラフを使用):

def get_centers1(X, r): 

    N = X.shape[0]
    D = X.shape[1]
    grid = np.zeros([0,D])
    nearest = near.NearestNeighbors(radius = r, algorithm = 'auto')
    nearest.fit(X)
    graph = nearest.radius_neighbors_graph(X)

    #This method is very slow even before doing any 'pruning'

方法 2:

def get_centers2(X, r, k): 

    N = X.shape[0]
    D = X.shape[1]
    k = k
    grid = np.zeros([0,D])
    nearest = near.NearestNeighbors(radius = r, algorithm = 'auto')

    while N > 0:
        nearest.fit(X)
        x = X[np.random.randint(0,N,k), :]

        #min_dist = near.NearestNeighbors().fit(x).kneighbors(x, n_neighbors = 1, return_distance = True)
        min_dist = dist(x, k, 2, np.ones(k)) # where dist is a cython compiled function
        x = x[min_dist < 0.1,:]

        _, del_x = nearest.radius_neighbors(x)
        X = np.delete(X, del_x[0], axis = 0)
        grid = np.vstack([grid, x])
        N = X.shape[0]

    return grid

これらを次のように実行します。

N = 50000
r = 0.1
x1 = np.random.rand(N)
x2 = np.random.rand(N)
X = np.vstack([x1, x2]).T

tic = time.time()
grid0 = get_centers0(X, r)
toc = time.time()
print 'Method 0: ' + str(toc - tic)

tic = time.time()
get_centers1(X, r)
toc = time.time()
print 'Method 1: ' + str(toc - tic)

tic = time.time()
grid2 = get_centers2(X, r)
toc = time.time()
print 'Method 1: ' + str(toc - tic)

方法0と2はほぼ同じです...

Method 0: 0.840130090714
Method 1: 2.23365592957
Method 2: 0.774812936783
4

4 に答える 4

4

質問から、あなたが何をしようとしているのか正確にはわかりません。「おおよそのグリッド」または「一様分布」を作成したいと言われていますが、提供するコードは、ペアごとの距離が より大きくならないようにポイントのサブセットを選択しますr。

いくつかの可能な提案:

  • おおよそのグリッドが必要な場合は、おおよそのグリッドを作成してから、各グリッド ポイントの最近傍をクエリします。アプリケーションによっては、これらの結果をさらにトリミングして、グリッド ポイントからの距離が実際に役立つよりも大きいカットアウト ポイントにする場合があります。

  • ポイント間から引き出されたほぼ均一な分布が必要な場合は、各ポイントでカーネル密度推定 ( sklearn.neighbors.KernelDensity) を実行し、各ポイントでローカル密度の逆数によって重み付けされたデータセットからランダム化されたサブセレクションを実行します。

  • ペアごとの距離が よりも大きくないようなポイント のサブセットが必要な場合は、まずradiusを使用しrて を構築します。これにより、一度に、近すぎるすべてのポイントのリストが得られます。次に、上で書いたものと同様の剪定アルゴリズムを使用して、これらの疎グラフ距離に基づいてポイントを削除できます。radius_neighbors_graphr

それが役立つことを願っています！

于 2013-10-30T15:13:57.390 に答える
4

以前の試みよりもはるかに効率的な非常に単純な方法を思いつきました。

これは単純にデータ セットをループし、既存のすべての中心からの距離が r よりも大きい場合にのみ、現在のポイントをグリッド ポイントのリストに追加します。この方法は、以前の試行よりも約 20 倍高速です。関連する外部ライブラリがないため、これをすべてcythonで実行できます...

@cython.boundscheck(False)
@cython.wraparound(False)
@cython.nonecheck(False)
def get_centers_fast(np.ndarray[DTYPE_t, ndim = 2] x, double radius):

    cdef int N = x.shape[0]
    cdef int D = x.shape[1]
    cdef int m = 1
    cdef np.ndarray[DTYPE_t, ndim = 2] xc = np.zeros([10000, D])
    cdef double r = 0
    cdef double r_min = 10
    cdef int i, j, k

    for k in range(D):
        xc[0,k] = x[0,k]

    for i in range(1, N):
        r_min = 10
        for j in range(m):
            r = 0
            for k in range(D):
                r += (x[i, k] - xc[j, k])**2
            r = r**0.5
            if r < r_min:
                r_min = r
        if r_min > radius:
            m = m + 1
            for k in range(D):
                xc[m - 1,k] = x[i,k]

    nonzero = np.nonzero(xc[:,0])[0]
    xc = xc[nonzero,:]

    return xc

これらのメソッドを次のように実行します。

N = 40000
r = 0.1
x1 = np.random.normal(size = N)
x1 = (x1 - min(x1)) / (max(x1)-min(x1))
x2 = np.random.normal(size = N)
x2 = (x2 - min(x2)) / (max(x2)-min(x2))
X = np.vstack([x1, x2]).T

tic = time.time()
grid0 = gt.get_centers0(X, r)
toc = time.time()
print 'Method 0: ' + str(toc - tic)

tic = time.time()
grid2 = gt.get_centers2(X, r, 10)
toc = time.time()
print 'Method 2: ' + str(toc - tic)

tic = time.time()
grid3 = gt.get_centers_fast(X, r)
toc = time.time()
print 'Method 3: ' + str(toc - tic)

新しい方法は約 20 倍高速です。早い段階でループを停止すれば、さらに高速になる可能性があります (たとえば、k 回の連続反復が新しい中心の生成に失敗した場合)。

Method 0: 0.219595909119
Method 2: 0.191949129105
Method 3: 0.0127329826355
于 2013-11-01T02:11:34.420 に答える
1

nearestおそらく、プロセスを高速化するために、k << N の削除ごとにオブジェクトを再調整することしかできませんでした。ほとんどの場合、近隣構造はあまり変化しないはずです。

于 2013-10-30T10:00:09.027 に答える
0

次のいずれかを再発明しようとしているようです。

  • クラスター機能 (BIRCH を参照)
  • データ バブル (「データ バブル: 階層的クラスタリングのための品質保持パフォーマンスの向上」を参照)
  • 林冠の事前クラスタリング

つまり、この概念は、わずかなバリエーションで少なくとも 3 回発明されています。

技術的には、クラスタリングではありません。K-means も実際にはクラスタリングではありません。

これは、ベクトル量子化としてより適切に説明されます。

于 2013-10-31T07:50:57.477 に答える