pdist

観測値ペア間のペアワイズ距離

構文

D = pdist(X)

D = pdist(X,Distance)

D = pdist(X,Distance,DistParameter)

D = pdist(X,Distance,CacheSize=cache)

D = pdist(X,Distance,DistParameter,CacheSize=cache)

説明

D = pdist(X) は、X 内の観測値ペア間のユークリッド距離を返します。

D = pdist(X,Distance) は、Distance で指定された方式を使用して距離を返します。

D = pdist(X,Distance,DistParameter) は、Distance および DistParameter で指定された方式を使用して距離を返します。DistParameter を指定できるのは、Distance が 'seuclidean'、'minkowski' または 'mahalanobis' である場合だけです。

D = pdist(X,Distance,CacheSize=cache) または D = pdist(X,Distance,DistParameter,CacheSize=cache) は、サイズが cache メガバイトのキャッシュを使用してユークリッド距離の計算を高速化します。この引数は、Distance が 'fasteuclidean'、'fastsquaredeuclidean'、または 'fastseuclidean' の場合のみ適用されます。

例

ユークリッド距離の計算と距離ベクトルから行列への変換

観測値ペア間のユークリッド距離を計算し、squareform を使用して距離ベクトルを行列に変換します。

3 つの観測値と 2 つの変数を使用して行列を作成します。

rng('default') % For reproducibility
X = rand(3,2);

ユークリッド距離を計算します。

D = pdist(X)

D = 1×3

    0.2954    1.0670    0.9448

ペアワイズ距離は (2,1)、(3,1)、(3,2) という順序で編成されます。観測値 i および j の間の距離は、squareform を使用すると簡単に求めることができます。

Z = squareform(D)

Z = 3×3

         0    0.2954    1.0670
    0.2954         0    0.9448
    1.0670    0.9448         0

squareform は、Z(i,j) が観測値 i および j の間のペアワイズ距離に対応する対称行列を返します。たとえば、観測値 2 および 3 の間の距離は次のように求めることができます。

Z(2,3)

ans = 
0.9448

Z を関数 squareform に渡して、関数 pdist の出力を再現します。

y = squareform(Z)

y = 1×3

    0.2954    1.0670    0.9448

squareform の出力 y と pdist の出力 D は同じです。

ミンコフスキー距離の計算

3 つの観測値と 2 つの変数を使用して行列を作成します。

rng('default') % For reproducibility
X = rand(3,2);

既定の指数 2 を使用してミンコフスキー距離を計算します。

D1 = pdist(X,'minkowski')

D1 = 1×3

    0.2954    1.0670    0.9448

指数を 1 にしてミンコフスキー距離を計算します。これは市街地距離に等しくなります。

D2 = pdist(X,'minkowski',1)

D2 = 1×3

    0.3721    1.5036    1.3136

D3 = pdist(X,'cityblock')

D3 = 1×3

    0.3721    1.5036    1.3136

カスタム距離関数の使用による、欠損要素があるペアワイズ距離の計算

NaN 値がある座標を無視するカスタム距離関数を定義し、この関数を使用してペアワイズ距離を計算します。

3 つの観測値と 2 つの変数を使用して行列を作成します。

rng('default') % For reproducibility
X = rand(3,2);

1 番目の観測値の 1 番目の要素が欠損していると仮定します。

X(1,1) = NaN;

ユークリッド距離を計算します。

D1 = pdist(X)

D1 = 1×3

       NaN       NaN    0.9448

観測値 i または j に NaN 値が含まれている場合、関数 pdist は i と j の間のペアワイズ距離として NaN を返します。したがって、(2,1) と (3,1) のペアワイズ距離である D1(1) および D1(2) は NaN 値になります。

NaN 値がある座標を無視してユークリッド距離を返すカスタム距離関数 naneucdist を定義します。

function D2 = naneucdist(XI,XJ)  
%NANEUCDIST Euclidean distance ignoring coordinates with NaNs
n = size(XI,2);
sqdx = (XI-XJ).^2;
nstar = sum(~isnan(sqdx),2); % Number of pairs that do not contain NaNs
nstar(nstar == 0) = NaN; % To return NaN if all pairs include NaNs
D2squared = sum(sqdx,2,'omitnan').*n./nstar; % Correction for missing coordinates
D2 = sqrt(D2squared);

pdist の入力引数として関数ハンドルを渡すことにより、naneucdist で距離を計算します。

D2 = pdist(X,@naneucdist)

D2 = 1×3

    0.3974    1.1538    0.9448

fasteuclidean 距離を使用したユークリッド距離計算の高速化

大規模な点の行列を作成し、既定の "euclidean" 距離計量を使用した pdist の所要時間を測定します。

rng default % For reproducibility
N = 10000;
X = randn(N,1000);
D = pdist(X); % Warm up function for more reliable timing information
tic
D = pdist(X);
standard = toc

standard = 
6.0508

次に、"fasteuclidean" 距離計量を使用した pdist の所要時間を測定します。キャッシュ サイズは 10 に指定します。

D = pdist(X,"fasteuclidean",CacheSize=10); % Warm up function
tic
D2 = pdist(X,"fasteuclidean",CacheSize=10);
accelerated = toc

accelerated = 
0.8650

計算の高速化によって標準よりも何倍速くなったかを評価します。

standard/accelerated

ans = 
6.9955

この例では、高速化したバージョンの方が計算が約 3 倍速くなっています。

入力引数

X — 入力データ

数値行列

入力データ。m 行 n 列の数値行列を指定します。行は各観測値に、列は各変数に対応します。

データ型: single | double

Distance — 距離計量

文字ベクトル | string スカラー | 関数ハンドル

距離計量。次の表に記載されているように文字ベクトル、string スカラーまたは関数ハンドルを指定します。

値	説明
'euclidean'	ユークリッド距離 (既定)
'squaredeuclidean'	2 乗ユークリッド距離(効率向上のみを目的に提供されているオプション。三角不等式は満たさない)。
'seuclidean'	標準化されたユークリッド距離。観測値間の各座標差は、標準偏差 S = std(X,'omitnan') の対応する要素で除算することによりスケーリングされます。S について別の値を指定するには、DistParameter を使用します。
'fasteuclidean'	予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算されるユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。詳細については、アルゴリズムを参照してください。
'fastsquaredeuclidean'	予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算される 2 乗ユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。詳細については、アルゴリズムを参照してください。
'fastseuclidean'	予測子の数が 10 個以上の場合に時間の短縮になる代替アルゴリズムを使用して計算される標準化されたユークリッド距離。このアルゴリズムは高速ですが、場合によっては精度が低下することがあります。'fast' から始まるアルゴリズムでは、スパース データはサポートされません。詳細については、アルゴリズムを参照してください。
'mahalanobis'	X の標本共分散を使用して C = cov(X,'omitrows') として計算されるマハラノビス距離。C について別の値を指定するには、DistParameter を使用します。ここで、行列 C は対称な正定値です。
'cityblock'	市街地距離
'minkowski'	ミンコフスキー距離。既定の指数は 2 です。異なる指数 P を指定するには、DistParameter を使用します。P は指数を表す正のスカラー値です。
'chebychev'	チェビシェフ距離 (最大座標差)
'cosine'	1 から、ベクトルとして扱われる点の間の夾角の余弦を引いた値
'correlation'	1 から、値の系列として扱われる点の間の標本相関を引いた値
'hamming'	ハミング距離 (異なる座標の比率)
'jaccard'	1 からジャカード係数 (異なる非ゼロ座標の比率) を減算
'spearman'	1 から観測値間の標本スピアマン順位相関係数を減算 (値の系列として処理)
@distfun	カスタム距離関数のハンドル。距離関数の形式は次のようになります。 function D2 = distfun(ZI,ZJ) % calculation of distance ... ここで ZI は、単一の観測値が含まれている 1 行 n 列のベクトルです。 ZJ は、複数の観測値が含まれている m2 行 n 列の行列です。distfun は、任意の個数の観測値が含まれている行列 ZJ を受け入れなければなりません。 D2 は m2 行 1 列の距離のベクトルであり、D2(k) は観測値 ZI と ZJ(k,:) の間の距離です。 データがスパースでない場合、通常は関数ハンドルではなく組み込みの距離計量を使用する方が高速に距離を計算できます。

定義については距離計量を参照してください。

'seuclidean'、'minkowski' または 'mahalanobis' を使用する場合、これらの尺度を制御する追加入力引数 DistParameter を指定できます。DistParameter を既定値にすると、これらの尺度を他の尺度と同じ方法で使用できます。

例: 'minkowski'

データ型: char | string | function_handle

DistParameter — 距離計量のパラメーター値

正のスカラー | 数値ベクトル | 数値行列

距離計量のパラメーター値。正のスカラー、数値ベクトルまたは数値行列を指定します。この引数は、Distance として 'seuclidean'、'minkowski' または 'mahalanobis' を指定した場合のみ有効です。

• Distance が 'seuclidean' の場合、DistParameter は各次元のスケーリング係数のベクトルで、正のベクトルを指定します。既定値は std(X,'omitnan') です。

• Distance が 'minkowski' の場合、DistParameter はミンコフスキー距離の指数で、正のスカラーを指定します。既定値は 2 です。

• Distance が 'mahalanobis' の場合、DistParameter は共分散行列で、数値行列を指定します。既定値は cov(X,'omitrows') です。DistParameter は、対称な正定値行列でなければなりません。

例: 'minkowski',3

データ型: single | double

cache — メガバイト単位のグラム行列のサイズ

1e3 (既定値) | 正のスカラー | "maximal"

メガバイト単位のグラム行列のサイズ。正のスカラーまたは "maximal" として指定します。関数 pdist で CacheSize=cache を使用できるのは、引数 Distance が 'fasteuclidean'、'fastsquaredeuclidean'、または 'fastseuclidean' の場合のみです。

cache が "maximal" の場合、pdist は、M 行 M 列のサイズの中間行列全体に十分なメモリを割り当てようと試みます。ここで、M は入力データ X の行数です。キャッシュ サイズは、中間行列全体に対して十分な大きさである必要はありませんが、少なくとも M 行 1 列のベクトルを保持する十分な大きさでなければなりません。そうでない場合、pdist でのユークリッド距離の計算に標準のアルゴリズムが使用されます。

距離の引数が 'fasteuclidean'、'fastsquaredeuclidean'、または 'fastseuclidean' の場合に、cache の値が大きすぎるか "maximal" であると、利用可能なメモリを超えるグラム行列の割り当てが pdist で試行されることがあります。この場合、MATLAB^® はエラーを生成します。

例: "maximal"

データ型: double | char | string

出力引数

D — ペアワイズ距離

数値行ベクトル

ペアワイズ距離。観測値のペアに対応する、長さ m(m–1)/2 の数値行ベクトルとして返されます。m は X 内の観測値の個数です。

距離は、(2,1)、(3,1)、...、(m,1)、(3,2)、...、(m,2)、...、(m,m-1) という順序で編成されます。つまり、m 行 m 列の距離行列の左下三角の列順になります。観測値 i および j の間のペアワイズ距離は、i≤j について D((i-1)*(m-i/2)+j-i) にあります。

関数 squareform を使用すると、D を対称行列に変換できます。Z = squareform(D) は、Z(i,j) が観測値 i および j の間のペアワイズ距離に対応する、m 行 m 列の行列を返します。

観測値 i または j に NaN が含まれている場合、組み込み距離関数では D 内の対応する値が NaN になります。

通常、D はクラスタリングまたは多次元尺度構成法で非類似度行列として使用されます。詳細については、階層クラスタリングと、関数 cmdscale、cophenet、linkage、mdscale および optimalleaforder のリファレンス ページを参照してください。これらの関数は入力引数として D を受け入れます。

詳細

距離計量

距離計量は、2 つの観測値の間の距離を定義する関数です。pdist は、以下の各種距離計量、ユークリッド距離、標準化されたユークリッド距離、マハラノビス距離、市街地距離、ミンコフスキー距離、チェビシェフ距離、コサイン距離、相関距離、ハミング距離、Jaccard 距離およびスピアマン距離をサポートします。

m 個の (1 行 n 列の) 行ベクトル x₁、x₂、...、x_m として扱われる m 行 n 列のデータ行列 X に対して、ベクトル x_s と x_t の間で各種の距離は次のように定義されます。

• ユークリッド距離

  $$d_{st}^2=(x_s-x_t)(x_s-x_t{)}^{\prime }.$$

  ユークリッド距離はミンコフスキー距離の特殊なケース、p = 2 の場合です。

• 標準化されたユークリッド距離

  $$d_{st}^2=(x_s-x_t)V^{-1}(x_s-x_t{)}^{\prime },$$

  ここで、V は j 番目の対角要素が (S(j))² である n 行 n 列の対角行列です。S は各次元のスケーリング係数のベクトルです。

• マハラノビス距離

  $$d_{st}^2=(x_s-x_t)C^{-1}(x_s-x_t{)}^{\prime },$$

  ここで、C は共分散行列です。

• 市街地距離

  $$d_{st}={\displaystyle \sum _{j=1}^n\left|x_{sj}-x_{tj}\right|}.$$

  市街地距離はミンコフスキー距離の特殊なケース、p = 1 の場合です。

• ミンコフスキー距離

  $$d_{st}=\sqrt[p]{{\displaystyle \sum _{j=1}^n{\left|x_{sj}-x_{tj}\right|}^p}}.$$

  p = 1 という特殊なケースでは、ミンコフスキー距離は市街地距離を与えます。p = 2 という特殊なケースでは、ミンコフスキー距離はユークリッド距離を与えます。p = ∞ という特殊なケースでは、ミンコフスキー距離はチェビシェフ距離を与えます。

• チェビシェフ距離

  $$d_{st}={\max }_j\left\{\left|x_{sj}-x_{tj}\right|\right\}.$$

  チェビシェフ距離はミンコフスキー距離の特殊なケース、p = ∞ の場合です。

• コサイン距離

  $$d_{st}=1-\frac{x_s{x^{\prime }}_t}{\sqrt{\left(x_s{x^{\prime }}_s\right)\left(x_t{x^{\prime }}_t\right)}}.$$

• 相関距離

  $$d_{st}=1-\frac{\left(x_s-{\overline{x}}_s\right){\left(x_t-{\overline{x}}_t\right)}^{\prime }}{\sqrt{\left(x_s-{\overline{x}}_s\right){\left(x_s-{\overline{x}}_s\right)}^{\prime }}\sqrt{\left(x_t-{\overline{x}}_t\right){\left(x_t-{\overline{x}}_t\right)}^{\prime }}},$$

  ここで

  $${\overline{x}}_s=\frac{1}{n}{\displaystyle \sum _j{x}_{sj}}$$ および $${\overline{x}}_t=\frac{1}{n}{\displaystyle \sum _j{x}_{tj}}$$ です。

• ハミング距離

  $$d_{st}=(\#(x_{sj}\ne x_{tj})/n).$$

• Jaccard 距離

  $$d_{st}=\frac{\#\left[\left(x_{sj}\ne x_{tj}\right)\cap \left(\left(x_{sj}\ne 0\right)\cup \left(x_{tj}\ne 0\right)\right)\right]}{\#\left[\left(x_{sj}\ne 0\right)\cup \left(x_{tj}\ne 0\right)\right]}.$$

• スピアマン距離

  $$d_{st}=1-\frac{\left(r_s-{\overline{r}}_s\right){\left(r_t-{\overline{r}}_t\right)}^{\prime }}{\sqrt{\left(r_s-{\overline{r}}_s\right){\left(r_s-{\overline{r}}_s\right)}^{\prime }}\sqrt{\left(r_t-{\overline{r}}_t\right){\left(r_t-{\overline{r}}_t\right)}^{\prime }}},$$

  ここで

  • r_sj は、tiedrank により計算される、x_1j、x_2j、... x_mj から取得された x_sj の順位です。

  • r_s および r_t は、x_s および x_t の座標単位の順位ベクトルです。つまり、r_s = (r_s1, r_s2, ... r_sn) です。

  • $${\overline{r}}_s=\frac{1}{n}{\displaystyle \sum _j{r}_{sj}}=\frac{\left(n+1\right)}{2}$$.

  • $${\overline{r}}_t=\frac{1}{n}{\displaystyle \sum _j{r}_{tj}}=\frac{\left(n+1\right)}{2}$$.

アルゴリズム

高速ユークリッド距離アルゴリズム

Distance 引数の fast から始まる値 ('fasteuclidean' や 'fastseuclidean' など) で使用されるアルゴリズムでは、計算時間の短縮のために追加のメモリを使用してユークリッド距離が計算されます。このアルゴリズムは、Albanie の[1]などで "ユークリッド距離行列トリック" として提唱されているものです。内部テストでは、このアルゴリズムによって予測子の数が 10 個以上の場合に時間の短縮になることが確認されています。

このアルゴリズムでは、x_i と x_j のすべての点間の距離の行列 D を求めるために (x_i のそれぞれに n 個の変数を格納)、次の方程式の最後の行を使用して距離を計算します。

$$\begin{array}{c}{D}_{i,j}^2=\Vert x_i-x_j{\Vert }^2\\ ={(}^{x_i}(x_i-x_j)\\ =\Vert x_i{\Vert }^2-2x_i^T{x}_j+\Vert x_j{\Vert }^2.\end{array}$$

方程式の最後の行にある行列 $$x_i^T{x}_j$$ は "グラム行列" と呼ばれます。正方化と加算によって平方距離を計算する代わりに、グラム行列を計算して使用すると、一連の平方距離の計算は高速になりますが、数値的安定性は少し低くなります。詳細については、Albanie の[1]を参照してください。

グラム行列を格納するためにソフトウェアで既定で使用されるキャッシュのサイズは 1e3 メガバイトです。キャッシュ サイズは引数 cache を使用して設定できます。cache の値が大きすぎるか "maximal" である場合、利用可能なメモリを超えるグラム行列の割り当てが pdist で試行されることがあります。この場合、MATLAB はエラーを生成します。

参照

[1] Albanie, Samuel. Euclidean Distance Matrix Trick. June, 2019. Available at https://www.robots.ox.ac.uk/%7Ealbanie/notes/Euclidean_distance_trick.pdf.

拡張機能

C/C++ コード生成

MATLAB® Coder™ を使用して C および C++ コードを生成します。

使用上の注意事項および制限事項:

• 距離の入力引数 (Distance) の値は、コンパイル時の定数でなければなりません。たとえば、ミンコフスキー距離を使用するには、coder.Constant('Minkowski') を codegen の -args の値に含めます。

• 距離の入力引数 (Distance) の値をカスタム距離関数にすることはできません。

• pdist では、高速ユークリッド距離計算、つまり名前が fast から始まる距離計量 ('fasteuclidean' など) のコード生成はサポートされていません。

• pdist に対して生成されるコードでは、parfor (MATLAB Coder) を使用して、サポートされる共有メモリ マルチコア プラットフォームで並列実行されるループが作成されます。コンパイラが Open Multiprocessing (OpenMP) アプリケーション インターフェイスをサポートしない場合、または OpenMP ライブラリを無効にした場合、MATLAB Coder™ は parfor ループを for ループとして扱います。サポートされるコンパイラについては、サポートされるコンパイラを参照してください。OpenMP ライブラリを無効にするには、構成オブジェクトの EnableOpenMP プロパティを false に設定します。詳細については、coder.CodeConfig (MATLAB Coder) を参照してください。

コード生成の詳細については、コード生成の紹介および一般的なコード生成のワークフローを参照してください。

GPU コード生成

GPU Coder™ を使用して NVIDIA® GPU のための CUDA® コードを生成します。

使用上の注意事項および制限事項:

• 最適化された CUDA コードについてサポートされる距離入力引数値 (Distance) は、'euclidean'、'squaredeuclidean'、'seuclidean'、'cityblock'、'minkowski'、'chebychev'、'cosine'、'correlation'、'hamming' および 'jaccard' です。

• Distance をカスタム距離関数にすることはできません。

• Distance はコンパイル時の定数でなければなりません。

GPU 配列

Parallel Computing Toolbox™ を使用してグラフィックス処理装置 (GPU) 上で実行することにより、コードを高速化します。

使用上の注意事項および制限事項:

• 入力引数 Distance を "fasteuclidean"、"fastsquaredeuclidean"、"fastseuclidean"、またはカスタム距離関数として指定することはできません。

詳細は、GPU での MATLAB 関数の実行 (Parallel Computing Toolbox)を参照してください。

バージョン履歴

R2006a より前に導入

R2023a: キャッシュを使用した高速ユークリッド距離

'fasteuclidean'、'fastseuclidean'、および 'fastsquaredeuclidean' の距離計量では、キャッシュと別のアルゴリズムを使用してユークリッド距離の計算が高速化されます (アルゴリズムを参照)。キャッシュのサイズは引数 cache を使用して設定します。

参考

cluster | clusterdata | cmdscale | cophenet | dendrogram | inconsistent | linkage | pdist2 | silhouette | squareform

トピック

• クラスター分析手法の選択
• 階層クラスタリング