データサイエンス設計マニュアル

10.3 グラフ、ネットワーク、距離 293

に分類できる。

LSH は、ハ

ッシュテーブルの管理や暗号への応用で使われる通常のハッシュ関数とは目標がまったく逆

になっていることに注意しよう。通常のハッシュ関数は、類似する 2 つの要素が大きく離れたハッシュ値を

持つようにして、両者が違うことを認識するとともに、テーブル全体を活用できるようにする。それに対

し、LSH は類似する要素が同じハッシュ値になり、衝突によって類似性を認識できるようにする。LSH で

は、最近傍要素は同じバケットに属する。

データサイエンスでは、局所鋭敏型ハッシュは、最近傍探索以外にも使われる。特に最も重要なのは、お

そらく動画や音楽のストリームといった複雑なオブジェクトから圧縮された特徴表現を作るというものだろ

う。こういったストリームの間隔から作られる LSH コードは、パターンマッチやモデル構築のための特徴

となり得る数値を定義する。

10.3 グラフ、ネットワーク、距離

グラフ

G

= (

V, E

)

は頂点集合

V

と

V

に含まれる

2

頂点の順序対または非順序対からなる辺集合

E

に

よって定義される。道路網をモデリングするとき、頂点は都市やジャンクションを表し、それらの対は道や

辺によって直接つながれる。人間同士のやり取りを分析するときには、頂点は人を表し、辺は関係のある人

同士を結ぶ。

ほかにも、グラフやネットワークで自然にモデリングできるデータセットはたくさんある。

• WWW（World Wide Web）：個々のウェブページがグラフの頂点で ...