OML4Pyを用いた大規模環境での最適なクラスタ数の選択 - エルボー法 (2021/06/30)

6月 29, 2021

OML4Pyを用いた大規模環境での最適なクラスタ数の選択 - エルボー法 (2021/06/30)

https://blogs.oracle.com/machinelearning/selecting-the-best-number-of-clusters-at-scale-using-oml4py-%e2%80%93-elbow-method

投稿者：Jie Liu | Data Scientist

クラスタリング・アルゴリズムの中で、K-meansは最もポピュラーなものです。K-meansは、高速で拡張性があり、解釈も簡単です。そのため、データサイエンティストがデータをクラスタリングし、データセットの内部構造を把握しようとするときには、ほぼデフォルトで最初の選択肢となります。この手法については、Oracle datascienceのブログで紹介されています。

しかし、K-meansクラスタリングには、適切に選択しなければならない重要なパラメータが1つあります。それは、アルゴリズムが生成するクラスターの数であるKで、これはユーザーが選ぶことができます。何の予備知識もなく与えられたデータセットに対して、そのデータセットに自然に存在するクラスターの数を確実に知ることはできません。誤ったKを選択すると、望ましくない結果になることが多いです。

この問題を解決するために、エルボー法、シルエット、ギャップ統計など、多くの方法が提案されています。これらの方法の中でも、エルボー法は最も直感的に理解でき、実装も簡単です。このブログでは、パフォーマンスとスケーラビリティを両立させるために、OML4Pyを使ってパラメータKを選択するエルボー法の実装方法を紹介します。

エルボー法

エルボー法は次のように動作します。最適なKが[1, n]の範囲にあると仮定して、K = 1, 2, ..., nごとにK平均を実行して、最適なKを探します。略して、平均クラスタ内距離と呼びます。当然のことながら、Kを増やせばこの数値は小さくなります。これは、中心が多ければ多いほど、平均クラスタ内距離は小さくなるからです。クラスタの数がデータセットのデータポイントの数と同じであれば、距離はすべてゼロになります。

最適なKを選択するためには、各Kの平均クラスタ内距離をプロットする必要があります。Kが1から増加するにつれて、最適なKに到達する前は、センターの数が最初から少なすぎて、新しいセンターが増えるたびに平均距離が大きく減少するため、減少速度は比較的速くなります。しかし、最適なKに達した後は、正しいクラスタ構造が既に発見されているため、新しく追加されたセンターは既に形成された特定のクラスタに現れるため、減少速度は遅くなります。そのため、平均クラスター内距離はあまり減少しません。曲線全体はL字型になっていて、最適なKはL字型の曲がり角や肘の部分にあります。通常、以下のようなプロットになります。

ニューヨーク市のイエロー・タクシー・データ

この方法を説明するために、オンラインで公開されているニューヨークのタクシーデータの実物データを使用します。

では、そのデータを見てみましょう。

NYC_DF = oml.sync(query = 'select START_LON, START_LAT, END_LON, END_LAT FROM NYC_DATA_200901')
NYC_DF.head()

  VENDOR_NAME TRIP_PICKUP_DATETIME TRIP_DROPOFF_DATETIME PASSENGER_COUNT
1         VTS  2009-01-26 23:04:00   2009-01-26 23:05:00               1
2         CMT  2009-01-23 10:11:33   2009-01-23 10:36:24               1
3         CMT  2009-01-23 11:40:37   2009-01-23 12:07:09               1
4         VTS  2009-01-26 16:32:00   2009-01-26 16:32:00               2
5         CMT  2009-01-23 06:20:49   2009-01-23 06:23:44               1
6         DDS  2009-01-06 07:50:21   2009-01-06 08:06:08               4
  TRIP_DISTANCE START_LON START_LAT RATE_CODE STORE_AND_FORWARD   END_LON  END_LAT
1          0.71 -73.97717  40.74292        NA                NA -73.98488 40.73889
2          3.70 -73.98622  40.76235        NA                NA -74.00987 40.72123
3          7.50 -73.99476  40.68473        NA                NA -73.98017 40.75152
4          0.99 -73.95994  40.77095        NA                NA -73.94618 40.77272
5          0.60 -73.97818  40.75410        NA                NA -73.97782 40.76318
6          2.10 -73.95949  40.77119        NA                NA -73.97552 40.79190
  PAYMENT_TYPE FARE_AMT SURCHARGE MTA_TAX TIP_AMT TOLLS_AMT TOTAL_AMT
1         CASH      4.1       0.5      NA       0         0       4.6
2         Cash     14.9       0.0      NA       0         0      14.9
3         Cash     21.7       0.0      NA       0         0      21.7
4       Credit      4.9       1.0      NA       1         0       6.9
5         Cash      4.1       0.0      NA       0         0       4.1
6         CASH      9.7       0.0      NA       0         0       9.7

タクシーの出発地と到着地の緯度と経度を組み合わせたクラスターを作ることができれば、面白いと思います。これにより、ニューヨーク市内での移動の通常のパターンが表示されます。例えば、マンハッタンのミッドタウンからダウンタウンへの移動が多いとします。当然のことながら、これらの特定の始点と終点はクラスターを形成します。そこで、4つの座標特徴に対してK-meansクラスタリングを行いたいと思います。start_lon, start_lat, end_lon, end_latです。

残る問題は、クラスターの数を決めることです。OML4Pyを使ってエルボープロットを生成する方法を紹介します。

前処理

クラスタリングを始める前に、データがきれいかどうかを確認する必要があります。通常、データには、分布の中心から極端に離れた外れ値が含まれています。クラスタリングアルゴリズムは、外れ値からなる小さなクラスタを形成し、それ以外のものをまとめてしまう傾向がありますが、これは有用ではありません。ここでは、座標特徴量の分布を見てみましょう。

NYC_DF.describe().round(2)

START_LON    START_LAT      END_LON      END_LAT
count  14092413.00  14092413.00  14092413.00  14092413.00
mean        -72.85        40.14       -72.87        40.15
std           9.10         4.99         8.97         4.96
min        -775.45        -7.34      -784.30        -7.34
25%         -73.99        40.74       -73.99        40.74
50%         -73.98        40.75       -73.98        40.75
75%         -73.97        40.77       -73.96        40.77
max        3555.91       935.53         0.10      1809.96

なお、NYCはおおよそ(40, -73)付近に位置しています。しかし、この座標の最大値は1000を超えています。これらは、ニューヨーク市から遠く離れた場所を目的地とする旅行です。我々の焦点はNYCの範囲内の交通パターンなので、これらの外れ値を除去する必要があります。次の関数は、ある特徴の外れ値を持つ行を、クオンタイルに基づいて削除します。

def IQR(SUMMARY_DF, features):
    result = [0]*len(features)    
    for i, feature in enumerate(features):
        result[i] = abs(SUMMARY_DF[feature]['75%'] - SUMMARY_DF[feature]['25%'])
return result 

def remove_outlier(DF, SUMMARY_DF, features):
    iqrs = IQR(SUMMARY_DF, features)    
    for i, iqr in enumerate(iqrs):
         H = 1.5*iqr
         DF = DF[ ( DF[features[i]] > SUMMARY_DF[features[i]]['25%'] - H ) & ( DF[features[i]] < SUMMARY_DF[features[i]]['75%'] + H )]
   print(DF.shape)
return DF

各座標に上記の関数を適用して外れ値を除去し、その結果を新しいテーブルとして保存します。なお、これらの計算はすべてデータベース上で行われており、OML4Py Transparency Layerを介してOracle Databaseを高性能な計算エンジンとして利用しています。

SUMMARY_DF = NYC_DF.describe()
NYC_DF_CLEAN = remove_outlier(NYC_DF, SUMMARY_DF, NYC_DF.columns)
try:
    oml.drop(table = 'NYC_DF_CLEAN')
except:
    print("No such table")
_ = NYC_DF_CLEAN.materialize(table = 'NYC_DF_CLEAN')

フィルターをかけた後の座標の範囲を見てみましょう。

NYC_DF_CLEAN.describe().round(2)

START_LON    START_LAT      END_LON      END_LAT
count  12468206.00  12468206.00  12468206.00  12468206.00
mean        -73.98        40.75       -73.98        40.75
std           0.02         0.02         0.02         0.02
min         -74.03        40.69       -74.03        40.68
25%         -73.99        40.74       -73.99        40.74
50%         -73.98        40.75       -73.98        40.75
75%         -73.97        40.77       -73.97        40.77
max         -73.93        40.82       -73.92        40.82

今では、レンジの見た目も良くなり、順調に進んでいます。

OML4Pyを使う理由

sklearn には K-means の実装がありますが、それが最も望ましい選択ではない場合があります。データセットが大きい場合、それぞれのクラスタリングモデルの構築には膨大な時間がかかります。デフォルトのsklearnのkmeansはインメモリでシングルスレッドです。大きなデータには対応できないかもしれません。特にメモリが限られている場合、sklearn kmeans はモデルを構築することさえできません。

これに対し、OMLが提供するアルゴリズムには大きな利点があります。データベース内に実装された並列分散型のアルゴリズムを使用することで、スケーラビリティやパフォーマンスの問題を十分に解決することができます。さらに、複数のモデルを並行して構築することで、全体の実行性能も向上させることができます。この話題は今後のブログに譲りたいと思います。

NYC Yellow Taxiデータセットを例に、オープンソースとデータベース内アルゴリズムの両方にかかる時間を測定してみましょう。例えば、K=4のK-meansを実行するとします。

まず、オープンソースのsklearn kmeansを使った場合の結果を見てみましょう。Oracle Databaseに保存されているデータから始めたとします。まず、データベースからデータをメモリに取り込む必要があります。ここで使用しているハードウェア環境は、2ノードのExadataサーバです。十分なメモリがあるので、安心してプルを実行できます。仮に、環境に十分なメモリがない場合は、オープンソースのソリューションを利用することも不可能ではありません。

データのロードにどのくらいの時間がかかるか見てみましょう。

X = NYC_DF_CLEAN.pull().values

これには11.99秒かかります。次に、メモリ内のデータに対してモデルをトレーニングします。

from sklearn.cluster import KMeans

km_skmod = KMeans(n_clusters=4, random_state=0).fit(X)

トレーニングには513秒かかります。2つのステップで523sかかります。

OMLのK-Meansを使えば、すぐにデータベース内の学習を開始することができます。

km_mod = oml.km(n_clusters = 4, **setting).fit(NYC_TRIMMED_1G)

これには45.72秒かかります。データベース内のアルゴリズムの方が10倍近く速いことがわかります。

OML4Py による実装

エルボー図を作成するためには、各Kのクラスター内二乗誤差の合計を計算する必要があります。 OML4Pyでは、APIの.score()を使ってこの指標を得ることができます。ただし、.score()の結果が元の指標の負の数であることを考慮して、abs()を追加する必要があります。このAPIを使えば、エルボープロットに必要なすべてのメトリックを生成するためのループを作成するだけでよいのです。

incluster_sum = []
for cluster in range(1, 9): 
    setting = {'kmns_iterations': 5, 'KMNS_RANDOM_SEED': 1}    
    km_mod = oml.km(n_clusters = cluster, **setting).fit(NYC_DF_CLEAN)
    incluster_sum.append(abs(km_mod.score(NYC_DF_CLEAN)))

コードを実行したところ、以下のグラフが得られました。クラスタ数Kが1から10まで増加すると、クラスタ内セントロイド和は最初の数ステップでは速く減少し、K=4以降では遅くなります。K=4の点は、このグラフの肘にあたります。これは、このデータセットのクラスタリングにK=4を選択することを示唆しています。

ビジュアル化

K=4が合理的な選択であることをどうやって知ることができるでしょうか？クラスタリングの結果を可視化してみましょう。この場合、特徴量の次元は4であり、直接視覚化するのは容易ではありません。一つの方法は、開始点をプロットし、クラスターのセントロイドから開始点と終了点をマークすることで、パターンを知ることができます。

この図を見ると、開始点はNYCの大まかな形をしており、ほとんどの点がマンハッタンに集中しています。図の上側に四角い隙間がありますが、これはセントラルパークです。また、始点と終点の両方で構成されるセントロイドを、始点から終点への黒い矢印でプロットしました。

矢印はトラフィックの一般的な方向を示しています。クラスタ3と5では矢印の長さが非常に短くなっていることに注意してください。これは、クラスタ3と5では開始点と終了点が非常に近いためです。これは、クラスター3と5の始点と終点が非常に近いため、アップタウンとダウンタウン内の移動であることを意味しています。他の2つのクラスターは、ミッドタウンからダウンタウンへ、ミッドタウンからアップタウンへの交通の流れを表しています。

まとめ

このブログでは、OML4Py とデータベース内の K-means クラスタリングアルゴリズムを使って、最適なクラスタ数を選択するエルボー法を実装する方法を紹介しました。NYCのイエロー・タクシーのデータを例にしました。K の最適な値が見つかった後、結果を可視化するためのプロットを作成したところ、いくつかの興味深いパターンが見つかりました。

このブログを検索

Oracle Cloud Infrastructure Blog(翻訳)