階層クラスター分析-Wikipedia
いつ 階層クラスター分析 クラスター分析のための特定のファミリーの距離ベースのメソッド(データベースの構造発見)を指す場合。クラスターは、他のクラスターのオブジェクトよりも距離が低い(またはその逆:類似性が高い)オブジェクトで構成されています。
このファミリの手順は、使用される距離または近接性(オブジェクト間だけでなく、クラスター全体の間)およびそれらの計算規制に従って区別できます。
計算規制に分割された場合、2つの重要なタイプの手順が区別されます。
- 分裂 すべてのオブジェクトが最初にクラスターと見なされ、その後、各クラスターが1つのオブジェクトのみで構成されるまで、すでに形成されたクラスターをより小さなクラスターに徐々に分割したクラスタープロセス。 (「トップダウンプロセス」とも呼ばれます)
- 凝集 各オブジェクトが最初にクラスターを形成し、次にすべてのオブジェクトがクラスターに属するまで既に形成されたクラスターを徐々に要約するクラスタープロセス。 (「ボトムアッププロセス」とも呼ばれます)
両方の手順で、一度形成されたクラスターを変更することはできません。構造は常に洗練されている(「分裂」)または粗い(「凝集」)のみであるため、厳格なクラスター階層が生じるようになります。結果の階層は、それがどのように計算されたかを見ることができなくなりました。
階層クラスター分析の利点は次のとおりです 柔軟性 手順には距離関数と融合法とは別の個別のパラメーターがなく、結果が下部構造を可能にするクラスター階層であるという複雑なスペーサー寸法を使用することにより。
欠点は、結果の分析です。などのその他の手順B. K-Meansアルゴリズム、DBSCANまたは階層光学アルゴリズムは、クラスター内のデータの単一のパーティションを提供します。階層的なクラスター分析は、多くのこのようなパーティションを提供し、ユーザーはパーティションの方法を決定する必要があります。ただし、ユーザーがクラスターの定性的動作の概要をユーザーに提供するため、これも利点になる可能性があります。この知識は、一般的なトポロジーデータ分析の基本であり、特に持続的な相同性です。
階層クラスター分析のもう1つの欠点は、実行時間の複雑さです。すべてのステップにあるため、実際と研究では、凝集計算がはるかに頻繁に発生します。
クラスターを要約する方法はあります。
リード。ただし、特別な場合、の完全な複雑さを伴う手順
知られています。しかし、すべてのステップには素朴です
データレコードを共有する機会。
階層クラスター分析のもう1つの欠点は、クラスターモデルを提供しないことです。たとえば、使用される寸法に応じて、チェーン効果(「シングルリンク効果」)が作成され、小さなクラスターは、いくつかの要素のみで構成される外れ値から生成されることがよくあります。したがって、見つかったクラスターは、モデルを取得するために通常、その後分析する必要があります。
階層的クラスター中に発生するツリー構造を視覚化するために、これは 樹状突起 (ギリシャ語。 木 (デンドロン)=ツリー)。樹状図は、データの量の階層分解であるツリーです
より小さなサブ量で。ルートは、全量を含む単一のクラスターを表します
含む。木の葉はクラスターを表し、そこにはデータの量の単一のオブジェクトがあります。内側の結び目は、子供のすべてのノードの結合を表します。属性として、結び目と彼の子供のノードの1つの間の各エッジには、2つの代表的な量のオブジェクト間の距離がまだあります。
軸が距離または(un)類似性を表示するために使用されると、樹状図はより有益になります。 2つのクラスターがまとめられている場合、これらのクラスターは互いに一定の距離または(un-)類似性を持ちます。接続ラインはこの高さで描画されます。隣接する例では、z。 B.オブジェクトRR1とRR4は、約62の類似性尺度の値にまとめられました。 「高さ」は水平軸です。
この表現では、樹状図を適切な高さに切断することにより、目的の数のクラスターを選択できます。通常、あなたは距離の間に大きな飛躍があるか、2つの融合の間に(un)類似性がある場所を探しています。 B.高さ40の右樹状図には、4つのクラスターがあり、そのうち2つは個々のオブジェクト(RR2、RR5)のみが含まれ、1つのクラスターには2つのオブジェクト(RR3とRR6)が含まれ、最後のクラスターには他のすべてのオブジェクトが含まれます。サイズが大幅に異なる階層クラスターがある場合、さまざまな高さで分解する必要がある場合があります。クラスターはまだ高さで近隣に接続されていますが、この高さの別の(「薄い」)クラスターは個々のオブジェクトに分類されます。
凝集体と分裂的な階層クラスター分析の両方で、2つのオブジェクト、1つのオブジェクトとクラスターまたは2つのクラスターの距離または(UN)類似性を計算する必要があります。基礎となる変数のスケールレベルに応じて、異なる寸法が使用されます。
- カテゴリ(公称および順序)変数では、類似性の寸法が使用されます。 H.ゼロの値は、オブジェクトに最大の欠如を持っていることを意味します。これらは距離寸法に変換できます。
- メトリック変数の場合、距離寸法が使用されます。 H.ゼロの値とは、オブジェクトの距離がゼロ、つまり最大の類似性があることを意味します。
次の表は、バイナリ変数とメトリック変数の類似性または距離の寸法を示しています。 2つ以上のカテゴリを持つカテゴリ変数は、いくつかのバイナリ変数に変換できます。 Gower距離は、公称スケーリング変数に対して定義することもできます。
例 [ 編集 | ソーステキストを編集します ]
- インターネットブックのディーラーは、2人の訪問者に対して、それぞれについて見たWebサイトを予約することを知っています したがって、ウェブサイトは0 =です 不特定 または1 = 見た 保存。 2人の訪問者がどのようになっているかに似ていますか? 2人の訪問者のどちらも見なかった本のウェブサイトの数( )、その多くは計算に含めるべきではありません。 Jaccard係数は、可能な係数、つまりH.両方の訪問者が見た本のウェブサイトの数( )、2人の訪問者のうち少なくとも1人が見た本のウェブサイトの数で分割されています( 最初の訪問者だけが見た本のウェブサイトの数、そして 2番目の訪問者だけが見た本のウェブサイトの数)。
- Allbusデータなど。回答オプションを使用した現在の経済状況の評価によると とても良い 、 腸 、 部分的に部分 、 悪い と ひどい 尋ねた。バイナリ変数が可能な回答のそれぞれに対して形成され、バイナリの類似性の次元を使用できるようになりました。異なるカテゴリを持ついくつかの変数では、カテゴリ番号に関する重みが行われるべきであることに注意する必要があります。
- IRISデータレコードでは、4つ( )Swordlilia Petalsの寸法。 2つの花びらの間の距離 と 計算するには、例えばB.ユークリッド距離を使用できます。
類似性または距離の測定は、最終的に、類似性または距離測定の目的のコンテンツ解釈に依存します。
階層クラスター分析の凝集計算は、最も単純で柔軟なケースです。最初は、各オブジェクトは最初に独自のクラスターとして理解されます。次に、各ステップで次のクラスターがクラスターに要約されます。クラスターがいくつかのオブジェクトで構成されている場合、クラスター間の距離が計算される方法を指定する必要があります。個々の凝集手順はここで異なります。すべてのクラスターが互いに特定の距離/類似性を超えたり、類似性を超えたり、十分な数のクラスターが決定されている場合、手順を終了できます。これは、最初に指定されているように、1つのオブジェクトしかないクラスターにとって些細なことです。
凝集クラスター分析を実行します
- a 距離- また 類似性 2つのオブジェクト間の距離を決定します
- a 融合アルゴリズム 2つのクラスター間の距離を決定します。
融合アルゴリズムの選択は、距離または類似性の選択よりも多くの場合重要です。
融合アルゴリズム [ 編集 | ソーステキストを編集します ]
次の表は、一般的な融合アルゴリズムの概要を示しています。距離
クラスター間
そして新しいクラスター
多くの場合、距離または非類似性を超えています
2つのオブジェクトによって計算されます。新しいクラスターBは、「グリーン」と「青」クラスターの合併から作成されます。
単一リンク [初め] [2] [3] [4] | |
---|---|
2つのクラスターからのすべての要素ペアからの最小距離
。 この手順は、鎖の形成を形成する傾向があります。 |
|
完全リンケージ [5] | |
2つのクラスターからのすべての要素ペアからの最大距離
。 この手順は小さなグループを形成する傾向があります。 |
|
算術平均(WPGMA)を使用した平均リンケージ、加重ペアグループ法 [6] | |
2つのクラスターからのすべての要素ペアからの平均距離
|
|
算術平均(UPGMA)を使用した平均グループリンケージ、マッキティ、非加重ペアグループメソッド [6] | |
AとBの統一からのすべての要素ペアからの平均距離
|
|
Centroid-Method、Centroids(UPGMC)を使用した非加重ペアグループ法 [6] | |
2つのクラスターの中心からの距離
したがって クラスターの中心 多分、 クラスターのもの 。 |
|
中央値、重心を使用した加重ペアグループ法(WPGMC) [7] | |
2つのクラスターの中心からの距離
したがって クラスターの中心 多分、 グリーンとブルークラスターのクラスター中心からの平均。 |
他の方法は次のとおりです。
- ワードの最小分散 [8]
- aとbの統一の分散の増加
したがって
クラスターの中心
多分、
クラスターのもの
。この手順は、同じ大きなクラスターを形成する傾向があります。
- EML
- 2つのクラスター間の距離は、 可能性 クラスターMultivariatは通常、同じ共分散行列で分布しているが、異なるサイズで分布しているという仮定の下で。手順はWardの最小分散に似ていますが、クラスターは異なるサイズを形成する傾向があります。
とりわけ、それは実際的な関連性です 単一のリンケージ 、それはアルゴリズムスリンクを使用して効率的な計算方法を可能にするためです。
融合アルゴリズムの例 [ 編集 | ソーステキストを編集します ]
これは、アルゴリズムの2番目のステップで特に明確になります。特定の距離測定を使用する場合、2つの次のオブジェクトが最初のステップでクラスターにマージされました。これは、距離マトリックスとして次のように表示できます。
間の距離 | cluster1 Object1 |
cluster2 Object2 |
cluster3 objekt3 |
cluster4 オブジェクト4 |
---|---|---|---|---|
Object1 | 0 | |||
Object2 | 4 | 0 | ||
objekt3 | 7 | 5 | 0 | |
オブジェクト4 | 8 | 十 | 9 | 0 |
最小の距離は、Object1とObject2(距離マトリックスの赤)の間で見つけることができるため、Object1とobject2をクラスター(合併)に要約します。これで、マトリックスを再度作成する必要があります( “o。” sits for oder)、つまり、新しいクラスターとobject3またはobject4の間の距離を再計算する必要があります(距離マトリックスでは黄色):
間の距離 | cluster1 Object1&2 |
cluster2 objekt3 |
cluster3 オブジェクト4 |
---|---|---|---|
Object1&2 | 0 | ||
objekt3 | 7 o。 5 | 0 | |
オブジェクト4 | 8 o。 10 | 9 | 0 |
手順は、2つの値のどれが距離決定に関連するかを決定します。
議事録 | 間の距離 | cluster1 Object1&2 |
cluster2 objekt3 |
cluster3 オブジェクト4 |
---|---|---|---|---|
|
Object1&2 | 0 | ||
objekt3 | 5 | 0 | ||
オブジェクト4 | 8 | 9 | 0 | |
|
Object1&2 | 0 | ||
objekt3 | 7 | 0 | ||
オブジェクト4 | 十 | 9 | 0 | |
|
Object1&2 | 0 | ||
objekt3 | 6 | 0 | ||
オブジェクト4 | 9 | 9 | 0 | |
|
Object1&2 | 0 | ||
objekt3 | 5.3 | 0 | ||
オブジェクト4 | 7.3 | 9 | 0 | |
|
Object1&2 | 0 | ||
objekt3 | 5 | 0 | ||
オブジェクト4 | 8 | 9 | 0 |
密度リンケージ [ 編集 | ソーステキストを編集します ]
密度リンケージは、各オブジェクトの密度値を推定します。計算では、通常の距離寸法の1つ、例えばB.オブジェクト間で使用されるマンハッタンの距離、ユークリッド距離。 2つのオブジェクトの密度値に基づいて、新しい距離は
それらの間で計算されます。これらはオブジェクトの周囲にも依存します
と
あちらへ。以前の融合方法の1つは、凝集クラスタリングに使用できます。
- 均一なカーネル
-
- その半径の医師 祭り
- 密度に感謝します より少ない距離の観測の割合として オブジェクトの もつ
- オブジェクト間の距離を計算します と いつ
- 最近隣人
-
- 隣人の数を配置します 祭り
- 距離を計算します のために プロパティの次の隣人
- 密度に感謝します より少ない距離の観測の割合として オブジェクトの 球体の体積で半径と分割しました
- オブジェクト間の距離を計算します と いつ
- ウォンズハイブリッド
-
- 最初にk-meansクラスタリングを実行し、 クラスターフォーカス
- 各クラスターの合計分散を計算します
- クラスターフォーカス間の距離を計算します と いつ
-
- ダイクラスター と 適用すると熱い隣接するひげ 。
密度リンケージアルゴリズムの問題の1つは、パラメーターを決定することです。
アルゴリズム光学とHDBSCAN*(DBSCANクラスタリングの階層的なバリアント)は、階層密度リンケージクラスタリングとして解釈することもできます。
融合アルゴリズムの効率的な計算 [ 編集 | ソーステキストを編集します ]
ランスとウィリアムズフォーミュラ [ 編集 | ソーステキストを編集します ]
ただし、オブジェクト間の距離を再計算するためにクラスターをマージする必要はありません。代わりに、上記の例のように、あなたは
スペーサーマトリックス。どのクラスターがマージされているかが明らかな場合、マージされたクラスターと他のすべてのクラスターの間の距離のみを再計算する必要があります。ただし、マージされたクラスター間の新しい距離はできます
そして別のクラスター
ランスとウィリアムズの式を使用して古い距離から計算されました:
ランスとウィリアムズは、式に基づいて独自の融合方法を提供しています。ランスウィリアムズフレキシブルベータ。
さまざまな融合方法にはさまざまな定数があります
、
、
と
それは次の表にあります。その意味は
クラスター内のオブジェクトの数
。
スリンクとクリンク [ 編集 | ソーステキストを編集します ]
階層クラスター分析の素朴な計算は複雑さが低いですが(複雑な類似性の場合、
また
発生)、場合によってはより効率的なソリューションがあります。
単一リンクのためにスリンクと呼ばれる凝集最適効率的な手順があります [9] 複雑さで
、および完全なリンケージクリンクでそれを一般化します [十] また、複雑さもあります
。
平均的なリンケージャなどの他の融合方法では、効率的なアルゴリズムは知られていません。 [11]
例 [ 編集 | ソーステキストを編集します ]
スイスの紙幣のデータセットは、100個の実際と100個の偽のスイスCHF 1,000紙幣で構成されています。各紙幣で6つの変数が上げられました。
- 紙幣の幅(幅)、
- 左側の紙幣の高さ(左)、
- 右側の紙幣の高さ(右)、
- 紙幣の上端(上)までの色の圧力の距離、
- 紙幣の下端(下)までの色の圧力の距離と
- 紙幣の色の圧力(対角線)の対角線(右下の左下)。
距離測定として、ユークリッドの距離は理想的です
- 。
また、次のグラフィックスでは、さまざまな階層クラスターメソッドが使用されました。各グラフィックは2つの部分で構成されています。
- データの最初の2つの主要なコンポーネントを左側に示します。このプレゼンテーションは、この(2次元)表現で、エリアの距離が6次元空間の間隔に対応するため、選択されます。したがって、2つの明確な個別のクラスターがある場合(クラスター間の距離が大きい)、このプレゼンテーションでも表示されます。同じクラスターに属するデータポイントは、同じ色でマークされています。黒いデータポイントのみがあるのは、各データポイントがクラスターを形成することです。
- 右側には、関連する樹状図が表示されます。 Y軸の「高さ」は、「距離」観測またはクラスターがまとめられて新しいクラスターを形成することを示します(Fusionアルゴリズムに従って)。 2つの部分クラスターが融合のための同じクラスターの一部である場合、樹状図はクラスターの対応する色で描画されます。さまざまなクラスターに属している場合、色は黒く使用されます。樹状図の左側の灰色のポイントは、合併が行われた「距離」を再び示しています。かなりの数のクラスターを決定するために、灰色のポイントで可能な最大のギャップが求められます。大きなギャップは、融合が次に融合するときにクラスターの間にマージされる大きな距離があることを意味するためです。
-
平均的なLinkkage手順のデータと樹図。
-
WARDメソッドを使用したデータと樹図。
-
完全なLinkKageプロセスのデータと樹図。
-
単一リンクケージ手順のデータと樹状図。
-
中央値のデータと樹状図。
-
Centroidメソッドを使用したデータと樹状図。
上記のように、理論的にはあります
データセットを持つ機会
オブジェクトを2つの部分に分割します。したがって、分裂的な手順では、通常、候補を生成するためのヒューリスティックが必要であり、たとえば、凝集計算と同じ次元で評価できるようにする必要があります。
Kaufman and Rousseeuw(1990)は、次のように分裂的なクラスタリング手順(Diana)を説明しています。 [12番目]
- すべての観測値を含むクラスターから始めます。
- すべてのクラスターの直径を計算します。直径は、クラスター内のすべてのオブジェクトの最大距離または非類似性です。
- 最大の直径のクラスターは、2つのクラスターに分割されます。
- これを行うために、オブジェクトはクラスター内で決定されます。クラスターは、平均距離が最も大きい、または他のすべてのオブジェクトと類似しています。 「Splinter Group」のコアを形成します。
- 残りのオブジェクトよりもSplinterグループに近いすべてのオブジェクトが、Splinterグループに割り当てられます。
- 手順2〜5は、すべてのクラスターに1つのオブジェクトのみが含まれるまで繰り返されます。
別の特別なアルゴリズムは、スペクトル緩和です。
基本と手順
- M.エステル、J。サンダー: データベースでの知識の発見。テクニックとアプリケーション。 スプリンガー、ベルリン、2000年。
- K. Backhaus、B。Erichson、W。Plinke、R。Weiber: 多変量解析方法。 スプリンガー
- S.ビッケル、T。シェファー、 マルチビュークラスタリング。 2004年、データマイニングに関するIEEE国際会議の議事録。
- J. Shi、J。Malik: 正規化されたカットと画像セグメンテーション。 Proc。 IEEE confの。 comp。ビジョンとパターン認識、プエルトリコ1997。
- L. XU、J。Neufield、B。Rarson、D。Shosuras: 最大マージンクラスタリング。 の: 神経情報処理システムの進歩。 17 (NIPS*2004)、2004
応用
- J. Bacher、A。Pöge、K。Wenzig: クラスター分析 – 分類方法のアプリケーション指向の紹介。 3.エディション。 Oldenbourg、Munich 2010、ISBN 978-3-486-58457-8。
- J.ボルツ: 社会科学者のための統計。 (第16章、クラスター分析)。スプリンガー、ベルリン1999年。
- W. Mr.Dle、L。Sommar: 適用された多変量統計分析。 スプリンガー、ニューヨーク2003。
- C.ホンブルク、H。クロマー: マーケティング管理:戦略 – 機器 – 実装 – 企業管理。 3.エディション。第8.2.2章、Gabler、Wiesbaden、2009年。
- H. Moosbrugger、D。フランク: クラスター – 個人研究における分析方法。アプリケーション指向の分類学的分類プロセスの紹介 。 Huber、Bern 1992、ISBN 3-456-82320-7。
- ↑ K. Florek、J。ukasiewicz、J。Perkal、H。Steinhaus、S。Zubrzycki: wroclawの分類法。 の: Antrophopレビュー。 17、1951、S。193–211。
- ↑ K. Florek、J。ukaszewicz、J。Perkal、H。Steinhaus、S。Zubrzycki: 完成したセットのポイントの接続と分割。 の: 数学者のインタビュー。 Vol。 2、No。3–4、1951、S。282–285。数学研究所ポーランド科学アカデミー。
- ↑ L. L.マッキティ: 直交および斜めのタイプと典型的な関連性を分離するための基本的な連鎖分析。教育的および心理的測定。 1957年。
- ↑ P. H.スナース: コンピューターの分類への適用。 の: Journal of General Microbiology。 17(1)、1957、S。201–226。
- ↑ P. N. M. MacNaughton-Smith: 個人を分類するためのいくつかの統計的およびその他の数値技術 。研究ユニットレポート6.ロンドン:Her下の静止オフィス、1965
- ↑ a b c R. R. Sokal、C。D。Michener: 体系的な関係を評価するための統計的方法 。の: カンザス大学科学速報38 、1958年、S。1409–1438。
- ↑ J. C. Gower: クラスター分析のいくつかの方法の比較。 の: 生体認証 23.4、
1967、S。623。 - ↑ J. H.ワードJR: 目的関数を最適化するための階層グループ。 の: Journal of the American Statistical Association。 58(301)、1963、S。236–244。
- ↑ R.シブソン: スリンク:シングルリンククラスターメソッドの最適なアルゴリズム 。の: コンピュータージャーナル 。 バンド 16 、 いいえ。 初め 。 British Computer Society、1973、 S. 30–34 ( web.Archive.org [PDF; 3.1 MB ; 2021年10月25日にアクセス])。
- ↑ D. defays: 完全なリンクメソッドの効率的なアルゴリズム 。の: コンピュータージャーナル 。 バンド 20 、 いいえ。 4 。 British Computer Society、1977、 S. 364–366 。
- ↑ ヨハネス・アセファルグ、クリスチャン・ベーム、カルステン・ボルグワード、マーティン・エステル、エシュレフ・ジャヌザジ、カリン・カイリング、ピア・クレガー、ヨルグ・サンダー、マティアス・シューベルト、アーサー・ザイメク: データベースでの知識発見、Kapitel 5:クラスタリング 。の: skript kdd i 。 2003( dbs.ifi.lmu.de [PDF])。
- ↑ L.カウフマン、P.J。 rousseeuw: データ内のグループの検索:クラスター分析の紹介 。ワイリー、ニューヨーク1990。
Recent Comments