Kmean アルゴリズム

NOTE:バカな日本語を利用してしまうことがあったら、申し訳ございません。

はじめに

最近エンジニアコミュニティーでMachineLearningとか、DataMiningとか, AI等のキーワードはよく言われていますけど、
エンジニアとしての僕は聞くと何それ? 解らない気持ちを持ってました。

働いてる会社ではAIとMachineLearningを研究していて、プロダクトに運用するため、CTO様は研究室を作りました。テクニカルメンバーの全員が楽しみに参加しています。ただ参加してからもうすぐ1ヶ月を立つになりますが、何もできなくて、研究のことを全てCTO様とGod様 (CTOより偉くないけど他人より技術力がすごい人)が担当してもらってるので、なんか少し恥ずかしいと感じてます。というわけで一生懸命勉強したくて、AIとMachineLearningの研究室に少し貢献できたいと思います。

まずはMachineLearning, DataMiningは何のか？実際にどのように適用されるのか?について知りたいですから、グーグルで検索してみました。いっぱい検索したり、参考したりすると、結論は 簡単に言うと全然わからないになります。
基本なアルゴリズムを理解できたら、なんとなくMachineLearningについてのイメージが作れるかなぁーと考えて、Kmeanというアルゴリズムを調べてみていきます。

Kmean とは？

Kmeanのキーワードをグーグルで入力したとたん、以下のワードを表示されました。

Kmean clustering  (Kmean clustering algorithms)

→ なにそれ? Clusteringは何？わからない。
→ Clusteringを調べてみます。

Clustering is the grouping of a particular set of objects based on their characteristics, aggregating them according to their similarities. Regarding to data mining, this metodology partitions the data implementing a specific join algorithm, most suitable for the desired information analysis.

Clusteringというのはセットのオブジェクトを特色と均一性を基づいてグループする方法です。Data miningに対してこの方法(Clustering)は指定のJoinアルゴリズムでデータを分析する。 

質問:

均一性(similarities)は何？ どうやって均一性が定義されるのか？

グーグル先生:

Defining similarity / dissimilarity is an important part in clustering, because it affects the structure of your groups. You need to change your measure based on the application that you have.

均一／不均一を定義することは clusteringに対して 大事なpartです。 何故かと言うとそれはあなたのグルップの構造に影響を与えます。 あなたのアプリの目的を基づいて測定を定義することは必要があります。

ここまで一旦以下のことが理解できたかなぁー。

Kmeanとはオブジェクトの特色を基づいてオブジェクトのセットをグループするアルゴリズムです。

もっと調べると クラスタリングアルゴリズムを大枠にわけると2タイプがある。

• distance-based clustering algorithms: 距離を基づきクラスタリングアルゴリズム
• density-based clustering algorithms: 密度を基づきクラスタリングアルゴリズム

Kmeanは距離を基づきクラスタリングアルゴリズムです。または密度を基づきクラスタリングアルゴリズムの例はDBSCANです。

OK. ここまでKmeanは何か大体解ってきましたね。
Kmeanのフローについて調べてみましょう!

アルゴリズム

問題は

2次元のn点とkグループが あります。どうやってn点をkグループにわけて、以下の条件を満たせるのか？
条件: グループごとに対して各点から重心点までの距離は一番短い。

インプット

• 2時点のn 点。(x, y)
• kグループ

アウトプット

• 各グループに対して点の一覧を出す

フロー

• STEP 1: まずn点からk点をランダムでkグループの重心点として選択
• STEP 2: 各グループの重心点に対して、各点からの距離を計算する Euclidの距離計算式:

d(a, b) ^ 2 = (ax - bx) ^ 2 + (ay - by) ^ 2

• STEP 3: 各点Aに対して、Aから重心点までの距離が最小だったグループに A点を追加
• STEP 4: 各グループの重心点の座標を再計算する

cx = SUM(a1.x + a2.x + ... + am.x) / m
cy = SUM(a1.y + a2.y + ... + am.y) / m

m: số phần từ của nhóm

• STEP 5: すべての重心点の座標が変わらなかったら OK、結果を見つかりました。 却って STEP 2に戻します。

アクティビティ図

例

インプット

• 以下の6点があります。

[{x: 127, y: 933}, {x: 138, y: 741}, {x: 846, y: 391}, {x: 876, y: 879}, {x: 980, y: 580}, {x: 369, y: 725}]

• 2グループ

フロー

以上の課題で、 n = 6, k = 2があります。

STEPずつを説明していきます。

• STEP 1: ランダムで2重心点を選択

  • cendoird_point_1 = {x: 846, y: 391}
  • cendoird_point_2 = {x: 980, y: 580}

• 【ループ1】STEP2: 各点から各重心点までの距離を計算する

	cendoird_point_1 (846, 391)	cendoird_point_2 (980, 980)	グループ
P1(127, 933)	900.4026876903467	923.1565414381247	1
P2(138, 741)	789.7873131419623	857.2543379884409	1
P3(846, 391)	0.0	231.68297304722245	1
P4(876, 879)	488.9212615544552	316.5706872090339	2
P5(980, 580)	231.68297304722245	0.0	2
P6(369, 725)	582.3100548676796	627.9697444941118	1

• 【ループ1】STEP 3: 各点を該当のグループに追加 STEP2のあと、以下の結果があります。

Group1: [P1{x: 127, y: 933}, P2{x: 138, y: 741}, P3{x: 846, y: 391}, P6{x: 369, y: 725}]
Group2: [P4{x: 876, y: 879}, P5{x: 980, y: 580}]

• 【ループ1】STEP 4: 各重心点を再計算する

cendoird_point_1.x = SUM(P1.x + P2.x + P3.x + P6.x) / 4 = 370
cendoird_point_1.y = SUM(P1.y + P2.y + P3.y + P6.y) / 4 = 697.5

cendoird_point_2.x = SUM(P4.x + P5.x) / 2 = 928
cendoird_point_2.y = SUM(P4.y + P5.y) / 2 = 729.5

• 【ループ1】STEP 5: 重心点の座標が変わるので STEP 2に戻す

• 【ループ2】STEP 2: 【ループ 1 ＞ STEP2】と同じに計算すると、以下のテーブルがあります。

	cendoird_point_1 (370, 697.5)	cendoird_point_2 (928, 729.5)	前のグループ => 後のグループ
P1(127, 933)	338.39215416436593	826.4461567458584	1 => 1
P2(138, 741)	236.04289864344574	790.0836980978661	1 => 1
P3(846, 391)	566.14331224523	348.2904678569312	1 => 2
P4(876, 879)	537.5669725717903	158.28534360451695	2 => 2
P5(980, 580)	621.213530116658	158.28534360451695	2 => 2
P6(369, 725)	27.518175811634027	559.0181124078182	1 => 1

• 【ループ2】STEP 3: 各点を該当のグループに追加。以下の結果があります。

Group1: [P1{x: 127, y: 933}, P2{x: 138, y: 741}, P6{x: 369, y: 725}]
Group2: [P3{x: 846, y: 391}, P4{x: 876, y: 879}, P5{x: 980, y: 580}]

• 【ループ2】STEP 4: 各重心点の座標を再計算する

cendoird_point_1 = {x: 211.333, y: 799.667}
cendoird_point_2 = {x: 900.667, y: 616.667}

→ 座標が未だ変わっていましたので、STEP 2にもう1回戻す。

• 【ループ2】STEP 2: 【ループ 1 ＞ STEP2】と同じに計算すると、以下のテーブルがあります。

	cendoird_point_1 ( 211.333, 799.667)	cendoird_point_2 (900.667, 616.667)	前のグループ => 後のグループ
P1(127, 933)	157.7648369504434	835.8392152669077	1 => 1
P2(138, 741)	93.91243675892987	772.7351731207789	1 => 1
P3(846, 391)	754.8582103799362	232.19404767995243	2 => 2
P4(876, 879)	669.3847516772398	263.4901587877619	2 => 2
P5(980, 580)	799.4388955873989	87.3967606836775	2 => 2
P6(369, 725)	174.4535576536059	542.5917782071527	1 => 1

• 【ループ３】STEP 3: 各点を該当のグループに追加。以下の結果があります。

Group1: [P1{x: 127, y: 933}, P2{x: 138, y: 741}, P6{x: 369, y: 725}]
Group2: [P3{x: 846, y: 391}, P4{x: 876, y: 879}, P5{x: 980, y: 580}]

• 【ループ2】STEP 4: 各重心点の座標を再計算する

cendoird_point_1 = {x: 211.333, y: 799.667}
cendoird_point_2 = {x: 900.667, y: 616.667}

→ すべての重心点の座標が変わらない
→ Oh my god! This is result. Stop looping.

アウトプット

6点を以下のように2グループにわけれます。

Group1: [P1{x: 127, y: 933}, P2{x: 138, y: 741}, P6{x: 369, y: 725}]
Group2: [P3{x: 846, y: 391}, P4{x: 876, y: 879}, P5{x: 980, y: 580}]

アルゴリズムを実装していましたので、参考したい方はここにクリックしてください。

References

• https://www.youtube.com/watch?v=_aWzGGNrcic
• https://home.deib.polimi.it/matteucc/Clustering/tutorial_html/kmeans.html
• https://www.coursera.org/learn/machine-learning/lecture/93VPG/k-means-algorithm