Efficient Clustering of High-Dimensional Data Sets with Application to Reference Matching

大規模なデータのクラスタリングの手法としてCanopy法というものを提唱。

仮定として、距離を計算する方法に軽い方法と重い方法があることを想定。
軽い方法でキャノピーを作り、そのなかで重い方法を使う。
キャノピーを作る際はN＾２のオーダの計算が必要だが、軽いからOKだという理屈。

キャノピーを作る方法は簡単、
1. 1点を選びそこから半径T1内のものはひとつのキャノピーの中と見なす。
   さらにT2< T1内の点は、以降の選択から取り除く
32 これを点が亡くなるまで行う。

後段にはk-meansなどを使うことを想定している。

今考えているアプリケーションは距離行列は所与なので使いようがない。。