「k-means++法」について学ぶ（統計学 / 教師なし学習 / クラスター分析）
この記事では、統計学を初めて学ぶ筆者が、「教師なし学習」における「クラスター分析」の手法である「k-means++法」について学んだ内容について記載しています。
学習には、Wikipediaの「k-means++法」の記事を参考にし、Pythonのプログラミングにも触れ、理解を深めました。
プログラミングには、機械学習ライブラリのscikit-learnを使用しました。
この記事は、他の人が参考にできるよう、わかりやすく書くことを心がけました。
教師なし学習
教師なし学習は、データからパターンや構造を見つけ出すための機械学習の手法です。データにはラベルや目的変数がなく、機械自身が学習し、データの背後にある構造を抽出します。例えば、ある企業の顧客データを教師なし学習で解析することで、似たような傾向を持つグループや、注目すべき特徴を抽出することができます。
一方、教師あり学習は、データにラベルや目的変数がある場合に用いられます。目的変数と予測値との誤差を最小化するようにモデルを構築し、未知のデータに対して予測を行います。例えば、画像認識や音声認識などが教師あり学習の例です。
クラスター分析は、教師なし学習の一例で、似た特徴を持つデータをグループ化する手法です。例えば、ある商品を顧客がどのような特徴で分類しているかをクラスター分析で解析することで、市場セグメンテーションを行うことができます。
教師なし学習とは、機械学習の手法の一つである。「出力すべきもの」があらかじめ決まっていないという点で教師あり学習とは大きく異なる。データの背後に存在する本質的な構造を抽出するために用いられる。
教師あり学習は、その「出力すべきもの」も入力として与える手法であり、データの背後に存在する本質的な構造を抽出するよりむしろ、思い通りの出力を再現する機械の構成に用いられる。
具体的な例として以下のようなものがある。
・クラスター分析
・主成分分析
・ベクトル量子化
・自己組織化マップ
教師なし学習
クラスター分析
クラスター分析とは、データを自動的に分類する方法の一つです。例えば、マーケティング分野で、顧客のデータをクラスター分析することで、似たような傾向を持つ顧客をグループ化し、そのグループごとに商品の販売戦略を立てたり、顧客へのアプローチ方法を変えることができます。
階層的手法では、与えられたデータをまず小さなグループに分類し、その後、より大きなグループに統合していく方法です。一方、非階層的手法の代表的なものにK-means法があり、この方法では、あらかじめ分類したいクラスターの数を指定し、その数に応じた分類を行います。この分類の際に、各データ点と各クラスター中心との距離を計算して、最も近いクラスターに割り当てることで分類します。
クラスタリング、クラスタ解析、クラスター分析は、データ解析手法（特に多変量解析手法）の一種。教師なしデータ分類手法、つまり与えられたデータを外的基準なしに自動的に分類する手法。また、そのアルゴリズム。
さまざまな手法が提案されているが、大きく分けるとデータの分類が階層的になされる階層型手法と、特定のクラスタ数に分類する非階層的手法とがある。それぞれの代表的な手法としてウォード法、K平均法などがある。
データ・クラスタリング
K平均法(K-means法)
k平均法は、多数のデータから類似するものをグループ分けする手法の一つで、特にデータの分類やクラスタリングに使用されます。例えば、カスタマーデータを分析する際に、年齢、性別、趣味などの属性を元に似た傾向をもつグループを作り出すことができます。k平均法は、あらかじめグループの数を指定する必要がありますが、その後は自動的にクラスターを作成します。そして、クラスターの中心にある平均値を求めることで、クラスターを特徴付けます。
k平均法は、非階層型クラスタリングのアルゴリズム。クラスタの平均を用い、与えられたクラスタ数k個に分類することから、MacQueen がこのように命名した。k-平均法（k-means）、c-平均法（c-means）とも呼ばれる。
k平均法
アルゴリズム
k平均法（k-means法）は、データをクラスターに分けるアルゴリズムです。まず、データをランダムにクラスターに割り当てます。その後、各クラスターの中心を求め、各データと各クラスターの中心との距離を計算し、最も近いクラスターに再度割り当てます。このプロセスを繰り返し、クラスターの割り当てが変化しなくなるまで続けます。ただし、最初のクラスターの割り当てによって結果が変わることがあります。そのため、k-means++法のように最初のクラスターの割り当て方法を工夫する方法があります。また、クラスターの数kは最初に与えられたものとして設定されているため、最適なクラスターの数を選択するためには他の配慮が必要です。
結果は、最初のクラスタのランダムな割り振りに大きく依存することが知られており、1回の結果で最良のものが得られるとは限らない。そのため、何度か繰り返して行って最良の結果を選択する手法や、k-means++法のように最初のクラスタ中心点の振り方を工夫する手法などが使用されることがある。
なお、このアルゴリズムではクラスタ数 k は最初に所与のものとして定めるため、最適なクラスタ数を選ぶには他の計算等による考察を用いる必要がある。
k平均法
k-means++法
k-means++法は、k-means法の初期値選択方法を改良したものです。k-means法は、データ点をランダムに選んで初期のクラスタ中心を設定しますが、この方法ではクラスタリングの結果が初期値に依存してしまい、非効率なクラスタリングが生じることがあります。
k-means++法は、より効率的な初期値選択方法を提案しています。具体的には、まず最初の中心点をランダムに選び、その後は、その中心点から最も遠いデータ点を新しい中心点として選択することを繰り返します。この方法によって、初期値がランダムである場合に比べて、より良いクラスタリングが得られることが知られています。
また、k-means++法は、k-means法が非クラスタにクラスタを割り当てる問題を解決するためにも使用されます。この問題は、初期値によってクラスタリングの結果が大きく変わるため、k-means法においては複数回の実行を行うことが推奨されています。
さらに、k-means++法は、k-means法がNP困難であるという問題を解決するためにも使用されます。NP困難問題とは、問題の大きさが大きくなるにつれて、計算時間が爆発的に増加する問題です。k-means++法は、初期値選択の効率化によって、計算時間を短縮することができます。
k-means++法は、非階層型クラスタリング手法の1つで、k-means法の初期値の選択に改良を行なった方法である。標準的なk-means法が頻繁にクラスタとすべきではないものにもクラスタ割り当てを行ってしまう問題や、k-means法がNP困難な問題であることを解消するために、2007年にDavid ArthurとSergei Vassilvitskiiによって提案された。2006年にRafail Ostrovskyらによって提案されたthree seeding methodと似ているが初期シードの分布が異なる。
アルゴリズム
k-means++法は、効率的なクラスタリングのために、クラスタ中心が適切に選択されるように改良された方法です。この方法では、最初のk個のクラスタ中心ができるだけ離れていることが重視されます。
まず、クラスタリング対象の中からランダムに1つのデータ点をクラスタ中心として選択します。そして、すべてのクラスタリング対象と選ばれたクラスタ中心との距離を計算します。残りのクラスタ中心は、選択されていないクラスタリング対象から距離の二乗に比例した確率で選択されます。つまり、距離が遠いほど選択される確率が高くなります。この方法によって、最初のクラスタ中心が遠く離れている場所に選ばれるため、より効率的なクラスタリングが可能になります。
例えば、100個のデータ点がある場合、最初のクラスタ中心をランダムに選ぶ方法では、その中心点が近くにある場合、そのクラスタリングは非効率になる可能性があります。しかし、k-means++法を使用する場合、最初のクラスタ中心が遠く離れた場所に選ばれるため、より効率的なクラスタリングが可能になります。
このk-means++法は、初期のk個のクラスタ中心はなるべく離れている方が良いという考えにもとづいている。まず始めにデータ点をランダムに選び1つ目のクラスタ中心とし、全てのデータ点とその最近傍のクラスタ中心の距離を求め、その距離の二乗に比例した確率でクラスタ中心として選ばれていないデータ点をクラスタ中心としてランダムに選ぶ。
アルゴリズムは以下の手順で行われる。
データ点からランダムに1つ選びそれをクラスタ中心とする。 while 個のクラスタ中心が選ばれるまで do それぞれのデータ点に関して、その点の最近傍中心との距離を計算する。 データ点に関して重みつき確率分布 を用いて、データ点の中から新しいクラスタ中心をランダムに選ぶ。 選ばれたクラスタ中心を初期値として標準的なk-means法を行う。
この初期化方法は、k-means法に比べて格段に優れています。初期値の決定には余分な時間がかかりますが、k-means++法は非常に早く収束し、計算時間もあまり必要ありません。実際に、2倍の収束速度と1000分の1の誤差が報告されるなど、その効果は高く評価されています。
この初期値決めの方法はk-means法を著しく改善する。 初期値決めに余計な時間がかかるが、k-means法は収束がとても早く計算時間はそれほどかからない。 著者らはこの手法を実データと人工データの両方で実験を行い、 だいたい収束スピードに関しては2倍、あるデータセットでは誤差が1000分の1となったことを報告している。 一連の実験では定番のk-means法に速度と誤差に関してつねに優っていた。
k-means++法
Pythonプログラミング
「k-means++」をイメージしやすいようPythonでのプログラミングについても学びます。
scikit-learn トイデータセット
機械学習ライブラリscikit-learnに用意されている「トイデータセット」を使います。トイデータセットは、機械学習の問題を解くためのサンプルデータセットのことで、いくつかの種類が用意されています。例えば、Iris（アヤメ）の花の特徴から、その種類を分類する問題を解くための「irisデータセット」や、ボストン市の住宅価格に関するデータを用いて、住宅価格を予測する問題を解くための「bostonデータセット」などがあります。
Irisデータセットは、Setosa、Versicolour、Virginicaの3種類のアヤメの花のデータが含まれており、各種類について50個のサンプルがあります。このデータセットには、がく片の長さや幅、花びらの長さや幅、そしてアヤメの種類という4つの特徴量が含まれています。
アヤメの花の4つの特徴量（花弁の長さや幅、がく片の長さや幅）を使って、k-means++法を使い、アヤメを3つのグループ（クラスター）に分けることができます。
scikit-learnにはいくつかの小さな標準データセットが付属しており、外部のウェブサイトからファイルをダウンロードする必要はありません。
これらは以下の関数を使って読み込むことができます。
load_boston() : load_boston は 1.0 で非推奨となり、1.2 で削除される予定である。
load_iris() : アヤメのデータセット(分類)をロードして返す。
load_diabetes() : 糖尿病のデータセット(回帰)をロードして返す。
load_digits() : 数字のデータセット(分類)をロードして返す。
load_linnerud() : 身体運動のデータセットをロードして返す。
load_wine() : ワインのデータセット(分類)をロードして返す。
load_breast_cancer() : ウィスコンシン州の乳がんのデータセット（分類）をロードして返す。7.1. Toy datasetsts
アヤメのデータセット
アヤメのデータセットは、機械学習における代表的なデータセットの1つであり、サンプルデータの中でも特に有名なものの1つです。
アヤメのデータセットには、ヒオウギアヤメ(Iris-Setosa)、アイリス・バージカラー(Iris Versicolour)、アイリス・ヴァージニカ(Iris Virginica)の3種類のアヤメが含まれており、各々50件のデータがあります。データには、「がく片の長さ」、「がく片の幅」、「花びらの長さ」、「花びらの幅」といった4つの属性があり、また3種のアヤメの分類に関するデータも含まれています。
Iris Versicolour （アイリス・バージカラー）
北アメリカ、アメリカ東部とカナダ東部に自生するアヤメの一種です。スゲ草地や湿地、川岸や海岸に普通に見られます。
特異形質バージカラー(versicolor)は「様々な色彩の」という意味です。
Iris Virginica （アイリス・ヴァージニカ）
北アメリカ東部原産の多年草です。アメリカ南東部のフロリダ州からジョージア州にかけての海岸平野によく見られます。
プログラム
k-means++法を使ってアヤメのデータセットをクラスター分析し、アヤメの種類とクラスター分析の結果をピボットテーブルで比較します。
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.cluster import KMeans
# アヤメのデータセットを読み込む
iris = load_iris()
# 特徴量データをDataFrameに変換する
df = pd.DataFrame(iris.data, columns=iris.feature_names)
# k-means++法でクラスタリングを行う
kmeans = KMeans(n_clusters=3, init='k-means++', random_state=0).fit(df)
# クラスタリング結果をDataFrameに追加する
df['cluster'] = kmeans.labels_
# アヤメの種類情報をDataFrameに追加する
df['species'] = [iris.target_names[i] for i in iris.target]
# 結果をピボットテーブルで表示する
result = pd.pivot_table(df, values='sepal length (cm)', index='species', columns='cluster', aggfunc='count')
print(result)実行結果
k-means++法によって、アヤメの種類がsetosaに分類されるものはすべてクラスタ1に、アヤメの種類がversicolorに分類されるものはクラスタ0とクラスタ2に、アヤメの種類がvirginicaに分類されるものはクラスタ0とクラスタ2に分類されたことがわかります。
cluster 0 1 2
species
setosa NaN 50.0 NaN
versicolor 48.0 NaN 2.0
virginica 14.0 NaN 36.0プログラムの説明
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.cluster import KMeanspandasライブラリをpdという名前でインポートします。
sklearn.datasetsライブラリからirisデータセットをインポートします。
sklearn.clusterライブラリからKMeansクラスをインポートします。
# アヤメのデータセットを読み込む
iris = load_iris()
# 特徴量データをDataFrameに変換する
df = pd.DataFrame(iris.data, columns=iris.feature_names)irisデータセットを読み込み、iris変数に代入します。
irisの特徴量データをiris.dataから取得し、列名にiris.feature_namesを指定してDataFrameに変換し、df変数に代入します。
# k-means++法でクラスタリングを行う
kmeans = KMeans(n_clusters=3, init='k-means++', random_state=0).fit(df)
# クラスタリング結果をDataFrameに追加する
df['cluster'] = kmeans.labels_k-means++法を適用し、クラスター数をn_clusters=3、ランダムシードをrandom_state=0として、dfデータフレームに対して学習を行い、結果をkmeansに代入します。
KMeans()関数は、K平均法を使用してクラスタリングを行います。K平均法は、データを指定された数のクラスタに分類する方法であり、各クラスタの中心（平均値）を求めることで、各データポイントが最も近いクラスタに割り当てられます。
引数のn_clustersは、分類するクラスタの数を指定するためのパラメータです。initは、クラスタ中心の初期化方法を指定するパラメータです。’k-means++’を指定することでk-means++法を用いた初期化が行われます。random_stateは、乱数のシードを指定するためのパラメータであり、同じ乱数シードを使用すると、再現性のある結果を得ることができます。
fit()関数は、k-means++によるクラスタリングを行うために、引数のdfを使ってkmeansオブジェクトを学習します。dfは、データフレーム形式の特徴量データ（花弁の長さや幅、がく片の長さや幅）であり、各行が異なる観測値を表し、各列が異なる特徴量を表します。K平均法は、各列ごとに平均を計算することで中心点を求めます。つまり、複数の特徴量がある場合、各特徴量の平均値を計算して、中心点を求めます。
dfデータフレームに、クラスター番号を表すcluster列を追加し、それにkmeans.labels_の値を代入します。
# アヤメの種類情報をDataFrameに追加する
df['species'] = [iris.target_names[i] for i in iris.target]irisのターゲットデータをiris.targetから取得し、iris.target_namesからアヤメの種類を取得して、それらをリストとして作成し、dfデータフレームにspecies列として追加します。
# 結果をピボットテーブルで表示する
result = pd.pivot_table(df, values='sepal length (cm)', index='species', columns='cluster', aggfunc='count')
print(result)dfデータフレームを使って、species列を行、cluster列を列として、’sepal length (cm)’列の値を集計してピボットテーブルを作成し、result変数に代入します。
pd.pivot_table()は、データフレームをピボットテーブルに変換する関数です。引数には以下のように指定します。
- df: 変換するデータフレーム
- values: 集計する値の列
- index: 行にくる特徴量列
- columns: 列にくる特徴量列
- aggfunc: 集計関数
この場合、dfはk-means++法によってクラスタリングされた各サンプルに対して、アヤメの種類がどのクラスタに属するかを示すラベルとともに、各特徴量の値が含まれたデータフレームです。valuesには集計する値の列を指定しています。この場合、1つ目の特徴量であるsepal length (cm)列を指定しているため、resultは各アヤメの種類とクラスターの組み合わせにおけるsepal length (cm)の値の件数を示すピボットテーブルになります。indexには行にくる特徴量列を指定しています。この場合、アヤメの種類を指定しています。columnsには列にくる特徴量列を指定しています。この場合、クラスターのラベルを指定しています。aggfuncには集計関数を指定しています。この場合、countを指定しているため、各セルには該当するアヤメの種類とクラスターの組み合わせにおけるsepal length (cm)の値の件数が表示されます。