データ構造に対して頑健なクラスタリング手法の開発
代表研究者

濵 砂 幸 裕近畿大学 理工学部情報学科 講師

1 はじめに
情報通信技術の飛躍的発展により、自然科学や社会科学など様々な分野において、多種多様な大量のデー
タが蓄積されている。また、蓄積されたビッグデータを活用したデータマイニングの重要性は極めて強く認識されている[1]。例えば、EC サイトにおける購買履歴の分析による商品の推薦、GPS を利用した行動履歴の分析による人流の予測、SNS 上のコミュニティ抽出によるトレンド予測など、その応用範囲は多岐にわたる。
情報通信機器の性能向上や低コスト化が著しい現代において、データマイニングの重要性は今後益々進展すると予想され、その中核をなすデータ解析手法の重要性は高まるばかりである。
データ解析手法の中でも、クラスタリングはデータの構造や規則性を明らかにする手法として知られており、データの前処理から分析まで幅広く用いられる手法として知られている[2]。クラスタリングとは、対象とするデータをクラスタと呼ばれる複数のデータの集まりに分割する手法である。その際に、同じクラスタに含まれるデータは似た特徴を持ち、特徴の似ていないデータは異なるクラスタに含まれるように分割される。クラスタリングとは、先に述べたように特徴の似たデータで 1 つのクラスタを構成するようにデータを分割する手法の総称であり、代表的な手法として k-means、ファジィ c-平均法[3]、階層的クラスタリング[4]が知られている。また、クラスタリングが対象とするデータはベクトルデータに限らず、近年ではグラフ構造で表されるネットワークデータも重要な解析対象の一つとなっている[5]。
クラスタリング手法は階層的手法と非階層的手法の 2 つに大別される。階層的クラスタリングは一つ一つのデータをクラスタとみなし、逐次的に結合することでクラスタ分割を生成する手法である。階層的手法は
非階層的手法に比べて計算量は多いものの、クラスタ分割の生成過程を樹形図として可視化することも可能
であることから、比較的小規模のデータを対象とする場合に有効な手法と考えられる[4]。一方、k-means を
はじめとする非階層的クラスタリングの多くの手法は、帰属度などの制約条件の下で、目的関数を最小化す
る交互最適化を行うことで、クラスタ分割を生成する手法である。非階層的手法の代表例である k-means はクラスタ中心と呼ばれるクラスタの代表点と帰属度と呼ばれるデータがクラスタへ所属するか否かを示す変数の交互最適化によりクラスタ分割を生成する手法である。非階層的手法は、階層的クラスタリングに比べて計算量が少ないことから比較的規模の大きなデータに対しても適用することが可能であり、大量のデータを少数のデータへ要約する前処理やデータの構造や規則性の分析にも用いられる[2,3,4]。また、k-means の帰属度を 0 か 1 の二値ではなく、0 から 1 の範囲を取るように拡張したファジィクラスタリングは、人間の感覚に沿った柔軟なクラスタ分割を生成するという点に加えて、確率モデルの分野における混合ガウス分布との関連性が議論されるなど、理論と応用の両面から重要な研究対象となっている[6]。
k-means やファジィクラスタリングを代表とする非階層的手法は、比較的規模の大きなデータを扱えるという特徴から様々な分野において利用されている。しかしながら、クラスタリング手法にはいくつかの問題点があるため、今後も増大かつ複雑化が進行すると考えられるビッグデータを扱うには、それらの問題点を克服した手法が望まれる。ここでは、クラスタリングにおける代表的な問題とそれらに対応するために提案されたクラスタリング手法について説明する。まず、k-means などの非階層的手法は、交互最適化を行うた
め、最終的に得られるクラスタ分割が初期値に依存するという初期値依存の問題がある。この初期値依存に対する手法として、初期値として与えるクラスタ中心をデータ個体の中から、ある確率に従って選択する kmeans++が提案されている[7]。k-means++はすでに選択されたデータ個体から遠いデータ個体ほど、次のクラスタ中心として選択されやすくする初期値選択の方法を取ることで、目的関数が収まる範囲を理論的に解析した手法である。k-means++は通常の k-means よりも早く収束し、良好なクラスタ分割を得られることから、
scikit-learn (https://scikit-learn.org/stable/index.html)などのデータ解析ライブラリにも収録されている。また、クラスタリング手法の多くは非類似度としてユークリッド距離の自乗を用いるため、結果として得られるクラスタ分割がボロノイ図を構成するという特徴がある。そのため、データの塊から離れた位置に存在する外れ値の影響を受けやすいという特徴がある。非類似度としてユークリッド距離の自乗を用いるもう一つの影響として、生成されるクラスタ分割が等方性を持つ超球状になるという性質もある。外れ値

1
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

に対する影響を低減した手法としては、可能性クラスタリング[8]、ノイズクラスタリング[9]、DBSCAN[10]、HDBSCAN[11]などが代表的である。また、多様なクラスタ分割を生成する手法としてカーネル法を用いたクラスタリング手法が提案されている[3]。このように、クラスタリングに関する諸問題を解決するには、非類似度や帰属度に関する数理モデルを拡張し、新たな目的関数に基づいたアルゴリズムを構築する方法が取られている。
そこで本研究では、外れ値などの影響を低減し、データの分布や構造に依存することなく良好なクラスタ
分割を生成する手法として、Jensen-Shannon divergence（JS-ダイバージェンス）[12]に基づく k-medoids（JS-divergence based k-medoids, JSKMdd）を提案する。従来手法では、単一のデータが持つ座標などの情報に対して非類似度を与えるため、外れ値やデータの分布を考慮することが困難となっている。そのため提案手法では、データが持つ情報だけでなく、データの周辺に分布するデータも併せて考慮する非類似度を用いる。具体的には、カーネル密度推定(Kernel Density Estimation, KDE)[13]を用いて、近傍に存在するデータを用いて一つの個体をデータ分布に変換する。さらに、KDE を用いて推定されたデータ分布間の非類似度を Jensen-Shannon Divergence（JS-ダイバージェンス）[12]により算出する。JS-ダイバージェンスの算
出は計算コストが大きいため、提案手法ではクラスタ中心をクラスタ内に存在する個体から選択する kmedoids 型のアルゴリズム[14]を用いる。
提案手法はクラスタリングの代表的手法である k-medoids を拡張したアルゴリズムである。数値実験では5 種類の人工データを用いて、クラスタリングの代表的手法である k-means、k-medoids、スペクトラルクラ
スタリング（Spectral clustering, SC）[15]と比較を行った。SC はカーネル法との関連性も示されており、複雑な構造を持つデータを適切に分割する有用な手法として知られている。数値実験の結果から、提案手法
JSKMdd は線形な境界を持つデータおよび非線形な境界を持つデータの両者を適切に扱える手法であり、パラメータを適切に設定することで SC を上回る性能を示すことが示唆された。

2 準備
クラスタリングの対象となるデータ集合を𝑋 = {𝑥! | 𝑥! ∈ 𝑅" , 𝑘 = 1~𝑛}とする。クラスタを𝐺# とし、クラス
タリングの結果として得られるクラスタ分割を𝐺 = {𝐺$ , … , 𝐺% }とする。また、データ𝑥! がクラスタ𝐺# に所属す
る度合いを示す帰属度を𝑢!# とし、帰属度の集合を𝑈 = {𝑢!# | 𝑘 = 1~𝑛, 𝑖 = 1~𝑐}とする。
2-1 k-medoids

k-medoids はクラスタリングの代表的手法の一つとして知られている[14]。最も代表的な手法である kmeans はクラスタの代表点であるクラスタ中心をクラスタ内の個体の平均とする手法である[2]。一方で、kmedoids はクラスタ内の個体から代表点を選択する手法となっている。そのため、k-medoids はベクトルデー
タのみならず、拡散カーネル[16]などを用いた重み付けを行うことでネットワークデータなどの関係データを扱うことも可能である[17]。k-medoids の目的関数を以下に示す。
%

'

'

(1)

𝐽(𝑈, 𝑊) = 9 9 9 𝑢!# 𝑤&# 𝑟!&#($ !($ &($ここで、𝑟!& はデータ間の関係性を示す尺度であり、ユークリッド距離、マンハッタン距離、ユークリッド
距離の自乗などが用いられる。また、𝑊 = {𝑤&# | 𝑙 = 1~𝑛, 𝑖 = 1~𝑐}はクラスタの代表点を決める重みである。
k-medoids のアルゴリズムは𝑢!# と𝑤&# の制約条件の下での交互最適化により構成される。𝑢!# と𝑤&# の制約条件を以下に示す。
%

𝑈 = =(𝑢!# ) ∶ 𝑢!# ∈ {0, 1}, 9 𝑢!# = 1, ∀𝑘@

(2)

#($
'

𝑊 = =(𝑤&# ) ∶ 𝑤&# ∈ {0, 1}, 9 𝑤&# = 1, ∀𝑖@&($2
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度(3)

k-medoids では、𝑤&# = 1となった𝑙番目の個体がクラスタの代表点となる。目的関数と制約条件より𝑢!# と𝑤&# の更新式は以下で与えられる。
'

1 D𝑖 = arg min 9 𝑤&* 𝑟!& K*
𝑢!# = C0 (otherwise)

(4)

&($

'

1 D𝑖 = arg min 9 𝑢!# 𝑟!+ K+
𝑤&# = C0 (otherwise)

(5)

!($

optimization problem of Jkd , the optimal solution of wli is ecpressed in (5).
Further, (6) considers k-medoids clustering in the algorithmic procedure.
k-medoidsTheのアルゴリズムは以下で表される。
algorithm of KMdd is summarized as follows:
Algorithm 1 KMdd
KMdd1 Set cluster number c and initial medoids wli ∈ W by choosing
objects at random.
KMdd2 Calculate uki ∈ U using (4).
KMdd3 Calculate wli ∈ W using (5).
KMdd4 If the convergence criterion is satisfied, stop. Otherwise, return toKMdd2.
The number of repetitions, convergence of each variable, or the conKMdd4 における収束条件として、最大繰り返し回数、変数の収束、目的関数の収束が考えられる。
vergence of an objective function is used as the convergence criterion in
KMdd4.
2-2 カーネル密度推定
カーネル密度推定は、特定の分布を仮定せずに与えられたデータセットに基づいて確率密度関数を推定する手法である[13]。𝑥
1.2 Kernel
density estimation! を独立同一分布に従う確率変数とすると、以下のカーネル密度推定により確率密度関数は以下で表される。

KDE is one of the methods to estimate the probability density function [?].
KDE is a nonparametric method anddoes not require a specific density'
1− 𝑥! function from given a set
function. KDE estimates the probability 𝑥density(6)
𝑝(𝑥) =
9𝐾WY𝑛ℎℎof objects automatically.
!($
Let xk be an independent, identically distributed random variable. KDE
ここで、𝐾(∙)はカーネル関数であり、ℎ> 0は滑らかさを調整するパラメータである。また、カーネル関数
estimates the probability density function according to the following func𝐾(∙)は以下の条件を満たす関数が用いられる。
tion:
#
"
n
x − xk1 !
K
p(x)=
𝐾(𝑥) ≥ 0,^ 𝐾(𝑥) 𝑑𝑥 = 1,
^ 𝑥 𝐾(𝑥)𝑑𝑥 = 0, . ^ 𝑥 , 𝐾(𝑥)𝑑𝑥 > 0 (7)
nh
h
k=1

where K(·) is a kernel function and h > 0 is the bandwidth parameter which
controls the smoothness.
The kernel function K(·) satisfies the following properties:

𝐾(∙)の代表的な例として、以下で表されるガウシアンカーネルがある。

K(x) ≥ 0,$
1
𝑥,
𝐾(𝑥) =K(x)dx
exp=d−
1, 2 e√2𝜋$xK(x)dx = 0,$x2 K(x)dx> 0.
3
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

カーネル密度推定により求められる多次元の確率密度関数は以下で表される。
'

"

1
1
𝑥 - − 𝑥!𝑝(𝑥) = 9 f 𝐾 d
e
𝑛
ℎℎ-

(7)

!($ -($

ここで、ℎ- > 0は𝑗次元に対する滑らかさを調整するパラメータであり、𝑥!- は𝑥! の𝑗次元目の要素である。
2-3 Jensen-Shannon Divergence
JS-ダイバージェンスは 2 つの確率密度関数に対する非類似度と考えることできる[12]。JS-ダイバージェ
ンスは Kullbuck-Leibler ダイバージェンス（KL-ダイバージェンス）[18]に基づいている。2 つの確率密度関数𝑝(𝑥)と𝑞(𝑥)間の KL-ダイバージェンスは以下で与えられる。
./

𝐾𝐿(𝑝(𝑥) || 𝑞(𝑥)) = ^0/𝑝(𝑥)log

𝑝(𝑥)
𝑑𝑥
𝑞(𝑥)

クラスタリングにおける非類似度は対称性を満たすことが一般的であるため、KL-ダイバージェンスをそのまま適用するには不都合が生じる場合がある。そこで、対称性を満たす尺度として、JS-ダイバージェンスが知られている[12]。JS-ダイバージェンスは以下で表される。
𝐽𝑆m𝑝(𝑥) ∥ 𝑞(𝑥)o =11𝐾𝐿m𝑝(𝑥) ∥ 𝑚(𝑥)o + 𝐾𝐿m𝑞(𝑥) ∥ 𝑚(𝑥)o
2
2

(8)

$

ここで、𝑚(𝑥) = , m𝑝(𝑥) + 𝑞(𝑥)oである。

3 提案手法本章では、本研究で提案する JS-ダイバージェンスを用いた k-medoids（JSKMdd）について説明する。JSKMdd
は k-medoids の拡張であり、データの構造や周辺の分布を考慮するために、KDE で推定したデータ分布間の非類似度を JS-ダイバージェンスで求める手法である。
はじめに KDE を用いてデータ分布を推定する方法について説明する。データ𝑥! の近傍個体の集合を𝑁(𝑥! )とし、以下で定める。
𝑁(𝑥! ) = {𝑥 ∈ 𝑋 | 𝑑(𝑥! , 𝑥) ≤ 𝐷}

(9)

ここで、𝐷 > 0はパラメータであり、𝑑(𝑥! , 𝑥)はユークリッド距離などの距離尺度である。式(9)では、データ𝑥! から 𝐷以下の非類似度となるデータが𝑁(𝑥! )に含まれることになる。また、任意の個数のデータを𝑁(𝑥! )に含む場合には、以下のように定義することも考えられる。
𝑁(𝑥! ) = w𝑥 ∈ 𝑋 | 𝑑(𝑥! , 𝑥) ≤ 𝑑m𝑥! , 𝑥1(+) ox(10)

ここで、𝑞(+) ∈ {1~𝑛}は𝑑(𝑥! , 𝑥$ ), … , 𝑑(𝑥! , 𝑥' )を昇順に並び替えた場合の個体番号を示しており、𝑡番目に小さい値を持つ個体番号を指す。式(9)と式(10)を比較した場合、式(10)で与える近傍では、必ず𝑡個の個体を含むことになる。
データ𝑥! と近傍に含まれるデータ集合𝑁(𝑥! )から KDE により推定される確率密度関数𝑝(𝑥! )は以下で表される。

4
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

defined by (10) or (11) as follows:1
p(xk ) =|N (x1k )|𝑝(𝑥! ) =

p
"
1

!

"

j=1
x∈N
(xk ) f9

|𝑁(𝑥! )|

4 ∈7(4!) -($#xj − xjk
K 1hj 𝑥 − 𝑥h!-j

ℎ-

𝐾d

e

ℎ-

$

.

(12)
(11)

where, |N (xk )| means the number of objects in N (xk ). p(xk ) is the data
distribution calculated by a set of neighbor objects N (xk ). The dissimilarity
ここで、|𝑁(𝑥is! )|は集合𝑁(𝑥! )に含まれる個体数を意味している。式(11)で求めたデータ𝑥! の確率密度関数
tocalculated by
JS-divergence with the data distribution p(xk ) accordingに対して、式(8)を用いて個体間の非類似度を算出する。
(9).
提案手法の目的関数は式(1)の𝑟!& を JS-ダイバージェンスに置き換えた以下の式で表される。また、制約条
The optimization
problem of JSKMdd is as follows:
件は k-medoids と同じく、式(2), (3)で表される。
n !
c !
n
!
"
JJSKMdd (U, W ) =uki wli rkl
,
%

'
'
i=1
k=1 l=1%

𝐽(𝑈, 𝑊) = 9 9 9 𝑢!# 𝑤&# 𝑟 8 !&#($ !($
&($
Uh =
(uki
) : uki ∈ {0, 1} ,𝑈 = =(𝑢%!# ) ∶%c!

uki = 1, ∀ k

i=1
𝑢!# ∈ {0, 1}, 9 𝑢!#n= 1, ∀𝑘@!

#($
Wh = (wli ) : wli ∈ {0, 1},
'

&

,

&

wli = 1, ∀ i .

∀𝑊 = =(𝑤&# ) ∶ 𝑤&# ∈ {0, 1}, 9 𝑤l=1&# = 1, 𝑖 @where, the objective function and constraints&($are the same as (1), (2), and" is the JS-divergence(3). The difference of KMdd and JSKMdd is that rkl
calculated by (9) under (11).
提案手法のアルゴリズムは以下で表される。
The algorithm of JSKMdd is summarized as follows:
Algorithm 2 JSKMdd
JSKMdd1 Set parameter D or t. Calculate p(xk ) by (12).
" by (9).
JSKMdd2 Calculate rkl

JSKMdd3 Set cluster number c and initial medoids wli ∈ W by choosing
objects at random..
JSKMdd4 Calculate uki ∈ U using (4).
JSKMdd5 Calculate wli ∈ W using (5).
JSKMdd6 If convergence criterion is satisfied, stop.
Otherwise, return to JSKMdd4.
JSKMdd1
k-medoids との大きな違いはにおいてパラメータを設定し、KDE
In this paper,
k-medoids
clustering type algorithmを用いて確率密度関数を推定す
is considered beる点、JSKMdd2 causeにおいて
JS-ダイバージェンスを算出する点である。𝑢と𝑤の更新式は式(4),a high calculation time is required to calculate
If (5)におい!#&#JS-divergence.
KMdd4 と同じく、最大繰りて𝑟!& を𝑟′!& に置き換えることで求められる。
における収束条件として、
JS-divergence is consideredJSKMdd6
in k-meansclustering type algorithm,
the dis返し回数、変数の収束、目的関数の収束が考えられる。
similarity between object and cluster centers is required to update in each

iteration. JS-divergence based k-means takes much computation costs in
updating the membership degree process JSKMdd4. k-medoids clustering

4 数値実験
4

提案手法の有効性を検証するために 5 種類の人工データを用いて数値実験を行った。はじめに、計算条件について述べ、その後実験結果について説明する。最後に提案手法の特徴について示す。本研究では、
k-means、
k-medoids、スペクトラルクラスタリングと比較を行った。

5
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

4-1 計算条件
今回使用する人工データは分割結果が既知のデータである。提案手法と上記の比較手法について、それぞthe value of hj is the same in all dimensions. The cluster partitions
れの手法が生成するクラスタ分割と人工データの分割を
randareindex(ARI)[19]を用いて評価した。
of all datasets used in the numerical Adjusted
experiments
known.
ARI, asARI は 2 つの分割結果の一致度合いを示す指標であり、完璧に一致した場合にARIの値は1 となる。
mentioned above, is used as an index to evaluate the accuracy of the
はじめに、使用した人工データのデータ数、次元数、クラスタ数について表 1 に示す。

clustering result [?].

表 1: 数値実験で使用したデータの詳細np cPolarisArtificial
Double circle
Double circle 2
Two moon

51
72
150
150
400

2
2
2
2
2

3
3
2
2
2

また、図 1 から 5 にそれぞれの人工データを適切に分割した際の結果を示す。図 3, 4 では外側のクラス
タに 100 個のデータが含まれ、内側のクラスタに 50 個のデータが含まれている。図 4 は図 3 の内側のクラスタを外側のクラスタに近づけたものとなっている。

図 1: Porlais dataset.

3.2

Experimental results

Figures 6, 7, 8, 9, and 10 show the ARI values by the proposed method
for five datasets. The ARI value in each graph is calculated from thecluster partition obtained using each method and the cluster labels. In
Figs. 6–10, the vertical and horizontal axes indicate the value of ARI
and the value of hj , respectively. The value of hj is applied each value
when the hundred division the range shown in Table 2. The highest ARI
value out of 100 initial trials is shown in Figs. 6–10 for each parameter.
The ARI results of each method are summarized in Table 3. Table 3
提案手法では、データ分布を推定する際のパラメータとして、𝐷もしくは𝑡を設定する必要があり、KDE でshows that several methods including the proposed method obtain ade-

確率密度関数を推定する際に、バンド幅ℎ- を設定する必要がある。適切なパラメータはデータセットによって異なるため、表 2 に示されるパラメータを用いて数値実験を行った。実験では、全てのバンド幅ℎ- に対し
6て同じ値を与えた。また、バンド幅は表 2 に示した値の範囲を100 分割し、それぞれの値を与えて実験を行った。また、提案手法は初期値に依存するため、初期値を 100 回変えて実行し最も値が良かった場合の ARIで評価した。

6
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

表 2: 数値実験で使用したパラメータの詳細
Data
t
hj

PolarisArtificial
Double circle
Double circle 2
Two moont ∈ {4, 6, 8}
t ∈ {4, 9, 14}t ∈ {4, 6, 8}
t ∈ {4, 9, 12}t ∈ {4, 8, 12}

hj ∈ [0.001, 5.000]
hj ∈ [0.001, 1.000]
hj ∈ [0.001, 0.100]
hj ∈ [0.001, 0.100]
hj ∈ [0.001, 0.500]

4-2 実験結果 the hundred division the range shown in Table 2. The highest ARI value
図 6 から 11 にバンド幅ℎの結果を示す。図の縦軸はARI の値、横軸はバンド
out of 100- と近傍数を変えた場合のinitial trials is shown inARI
Figs.
1–5 for each parameter.
幅ℎ- の値を示している。図7 は線形に分離可能なデータセットであるため、ARI
1 となる場合が多いこ
The ARI6,resultsof each method are summarized in Table 3.がTable
3とが確認できる。また、図 8 から 11 は非線形境界を持つデータセットであるため、図 6, 7 と比較すると ARI
shows that several methods including the proposed method obtain adeが低くなっている個所が多いことが確認できる。また、図 9 と 10 は、Double circle 2 dataset に対して近quate cluster partition. The best ARI is shown by k-means clustering,
傍数を増加させた場合の結果である。図 10 の結果より、近傍数が大きすぎる場合には良好な分割結果が得ら
k-medoids clustering,and spectral clustering.
The highest
ARI value
れないことが確認できる。図11 の結果から提案手法は
Two moon datasetに対して良好なクラスタ分割を生
out of 100 initial trials is shown for k-means clustering and k-medoids
成することが難しいことが確認できる。

clustering. The value in bold in Table 3 is the highest ARI value foreach dataset. For spectral clustering, the highest ARI value is shown
under the number of neighbors in 3 to 15.
The ARI value is one by the proposed method JSKMdd results except
for the Two moon dataset. For the Polaris and Artificial datasets, the
ARI is 1 in many cases with changing t and hj . It is suggested that the
proposed method is robust with respect to these data. For two types ofDouble circle datasets, it is shown that ARI is 1 in some cases, althoughsevere parameter selection is required from Figs. 3 and 4. It is also
shown that the proposed method JSKMdd obtains better results thanspectral clustering from Table 3. For the Two moon dataset, the ARI is
higher than 0.5 from Fig. 5.
The proposed method JSKMdd, can not obtain better results thanspectral clustering. The proposed method JSKMdd obtains both linear and non-linear cluster boundaries. Although estimating the object
distribution by KDE and calculating the dissimilarity by JS-divergencerequire much calculation cost, this feature is essential to apply JSKMdd
to real-world datasets.
次に表 3 にそれぞれの人工データに対して、k-means、k-medoids、スペクトラルクラスタリング、提案手法を適用した場合に最も良好な値となった ARI の値を示している。太字で示された値はそれぞれのデータセットに対して、最も良好な結果を得たことを意味している。Polaris データセットは線形分離可能であるため、全ての手法で適切なクラスタ分割を得ていることが確認できる。Artificial データセットは、線形分離
可能に見えるが、k-means や k-medoids では扱いにくいクラスタの形状となっているため、ARI の値が小さく6なっている。一方で、カーネル法を用いているスペクトラルクラスタリングや提案手法では適切な分割結果を得ている。非線形なクラスタ境界を持つ Double circle や Two moon データセットは、k-means や k-medoids
で扱いにくいクラスタの構造であるため ARI の値が小さくなっている。Double circle に対しては SC と提案

7
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

spectral clustering from Table ??. For the Two moon dataset, the ARI
is higher than 0.5 from Fig. ??.
The proposed method JSKMdd, can not obtain better results thanspectral clustering. The proposed method JSKMdd obtains both linear and non-linear cluster boundaries. Although estimating the object
distribution by KDE and calculating the dissimilarity by JS-divergence
手法がどちらとも良好な分割を得ている。
Double2 ではスペクトラルクラスタリングの結果が悪く、
require much calculation
cost, circle
this featureis essential to apply JSKMdd
Two moon では提案手法の結果が悪くなっていることからが確認できる。
to real-world datasets.

Data
PolarisArtificial
Double circle
Double circle 2
Two moon

表 3: ARI の結果
KM
KMdd
SC

1.000
0.469
0.008
0.058
0.233

1.000
0.469
0.005
0.033
0.274

1.000
1.000
1.000
0.478
1.000

JSKMdd
1.000
1.000
1.000
1.000
0.510

図 6 から 11 および表 3 の結果より、提案手法は線形や非線形の構造を持つデータセットに対して良好なクラスタ分割を得ることができる手法であることが確認できる。また提案手法では 2 つのパラメータが必要となるが、複雑な構造を持つデータセットに対しては、近傍数の影響がより強いことが示唆される。
提案手法で用いる KDE による確率密度関数の推定および
6 JS-ダイバージェンスの計算は大きな計算コストを必要とする。そのため、実データを対象とする場合には、それぞれの計算効率の向上および最適なパラメータの自動推定が必要となることが考えられる。

5 おわりに
本研究では、JS-ダイバージェンスに基づく k-medoids (JSKMdd)を提案した。提案手法は k-medoids の拡張であり、KDE と JS-ダイバージェンスを用いるころで、線形のクラスタ構造を持つデータセットおよび非線形なクラスタ構造を持つデータセットの両者を適切に扱える手法である。数値実験により提案手法を従来手法と比較し、その有効性を示した。数値実験の結果より、提案手法は適切なパラメータを設定することで、従来手法を上回る性能を示すことが示唆された。
今後の課題として、ベンチマークデータを用いた提案手法の評価が挙げられる。また、KDE と JS-ダイバー
ジェンスにより求められる非類似度がどのような特徴を持つか、詳細に分析する必要がある。さらに、パラメータの自動推定やネットワークデータなどへの適用も重要な課題と考えられる。

【参考文献】[1] Han J., Pei J., and Kamber M., Data Mining: Concepts and Techniques, Morgan Kaufmann, 2011.
[2] Jain, A.K., Data clustering: 50 years beyond K-means. Pattern Recogn. Lett. Vol. 31, No. 8,
pp. 651-666, 2010.
[3] Miyamoto, S., Ichihashi, H., Honda, K., Algorithms for Fuzzy Clustering. Springer,
Heidelberg, 2008.
[4] 宮本定明, クラスター分析入門―ファジィクラスタリングの理論と応用, 森北出版, 1999.
[5] Newman M., Networks: An Introduction, Oxford University Press, New York, 2010.
[6] Ichihashi H., Honda K., and Tani N., Gaussian mixture PDF approximation and fuzzy c-meansclustering with entropy regularization, Proc. 4th Asian Fuzzy System Symp., pp. 217-221, 2000.
[7] D. Arthur, Vassilvitskii S., k-means++: the advantages of careful seeding, Proc. of the eighteenth
annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied
Mathematics Philadelphia, PA, USA. pp. 1027–1035, 2007.
[8] Krishnapuram R., Keller J.M., A possibilistic approach to clustering, IEEE Trans. on Fuzzy
Systems, Vol. 1, No. 2, pp. 98-110, 1993.

8
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

[9] Dave R.N., Krishnapuram R., Robust clustering methods: a unified view, IEEE Trans. on Fuzzy
Systems, Vol. 5, No. 2, pp. 270-293, 1997.
[10] Ester, M., Kriegel H. P., Sander J., and Xu, X., A density-based algorithm for discovering clusters
in large spatial databases with noise, Proc. of the Second International Conference on Knowledge
Discovery and Data Mining (KDD’96), pp. 226-231, 1996.
[11] Campello R. J. G. B., Moulavi D., and Sander J., Density-based clustering based on hierarchicaldensity estimates, Proc. of Pacific-Asia Conference on Knowledge Discovery and Data Mining(PAKDD 2013), LNCS7819, Springer, Berlin, Heidelberg, pp. 160-172, 2013.
[12] Fuglede, B., Topsoe, F., Jensen-Shannon divergence and Hilbert space embedding, Proc.
International Symposium on Information Theory (ISIT2004), 2004.
[13] Epanechnikov V. A., Non-parametric estimation of a multivariate probability density, Theory ofProbability and its Application, Vol. 14, pp. 153-158, 1969.
[14] Kaufman L. and Rousseeuw P. J., Finding Groups in Data: An Introduction to Cluster Analysis,
Wiley, New York, 1990.
[15] Luxburg U. von, A tutorial on spectral clustering, Statistics and Computing, Vol. 17, No. 4,
pp. 395-416, 2007.
[16] Kondor R. I. and Lafferty J. D., Diffusion kernels on graphs and other discrete input spaces,
Proc. of ICML, pp. 315–322, 2002.
[17] Nakano S., Hamasuna Y., Endo Y., A study on controlled node sized network clustering for
unweighted network data, Joint 10th International Conference on Soft Computing andIntelligent Systems and 19th International Symposium on Advanced Intelligent Systems (SCIS& ISIS 2018), pp. 826–831, 2018.
[18] Kullback, S., and Leibler, R. A., On information and sufficiency, Annals of Mathematical
Statistics, Vol. 22, pp. 79-86, 1951.
[19] Hubert L., and Arabie P., Comparing Partitions, Journal of Classification, Vol. 2, No. 1,
pp. 193–218, 1985.

〈発
題

名

k-medoids Clustering based on Kernel
Density Estimation and Jensen-Shannon
Divergence

表

資

料〉

掲載誌・学会名等
The 16th International
Conference on Modeling
Decisions for Artificial
Intelligence (MDAI 2019),
Springer, LNCS 11676,
pp. 272-282, 2019

発表年月

2019 年 9 月

9公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度