᪥ᚰ➨ 㻣㻡 ᅇ኱఍䠄㻞㻜㻝㻝䠅㻌 ᩘ⌮䞉⤫ィ㻌㻝㻭㻹㻜㻠㻝㻌正則化法を用いた重みつき k-means 法 ○西田豊（大阪大学大学院人間科学研究科）キーワード：k 平均法・変数重み付け・正則化 Weighted k-means clustering using regularization techniques Yutaka NISHIDA (Graduate School of Human Sciences, Osaka University) Key words: k-means clustering, variable weighting, regularization 目的 k 平均法 (MacQueen, 1967) は非階層的クラスタリングの手法で，クラスタリングアルゴリズムのうち最もよく使われているものの 1 つであるが，問題がないわけではない．本研究では 2 つの問題点を取り上げる，1 つはクラスタサイズの問題，もう 1 つは変数に関する重み付けの問題である．クラスタサイズの問題とは，k 平均法はクラスタに含まれるサンプルの数が等しくなりやすいことである．そのため，クラスタに含まれるサンプルの数が大きく異なるように分類されるべき場合でも，サンプルの数が等しくなるように分類されてしまうことがある．このような問題に対し Miyamoto, Ichihashi & Honda (2008) はクラスタサイズ調整パラメータ α を導入して解決を試みている．クラスタサイズ調整パラメータはクラスタに含まれるサンプルの数とクラスタの領域が比例するという考えに基づいている．重み付けの問題とは，k 平均法は分類の過程でクラスタ中心とデータポイントとの距離を計算するとき，どの変数も等しく扱うことである．しかしながら，ある変数はほかの変数よりも重要である場合も考えられる．このような考えは通常の k 平均法では反映することはできない．そこで本研究では重み付けの問題に対し，変数の重み付けパラメータ W を導入し，ファジィc 平均法で用いられるエントロピー正則化法 (Miyamoto et al., 2008) を用いて，その推定を行う．エントロピー正則化法を用いたファジィc 平均法は，k 平均法の目的関数に正則化項を付けることにより非線形化し，バイナリで計算されるメンバシップ値 U を [0, 1] のファジィメンバシップ値を求められるようにしたアルゴリズムである．本研究のアプローチはファジィc 平均法と同様で，通常の k 平均法では重み付けが全変数で同じ，すなわち 1/[変数の数] であると考え，エントロピー正則化により重み付けのパラメータをファジイ化し，[0, 1] の値をとることができるように拡張するものである．すなわち，クラスタサイズ調整機能を有する重きつき k 平均法の目的関数とそのアルゴリズムを提案する．なお，クラスタサイズ調整パラメータを導入する場合，メンバシップ値がクリスプとファジィの 2 つが提案されているが，本研究ではクリスプな手法を採用する．目的関数データを N × P の行列 X = {xi j } とする．N と P はそれぞれサンプルと変数の数である．クラスタ数を K で表し，nk はクラスタ k に含まれるサンプル数とする．提案手法の目的関数は N P K ¯ W, α) = F(U, X, uik w j (xi j − x¯k j )2 k=1 i=1 j=1 +λ−1 P j=1 とあらわせる． w j log w j − φ−1 K N i=1 k=1 uik log αk (1) U = {uik } はサンプル i がクラスタ k に含まれるか否かを示す N × K のメンバシップ行列である．サンプル i がクラスタ ¯ = {xk j } k に含まれる場合は 1，含まれない場合は 0 となる．X はクラスタ k のセントロイドを示す K × P の平均行列である． W = diag{w j } は変数 j への重み付けを対角要素に持つ対角行列である．α = {αk } はクラスタ k のクラスタサイズを示すパラメータを要素に持つベクトルである．ここで λ > 0，φ > 0 は正則化パラメータである．この目的関数に課される制約は 3 つある． K uik = 1 and uik ∈ {0, 1}, (2) w j = 1 and 0 ≤ w j ≤ 1, (3) k=1 P j=1 K αk = 1 and 0 ≤ αk ≤ 1. (4) k=1 (2) はメンバシップを示すパラメータ u に関するもので，サンプルはいずれかのクラスタに含まれ，かつ 1 つのみのクラスタに含まれることを意味する．(3) は重み付けを示すパラメータ w に関するもので，変数への重み付けの総和は 1 であり，各変数へ配分することを意味する．(4) はクラスタサイズを示すパラメータ α に関するもので，サンプルサイズ全体を 1 とし，各クラスタに配分することを意味する．アルゴリズム ¯，W，α を求める (1) の関数を最小にするパラメータ U，X 4 つのステップを反復する交互最適化アルゴリズムを用いる．それぞれのステップでは以下のように最適解が求まる． • U ステップ ⎧ P ⎪ ⎪ ⎨ 1, k = arg min j=1 w j (xi j − x¯k j )2 − φ−1 log αk . uik = ⎪ (5) ⎪ ⎩ 0, other. ¯ ステップ •X N i=1 x¯k j = N • W ステップ uik xi j i=1 uik . exp(−λ kK iN uik (xi j − x¯k j )2 ) w j = P . K N ¯k j )2 ) j=1 exp(−λ k i uik (xi j − x (6) (7) • α ステップ αk = nk /N. (8) 引用文献 MacQueen, J. B. (1967). Some methods for classiﬁcation and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium, Vol. 1, 281-297. Miyamoto, S., Ichihashi, H., & Honda, K. (2008). Algorithms for fuzzy clustering: Methods in c-means clustering with applications. Berlin: Springer-Verlag. ̿ 487 ̿