CodeZine(コードジン)

特集ページ一覧

視覚的にイメージしにくいアルゴリズムを徹底的にイラストで表現するとこうなる

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2017/06/13 07:00

目次

k-means法――クラスタリング

 最後に紹介するのは、クラスタリングのアルゴリズム「k-means法」です。

 クラスタリングとは、多数のデータを似たもの同士のグループに分類する操作のことで、それぞれのグループをクラスターと呼びます。データ間の距離を定義できれば、距離の遠近でそれぞれのデータがどれくらい似ているかを判断でき、クラスタリングすることができます。

 k-means法は基本的・代表的なもので、クラスターが事前に与える数(k個)になるようにクラスタリングするアルゴリズムです。

リスト4-1

 まず、クラスタリングを行いたいデータを用意しましょう。次に、クラスター数を決めます。今回は3とします。このイラストでは、データを点で表し、データ間の距離は2点間の直線距離を用います。

リスト4-2

 クラスターの中心点として、3点をランダムに設置します。

リスト4-3

 各データについて、3つの中心点のうち最も近い点を計算します。

リスト4-4

 各データを決定したクラスターに分類します。これで三つのクラスターができました。

リスト4-5

 各クラスターに属するデータの重心を計算し、クラスターの中心点をそこに移動させます。

リスト4-6

 最も近いクラスターの中心点を再計算し、各データをクラスターに再分類しました。

リスト4-7

 各データのクラスターへの分類と、中心点の重心への移動を中心点が収束するまで(動かなくなるまで)繰り返します。

リスト4-8

 これは3回目の繰り返しが終わったあとの状態です。

リスト4-9

 4回目の繰り返しが終わったところです。これ以上やっても中心点は移動しないので、クラスタリング完了です。

 k-measn法では操作を繰り返すと中心点が必ずどこかに収束することが証明されています。設定するクラスター数が適切でないと、有意な結果が得られないこともあるので気をつけましょう。

ビジュアライズされたアルゴリズム

 紹介した三つのアルゴリズムを既に知っていた方、あるいは全然知らなかった方も、このように仕組みをイラストでしっかり表現すれば、一気に視覚的にイメージしやすくなったのではないでしょうか。

アルゴリズム図鑑』にはほかのアルゴリズムも掲載していますので、気になる方はチェックしてみてください。

購入者限定の特典はこちら

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

Amazon SEshop その他


アルゴリズム図鑑 絵で見てわかる26のアルゴリズム

著者:石田保輝、宮崎修一
発売日:2017年6月5日(月)
価格:2,570円(税込)

本書のポイント

・基本的な26のアルゴリズムすべてイラストで解説
・誌面がフルカラーなので、図の動きがわかりやすい
・各アルゴリズムの考え方や計算効率、問題点もフォロー
・50万人が学んだ大人気アプリを書籍化



  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • 渡部 拓也(ワタナベ タクヤ)

     翔泳社マーケティング課。MarkeZine、CodeZine、EnterpriseZine、Biz/Zine、ほかにて翔泳社の本の紹介記事や著者インタビュー、たまにそれ以外も執筆しています。

バックナンバー

連載:翔泳社 新刊紹介

もっと読む

All contents copyright © 2005-2020 Shoeisha Co., Ltd. All rights reserved. ver.1.5