正規化された圧縮距離

正規化圧縮距離( NCD ) は、 2 つのオブジェクト (2 つの文書、2 つの手紙、2 つの電子メール、2 つの楽譜、2 つの言語、2 つのプログラム、2 つの画像、2 つのシステム、2 つのゲノムなど) 間の類似性を測定する方法です。このような測定は、アプリケーションに依存したり、恣意的であったりしてはなりません。2 つのオブジェクト間の類似性の適切な定義は、それらを相互に変換するのがどれだけ難しいかです。

情報検索やクラスター分析のためのデータマイニングに使用できます。

情報距離

ここで話題にしているオブジェクトは0 と 1 の有限の文字列であると仮定します。つまり、文字列の類似性を意味します。すべてのコンピュータファイルはこの形式です。つまり、オブジェクトがコンピュータ内のファイルである場合、この形式になります。文字列と間の情報距離は、からを計算する最短プログラムの長さとして定義でき、その逆も同様です。この最短プログラムは、固定されたプログラミング言語で記述されます。技術的な理由から、チューリングマシンの理論的概念が使用されます。さらに、長さを表すために、コルモゴロフ複雑性の概念が使用されます。次に、次のことが示されています^[1] $x$ $y$ $p$ $x$ $y$ $p$

|p|=\max\{K(x\mid y),K(y\mid x)\}

対数加法項までは無視できる。この情報距離はメトリックであることが示されており（対数加法項までのメトリック不等式を満たしている）、普遍的である（例えば特徴から計算される計算可能な距離を定数加法項まですべてマイナー化する）。^[1]

正規化された情報距離（類似度メトリック）

情報距離は絶対的なものです。しかし、類似性を表現する場合は、相対的な情報距離の方が重要です。たとえば、長さが 1,000,000 の 2 つの文字列が 1000 ビット異なる場合、それらの文字列は、1000 ビット異なる 2 つの 1000 ビットの文字列よりも相対的に類似していると考えられます。したがって、類似性メトリックを取得するには正規化する必要があります。この方法で、正規化された情報距離 (NID) を取得します。

NID(x,y)={\frac {\max\{K{(x\mid y)},K{(y\mid x)}\}}{\max\{K(x),K(y)\}}},

ここで、は入力として与えられたアルゴリズム情報です。NIDは類似度メトリックと呼ばれます。関数はメトリック距離測定の基本要件を満たすことが示されているため。^[2]^[3]ただし、計算可能ではなく、半計算可能でもありません。^[4] $K(x\mid y)$ $x$ $y$ $NID(x,y)$

正規化された圧縮距離

NID メトリックは計算可能ではありませんが、用途は豊富です。実際の圧縮機で単純に近似すると、圧縮機 Z (たとえば、「gzip」、「bzip2」、「PPMZ 」) で圧縮されたファイルのバイナリ長となり、NID を簡単に適用できるようになります。^[2]Vitanyiと Cilibrasi は NID を書き直して、正規化圧縮距離 (NCD) を取得しました。 $K$ $Z(x)$ $x$

NCD_{Z}(x,y)={\frac {Z(xy)-\min\{Z(x),Z(y)\}}{\max\{Z(x),Z( y)\}}}.

^[3]

NCDは実際にはコンプレッサーZでパラメータ化された距離のファミリーです。Zが優れているほど、NCDはNIDに近づき、結果は良くなります。^[3]

アプリケーション

正規化された圧縮距離は、言語や系統樹を完全に自動的に再構築するために使用されています。^[2]^[3]また、任意のドメインにおける自然データの一般的なクラスタリングと分類の新しいアプリケーションにも使用できます。 ^[3]異種データのクラスタリング、^[3]およびドメイン間の異常検出にも使用できます。 ^[5] NIDとNCDは、音楽分類、^[3]ネットワークトラフィックの分析とコンピューターワームとウイルスのクラスタリング、^[6]作者の帰属、^[7]遺伝子発現ダイナミクス、^[8]有用な幹細胞と役に立たない幹細胞の予測、^[9]重要なネットワーク、^[10]画像登録、^[11]質問応答システムなど、さまざまな対象に適用されています。^[12]

パフォーマンス

データマイニングコミュニティの研究者は、NCD とバリアントを「パラメータフリー、機能フリー」のデータマイニングツールとして使用しています。^[5]あるグループは、多種多様なシーケンスベンチマークで密接に関連するメトリックを実験的にテストしました。過去 10 年間に 7 つの主要なデータマイニング会議で見つかった 51 の主要な方法と圧縮方法を比較した結果、異種データのクラスタリング、異常検出、およびドメインデータのクラスタリングにおける競争力において、圧縮方法が優れていることが証明されました。

NCDはノイズに対して堅牢であるという利点がある。^[13]しかし、NCDは「パラメータフリー」のように見えるが、実際的な問題としては、NCDの計算にどのコンプレッサーを使用するか、その他の考えられる問題などがある。^[14]

正規化相対圧縮（NRC）との比較

ある文字列の情報を他の文字列と比較して測定するには、相対距離 (NRC) に頼る必要があります。^[15]これらは、対称性や三角不等式の距離特性を考慮する必要のない尺度です。NCD と NRC は非常によく似ていますが、異なる問題に取り組んでいます。NCD は主に情報量を使用して両方の文字列がどの程度類似しているかを測定しますが、NRC は別の文字列の情報を使用して構築できないターゲット文字列の割合を示します。霊長類ゲノムの進化への応用との比較については、^{[16]を参照してください。}

正規化されたGoogle距離

オブジェクトは、文字通りの 4 文字のネズミのゲノムや、トルストイの『戦争と平和』のテキストのように、文字どおりに表現できます。簡単にするために、オブジェクトのすべての意味は、文字どおりのオブジェクト自体によって表されるものとみなします。オブジェクトは、「ネズミの 4 文字のゲノム」や「トルストイの『戦争と平和』のテキスト」のように、名前で表現することもできます。また、文字通り表現できず、名前でしか表現できないオブジェクトもあり、その意味は、「家」や「赤」のように、人類の背景の共通知識のコンテキストから得られます。私たちは、意味の類似性に関心があります。ウェブから Google によって返されるページヒット数から取得したコードワードの長さを使用して、NCD 式を使用して意味の距離を取得し、Google をデータマイニング、テキスト理解、分類、翻訳に役立つ圧縮ツールと見なします。正規化された Google 距離(NGD) と呼ばれる関連する NCD は、次のように書き直すことができます。

NGD(x,y)={\frac {\max\{\log f(x),\log f(y)\}-\log f(x,y)}{\log N-\min\{\log f(x),\log f(y)\}}},

ここで、は検索語を含むページ数、はとの両方を含むページ数を表します。これらは、Google または総ページ数を返すことができる検索エンジンによって返されます。この数値はインデックスされたページ数に設定できますが、各ページに含まれる検索語またはフレーズの数に応じて各ページをカウントする方が適切です。経験則として、ページ数を、たとえば 1000 倍にすることができます... ^[17] $f(x)$ $x$ $f(x,y)$ $x$ $y$ $N$

参照

ワード2ベク

参考文献

^ ab CH Bennett、P. Gacs、M. Li、PMB Vitányi、W. Zurek、「情報距離」、IEEE Trans. Inform. Theory、IT-44:4(1998) 1407–1423
^ abc Li, Ming; Chen, Xin; Li, Xin; Ma, Bin; Vitanyi, PMB (2011-09-27). "M. Li, X. Chen, X. Li, B. Ma, PMB Vitanyi、「類似度メトリック」、IEEE Trans. Inform. Th.、50:12(2004)、3250–3264。IEEE Transactions on Information Theory。50 ( 12): 3250–3264。doi :10.1109/TIT.2004.838101。S2CID 221927 。
^ abcdefg チリブラシ、R.;ビタニー、PMB (2011-09-27)。「R. Cilibrasi、PMB Vitanyi、圧縮によるクラスタリング」。IEEE 情報理論トランザクション。51 (4): 1523 ～ 1545 年。arXiv : cs/0312044。土井：10.1109/TIT.2005.844059。S2CID 911。
^ テルウィン、セバスティアン A.;トーレンブリート、リーン。ヴィタニー、ポール MB (2011)。「正規化された情報距離の非近似性」。コンピュータとシステム科学のジャーナル。77 (4): 738–742。土井：10.1016/j.jcss.2010.06.018。hdl : 2066/92129。S2CID 10831035。
^ ab Keogh, Eamonn; Lonardi, Stefano; Ratanamahatana, Chotirat Ann (2004-08-22)。「パラメータフリーのデータマイニングに向けて」。E. Keogh、S. Lonardi、および CA Ratanamahatana。「パラメータフリーのデータマイニングに向けて」。データにおける知識発見に関する会議：知識発見とデータマイニングに関する第 10 回 ACM SIGKDD 国際会議の議事録、第 22 巻、第 25 号、pp. 206–215。2004 年。Dl.acm.org。p . 206。doi :10.1145/1014052.1014077。ISBN 978-1581138887.S2CID 1616057 。
^ 「S. Wehner、圧縮を使用したワームとネットワークトラフィックの分析、Journal of Computer Security、15:3(2007)、303–320」。Iospress.metapress.com 。 2012年11月3日閲覧。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
^ Stamatatos, Efstathios (2009). 「現代の著者帰属方法の調査」.アメリカ情報科学技術学会誌. 60 (3): 538–556. CiteSeerX 10.1.1.207.3310 . doi :10.1002/asi.21001.
^ Nykter, M. (2008). 「マクロファージにおける遺伝子発現ダイナミクスは臨界状態を示す」。米国科学アカデミー紀要。105 (6): 1897–1900。Bibcode :2008PNAS..105.1897N。doi : 10.1073 / pnas.0711525105。PMC 2538855。PMID 18250330。
^ Cohen, Andrew R (2010). 「神経前駆細胞の運命の計算予測」. Nature Methods . 7 (3): 213–218. doi :10.1038/nmeth.1424. hdl : 1866/4484 . PMID 20139969. S2CID 18652440.
^ ニクテル、マッティ;プライス、ネイサン D.ラルホ、アンティ。ああ、トミ。カウフマン、スチュアート A.イリ・ハルジャ、オリ。イリヤ・シュムレヴィッチ（2008）。「M. Nykter、ND Price、A. Larjo、T. Aho、SA Kauffman、O. Yli-Harja1、および I. Shmulevich、クリティカルネットワークは構造力学関係において最大限の情報多様性を示す、Phys. Rev. Lett. 100、 058702 (2008)」。物理的なレビューレター。100 (5): 058702.arXiv : 0801.3699。土井：10.1103/PhysRevLett.100.058702。PMID 18352443。S2CID 5760862 。
^ バルデラ、アントン;フェイシャス、ミケル。ボアダ、イマ。マテウ、スバート（2006 年 7 月）。「圧縮ベースの画像レジストレーション」。M. Feixas、I. Boada、M. Sbert、圧縮ベースの画像レジストレーション。手順情報理論に関する IEEE 国際シンポジウム、2006 年、436–440。IEEE。 436–440ページ。土井：10.1109/ISIT.2006.261706。hdl :10256/3052。ISBN 978-1-4244-0505-3. S2CID 12549455。
^ Zhang, Xian; Hao, Yu; Zhu, Xiaoyan; Li, Ming; Cheriton, David R. (2007). 「質問から回答までの情報距離」 X Zhang、Y Hao、X Zhu、M Li、「質問から回答までの情報距離」、Proc. 13th ACM SIGKDD international conference on Knowledge discovery and data mining、2007、874–883。 Dl.acm.org。p. 874。doi :10.1145/1281192.1281285。ISBN 9781595936097. S2CID 3040254。
^ Cebrian, M.; Alfonseca, M.; Ortega, A. (2011-09-27). 「正規化された圧縮距離はノイズに強い」. IEEE Transactions on Information Theory . 53 (5): 1895–1900. CiteSeerX 10.1.1.158.2463 . doi :10.1109/TIT.2007.894669. S2CID 15691266.
^ 「M. Cebrián、M. Alfonseca、A. Ortega、「正規化された圧縮距離を使用する際の一般的な落とし穴：コンプレッサーで注意すべきこと」、Commun. Inf. Syst. 5:4(2005)、367–384」。Projecteuclid.org 。 2012年11月3日閲覧。
^ Ziv, J.; Merhav, N. (1993). 「ユニバーサル分類への応用を伴う個々のシーケンス間の相対エントロピーの測定」IEEE Transactions on Information Theory . 39 (4): 1270–1279. doi :10.1109/18.243444.
^ Pratas, Diogo; Silva, Raquel M.; Pinho, Armando J. (2018). 「圧縮ベースの尺度の比較と霊長類ゲノムの進化への応用」.エントロピー. 20 (6): 393. Bibcode : 2018Entrp..20..393P. doi : 10.3390/e20060393 . PMC 7512912. PMID 33265483. 資料はこのソースからコピーされたもので、Creative Commons Attribution 4.0 International License に基づいて利用可能です。
^ Cilibrasi, RL; Vitanyi, PMB (2011-09-27). 「RL Cilibrasi、PMB Vitanyi、「Google 類似度距離」、IEEE Trans. Knowledge and Data Engineering、19:3(2007)、370-383」。IEEE Transactions on Knowledge and Data Engineering . 19 (3): 370–383. arXiv : cs/0412098 . doi :10.1109/TKDE.2007.48. S2CID 59777.

外部リンク

ベクトル空間における単語表現の効率的な推定
M. LiおよびP. Vitanyi、「コルモゴロフ複雑性とその応用入門」、Springer-Verlag、ニューヨーク、第 4 版、2019 年

[BGLVZ98-1] CH Bennett、P. Gacs、M. Li、PMB Vitányi、W. Zurek、「情報距離」、IEEE Trans. Inform. Theory、IT-44:4(1998) 1407–1423

[Li04-2] Li, Ming; Chen, Xin; Li, Xin; Ma, Bin; Vitanyi, PMB (2011-09-27). "M. Li, X. Chen, X. Li, B. Ma, PMB Vitanyi、「類似度メトリック」、IEEE Trans. Inform. Th.、50:12(2004)、3250–3264。IEEE Transactions on Information Theory。50 ( 12): 3250–3264。doi :10.1109/TIT.2004.838101。S2CID 221927 。

[CV05-3] チリブラシ、R.;ビタニー、PMB (2011-09-27)。「R. Cilibrasi、PMB Vitanyi、圧縮によるクラスタリング」。IEEE 情報理論トランザクション。51 (4): 1523 ～ 1545 年。arXiv : cs/0312044。土井：10.1109/TIT.2005.844059。S2CID 911。

[4] テルウィン、セバスティアン A.;トーレンブリート、リーン。ヴィタニー、ポール MB (2011)。「正規化された情報距離の非近似性」。コンピュータとシステム科学のジャーナル。77 (4): 738–742。土井：10.1016/j.jcss.2010.06.018。hdl : 2066/92129。S2CID 10831035。

[Ke04-5] Keogh, Eamonn; Lonardi, Stefano; Ratanamahatana, Chotirat Ann (2004-08-22)。「パラメータフリーのデータマイニングに向けて」。E. Keogh、S. Lonardi、および CA Ratanamahatana。「パラメータフリーのデータマイニングに向けて」。データにおける知識発見に関する会議：知識発見とデータマイニングに関する第 10 回 ACM SIGKDD 国際会議の議事録、第 22 巻、第 25 号、pp. 206–215。2004 年。Dl.acm.org。p . 206。doi :10.1145/1014052.1014077。ISBN 978-1581138887.S2CID 1616057 。

[6] 「S. Wehner、圧縮を使用したワームとネットワークトラフィックの分析、Journal of Computer Security、15:3(2007)、303–320」。Iospress.metapress.com 。 2012年11月3日閲覧。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です

[7] Stamatatos, Efstathios (2009). 「現代の著者帰属方法の調査」.アメリカ情報科学技術学会誌. 60 (3): 538–556. CiteSeerX 10.1.1.207.3310 . doi :10.1002/asi.21001.

[8] ^ Nykter, M. (2008). 「マクロファージにおける遺伝子発現ダイナミクスは臨界状態を示す」。米国科学アカデミー紀要。105 (6): 1897–1900。Bibcode :2008PNAS..105.1897N。doi : 10.1073 / pnas.0711525105。PMC 2538855。PMID 18250330。

[9] Cohen, Andrew R (2010). 「神経前駆細胞の運命の計算予測」. Nature Methods . 7 (3): 213–218. doi :10.1038/nmeth.1424. hdl : 1866/4484 . PMID 20139969. S2CID 18652440.

[10] ニクテル、マッティ;プライス、ネイサン D.ラルホ、アンティ。ああ、トミ。カウフマン、スチュアート A.イリ・ハルジャ、オリ。イリヤ・シュムレヴィッチ（2008）。「M. Nykter、ND Price、A. Larjo、T. Aho、SA Kauffman、O. Yli-Harja1、および I. Shmulevich、クリティカルネットワークは構造力学関係において最大限の情報多様性を示す、Phys. Rev. Lett. 100、 058702 (2008)」。物理的なレビューレター。100 (5): 058702.arXiv : 0801.3699。土井：10.1103/PhysRevLett.100.058702。PMID 18352443。S2CID 5760862 。

[11] バルデラ、アントン;フェイシャス、ミケル。ボアダ、イマ。マテウ、スバート（2006 年 7 月）。「圧縮ベースの画像レジストレーション」。M. Feixas、I. Boada、M. Sbert、圧縮ベースの画像レジストレーション。手順情報理論に関する IEEE 国際シンポジウム、2006 年、436–440。IEEE。 436–440ページ。土井：10.1109/ISIT.2006.261706。hdl :10256/3052。ISBN 978-1-4244-0505-3. S2CID 12549455。

[12] Zhang, Xian; Hao, Yu; Zhu, Xiaoyan; Li, Ming; Cheriton, David R. (2007). 「質問から回答までの情報距離」 X Zhang、Y Hao、X Zhu、M Li、「質問から回答までの情報距離」、Proc. 13th ACM SIGKDD international conference on Knowledge discovery and data mining、2007、874–883。 Dl.acm.org。p. 874。doi :10.1145/1281192.1281285。ISBN 9781595936097. S2CID 3040254。

[13] Cebrian, M.; Alfonseca, M.; Ortega, A. (2011-09-27). 「正規化された圧縮距離はノイズに強い」. IEEE Transactions on Information Theory . 53 (5): 1895–1900. CiteSeerX 10.1.1.158.2463 . doi :10.1109/TIT.2007.894669. S2CID 15691266.

[14] 「M. Cebrián、M. Alfonseca、A. Ortega、「正規化された圧縮距離を使用する際の一般的な落とし穴：コンプレッサーで注意すべきこと」、Commun. Inf. Syst. 5:4(2005)、367–384」。Projecteuclid.org 。 2012年11月3日閲覧。

[15] Ziv, J.; Merhav, N. (1993). 「ユニバーサル分類への応用を伴う個々のシーケンス間の相対エントロピーの測定」IEEE Transactions on Information Theory . 39 (4): 1270–1279. doi :10.1109/18.243444.

[16] Pratas, Diogo; Silva, Raquel M.; Pinho, Armando J. (2018). 「圧縮ベースの尺度の比較と霊長類ゲノムの進化への応用」.エントロピー. 20 (6): 393. Bibcode : 2018Entrp..20..393P. doi : 10.3390/e20060393 . PMC 7512912. PMID 33265483. 資料はこのソースからコピーされたもので、Creative Commons Attribution 4.0 International License に基づいて利用可能です。

[17] Cilibrasi, RL; Vitanyi, PMB (2011-09-27). 「RL Cilibrasi、PMB Vitanyi、「Google 類似度距離」、IEEE Trans. Knowledge and Data Engineering、19:3(2007)、370-383」。IEEE Transactions on Knowledge and Data Engineering . 19 (3): 370–383. arXiv : cs/0412098 . doi :10.1109/TKDE.2007.48. S2CID 59777.