グリッドベースクラスタリングのアルゴリズムとは？仕組みと手順を解説

グリッドベースのクラスタリングとは

グリッド（格子）は、データ集合を整理するための非常に効果的な手法であり、特に低次元のデータにおいて有用です。その基本的な考え方は、各属性の取り得る値を複数の連続した区間に分割し、グリッドセル（格子単位）の集合を作成することです。そして、各オブジェクトは、自身の属性値が含まれる区間に対応するセルへと割り当てられます。

オブジェクトをセルへ振り分ける処理は、データを一度走査するだけで完了します。さらに同時に、セル内に含まれる点の数など、各セルに関する情報も併せて収集することが可能です。

グリッドベースクラスタリングのアルゴリズムの手順

グリッドを用いたクラスタリングにはさまざまな実装方法がありますが、その多くは密度（density）ベースのアプローチに基づいています。一般的なアルゴリズムは以下の手順で構成されます。

• グリッドセルの集合を作成する。
• 各オブジェクトを適切なセルに割り当て、各セルの密度を計算する。
• 密度が定義済みの閾値 r を下回るセルを除去する。
• 隣接する高密度セルの連なりからクラスタを形成する。

グリッドセルの定義

グリッドセルの定義はプロセスの基本となるステップですが、同時に最も曖昧さを伴う部分でもあります。各属性の取り得る値を連続的な区間に分割する方法は複数存在するためです。連続属性に対する代表的な手法の一つは、値を等幅（同じ幅）の区間に分割することです。この方法をすべての属性に適用すると、生成されるすべてのグリッドセルが同じ体積を持つことになり、セルの密度は「セル内の点の数」として簡潔に定義できます。

グリッドセルの密度

グリッドセルの密度は、「領域の体積で除した点の数」として定義できます。言い換えれば、密度とは領域の次元性にかかわらず、単位体積（または単位面積）あたりの点の数を意味します。

高密度セルからのクラスタ形成

隣接する高密度セルの集合からクラスタを形成すること自体は比較的容易です。ただし、「どのセルを隣接とみなすか」を明確に定義する必要があるという課題があります。また、このクラスタリング手法にはいくつかの欠点があり、アルゴリズムをやや洗練させることで対応できます。たとえば、クラスタの境界付近には部分的に空のセルが生じやすく、これが精度に影響を与える可能性があります。

空間属性と非空間属性を活用した高度化

基本的なグリッドベースクラスタリングは、より高次元の密度情報を活用することで改善できます。実際のデータには、空間的属性と非空間的属性の両方が含まれるケースが多くあります。つまり、一部の属性が時間・空間におけるオブジェクトの位置を決定し、別の属性がオブジェクトのその他の特性を表すという構成です。

具体例として住宅を挙げると、住宅は位置情報に加えて、価格や床面積（平方フィート）といった多数の特徴を持っています。空間的（または時間的）自己相関の性質により、同一のセル内に存在するオブジェクトは、それらの他の属性についても互いに似通った値を持つ傾向があります。この特性を利用することで、位置だけでなく属性値も考慮した、より精緻なクラスタリングが実現できます。