未知の数のクラスターへのクラスタリング
1. 概要
データサイエンスでは、発見の最初のフェーズの1つは、データに何が含まれているかを判断することです。 データについての知識が少なければ少ないほど、データについてより多くのことを発見するのに役立つアルゴリズムが必要になります。 データをグラフ化して明確に定義されたクラスターを確認できる場合は、クラスターの数を自分で指定するだけのアルゴリズムがあります。
ただし、パラメーターの数が多い場合やクラスターの定義が不十分な場合は、事前に多数のクラスターを必要とするアルゴリズムを使用するのが難しくなります。 幸いなことに、事前の知識を必要としないアルゴリズムがいくつかあります。 このチュートリアルでは、これらのアルゴリズムのいくつかについて説明します。
2. クラスタリングの概念
クラスタリングは分類に似ています。分類するには、データをどのカテゴリに分類するかを知る必要があります。 ただし、これらの分類が何であるかわからない場合は、クラスタリングを使用できます。 その場合、パターンを見つけてクラスターを作成するのはアルゴリズム次第です。 アルゴリズムが異なれば、クラスターも異なります。 したがって、複数のアルゴリズムを使用して、それぞれから異なるパターンまたはクラスターを見つけることは珍しくありません。
クラスターという用語を使用するのは、グラフ上でこれを行うことを想像しているためです。グラフでは、ポイントがクラスター化されていることがわかります。クラスターとは何ですか。 これは、互いに近いポイントのグループです。
しかし、それらが「近い」とどのように判断するのでしょうか。 それらの間の距離を測定します。
3. 距離または類似性の計算
簡単に言えば、クラスターとその近くのポイントを「どれだけ近づけるか」を決定するために使用できる4つの方法があります。
- 最初に、クラスター内の最も近いポイントを外側のポイントに見ていきます。
- 2番目では、クラスター内の最も遠いポイントから外側のポイントを確認します。
- 3番目の方法では、クラスター内のすべてのポイントと外側のポイントの間の平均距離を決定するように求められます。
- 最後の方法では、クラスターの重心または重心を計算し、その仮想点から外側の点までの距離を測定します。
測定したい距離を決定したら、どのように測定しますか? 基本的な幾何学では、ユークリッド距離の公式を学びました。
そして、これは最も一般的に使用される方法のようですが、他のオプションがいくつかあります。
距離を定義する方法と使用する式を決定したら、クラスタリングアルゴリズムを選択する準備が整いました。
4. アルゴリズム
クラスタリングを実現するには、いくつかの方法があります。
- Compactness は、代表的なポイントとそのパラメーターを取ります。 クラスター内の他のポイントが類似しているほど、クラスターはコンパクトになります。
- 接続性は、近くにあるオブジェクトは、遠くにあるオブジェクトよりも関連性が高いという考えに基づいています。
- 線形性は、使用される関数の種類、線形または非線形、および
ハード対。 柔らかい –ハードクラスタリングアルゴリズムでは、データは1つのクラスターにのみ割り当てられます。 ソフトクラスタリングでは、データが複数のクラスターに割り当てられる場合があります。
また、クラスタリングアルゴリズムを分類するには、階層的アルゴリズムと階層的アルゴリズムの2つの方法があります。 パーティション対。 モデルベース、図心vs。 分布対。 接続性と 密度など 各アルゴリズムは、あるデータポイントが別のデータポイントに「似ている」よりも1つのデータポイントに「似ている」かどうかを判断します。しかし、その類似性を判断する方法は、実装されているアルゴリズムによって異なります。 クラスターの数を事前に定義する必要のないアルゴリズムに焦点を当てて、利用可能なアルゴリズムのいくつかを簡単に調査してみましょう。
4.1. 階層的クラスタリング
階層的クラスタリングは、接続性を使用する階層的アルゴリズムです。 2つの実装があります:凝集型と分割型。
agglomerative クラスタリングでは、各ポイントをシングルポイントクラスターにします。 次に、最も近い2つのポイントを取得し、それらを1つのクラスターにします。 クラスターが1つになるまで、このプロセスを繰り返します。
divisive メソッドは、1つのクラスターから開始し、フラットクラスタリングアルゴリズムを使用してそのクラスターを分割します。 クラスタごとに要素が1つだけになるまで、このプロセスを繰り返します。
アルゴリズムは、クラスターがどのように形成または分割されたかの記憶を保持します。この情報は、樹状図を作成するために使用されます。 樹状図は、作成するクラスターの数を決定するためのしきい値を設定するために使用されます。
樹状図で最も長い切れ目のない線を見つけ、その点に垂直線を作成し、交差した線の数を数えることによって、クラスターの最適な数を見つけます。 上記の例では、2つのクラスターが見つかります。
4.2. DBSCAN(ノイズのあるアプリケーションの密度ベースの空間クラスタリング)
DBSCANは、密度ベースのクラスタリングアルゴリズムです。 最小ポイントカウントしきい値を使用して、距離測定内のポイントをグループ化します。
EPS (イプシロン)は、近傍の最大半径です。 これは、ポイントがクラスターの一部と見なされる距離を定義します。 この値が小さすぎないようにします。特定の領域で最小ポイント数を見つけるのが難しいためです。 値が大きすぎる場合、オブジェクトの大部分が1つのクラスターに含まれます。
MinPts は、密な領域を形成するための最小のポイント数です。 この値は、データセットの次元数から計算できます。 経験則は次のとおりです。
許可される最小値は3です。 ただし、大きなデータセットやノイズの多いデータセットの場合は、値が大きいほど良いです。
4.3. 平均シフト
平均シフトは、セントロイドベースのアルゴリズムです。 これは、重心の候補を更新して、特定の領域内のポイントの平均になるようにすることで機能します。 つまり、最も密度の高い領域を探し、その重心を見つけます。
平均シフトを実装するために、ランダムシードとウィンドウ( W )を初期化します。 次に、 W の重心(平均)を計算します。 検索ウィンドウを平均にシフトし、収束が達成されるまで計算を繰り返します。
4.4. スペクトルクラスタリング
スペクトルクラスタリングでは、データポイントはグラフ上でノードとして扱われます。 ノードは、クラスターを形成するために簡単に分離できる低次元空間にマップされます。 規則的なパターンを想定する他のアルゴリズムとは異なり、スペクトルクラスタリングのクラスターの形状や形式については想定されていません。
クラスターを見つけるために、最初にグラフを作成します。 このグラフは隣接行列で表すことができます。ここで、行と列のインデックスはノードを表し、エントリはノード間のエッジの有無を表します。 次に、このデータを低次元空間に投影し、クラスターを作成します。
5. 結論
この記事では、クラスタリングアルゴリズムがどのように定義され、区別されるかを示しました。
クラスターの数がわからない場合に使用できるアルゴリズムのタイプのさまざまな例を示しました。 クラスターの数を決定したら、 K-Means Clustering アルゴリズムを使用して、データに関するより多くの洞察を得ることができます。
クラスタリングは、データ分析のための1つの探索的アルゴリズムにすぎません。 また、データ探索は、データサイエンスプロセスの1つのステップにすぎません。 プロセス全体に役立つツールの詳細については、 SparkMLlibのガイドをご覧ください。