32

Python でのOPTICSアルゴリズムのまともな実装を探しています。これを使用して、密度ベースの点のクラスター ((x,y) ペア) を形成します。

(x,y) ペアを取り、クラスターのリストを出力するものを探しています。リスト内の各クラスターには、そのクラスターに属する (x, y) ペアのリストが含まれています。

4

7 に答える 7

10

OPTICS の完全かつ正確な Python 実装については知りません。ここに掲載されているリンクは、OPTICS のアイデアの大まかな概算にすぎません。また、高速化のためにインデックスを使用しないため、 で実行されるO(n^2)可能性が高くなりO(n^3)ます。

OPTICS には、当たり前のアイデア以外にも、いくつかのトリッキーな機能があります。特に、しきい値処理は、ここに掲載されている絶対しきい値ではなく、相対しきい値 ("xi") を使用して行うことを提案しています (その時点で、結果はほぼ DBSCAN の結果になります!)。

元の OPTICS の論文には、アルゴリズムの出力を実際のクラスターに変換するための提案されたアプローチが含まれています。

http://www.dbs.informatik.uni-muenchen.de/Publikationen/Papers/OPTICS.pdf

Weka での OPTICS の実装は、基本的に保守されておらず、不完全です。実際にクラスターを生成するのではなく、クラスターの順序を計算するだけです。このために、データベースの複製を作成します - それは実際には Weka コードではありません。

最初に OPTICS を公開したグループによって、ELKI in Javaで利用可能なかなり広範な実装があるようです。この「公式」バージョンに対して他の実装をテストすることをお勧めします。

于 2012-02-08T17:49:49.080 に答える
8

編集：以下は、OPTICSの完全な実装ではないことがわかっています。

クイック検索を行ったところ、次のものが見つかりました（光学）。その品質を保証することはできませんが、アルゴリズムは非常に単純なように見えるので、すぐに検証/適応できるはずです。

光学アルゴリズムの出力でクラスターを構築する方法の簡単な例を次に示します。

def cluster(order, distance, points, threshold):
    ''' Given the output of the options algorithm,
    compute the clusters:

    @param order The order of the points
    @param distance The relative distances of the points
    @param points The actual points
    @param threshold The threshold value to cluster on
    @returns A list of cluster groups
    '''
    clusters = [[]]
    points   = sorted(zip(order, distance, points))
    splits   = ((v > threshold, p) for i,v,p in points)
    for iscluster, point in splits: 
        if iscluster: clusters[-1].append(point)
        elif len(clusters[-1]) > 0: clusters.append([])
    return clusters

    rd, cd, order = optics(points, 4)
    print cluster(order, rd, points, 38.0)
于 2011-04-28T17:08:01.557 に答える
6

技術的には OPTICS ではありませんが、 https://github.com/lmcinnes/hdbscanで入手できる Python 用の HDBSCAN* 実装があります。これは、最大イプシロンが無限大で、クラスター抽出方法が異なる OPTICS と同等です。実装により、生成されたクラスター階層へのアクセスが提供されるため、必要に応じて、より従来の OPTICS メソッドを使用して、そこからクラスターを抽出することもできます。

イプシロン パラメータを制限していないにもかかわらず、この実装は kd-tree および ball-tree ベースの最小スパニング ツリー アルゴリズムを使用して O(n log(n)) パフォーマンスを達成し、非常に大きなデータセットを処理できることに注意してください。

于 2016-04-15T16:47:18.237 に答える
6

Python と OPTICS の C++ 実装を含むライブラリpyclusteringが存在します。

于 2018-06-11T08:19:37.947 に答える
1

http://www.chemometria.us.edu.pl/index.php?goto=downloadsの「密度ベースのクラスタリング アプローチ」を 参照してください。

于 2011-04-01T16:04:55.187 に答える
1

空間充填曲線または空間インデックスを見たいとします。sfc は、2 次元の複雑さを 1 次元の複雑さに減らします。Nick のヒルベルト曲線四分木空間インデックス ブログを見たいとします。私の sfc の実装を phpclasses.org (hilbert-curve) からダウンロードしたいと考えています。

于 2011-04-23T21:27:39.183 に答える