ボロノイ図(ボロノイ分解のプロット)は、距離行列(DM)を視覚的に表す1つの方法です。
また、Rを使用して作成およびプロットするのも簡単です。両方を1行のRコードで実行できます。
計算幾何学のこの側面に精通していない場合は、2つの関係(VDとDM)は簡単ですが、簡単な要約が役立つ場合があります。
距離行列(つまり、ある点と1つおきの点の間の距離を示す2D行列)は、kNN計算中の中間出力です(つまり、k最近傍法、に基づいて特定のデータ点の値を予測する機械学習アルゴリズム)。 'k'最近傍の加重平均値、距離単位。ここで、'k'は整数で、通常は3から5の間です。)
kNNは概念的に非常に単純です。トレーニングセットの各データポイントは、本質的にn次元空間の「位置」であるため、次のステップは、距離メトリックを使用して各ポイントと他のすべてのポイントとの間の距離を計算することです(例: 、ユークリッド、マンハッタンなど)。トレーニングステップ(つまり、距離行列の解釈)は簡単ですが、新しいデータポイントの値を予測するためにそれを使用することは、データ検索によって実際に妨げられます-数千または数百万の中から最も近い3または4ポイントを見つけますn次元空間に散在しています。
この問題に対処するために、2つのデータ構造が一般的に使用されます。kdツリーとVoroni分解(別名「ディリクレテッセレーション」)です。
ボロノイ分解(VD)は、距離行列によって一意に決定されます。つまり、1:1のマップがあります。したがって、実際には距離行列の視覚的表現ですが、これも目的ではありません。主な目的は、kNNベースの予測に使用されるデータを効率的に保存することです。
それを超えて、このように距離行列を表すのが良い考えであるかどうかは、おそらく何よりもあなたの聴衆に依存します。ほとんどの場合、VDと先行距離行列の関係は直感的ではありません。しかし、それは間違いではありません。統計トレーニングを受けていない人が、2つの母集団が同様の確率分布を持っているかどうかを知りたくて、QQプロットを示した場合、彼らはおそらくあなたが彼らの質問に関与していないと思うでしょう。したがって、自分が何を見ているのかを知っている人にとって、VDはDMのコンパクトで完全かつ正確な表現です。
では、どうやって作るのですか?
ボロノイデコンプは、トレーニングセット内からポイントのサブセットを(通常はランダムに)選択することによって構築されます(この数は状況によって異なりますが、1,000,000ポイントの場合、100がこのサブセットの妥当な数です)。これらの100個のデータポイントはボロノイセンター(「VC」)です。
ボロノイデコンプの背後にある基本的な考え方は、1,000,000のデータポイントをふるいにかけて最近傍を見つけるのではなく、これらの100を調べるだけでよいということです。次に、最近傍を見つけたら、実際の最近傍を検索します。そのボロノイセル内のポイントのみに制限されます。次に、トレーニングセット内の各データポイントについて、最も近いVCを計算します。最後に、各VCとそれに関連するポイントについて、凸包を計算します。概念的には、VCから最も遠いVCに割り当てられたポイントによって形成される外側の境界だけです。ボロノイ中心の周りのこの凸包は、「ボロノイセル」を形成します。完全なVDは、トレーニングセット内の各VCにこれらの3つのステップを適用した結果です。これにより、表面の完全なテッセレーションが得られます(下の図を参照)。
RでVDを計算するには、tripackパッケージを使用します。重要な関数は「voronoi.mosaic」であり、x座標とy座標を別々に渡すだけです(DMではなく生データ) 。次に、voronoi.mosaicを「plot」に渡すだけです。
library(tripack)
plot(voronoi.mosaic(runif(100), runif(100), duplicate="remove"))
