Loading article…
数学、コンピュータサイエンス、特にグラフ理論において、距離行列は、集合の要素間の距離をペアごとに含む正方行列（2次元配列）です。 [ 1 ]関係するアプリケーションによっては、この行列を定義するために使用される「距離」は、メトリックである場合もそうでない場合もあります。要素がN個ある場合、この行列のサイズはN × Nになります。グラフ理論のアプリケーションでは、要素は通常、点、ノード、または頂点と呼ばれます。
一般に、距離行列は、あるグラフの重み付き隣接行列です。ネットワーク（弧に重みが割り当てられた有向グラフ）では、ネットワークの 2 つのノード間の距離は、2 つのノードを結ぶ最短経路の重みの合計の最小値として定義できます (経路のステップ数は制限されています)。[ 2 ]この距離関数は、定義は適切ですが、メトリックではありません。重みには、組み合わせて比較できる必要がある以外に制限は必要なく、そのため、一部のアプリケーションでは負の重みが使用されます。経路は有向であるため、対称性は保証されず、負の重みのサイクルが存在する場合、距離行列は中空にならない可能性があります(ステップ数に制限がない場合、行列は定義されない可能性があります)。
上記の代数的定式化は、min-plus代数を用いることで得られる。このシステムにおける行列乗算は次のように定義される。2つのn × n行列A = ( a ij )とB = ( b ij )が与えられたとき、それらの距離積C = ( c ij ) = A ⭑ Bは、次のn × n行列として定義される。
直接接続されていない非対角要素は、min-plus演算が正しく機能するように、無限大または適切な大きな値に設定する必要があることに注意してください。これらの位置にゼロを設定すると、距離やコストなどがゼロのエッジとして誤って解釈されます。
W がグラフのエッジの重みを含むn × n行列である場合、W k (この距離積を使用) は、最大でkエッジの長さのパスを使用した頂点間の距離を表し、ステップ数の上限をkに設定した場合のグラフの距離行列となります。負の重みのループがない場合、W n は上限のない真の距離行列になります。これは、パスから重複する頂点を削除しても、その重みを下げることができないためです。一方、iとj が負の重みのループ上にある場合、kが増加するにつれてW k ij は上限なく減少します。
n個の頂点を持つ任意のグラフG は、 Gの辺に対応する完全グラフの各辺に重み 1 を割り当て、その他のすべての辺に無限大を割り当てることにより、n 個の頂点を持つ重み付き完全グラフとしてモデル化できます。この完全グラフのWは、Gの隣接行列です。G の距離行列は、上記のようにWから計算できます。一方、通常の行列乗算を使用し、リンクされていない頂点を 0 で表す場合、W n は代わりに、長さがちょうどnである任意の 2 つの頂点間のパスの数をエンコードします。
多くの応用において距離行列形式の価値は、距離行列が計量公理を明確に符号化できることと、線形代数技術の使用に適していることにある。つまり、M = ( x ij ) ( 1 ≤ i , j ≤ N)が計量距離の距離行列である場合、
距離行列が最初の 3 つの公理を満たす場合 (つまり、半距離行列となる場合)、それは事前距離行列と呼ばれることがあります。ユークリッド空間に埋め込むことができる事前距離行列は、ユークリッド距離行列と呼ばれます。数値記述子とカテゴリ記述子の両方を含む混合型データの場合、Gower の距離が一般的な代替手段となります。
距離行列のもう一つの一般的な例は、符号理論において、ブロック符号の要素がアルファベット上の固定長の文字列であり、それらの間の距離がハミング距離で表される場合に現れます。距離行列の最小の非ゼロ要素は、符号の誤り訂正能力と誤り検出能力を表します。
加法距離行列は、バイオインフォマティクスで系統樹を構築するために用いられる特殊な行列です。2つの種iとjの間の最小共通祖先をxとすると、M ij = M ix + M xjが成り立つと予想されます。これが加法距離の由来です。種の集合Sの距離行列Mは、 Sの系統樹T が存在し、以下の条件を満たす場合に限り、加法行列であると言われます。
この場合、Mは加法行列、Tは加法木と呼ばれます。以下に、加法距離行列とその対応する木の例を示します。
超距離行列は、定数分子時計をモデル化した加法行列として定義される。これは系統樹の構築に用いられる。行列Mは、次のような系統樹Tが存在する場合に超距離行列であると言われる。
以下に、超距離行列とその対応するツリーの例を示します。
距離行列はバイオインフォマティクス分野で広く用いられており、様々な手法、アルゴリズム、プログラムに用いられています。距離行列は、タンパク質構造を座標に依存しない形で表現するだけでなく、配列空間における2つの配列間のペアワイズ距離を表すためにも使用されます。構造アライメントや配列アライメント、 NMRやX線結晶構造解析によるタンパク質構造の決定などに利用されています。
データを類似度行列として表現する方が便利な場合もある。
また、距離相関を定義するためにも使用されます。
2 つの配列のアライメントは、配列に沿って任意の位置にスペースを挿入することによって形成され、最終的に同じ長さになり、拡張された 2 つの配列の同じ位置に 2 つのスペースが存在しないようにします。[ 3 ]配列アライメントの主要な方法の 1 つは動的計画法です。この方法は、距離行列を埋めてからアライメントを取得するために使用されます。一般的な使用法では、配列アライメントには、アミノ酸の一致または不一致にスコアを割り当て、一方の配列のアミノ酸が他方の配列のギャップと一致した場合にギャップペナルティを割り当てるために行列が使用されます。
グローバルアライメントを計算するために使用されるニードルマン・ウンシュアルゴリズムは、動的計画法を用いて距離行列を取得します。
スミス・ウォーターマンアルゴリズムも動的計画法に基づいており、距離行列を取得してから局所的なアライメントを取得するという手順で行われます。
多重配列アライメントは、ペアワイズアライメントを拡張し、複数の配列を一度にアライメントする手法です。様々な多重配列アライメント手法は、グローバルアライメントやローカルアライメントと同様に、距離行列という同じ概念に基づいています。
人気が高いため、独自のプログラムが用意されている方法も他にもあります。
高速フーリエ変換を用いた多重アライメント（MAFFT）は、プログレッシブアライメントに基づくアルゴリズムを採用したプログラムであり、様々な多重アライメント戦略を提供します。まず、MAFFTは共有する6タプルの数に基づいて距離行列を作成します。次に、この行列に基づいてガイドツリーを構築します。最後に、高速フーリエ変換を用いて配列をクラスタリングし、アライメントを開始します。新しいアライメントに基づいてガイドツリーを再構築し、再度アライメントを実行します。
系統解析を行うには、まず系統樹を再構築する必要があります。つまり、複数の種が与えられた場合、それらの種間の祖先関係、すなわち種間の系統樹を再構築または推定することが課題となります。距離行列法はこの作業を実行します。
系統解析の距離行列法は、分類される配列間の「遺伝的距離」の尺度に明示的に依存するため、入力として複数の配列を必要とします。距離法は、各配列ペア間の距離を記述する配列クエリセットから全対全行列を構築しようとします。これによって、密接に関連する配列を同じ内部ノードの下に配置し、その枝の長さが配列間の観測された距離を忠実に再現する系統樹が構築されます。距離行列法は、計算に使用されるアルゴリズムに応じて、根付きツリーまたは根なしツリーのいずれかを生成する可能性があります。[ 4 ] n種の場合に 、入力はn × n距離行列Mであり、M ijは種iと種jの間の突然変異距離です。目標は、距離行列と一致する次数3のツリーを出力することです。
これらは、多重配列アライメントの漸進的および反復的なタイプの基礎として頻繁に使用されます。距離行列法の主な欠点は、複数のサブツリーにまたがって現れる局所的な高変異領域に関する情報を効率的に使用できないことです。[ 4 ]潜在的な問題にもかかわらず、距離法は非常に高速であり、多くの場合、系統発生の妥当な推定値を生成します。また、文字を直接使用する方法よりもいくつかの利点があります。特に、距離法では、DNA-DNAハイブリダイゼーションアッセイなど、文字データに簡単に変換できない可能性のあるデータを使用できます。
系統樹再構築のための距離ベースの手法は以下のとおりです。
加法ツリー再構築は、加法距離行列と超距離行列に基づいています。これらの行列には特別な特徴があります。
加法行列Mを考えます。任意の 3 つの種i、j、k に対して、対応するツリーは一意です。[ 3 ]すべての超距離行列は加法行列です。以下のツリーでは、種i、j、kから構成されるこの性質を観察できます。
加算ツリー再構築手法は、このツリーから始まります。そして、距離行列と上記の特性を組み合わせて、毎回1つの種を追加していきます。たとえば、加算行列Mと5つの種a、b、c、d、eを考えます。まず、2つの種aとbの加算ツリーを作成します。次に、3番目の種cを選択し、 aとbの間のエッジ上の点xに接続します。エッジの重みは、上記の特性を使用して計算されます。次に、4番目の種dを任意のエッジに追加します。特性を適用すると、dは特定の1つのエッジにのみ接続する必要があることがわかります。最後に、以前と同じ手順でeを追加します。
UPGMA (算術平均による非加重ペアグループ法) の基本原理は、類似種は系統樹上でより近い位置にあるべきであるというものです。そのため、類似した配列を反復的にクラスタリングすることで系統樹を構築します。この方法は、系統樹を葉から下から上に構築することで機能します。最初は、n 個の葉 (またはn 個のシングルトンツリー) があり、それぞれがS内の種を表します。これらのn個の葉はn 個のクラスターと呼ばれます。次に、 n -1回の反復を実行します。各反復で、平均距離が最小の2 つのクラスターC 1とC 2を特定し、それらをマージしてより大きなクラスターCを形成します。Mが超距離であると仮定すると、 UPGMA アルゴリズムによって作成された任意のクラスターCに対して、 Cは有効な超距離ツリーになります。
ネイバー法はボトムアップ型のクラスタリング手法です。各シーケンスペア間の距離を指定する距離行列を入力として受け取ります。このアルゴリズムは、完全に未解決の木構造（そのトポロジーはスター型ネットワークのトポロジーに対応）から開始し、木構造が完全に解決され、すべての枝の長さが判明するまで、以下の手順を繰り返します。
Fitch–Margoliash法は、遺伝的距離に基づくクラスタリングに重み付き最小二乗法を使用します。系統樹構築プロセスでは、遠縁の配列間の距離測定の不正確さの増加を補正するために、近縁の配列により大きな重みが与えられます。これらの距離に適用される最小二乗基準は、近隣結合法よりも正確ですが、効率は劣ります。データセット内の多くの近縁配列から生じる距離間の相関を補正する追加の改善も、計算コストの増加を伴いますが適用できます。[ 6 ]
データマイニングにおける一般的な機能の一つは、与えられたデータセットに対してクラスタ分析を適用し、他のグループと比較してどの程度類似しているかに基づいてデータをグループ化することです。距離行列は、類似性を距離指標で測定できるため、クラスタ分析において非常に重要かつ活用されるようになりました。そのため、距離行列は、データセット内のすべての異なるデータペア間の類似度を表すものとなりました。
距離行列は、系統樹の再構築など、生物科学でよく用いられるヒューリスティックな手法である従来の階層的クラスタリングアルゴリズムに不可欠です。データマイニングで階層的クラスタリングアルゴリズムを実装する場合、距離行列にはすべての点間のペアワイズ距離が格納され、その後、2つの異なる点間のクラスタ、または距離行列からの距離のみに基づいてクラスタが作成されます。
点の数をNとすると、階層的クラスタリングの複雑さは次のようになります。
距離指標は、教師あり学習と教師なし学習の両方で使用される、いくつかの機械学習アルゴリズムの重要な要素です。これらは一般的にデータポイント間の類似性を計算するために使用され、その際に距離行列が不可欠な要素となります。効果的な距離行列を使用することで、分類タスクであろうとクラスタリングであろうと、機械学習モデルのパフォーマンスが向上します。[ 7 ]
k-NNアルゴリズムは、分類タスクと回帰タスクの両方に使用できる、インスタンスベースの機械学習アルゴリズムの中で最も処理速度は遅いものの、最もシンプルで広く使用されているアルゴリズムの1つであり、距離行列を利用します。このアルゴリズムは、各テストサンプルの予測結果を得るために、テストサンプルとトレーニングセット内の各トレーニングサンプルとの間の距離行列を完全に計算する必要があるため、最も処理速度の遅い機械学習アルゴリズムの1つです。距離行列が計算されると、アルゴリズムはテストサンプルに最も近いK個のトレーニングサンプルを選択し、選択されたセットの多数決（分類）または平均（回帰）値に基づいてテストサンプルの結果を予測します。
この分類に特化したモデルは、ターゲットと各トレーニングサンプル間の距離行列に基づいてターゲットのラベルを予測し、ターゲットに最も近いK個のサンプルを決定します。
距離行列は、画像予測機械学習モデルにおける2次元から3次元への回帰のためのニューラルネットワークで使用できる。
情報検索のトピックで注目すべき基本的なアルゴリズムとしては、魚群探索アルゴリズムがあります。これは、魚群の集団行動を収集するために距離行列を使用する情報検索アルゴリズムです。給餌演算子を使用して重みを更新することで、
式A：
式B：
Stepvolは、距離行列、特にユークリッド距離行列を用いて実行される最大体積変位のサイズを定義します。
類似する文書を整理・グループ化するために、距離ベースの指標を用いた階層的クラスタリングを実装するには、距離行列が必要となり、その利用が不可欠となる。距離行列は、ある文書と別の文書との関連性の度合いを表し、ユーザーのクエリに関連する文書を検索する手法において利用される、密接に関連する文書のクラスタを作成するために使用される。
Isomapは、距離行列を用いて測地距離を利用し、低次元埋め込みを計算する機能を備えています。これにより、膨大な次元に存在する文書群を扱いやすくなり、文書クラスタリングの実行が可能になります。
ディスプレイ／画面に表示される類似性に基づいて類似データを見つけるために距離行列を使用する、教師なし学習と教師あり学習の両方で使用されるアルゴリズム。
教師なしNeRVに必要な距離行列は、固定された入力ペアワイズ距離を用いて計算できる。
教師ありNeRVに必要な距離行列では、入力の距離を教師ありで計算できるように、教師あり距離指標を策定する必要があります。
距離行列は、化学のグラフ理論（位相幾何学）と幾何学（地形）の両方のバージョンで広く使用されている数学的対象です。[ 8 ]化学では、距離行列は明示的および暗黙的な形式で使用されます。
距離行列は、2つの置換異性体間の再配列を決定するために必要な最短経路シーケンスを図示し明らかにするための主要な手法として使用された。
分子構造の距離多項式および距離スペクトルを構築するには、距離行列を明示的に使用する必要がある。
距離行列の暗黙的な使用は、すべての化学構造における距離を表すために考案された距離ベースの指標であるウィーナー数／ウィーナー指数を用いることによって適用された。ウィーナー数は、距離行列の要素の合計の半分に等しい。
化学における距離行列は、分子グラフの2次元表現に使用され、様々な応用において分子の主要な基本的特徴を示すために用いられる。
グラフ理論距離行列2次元は分子の構成的特徴を捉えますが、その3次元（3D）特性は幾何学的距離行列に符号化されます。幾何学的距離行列は、分子のグラフ理論距離行列に基づいて3D分子構造を表現し、グラフ化する別のタイプの距離行列です。[ 8 ]分子構造Gの幾何学的距離行列は、2次元行列と同じように定義される実対称n × n行列です。ただし、行列要素D ijには、 G内のiとj間の最短デカルト距離の集合が格納されます。地形行列とも呼ばれる幾何学的距離行列は、分子の既知の幾何学から構築できます。例として、2,4-ジメチルヘキサンの炭素骨格の幾何学的距離行列を以下に示します。
動的時間伸縮法（DTW）距離行列は、時系列オブジェクトの集合／グループのクラスタリングおよび分類アルゴリズムで利用されます。
例えば、ピクセルユークリッド距離を距離指標として、これらのデータを分析するとします。
距離行列は次のようになります。
これらのデータは、ヒートマップとしてグラフ形式で表示できます。この画像では、黒は距離0、白は最大距離を表しています。
