イジングマシンを用いたクラスタリング手法の研究
理学専攻・情報科学コース

1

はじめに1. 誤差パラメータ δ を設定, 反復カウンタ n を n = 0,パラメータ λ を初期値 λ0 = 0 とする.
2. イジングマシンを用いて次式で表された目的関数を最小化する．
H=− λnH=dij

1≤i<j≤Nxi,g xj,g + α

g=1N∑




i=1G
∑

H=

g=1i<j dij xi,g xj,gNg (Ng − 1)+αN
∑
i=1




g=1i=1xi,g − 1

λn+1 =(1))( N∑G∑2xi,g − 1g=1)(3)

xi,g − 1i=1G∑∑Ni<j dij x̂i,g x̂j,gN̂g (N̂g − 1)(4)∑
ここで，N̂g = i x̂i,g とする. x̂ が有効解でなければ，解なしで終了する．
4. |λn+1 − λn | ≤ δ の場合，x̂ を最終解として終了する．それ以外の場合，n + 1 < nmax の間は，n → n+1 としてステップ 2 に戻り，n+1 = nmaxのときは，解なしで終了する.
アルゴリズムが正常に終了した場合，λn+1 は最小コストを与えることが期待される．誤差パラメータ δ は10−6 ，最大反復回数 nmax は 10 とした．

3

結果

本節では単純コスト法と反復分数コスト法の実行結果を示す．目的関数を最小化するためのアルゴリズムとして，シミュレーテッド・アニーリング法 (SA) とシミュレーテッド分岐アルゴリズム (SB) [2] の 2 種類を用いる．ここでは，SB の結果のみを述べる．正方形
領域に一様に分布する点の集合と，同じ大きさの領域に不均一に分布する点の集合の 2 種類のデータセットに対して実行した．使用したデータセットは 200 点で構成され，これを 10 グループにクラスタリングした．
ハイパーパラメータ α の値は単純コスト法では一様分布と不均一分布でそれぞれ 6 と 5，反復分数コスト法

2xi,g − 1

xi,gg=1

g=1G
∑

(N∑

2

2.2 反復分数コスト法
前節の問題を解決するために，次式で表される別の目的関数を提案する．
∑G
∑

i=1



3. x̂ が有効解であれば，次の反復での λ を次式のように設定する．

ここで，dij は点 i と点 j 間の距離，N は点の数，Gはグループ数である．点 i がグループ g に所属するなら xi,g = 1，そうでなければ xi,g = 0 とする．したがって，(1) の右辺第 1 項は，同じグループに所属する点の 2 点間距離の総和となる．右辺第 2 項は，各点はちょうど 1 つのグループに所属するという制約を満たすための制約項である．この制約を満たす解を有効解と呼ぶことにする．α は正の定数で，制約の強さを表す．この目的関数では各グループに含まれる点のペアの組合せの数だけペア間の距離が加算されるため，各グループに含まれる点の数が均等になりやすい傾向がある．そのため，不均一に分布したデータセットに対して，うまくクラスタリングすることができないという問題がある．

G∑

dij xi,g xj,g + αN∑

ここで，x は二値変数を表す．また，得られた解を x̂ とする．

2.1 単純コスト法
イジングマシンを用いたクラスタリングの従来手法の目的関数は次式のように表される．
G
∑

G ∑N
∑
g=1 i<jモデル

∑

松本 奈紗

イジングマシンは式 (2) のような非 QUBO 形式を直接最小化することができない．そこで，QUBO 形式で記述された別の目的関数を反復的に最小化するハイブリッドアルゴリズムを採用した．この手法を反復分数コスト法と呼ぶことにする．反復分数コスト法は，配送計画問題を解くために提案されたハイブリッド・パラメトリック法を基盤としている [1]．ハイブリッド法
では，元の分数目的関数を最小化する代わりに，イジングマシンを用いて，離散最適化ステップで，対応するパラメトリック問題を反復的に解く．
反復分数コスト法のアルゴリズムを以下に示す．

近年，E コマース市場の成長による宅配便取扱数や輸送交通量の増加に伴い，運送業の人手不足や排気ガスによる環境汚染が社会問題となっている．この問題の解決策として，宅配の物流拠点から個人宅までの配送における配送計画問題を解き，配送を効率化することが挙げられる．配送計画問題についての研究を進めていく中で，複数の車両に荷物を割り当てたり，各車両の配送経路を求める際に荷物をグループ分けしたりするためのクラスタリングの精度が最終的な配送ルートに影響を及ぼし，重要であることがわかった．そこで本研究では，2 次元空間上の頂点を 2 点間距離をもとに分割するクラスタリング問題に着目し，クラスタリングの精度を向上させるために，イジングマシンを用いたクラスタリング手法を 2 種類提案する．ここでは 1 つ目の手法について述べる．イジングマシンとは，組合せ最適化問題を解くための専用計算機である．イジングマシンは，目的関数を定義するパラメータを入力とし，目的関数を最小化するような二値変数の組を解として返す．イジングマシンは組合せ最適化問題を高速に解くことが期待されている．クラスタリングは組合せ最適化問題として定式化できる．

22040655

(2)

g=1

∑N
ここで，Ng = i=1 xi,g はグループ g の点の数である．式 (2) の右辺第一項は各グループ内の点のペア間の平均距離の総和を表している．
1

では一様分布と不均一分布の両方で 5.5 とした．また，離散最適化の計算時間を制御するパラメータである時間ステップ数を変化させる．時間ステップごとに単純コスト法では 100 回，反復分数コスト法では 50 回のシミュレーションを行なった．
単純コスト法図 1 は単純コスト法のクラスタリング結果の中で最も良いものを示している. 同じ色の点は同じグループに属していることを表す．不均一分布では，見かけ上のクラスターが二つのグループに分割されていたりした．

(a) 一様分布

図 3: 反復分数コスト法のクラスタリング結果．

(b) 不均一分布式 (3) の有効解をいくつか得るために，離散最適化ステップ (ステップ 2) で 100 回の最適化サンプリングを行った．最終的な有効解率は，時間ステップ数が 1600以上の場合は 80–100%となった．最終解が得られるまでの，ステップ 2–4 の反復回数はほとんどの場合においては，3 回だった．
図 4 は反復分数コスト法による離散最適化にかかる時間を示したものである．反復分数コスト法での実行時間は，ワンショット実行時間の合計と定義する．実行時間は，反復回数，離散最適化ステップでの最適化サンプリング数，時間ステップ数に依存する．平均シルエット係数は，図 4 に対応する領域では，ハイパー
パラメータ α と時間ステップ数にほとんど依存しない．
一様分布では，平均シルエット係数は 0.392–0.394 となり，単純コスト法と同程度の値となった．一方で，不均一分布では，平均シルエット係数は 0.709–0.716 となり，単純コスト法よりも約 18 %高くなった．

図 1: 単純コスト法のクラスタリング結果．
図 2 は，クラスタリング結果が実行時間にどのように依存するかを示したものである．箱ひげ図は，有効解の平均シルエット係数の分布を示している．平均シ
ルエット係数はクラスタリング評価指標であり，高いほどクラスタリング結果が良いとされる．単純コスト法での実行時間は，1 つの離散最適化問題の解を得るために必要な時間であるワンショット実行時間と定義する．図 2 での実行時間は時間ステップ数ごとの有効解の平均値である．平均シルエット係数は，一様に分布したデータセットでは 0.35–0.39 程度またはそれ以下であるのに対し，不均一に分布したデータセットでは 0.45–0.6 程度またはそれ以上と高くなっている．この差は，データ分布の違いを反映している.

(a) 一様分布average silhouette coefficient

average silhouette coefficient

0.300.010

0.015
time (s)

0.020

0.025

time (s)(b) 不均一分布

2525202015151050105800

1200

1600

2000

2400

n_steps

2800

3200

3600

4000

0400

800

1200

1600

2000

2400

n_steps

2800

3200

3600

4000

図 4: 実行時間の箱ひげ図. 横軸は時間ステップ数.

(d) SB, uneven

0.35

0.250.005(a) 一様分布(b) 不均一分布(b) SB, uniform

0.40

0.8
0.7

4

0.6

0.4
0.005

0.010

0.015
time (s)

0.020

まとめ

本研究では，2 次元空間上の頂点を 2 点間距離をもとに分割するクラスタリング問題に着目し，クラスタリングの精度を向上させるために，イジングマシンを用いた反復分数コスト法と呼ばれるクラスタリング手法を提案した．この手法は，従来手法である単純コスト法と比べて，不均一に分布したデータセットに対し，クラスタリング精度が高いことが確認できた．

0.50.025

図 2: 平均シルエット係数の箱ひげ図．横軸はワンショッ
ト実行時間．

3.2(b) 不均一分布

time (s)3.1(a) 一様分布

反復分数コスト法

参考文献

図 3 は反復分数コスト法のクラスタリング結果の中で最も良いものを示している. 図 1 と比較して，不均一分布においてうまく分類されていることがわかる．

[1] A. Ajagekar, T. Humble and F. You, Computers& Chemical Engineering 132, 106630 (2020).
[2] H. Goto, K. Endo, M. Suzuki, Y. Sakai, T. Kanao,Y. Hamakawa, R. Hidaka, M. Yamasaki and
K. Tatsumura, Science Advances 7, eabe7953(2021).
2