技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

---

5. クラスタリングの品質評価

クラスター分析はデータセットをサブセットに分解することであり、各サブセットはクラスターと呼ばれ、すべてのサブセットの集合はオブジェクトセットのクラスターと呼ばれます。優れたクラスタリング アルゴリズムは、高品質のクラスターと高品質のクラスターを生成する必要があります。つまり、クラスター内の全体的な類似性が最も高く、クラスター間の全体的な類似性が最も低くなります。多くのクラスタリング アルゴリズムには次のものが含まれることを考慮すると、 $け$- 平均化アルゴリズム、DBSCAN アルゴリズムなどはすべて、ユーザーが事前にクラスター内のクラスター数を指定する必要があります。$け$したがって、ｋの簡単な推定方法を以下に説明する。

(1) クラスタ数の推定

次のような多くのクラスタリング アルゴリズム $け$- 平均化アルゴリズム、たとえ DIANA アルゴリズムなどでも、事前にクラスターの数を指定する必要があります$け$、そして$け$の値はクラスタリングの品質に大きく影響しますが、クラスタの数は事前に決定する必要があります。$け$簡単な仕事ではありません。まず 2 つの極端なケースを考えてみましょう。
(1) データセット全体を置く$S$クラスターとしてみなされる、つまり $け=1$、これは簡単で便利に思えますが、このクラスター分析の結果には何の価値もありません。
(2) データセットを置く$S$の各オブジェクトはクラスターとして扱われます。つまり、 $け=|S|=ん$ 、したがって、最もきめの細かいクラスタリングが生成されます。したがって、各クラスタにはクラスタ内差分がなく、クラスタ内類似度が最も高くなる。ただし、この種のクラスタリングは次の目的には使用できません。$S$～についての情報を提供してください$S$一般的な説明。
クラスターの数がわかると思います。$け$少なくとも満足するはずです $2\le け\le ん-1$、ただしクラスターの数$け$正確にどの値が最も適切であるかは依然として曖昧です。
一般的に考えると、$け$の値は、データセットの分布の形状と規模、およびユーザーが必要とするクラスタリング解像度によって推定でき、学者はエルボー法、交差検証法、情報理論など、さまざまな推定方法を持っています。ベースのメソッドなど
シンプルでよく使われる$け$価値経験的推定方法は、次のような特徴を持つ人にとって、$ん$オブジェクトのデータセット、それがクラスター化されるクラスターの数$け$選ぶ $\begin{array}{r}\sqrt{\frac{ん}{2}}\end{array}$ それは適切です。現時点では、平均的な期待の下で、各クラスターは約$\sqrt{2ん}$ オブジェクト。これに基づいて、さらに追加の制限、つまりクラスターの数を提案する人もいます。$け<\sqrt{ん}$。
たとえば、次のように仮定します。$ん=8$、クラスターの数 $け=2$ は適切であり、クラスターごとに平均 4 つのポイントがあり、追加の経験式によると、$け<2.83$ 。クラスターの数に関するこれら 2 つの情報を使用する$け$例 10-5 では、実験式が一方の側面から説明されているように見えます。 $け=2$ はクラスターの最適な数です。

(2) 外部品質評価

クラスター数の適切な推定値がある場合$け$、たとえば、1 つ以上のクラスタリング方法を使用できます。$け$ - 平均アルゴリズム、凝集階層アルゴリズム、または DBSCAN アルゴリズムは、既知のデータセットに対してクラスター分析を実行し、さまざまな異なるクラスター化結果を取得します。ここで問題となるのは、どの方法がより良いクラスタリング結果をもたらすか、つまり、異なる方法で生成されたクラスタリング結果をどのように比較するかということです。これがクラスタリングの品質評価です。
現在、クラスタリングの品質評価には多くの方法がありますが、一般に、外部 (外部) 品質評価と内部 (内部) 品質評価の 2 つのカテゴリに分類できます。
外部品質評価では、理想的なクラスターがデータセット (通常は専門家によって構築される) にすでに存在すると仮定し、それを一般的に使用されるベンチマーク手法として、特定のアルゴリズムのクラスタリング結果と比較します。その比較評価には、主にクラスタリング エントロピーとクラスタリングが含まれます。はクラス精度の 2 つの一般的な方法です。

1. クラスタリングエントロピー法

仮説的なデータセット S = {X 1 、X 2 、…、X n } S = {X_1、X_2、…、X_n}S={バツ1​,バツ2​,…,バツん​}、そして T = {T 1 、T 2 、…、T m } T={T_1、T_2、…、T_m}T={T1​,T2​,…,Tメートル​} 専門家によって与えられた理想的な標準クラスタリングであり、 C = { C 1 、 C 2 、 … 、 C k } C = {C_1、C_2、…、C_k}Ｃ={Ｃ1​,Ｃ2​,…,Ｃけ​} についてのアルゴリズムによって決定されます$S$のクラスター、次にクラスターの場合${Ｃ}_{私}$ベースラインクラスタリングとの比較$T$のクラスタリング エントロピーは次のように定義されます。
$$え({Ｃ}_{私}|T)=-\sum _{じゅう=1}^{メートル}\frac{|{Ｃ}_{私}\cap T_{じゅう}|}{|{Ｃ}_{私}|}{\mathrm{見よグ}}_2\frac{|{Ｃ}_{私}\cap T_{じゅう}|}{|{Ｃ}_{私}|}\text{\hspace{1em}(10-20)}$$ そして$Ｃ$ベンチマークについて$T$全体的なクラスタリング エントロピーは、すべてのクラスタとして定義されます。${Ｃ}_{私}$ベンチマークについて$T$クラスタリング エントロピーの加重平均、つまり
$$え(Ｃ)=\frac{1}{\sum _{私=1}^{け}|{Ｃ}_{私}|}\sum _{私=1}^{け}|{Ｃ}_{私}|\times え({Ｃ}_{私}|T)\text{\hspace{1em}(10-21)}$$ クラスタリング エントロピー法では次のように考えられます。$え(Ｃ)$ 値が小さいほど、$Ｃ$ベースラインとの比較$T$クラスタリングの品質が高くなります。
式 (10-21) の右辺の第 1 項の分母に注目してください。$\begin{array}{r}\sum _{私=1}^{け}|{Ｃ}_{私}|\end{array}$ 各クラスタ内の要素数の合計であり、使用できません$ん$交換する。なぜなら、そのときだけ$Ｃ$がパーティショニングクラスタの場合、分母は次のようになります。$ん$、DBSCAN クラスタリングなどの一般的なクラスタリング手法の分母は、$ん$。

2. クラスタリングの精度

クラスタリングの精度 (精度) 評価の基本的な考え方は、クラスタ内のカテゴリの最大数をクラスタのカテゴリ ラベルとして使用することです。つまり、クラスタのカテゴリ ラベルとして使用します。${Ｃ}_{私}$、それが存在する場合$T_{じゅう}$作る ∣ C i ∩ T j ∣ = max ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } |C_icap T_j|=max{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}∣Ｃ私​∩Tじゅう​∣=最大{∣Ｃ私​∩T1​∣,∣Ｃ私​∩T2​∣,⋯,∣Ｃ私​∩Tメートル​∣}、と考えられます。${Ｃ}_{私}$カテゴリは$T_{じゅう}$ 。したがって、クラスターは、${Ｃ}_{私}$ベンチマークについて$T$精度は次のように定義されます。
J ( C i ∣ T ) = max ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } ∣ C i ∣ (10-22) J(C_i|T)=frac{max{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}}{|C_i|}tag{10-22}J(Ｃ私​∣T)=∣Ｃ私​∣最大{∣Ｃ私​∩T1​∣,∣Ｃ私​∩T2​∣,⋯,∣Ｃ私​∩Tメートル​∣}​(10-22) そして$Ｃ$ベンチマークについて$T$の全体的な精度はすべてのクラスターに対して定義されます。${Ｃ}_{私}$ベンチマークについて$T$クラスタリング精度の加重平均、つまり
$$J(Ｃ)=\frac{1}{\sum _{私=1}^{け}|{Ｃ}_{私}|}\sum _{私=1}^{け}|{Ｃ}_{私}|\times J({Ｃ}_{私}|T)\text{\hspace{1em}(10-23)}$$ クラスタリング精度手法では、次のように考えられます。$J(Ｃ)$ 値が大きいほど、クラスタリングされます。$Ｃ$ベースラインとの比較$T$クラスタリングの品質が高くなります。
また、一般的には、$1-J(Ｃ)$ 呼ばれた$Ｃ$ベンチマークについて$T$全体的なエラー率。したがって、クラスタリングの精度は、 $J(Ｃ)$ 大きなエラー率または全体的なエラー率$1-J(Ｃ)$ 小さい場合、クラスタリング アルゴリズムが異なるカテゴリのオブジェクトを異なるクラスタに適切にクラスタリングできる、つまりクラスタリングの精度が高いことを示しています。

(3) 内部品質評価

内部品質評価のための既知の外部ベンチマークはなく、データセットのみが使用されます$S$そしてクラスタリング$Ｃ$クラスターの固有の特性と規模を評価するには$Ｃ$の品質。すなわち、クラスタリング効果は、一般に、クラスタ内の平均類似度、クラスタ間の平均類似度、または全体の類似度を計算することによって評価される。
内部品質評価はクラスタリング アルゴリズムに関連しており、クラスタリングの有効性指標は主にクラスタリング効果の品質を評価したり、最適なクラスタ数を判断したりするために使用されます。したがって、クラスタリングの有効性は、通常、クラスタ内距離とクラスタ間距離の何らかの形式の比によって測定されます。このタイプの一般的に使用されるインジケーターには、CH インジケーター、ダン インジケーター、I インジケーター、Xie-eni インジケーターなどが含まれます。

1.CHインジケーター

CH インデックスは、Calinski-Harabasz インデックスの略称です。まず、各クラスター ポイントとそのクラスター中心間の距離の二乗和を計算して、クラス内の近さを測定します。次に、距離の二乗和を計算します。各クラスターの中心点と測定するデータセットの中心点との間のデータセットの分離、および分離と近さの比が CH インデックスです。
設定${\overline{バツ}}_{私}$クラスターを表します$Ｃ$中心点 (平均)、$\overline{バツ}$データセットを表します$S$の中心点$d({\overline{バツ}}_{私},\overline{バツ})$ のために${\overline{バツ}}_{私}$到着$\overline{バツ}$の特定の距離関数、その後のクラスタリング$Ｃ$中間クラスターのコンパクトさは次のように定義されます。
$$\text{痕跡}(あ)=\sum _{私=1}^{け}\sum _{{バツ}_{じゅう}\in {Ｃ}_{私}}d({バツ}_{じゅう},{\overline{バツ}}_{私}{)}^2\text{\hspace{1em}(10-24)}$$ したがって、Trace(A) はクラスターです。$Ｃ$クラスター中心間の距離の二乗の合計。そしてクラスタリング$Ｃ$分離度は次のように定義されます。
$$\text{痕跡}(B)=\sum _{私=1}^{け}|{Ｃ}_{私}|d({\overline{バツ}}_{私},\overline{バツ}{)}^2\text{\hspace{1em}(10-25)}$$ つまり、Trace(B) はクラスタリングしています。$Ｃ$各クラスターの中心点$S$の中心点からの距離の重み付き平方和。
このことから、もし$\begin{array}{r}いいえ=\sum _{私=1}^{け}|{Ｃ}_{私}|\end{array}$ 次に、CH インジケーターは次のように定義できます。
$${五}_{\text{中国語}}(け)=\frac{\text{痕跡}(B)/(け-1)}{\text{痕跡}(あ)/(いいえ-け)}\text{\hspace{1em}(10-26)}$$ 式 (10-26) は通常、次の 2 つの状況で使用されます。
(1) 2 つのアルゴリズムで得られたどちらのクラスタリングが優れているかを評価します。
データセットの分析に 2 つのアルゴリズムが使用されると仮定します。$S$クラスター分析が実行され、2 つの異なるクラスター (両方とも$け$クラスタ)、CH 値が大きいほど、クラスタ内の各クラスタがそれ自体に近くなり、クラスタがより分散されることを意味するため、より大きな CH 値に対応するクラスタリングがより優れています。
（２）同じアルゴリズムで得られたクラスタ数の異なる２つのクラスタのうちどちらが優れているかを評価する。
アルゴリズムにデータセットがあると仮定します。$S$クラスター分析が実行され、クラスターの数が次のように取得されました。${け}_1$そして$b_2$ 2 つのクラスターのうち、CH 値が大きいほどクラスター化結果が良好です。これは、このクラスターに対応するクラスターの数がより適切であることも意味します。したがって、式 (10-26) を繰り返し適用することにより、データセットを取得することもできます。$S$クラスタリングに最適なクラスターの数。

2.ダンインジケーター

ダンインジケーターはクラスターを使用します${Ｃ}_{私}$クラスター付き${Ｃ}_{じゅう}$間の最小距離 $d_s({Ｃ}_{私},{Ｃ}_{じゅう})$ すべてのクラスターの中で最大のクラスター直径を使用しながらクラスター間の分離を計算します。 最大⁡ { Φ ( C 1 ) 、 Φ ( C 2 ) 、 . . . 、 Φ ( C k ) } max{varPhi(C_1)、 varPhi(C_2)、...、varPhi(C_k)}最大{Φ(Ｃ1​),Φ(Ｃ2​),...,Φ(Ｃけ​)} クラスター内の緊密さを特徴付けるために、ダン指数は前者と後者の比率の最小値です。
VD ( k ) = min ⁡ i ≠ jds ( C i 、 C j ) max ⁡ { Φ ( C 1 ) 、 Φ ( C 2 ) 、 . 。 。 , Φ ( C k ) } (10-27) V_D(k)=min_{i≠j}frac{d_s(C_i,C_j)}{max{varPhi(C_1), varPhi(C_2),...,varPhi (C_k)}}タグ{10-27}五だ​(け)=私=じゅう分​最大{Φ(Ｃ1​),Φ(Ｃ2​),...,Φ(Ｃけ​)}ds​(Ｃ私​,Ｃじゅう​)​(10-27) Dunn 値が大きいほど、クラスター間の距離が遠くなり、対応するクラスター化がより良くなります。CH 評価指数と同様に、ダン指数は、異なるアルゴリズムによって取得されたクラスターの品質を評価するために使用できます。また、同じアルゴリズムによって異なるクラスター数で取得されたどのクラスターがより優れているかを評価するためにも使用できます。を求めるために使用できます$S$最適なクラスターの数。

6. 外れ値マイニング

外れ値は、ほとんどのデータから大幅に逸脱した、データ セット内の特別なデータです。前に紹介した分類やクラスタリングなどのデータ マイニング アルゴリズムの焦点は、ほとんどのデータに適用される規則的なパターンを発見することです。そのため、多くのデータ マイニング アルゴリズムは、マイニングの実装時に外れ値の影響を軽減または排除し、外れ値を削減しようとします。またはノイズとして無視されますが、多くの実際のアプリケーションでは、外れ値点の逸脱はランダムな要因によって引き起こされるのではなく、別のまったく異なるメカニズムによって引き起こされる可能性があり、特別な分析と利用のために掘り出す必要があるのではないかと人々は疑っています。たとえば、セキュリティ管理やリスク管理などのアプリケーション分野では、外れ値を特定するパターンの方が通常のデータのパターンよりも価値があります。

(1) 関連事項の概要

Outlier という言葉は通常、外れ値と訳されますが、異常とも訳されます。ただし、孤立点、異常点、新規点、逸脱点、例外点、ノイズ、異常データなど、アプリケーションの状況に応じてさまざまな別名が存在します。中国文献では、外れ値マイニングには、異常データ マイニング、異常データ検出、外れ値データ マイニング、例外データ マイニング、レア イベント マイニングなどの類似した用語があります。

1. 外れ値の生成

(1) データは、詐欺、侵入、病気の発生、異常な実験結果などによって引き起こされる異常に由来します。例えば、ある人の携帯料金は平均200元程度だが、ある月に突然数千元に上がったり、クレジットカードの利用額が通常は月5000元程度だったのが、ある月には3万元を超えたりする。このような外れ値は通常、データ マイニングにおいて比較的興味深いものであり、アプリケーションの重要なポイントの 1 つです。
(2) 気候変動、顧客の新しい購入パターン、遺伝子変異などのデータ分布の自然な特性を反映した、データ変数の固有の変化によって引き起こされます。これも興味深い焦点分野の 1 つです。
(3) データの測定および収集のエラーは、主に人的エラー、測定機器の故障、またはノイズの存在によるものです。たとえば、特定のコースでの学生の成績が -100 であるのは、プログラムによって設定されたデフォルト値が原因である可能性があります。企業のトップ マネージャーの給与が一般の従業員の給与よりも大幅に高いことが異常値のように見えるかもしれませんが、実際はそうなのです。妥当なデータ。

2. 外れ値マイニングの問題

通常、外れ値マイニングの問題は 3 つのサブ問題に分解して説明できます。
(1) 外れ値の定義
外れ値は実際の問題と密接に関係しているため、どのような種類のデータが外れ値または異常データであるかを明確に定義することが、外れ値マイニングの前提および主なタスクです。一般に、外れ値を正確に分析するには、ドメインの専門家の経験と知識を組み合わせる必要があります。適切な説明または定義を入力してください。
(2) マイニング外れ値
外れ値ポイントが明確に定義された後、定義された外れ値ポイントを効果的に特定またはマイニングするためにどのようなアルゴリズムを使用するかが、外れ値マイニングの重要なタスクです。外れ値マイニング アルゴリズムは通常、ユーザーの注意を引くために、データに反映され得るパターンの観点から疑わしい外れ値データをユーザーに提供します。
(3) 外れ値を理解する
外れ値マイニングの目標は、マイニング結果の合理的な説明、理解、および実際の適用の指導です。外れ値が生成されるメカニズムは不明であるため、外れ値マイニングアルゴリズムによって検出された「外れ値」が実際に実際の異常な動作に対応しているかどうかは、外れ値マイニングアルゴリズムによって説明および説明することはできず、外れ値マイニングアルゴリズムによってのみ説明できます。業界または分野の専門家が指示を理解し、説明します。

3. 外れ値の相対性

外れ値は、ほとんどのデータから明らかに逸脱している、データ セット内の特別なデータですが、「明らかに」と「ほとんど」は相対的なものです。つまり、外れ値は異なりますが、相対的なものです。したがって、外れ値を定義してマイニングする際には、考慮すべき問題がいくつかあります。
(1) グローバルまたはローカルの外れ値
データ オブジェクトは、そのローカルの近傍と比較すると外れ値である可能性がありますが、データ セット全体と比較すると外れ値ではありません。たとえば、身長 1.9 メートルの生徒は、本校の数学専攻のクラス 1 では異常値ですが、ヤオ・ミンのようなプロ選手を含む全国の人々の間では異常値ではありません。
(2) 外れ値の数
外れ値ポイントの数は不明ですが、通常ポイントの数は外れ値ポイントの数をはるかに上回るはずです。つまり、大規模なデータセットでは外れ値ポイントの数が占める割合は低いはずであると一般に考えられています。外れ値ポイントの割合は 5% 未満、さらには 1% 未満である必要があります。
(3) 点の外れ値要因
オブジェクトが外れ値であるかどうかを報告するために「はい」または「いいえ」を使用することはできません。代わりに、オブジェクトの逸脱度、つまり外れ値係数 (Outlier Factor) または外れ値スコア (Outlier Score) を使用する必要があります。グループからのデータの偏差を特徴付け、特定のしきい値よりも高い外れ値要素を持つオブジェクトを除外し、それらを意思決定者または専門家に提供して理解と説明を求め、実際の作業に適用します。

(2) 距離ベースの方法

1. 基本的な考え方

定義10-11 正の整数があります$け$、 物体$バツ$の $け$- 最近隣距離は、次の条件を満たす正の整数です。 $d_{け}(バツ)$：
(1)除く$バツ$さらに、少なくとも$け$オブジェクト$はい$満足する $d(バツ,はい)\le d_{け}(バツ)$。
(2)除く$バツ$さらに、最大でも $け-1$ オブジェクト$はい$満足する $d(バツ,はい)<d_{け}(バツ)$。
で$d(バツ,はい)$ オブジェクトです$バツ$そして$はい$それらの間の距離関数。

オブジェクトの $け$- 最近隣距離が大きいほど、オブジェクトがほとんどのデータから遠く離れている可能性が高くなります。$バツ$の $け$- 最近隣距離 $d_{け}(バツ)$ 外れ値要因として。

定義 10-12 作る D ( X , k ) = { Y ∣ d ( X , Y ) ≤ dk ( X ) ∧ Y ≠ X } D(X,k)={Y|d(X,Y)≤d_k(X)wedge Y≠X}だ(バツ,け)={はい∣d(バツ,はい)≤dけ​(バツ)∧はい=バツ}、その後、それは呼び出されます $だ(バツ,け)$ はい$バツ$の $け$-最近傍 (ドメイン)。

定義 10-12 から次のことがわかります。$だ(バツ,け)$ はい$バツ$中心として、距離として$バツ$を超えない $d_{け}(バツ)$ 物体$はい$で構成されたコレクション。特に注意を払う価値があるのは、$バツ$それに属しません $け$-最も近い隣人、つまり $バツ\notin だ(バツ,け)$ 。特に、$バツ$の $け$-最も近い隣人 $だ(バツ,け)$ 含まれるオブジェクトの数ははるかに多くなる可能性があります$け$、今すぐ $|だ(バツ,け)|\ge け$。

定義10-13 正の整数があります$け$、 物体$バツ$の $け$- 最近隣の外れ値係数は次のように定義されます。
$${\text{の}}_1(バツ,け)=\frac{\sum _{はい\in だ(バツ,け)}d(バツ,はい)}{|だ(バツ,け)|}\text{\hspace{1em}(10-28)}$$

2. アルゴリズムの説明

特定のデータセットと最近傍距離の数について$け$、上記の式を使用して計算できます。$け$-最近傍の外れ値要因を大きいものから小さいものへ順に出力します。その中で、外れ値要因である可能性が最も高いオブジェクトは、意思決定者または業界の専門家によって分析および判断される必要があります。 , どの点が本当に外れ値なのか。

アルゴリズム 10-8 距離ベースの外れ値検出アルゴリズム
入力: データセット$S$、最近傍距離の数$け$
出力: 外れ値の疑いのある点と対応する外れ値要因の降順リスト
（1）繰り返し
(2)テイク$S$未処理のオブジェクト$バツ$
(3) OK$バツ$の$け$-最も近い隣人$だ(バツ,け)$
(4) 計算$バツ$の$け$- 最近隣の外れ値係数${\text{の}}_1(バツ,け)$
（5）まで$S$すべてのポイントが処理されました
(6) はい${\text{の}}_1(バツ,け)$降順にソートして出力する$(バツ,{\text{の}}_1(バツ,け))$

3. 計算例

例10-12 11 点の 2 次元データセット$S$それは表 10-10 で与えられます。$け=2$、ユークリッド距離の二乗計算を使用します。 ${バツ}_7,{バツ}_{10},{バツ}_{11}$ 他のすべてのポイントに対する外れ値係数。

ほどく: アルゴリズムの原理を直感的に理解するために、$S$のデータ オブジェクトは、以下の図 (10-27) の平面上に表示されます。

以下では、指定した点とその他の点の外れ値係数をそれぞれ計算します。

(1) 計算対象${バツ}_7$外れ値要因
図からもわかるように、距離は${バツ}_7=(6,8)$ 最も近い点は、${バツ}_{10}=(5,7)$、そして $d({バツ}_7,{バツ}_{10})=1.41$、他の最も近いポイントは次のとおりである可能性があります。 ${バツ}_{11}=(5,2)$，${バツ}_9=(3,2)$，${バツ}_8=(2,4)$；
計算された$d({バツ}_7,{バツ}_{11})=6.08$，$d({バツ}_7,{バツ}_9)=6.71$，$d({バツ}_7,{バツ}_8)=5.66$
なぜなら$け=2$、それで $d_2({バツ}_7)=5.66$したがって、定義 10-11 によれば、次のようになります。 D ( X 7 , 2 ) = { X 10 , X 8 } D(X_7,2)={X_{10},X_8}だ(バツ7​,2)={バツ10​,バツ8​}
式(10-28)によれば、${バツ}_7$外れ値要因
$$\begin{array}{rl}{\text{の}}_1({バツ}_7,2)& =\frac{\sum _{はい\in いいえ({バツ}_7,2)}d({バツ}_7,はい)}{|いいえ({バツ}_7,け)|}=\frac{d({バツ}_7,{バツ}_{10})+d({バツ}_7,{バツ}_8)}{2}\\ & =\frac{1.41+5.66}{2}=3.54\end{array}$$(2) 計算対象${バツ}_{10}$外れ値要因 ${\text{の}}_1({バツ}_{10},2)=2.83$

(3) 計算対象${バツ}_{11}$外れ値要因 ${\text{の}}_1({バツ}_{11},2)=2.5$

(4) 計算対象${バツ}_5$外れ値要因 ${\text{の}}_1({バツ}_5,2)=1$

同様に、残りのオブジェクトの外れ値係数を計算できます。次の表 (10-11) を参照してください。

4. 外れ値係数の閾値

によると$け$ - 最近傍理論では、外れ値係数が大きいほど、外れ値である可能性が高くなります。したがって、外れ値と正常な点を区別するためにしきい値を指定する必要があります。最も単純な方法は外れ値点の数を指定することですが、この方法は単純すぎるため、実際の外れ値点をいくつか見逃したり、過剰な正常点を外れ値点の可能性があると判断したりするため、ドメインの専門家や意思決定者にとって困難が生じます。外れ値の理解と解釈において。
(1) 外れ値要因分割閾値法では、まず外れ値要因を降順に並べると同時に、外れ値要因に応じてデータオブジェクトの番号を昇順に振り直す。
(2) 外れ値要因による${\text{の}}_1(バツ,け)$ は縦軸、外れ値要因のシリアル番号は横軸、つまり (シリアル番号、${\text{の}}_1$値) を平面上にマークして接続して非増加ポリラインを形成し、そのポリラインが急激な減少と緩やかな減少で交差する点が、異常値係数を下回るしきい値として異常値係数に対応することがわかります。このしきい値以上は正常なオブジェクトであり、それ以外は外れ値である可能性があります。

例10-13 例10-12のデータセット$S$ 、その外れ値要因を降順およびシリアル番号で表 10-11 にまとめます。外れ値要素セグメント化しきい値方法に基づいて、外れ値ポイントのしきい値を見つけてみます。

ほどく: まず、(シリアル番号、 ${\text{の}}_1$値）を平面上の点として、平面上にマークされ、ポリラインで接続されます。以下の図 10-28 に示すように。

次に、図 10-28 を見ると、4 番目の点 (4, 1.27) の左側のポリラインは非常に急激に低下しているのに対し、右側のポリラインは非常に緩やかに低下していることがわかります。したがって、外れ値係数 1.27 が選択されています。しきい値。なぜなら${バツ}_7、{バツ}_{10}$ そして${バツ}_{11}$ 外れ値係数はそれぞれ 3.54、2.83、2.5 で、いずれも 1.27 より大きくなります。したがって、これら 3 つのポイントは外れ値ポイントである可能性が最も高く、残りのポイントは通常のポイントです。
図 10-27 をもう一度見ると、次のことがわかります。${バツ}_7、{バツ}_{10}$ そして${バツ}_{11}$ 実際、左側の密集した大部分のオブジェクトからは遠く離れているため、それらをデータセットとして扱います$S$外れ値は妥当です。

5. アルゴリズムの評価

距離ベースの外れ値検出方法の最大の利点は、原理がシンプルで使いやすいことですが、その欠点は主に次の点に反映されます。
(1) パラメータ$け$この選択には、パラメータに対するテスト結果の影響を判断するための簡単で効果的な方法がありません。$け$感受性の程度に関して広く受け入れられている分析結果はありません。
(2) 時間計算量は次のようになります。$お(|S{|}^2)$、大規模なデータセットに対するスケーラビリティが欠けています。
(3) グローバルな外れ値係数しきい値を使用しているため、異なる密度の領域を含むデータ セット内の外れ値を検出することは困難です。

(3) 相対密度による方法

距離法はグローバルな外れ値チェック方法ですが、異なる密度領域のデータ セットを処理できません。つまり、実際のアプリケーションでは、すべてのデータが単一の密度で分布しているわけではありません。データセットに複数の密度分布が含まれている場合、または異なる密度サブセットが混合されている場合、距離などのグローバルな外れ値検出方法は通常うまく機能しません。これは、オブジェクトが外れ値であるかどうかは周囲のデータとの関係だけではないためです。近隣の密度に関係します。

1. 相対密度の概念

密度近傍の観点から見ると、外れ値は低密度領域にあるオブジェクトであるため、局所近傍密度とオブジェクトの相対密度の概念を導入する必要があります。

定義10-14 (1) 物体$バツ$の$け$- 最近傍局所密度 (密度) は次のように定義されます。
$$\text{ダスティ}(バツ,け)=\frac{|だ(バツ,け)|}{\sum _{はい\in だ(バツ,け)}d(バツ,はい)}\text{\hspace{1em}(10-29)}$$ (2) 物体$バツ$の$け$・最近傍局所相対密度（相対密度）
$$\text{rdsty}(バツ,け)=\frac{\sum _{はい\in だ(バツ,け)}\text{ダスティ}(バツ,け)/|だ(バツ,け)|}{\text{ダスティ}(バツ,け)}\text{\hspace{1em}(10-30)}$$ で$だ(バツ,け)$ それはオブジェクトです$バツ$の$け$- 最近隣 (定義 10 ～ 12 で指定)、$|だ(バツ,け)|$ コレクション内のオブジェクトの数です。

2. アルゴリズムの説明

による $\text{rdsty}(バツ,け)$ 外れ値として${\text{の}}_2(バツ,け)$、その計算は 2 つのステップに分かれています
(1) 隣人の数に応じて$け$、各オブジェクトを計算します$バツ$の$け$-最近傍局所密度 $\text{ダスティ}(バツ,け)$
(2) 計算$バツ$最近傍の平均密度と$け$-最近傍局所相対密度 $\text{rdsty}(バツ,け)$
データ セットは複数の自然クラスターで構成されます。クラスター内の中心点に近いオブジェクトの相対密度は 1 に近く、クラスターの端またはクラスターの外側にあるオブジェクトの相対密度は比較的大きくなります。したがって、相対密度値が大きいほど、外れ値である可能性が高くなります。

アルゴリズム 10-9 相対密度に基づく外れ値検出アルゴリズム
入力: データセット$S$、最近傍の数$け$
出力: 外れ値の疑いのある点と対応する外れ値要因の降順リスト
（1）繰り返し
(2)テイク$S$未処理のオブジェクト$バツ$
(3) OK$バツ$の$け$-最も近い隣人$だ(バツ,け)$
(4) 活用$だ(バツ,け)$計算する$バツ$密度$\text{ダスティ}(バツ,け)$
（5）まで$S$すべてのポイントが処理されました
（6）繰り返す
(7)テイク$S$の最初のオブジェクト$バツ$
(8) OK$バツ$の相対密度$\text{rdsty}(バツ,け)$に割り当てます。${\text{の}}_2(バツ,け)$
（9）まで$S$内のすべてのオブジェクトが処理されました
(10) 右${\text{の}}_2(バツ,け)$降順にソートして出力する$(バツ,{\text{の}}_2(バツ,け))$

例10-14 例10-12に示す2次元データセットの場合$S$ (詳細については、表 10-10 を参照)$け=2$、ユークリッド距離を計算してみます ${バツ}_7,{バツ}_{10},{バツ}_{11}$ 等しいオブジェクトの相対密度に基づく外れ値係数。

ほどく：なぜなら$け=2$, したがって、すべてのオブジェクトの 2 最近傍局所密度が必要になります。

(1) 表 10-11 の各データ オブジェクトの 2 近傍を検索します。 $だ({バツ}_{私},2)$。
例 10-12 と同じ計算方法に従って、次を得ることができます。
D (X 1 , 2 ) = {X 2 , X 3 , X 5 }、 D (X 2 , 2 ) = {X 1 , X 6 }、 D (X 3 , 2 ) = {X 1 , X 4 }、 D (X 4 , 2 ) = {X 3 , X 5 }、 D (X 5 , 2 ) = {X 1 , X 4 , X 6 , X 9 }、 D (X 6 , 2 ) = {X 2 , X 5 , X 8 }、 D (X 7 , 2 ) = {X 10 , X 8 }、 D (X 8 , 2 ) = {X 2 , X 6 }、 D (X 9 , 2 ) = {X 5 , X 4 、X 6 }、D (X 10 、2) = {X 7 、X 8 }、D (X 11 、2) = {X 9 、X 5 } $$begin{aligned} &D(X_1,2)={X_2,X_3,X_5}，D(X_2,2)={X_1,X_6}， D(X_3,2)={X_1,X_4}，\ &D(X_4,2)={X_3,X_5}， D(X_5,2)={X_1,X_4,X_6,X_9}，D(X_6,2)={X_2,X_5,X_8}，\ &D(X_7,2)={X_{10},X_8}， D(X_8,2)={X_2,X_6}， D(X_9,2)={X_5,X_4,X_6}，\ &D(X_{10},2)={X_7,X_8}， D(X_{11},2)={X_9,X_5} end{aligned}$$ ​だ(バツ1​,2)={バツ2​,バツ3​,バツ5​}，だ(バツ2​,2)={バツ1​,バツ6​}，              だ(バツ3​,2)={バツ1​,バツ4​}，だ(バツ4​,2)={バツ3​,バツ5​}，       だ(バツ5​,2)={バツ1​,バツ4​,バツ6​,バツ9​}，だ(バツ6​,2)={バツ2​,バツ5​,バツ8​}，だ(バツ7​,2)={バツ10​,バツ8​}，     だ(バツ8​,2)={バツ2​,バツ6​}，               だ(バツ9​,2)={バツ5​,バツ4​,バツ6​}，だ(バツ10​,2)={バツ7​,バツ8​}，     だ(バツ11​,2)={バツ9​,バツ5​}​

(2) 各データオブジェクトの局所密度を計算する $\text{ダスティ}({バツ}_{私},2)$：

①計算する${バツ}_1$密度
なぜなら D ( X 1 , 2 ) = { X 2 , X 3 , X 5 } D(X_1,2) = {X_2,X_3,X_5}だ(バツ1​,2)={バツ2​,バツ3​,バツ5​}, したがって、計算後、次のようになります。 $d({バツ}_1,{バツ}_2)=1$，$d({バツ}_1,{バツ}_3)=1$，$d({バツ}_1,{バツ}_5)=1$；
式 (10-29) によれば、次のようになります。
$$\begin{array}{rl}\text{ダスティ}({バツ}_1,2)& =\frac{|だ({バツ}_1,2)|}{\sum _{はい\in いいえ({バツ}_1,2)}d({バツ}_1,はい)}\\ & =\frac{|いいえ({バツ}_1,2)|}{d({バツ}_1,{バツ}_2)+d({バツ}_1,{バツ}_3)+d({バツ}_1,{バツ}_5)}\\ & =\frac{3}{1+1+1}=1\end{array}$$

② 計算${バツ}_2$密度
なぜなら D ( X 2 , 2 ) = { X 1 , X 6 } D(X_2,2) = { X_1 , X_6 }だ(バツ2​,2)={バツ1​,バツ6​}、したがって、計算された $d({バツ}_2,{バツ}_1)=1$，$d({バツ}_2,{バツ}_6)=1$；
式 (10-29) によれば、次のようになります。
$$\begin{array}{rl}\text{ダスティ}({バツ}_2,2)& =\frac{|だ({バツ}_2,2)|}{\sum _{はい\in いいえ({バツ}_2,2)}d({バツ}_2,はい)}=\frac{2}{1+1}=1\end{array}$$

他のデータ オブジェクトの局所密度も同様に計算できます。以下の表 10-12 を参照してください。

(3) 各オブジェクトの計算${バツ}_{私}$の相対密度 $\text{rdsty}({バツ}_{私},2)$、それを外れ値要因とみなします ${\text{の}}_2$。
①計算する${バツ}_1$の相対密度
相対密度の式 (10-30) に従って、表 10-12 の各オブジェクトの密度値を使用すると、次のようになります。
$$\begin{array}{rl}\text{rdsty}({バツ}_1,2)& =\frac{\sum _{はい\in いいえ({バツ}_1,2)}\text{ダスティ}(はい,2)/|いいえ({バツ}_1,2)|}{\text{ダスティ}({バツ}_1,2)}\\ & =\frac{(1+1+1)/3}{1}=1={\text{の}}_2({バツ}_1,2)\end{array}$$

②同様の計算ができる ${バツ}_2、{バツ}_3、\dots 、{バツ}_{11}$ 相対密度値。
例えば${バツ}_5$次の相対密度:
$$\begin{array}{rl}\text{rdsty}({バツ}_5,2)& =\frac{\sum _{はい\in いいえ({バツ}_5,2)}\text{ダスティ}(はい,2)/|いいえ({バツ}_5,2)|}{\text{ダスティ}({バツ}_5,2)}\\ & =\frac{(1+1+1+0.79)/4}{1}=0.95={\text{の}}_2({バツ}_5,2)\end{array}$$ 結果を以下の表１０〜１３に要約する。

例10-15 表 10-14 に示すデータセットを考慮して、ユークリッド距離を使用して、$け=2,3,5$、各ポイントの値を計算します$け$-最近傍局所密度、$け$- 最近傍局所相対密度 (外れ値係数)${\text{の}}_2$) に基づいて$け$- 最近隣距離の外れ値係数${\text{の}}_1$。

ほどく: (1) 理解を容易にするために、次のようにすることができます。$S$点の相対位置は 2 次元平面上にマークされます (図 10-30)。

(2) 距離ベースのアルゴリズム 10-8 と相対密度ベースのアルゴリズム 10-9 をそれぞれ利用します。各オブジェクトを個別に計算する$け$- 最近傍局所密度$\text{ダスティ}$、$け$- 最近傍局所相対密度 (外れ値係数)${\text{の}}_2$) に基づいて$け$- 最近隣距離の外れ値係数${\text{の}}_1$、結果を表 10-15 にまとめます。

(3) 簡易分析
① 図 10-30 からわかるように、${バツ}_{15}$そして${バツ}_{16}$はい$S$明らかな異常値が 2 つあり、距離と相対密度に基づく方法を使用すると、それらをより適切に検出できます。
② この例から、2 つのアルゴリズムは次のようになります。$け$は予想ほど敏感ではありません。おそらく外れ値です。${バツ}_{15}$そして${バツ}_{16}$他のオブジェクトからの分離は非常に明白です。
③表 10-15 から分かるように、$け$2、3、または 5 を選択してください。${バツ}_1$地域の $\text{ダスティ}$ 値はよりも大幅に低い${バツ}_7$地域の $\text{ダスティ}$ この値は、図 10-30 に示す面密度と一致します。ただし、2 つの領域の相対密度値は${\text{の}}_2$ しかし、明らかな違いはほとんどありません。これは相対密度の性質によって決定されます。つまり、データ ポイントが均一に分布している場合、コア ポイントの相対密度は、ポイント間の距離に関係なく 1 になります。

7. その他のクラスタリング手法

1. クラスタリングアルゴリズムの改善

  （1）$け$-モッド （$け$-modes) アルゴリズムは$け$ - 平均アルゴリズムは数値属性の制限にのみ適しており、離散データの迅速なクラスタリングを達成するために提案されています。なぜなら$け$- モジュール式アルゴリズムは、単純な 0-1 マッチング方法を使用して、同じ離散属性の下にある 2 つの属性値間の距離を計算します。これにより、順序属性値間の差異が弱められます。つまり、2 つの属性値間の差異を完全に反映することはできません。同じ順序属性の下でも、まだ改善の余地があります。
  （2）$け$-プロトタイプ（$け$-Prototype) アルゴリズムと組み合わせた$け$- 平均化アルゴリズム$け$ - モジュラー アルゴリズムの利点は、離散属性と数値属性 (混合属性と呼ばれる) の両方を持つデータ セットをクラスター化できることです。個別の属性の場合は必要です$け$-モジュール式アルゴリズム計算オブジェクト$バツ$そして$はい$間の距離 $d_1(バツ,はい)$、数値属性の場合は、次を使用します。$け$- 平均化アルゴリズムのメソッドはオブジェクト間の距離を計算します $d_2(バツ,はい)$、そして最後に重み付け方法を使用します。 $\alpha d_1(バツ,はい)+(1-\alpha )d_2(バツ,はい)$ データセットオブジェクトとして$バツ$そして$はい$間の距離 $d(バツ,はい)$、で $\alpha \in [0,1]$ は重み係数です。通常は次のようになります。$\alpha =0.5$。
(3) BIRCH アルゴリズム (Balanced Iterative Reducing and Clustering using Hierarchies) は、包括的な階層クラスタリング手法です。クラスタリング機能 (CF) とクラスタリング機能ツリー (B ツリーに似た CF ツリー) を使用して、クラスタのクラスタを要約します。${Ｃ}_{私}$、で ${\text{CF}}_{私}=(に,{\text{LS}}_{私},{\text{SS}}_{私})$ 三つ子です、${ん}_{私}$はクラスター内のオブジェクトの数です。${\text{LS}}_{私}$はい${ん}_{私}$オブジェクトのコンポーネントの線形和、${\text{SS}}_{私}$はい${ん}_{私}$オブジェクトのコンポーネントの二乗の合計。
(4) CURE (Clustering using 代表者) アルゴリズムは、$け$ - 平均化アルゴリズムのもう 1 つの改善。多くのクラスタリング アルゴリズムは球状クラスタのクラスタリングのみに適していますが、一部のクラスタリング アルゴリズムは孤立点に対してより敏感です。 上記 2 つの問題を解決するために、CURE アルゴリズムが変更されました$け$- 平均化アルゴリズムはクラスター中心和を使用します$け$-中心点アルゴリズムは、クラスターを表すために単一の特定のオブジェクトを使用する従来の方法ですが、クラスター内の複数の代表オブジェクトを使用してクラスターを表すため、非球形クラスターのクラスタリングに適応して、クラスターの影響を軽減できます。クラスタリング上のノイズ。
(5) ROCK (RObust Clustering using linK) アルゴリズムは、バイナリまたはカテゴリカル属性データ セットに対して提案されたクラスタリング アルゴリズムです。
(6) OPTICS (クラスタリング構造を識別するための順序付けポイント) アルゴリズムは、DBSCAN アルゴリズムの密度を減らすために使用されます。$(\epsilon ,\text{最小ポイント})$ パラメータの感度。結果クラスターは明示的に生成されませんが、クラスター分析用の拡張クラスター ランキング (たとえば、到達可能距離を縦軸、サンプル ポイントの出力順序を横軸とした座標チャート) を生成します。このランキングは、各サンプル ポイントの密度に基づくクラスタリング構造を表します。任意の密度パラメータに基づいてこの並べ替えから取得できます。$(\epsilon ,\text{最小ポイント})$ DBSCAN アルゴリズムのクラスタリング結果。

2. その他の新しいクラスタリング手法

新しい理論や手法を使用して、新しいクラスタリング手法を設計します。

(1) グリッドベースのクラスタリング手法
グリッドベースの方法では、オブジェクト空間を限られた数のセルに定量化してグリッド構造を形成し、各次元の分割点の位置情報を配列に格納します。分割線は空間全体を通過し、すべてのクラスタリングが行われます。操作は、このグリッド構造 (つまり、量子化空間) で実行されます。この方法の主な利点は、その処理速度がデータ オブジェクトの数に依存せず、定量化空間の各次元のセルの数にのみ関係するという点です。クラスタリングの結果が犠牲になります。グリッド クラスタリング アルゴリズムには定量化スケールの問題があるため、通常、最初は小さなユニットからクラスターの検索を開始し、その後徐々にユニットのサイズを大きくし、満足のいくクラスターが見つかるまでこのプロセスを繰り返します。

(2) モデルベースのクラスタリング手法
モデルベースの方法では、クラスターごとにモデルを想定し、指定されたモデルに対するデータの最適な適合を見つけます。モデルベースの方法では、クラスターの位置を特定するサンプルの空間分布を反映する密度関数を確立することにより、特定のデータと特定のデータ モデル間の適応性の最適化を試みます。

(3) ファジィ集合に基づくクラスタリング手法
実際には、ほとんどのオブジェクトがどのクラスタに属するかという厳密な属性値は存在せず、それらの属性値と形式には中間または不確実性があり、これはソフト分割に適しています。ファジィ クラスタリング分析には、サンプルの帰属間の関係を記述し、現実世界を客観的に反映できるという利点があるため、今日のクラスター分析研究のホット スポットの 1 つとなっています。
ファジー クラスタリング アルゴリズムは、ファジー数学理論と不確実なクラスタリング手法に基づいた教師なし学習手法です。ファジー クラスタリングが提案されると、学術コミュニティから大きな注目を集めました。ファジー クラスタリングに関する研究も非常に活発です。

(4) ラフセットに基づくクラスタリング手法
ラフ クラスタリングは、ラフ集合理論に基づいた不確実なクラスタリング手法です。ラフ セットとクラスタリング アルゴリズム間の結合の観点から、ラフ クラスタリング手法は、強結合ラフ クラスタリングと弱結合ラフ クラスタリングの 2 つのカテゴリに分類できます。
もちろん、クラスター分析の新しい研究の方向性はこれらをはるかに超えています。たとえば、データ フロー マイニングとクラスター化アルゴリズム、不確実なデータとそのクラスター化アルゴリズム、量子コンピューティングと量子遺伝的クラスター化アルゴリズムはすべて、近年登場したクラスター化テクノロジーです。 . 最先端の研究テーマ。

3. その他の外れ値マイニング方法

前に紹介した外れ値マイニング手法は、外れ値マイニングの代表的な 2 つです。実際のアプリケーションでは、マイニング手法で使用される技術の種類や事前知識の使用によって、さらに多くの成熟した外れ値マイニング手法が決定されます。角度: 度。

(1) 使用する技術の種類
主に統計的手法、距離ベースの手法、密度ベースの手法、クラスタリングベースの手法、偏差ベースの手法、深さベースの手法、ウェーブレット変換ベースの手法、グラフベースの手法、パターンベースの手法、およびニューラルネットワークがあります。方法など。

(2) 事前知識の活用
正常クラスまたは異常値クラスの情報が入手できるかどうかに応じて、次の 3 つの一般的なアプローチがあります。
① 教師なし外れ値検出方法。つまり、データセットにカテゴリラベルなどの事前知識がありません。
② 教師付き外れ値検出方法、つまり、外れ値と正常点を含むトレーニングセットの存在を通じて外れ値の特徴を抽出します。
③ 半教師あり外れ値検出方法。トレーニング データにはラベル付きの正常データが含まれていますが、外れ値データ オブジェクトに関する情報はありません。