K-means クラスタリングの一致性について

$$
\newcommand{\R}{\mathbb{R}}
\newcommand{\asarrow}{\overset{a.s.}{\to}}
\newcommand{\Pn}{\mathbb{P}_{n}}
\renewcommand{\d}{,\mathrm{d}}
$$

はじめに

総研大 統計科学コース Advent Calendar 2025 5日目の記事です．
こんにちは．総研大 統計科学コースのとりです．$K$-means クラスタリングの一致性に関する記事を書きました．

$K$-means クラスタリングはよく知られたクラスタリング手法です．データセット $\mathcal{X}_{n}=\{x_{1},\dots,x_{n}\}\subset\mathbb{R}^{d}$ が与えられたときに，これらのデータを使って，以下で与えられる損失関数 $L_{n}$ を最小化することによって， $k$ 個の代表点 $A=\{a_{1},\dots,a_{k}\}$ を推定します．

L_{n}(A)=\sum\limits_{i=1}^{n}\min_{a\in A}\|x_{i}-a\|^{2}

ここで，$\|\,\cdot\,\|$ は Euclid ノルムで $\|x\|^{2}=x^{\top}x$ です．$L_{n}$ を最小にする $A_{n}$ が求まると，$A_{n}$ の各点を代表点とする $k$ 個のクラスタ

C_{j}=\left\{x_{i}\in\mathcal{X}_{n}\,\middle|\, a_{j}\in\arg\min_{a\in A_{n}}\|x_{i}-a\|\right\}

が形成されます．

この記事では，推定された代表点の集合 $A_{n}$ の漸近的な性質を紹介します．

データセット $\mathcal{X}_{n}$ がある確率分布 $P$ からの実現値である場合に，$A_{n}$ が $n\to\infty$ の極限で（ある意味での）真の $A^{*}$ に収束することを示すことが目標です．証明の基本方針は Pollard (1981) と Terada (2014) に基づきます．

準備

はじめに，以降で用いる記法を準備します．

• $(\Omega,\mathcal{F},P)$ は完備確率空間とします．完備性は推定量の可測性を保証するために使います．
• $X_{1},\dots,X_{n}\overset{i.i.d.}{\sim}P$ に対し，その経験分布を $\mathbb{P}_{n}$ で表します．点 $x\in\mathbb{R}^{d}$ におけるDirac 測度を $\delta_{x}$ とすると，$\mathbb{P}_{n}=n^{-1}\sum_{i=1}^{n}\delta_{X_{i}}$ です．
• 可測関数 $f:\mathbb{R}^{d}\to\mathbb{R}$ の $P$ に関する期待値を $P[f],Pf,P[f(x)]$ と表します．経験分布 $\mathbb{P}_{n}$ に関する期待値も同様に $\mathbb{P}_{n}[f],\mathbb{P}_{n}f,\mathbb{P}_{n}[f(x)]$ などと表します．
• 確率1での収束を $\overset{a.s.}{\to}$ で表します．
• 有限集合 $A$ の要素数を $\#{A}$ で表します．
• $\mathbb{R}^{d}$ 上の有限集合 $A$ に対して，可測関数 $\phi_{A}:\mathbb{R}^{d}\to[0,\infty)$ を$\phi_A(x):=\min_{a\in A}\|x-a\|^{2}$ で定めます．
• $M>0$ に対し，$B(M):=\{x\in\mathbb{R}^{d}\mid \|x\|\leq M\}$ とします．
• $\mathscr{A}$ を $\mathbb{R}^{d}$ 上のコンパクト集合全体として，$\mathscr{A}_{k}:=\{A\subset\mathbb{R}^{d}\mid \#{A}\leq k\}$,$\mathscr{A}(M):=\{A\subset B(M)\mid A\in\mathscr{A}\},\mathscr{A}_{k}(M):=\{A\subset B(M)\mid \#{A}\leq k\}$ とします．
• $m_{k}(P):=\inf\left\{P\phi_{A}\,\middle|\, A\in\mathscr{A}_{k} \right\}$ と定めます．$m_{k}(\mathbb{P}_{n})$ も同様に定めます．
• $\mathscr{A}_{k}^{*}:=\{A\in \mathscr{A}_{k}\mid P\phi_{A}=m_{k}(P)\},\mathscr{A}_{k}^{*}(M):=\{A\in \mathscr{A}_{k}(M)\mid P\phi_{A}=m_{k}(P)\}$ とします．

代表点の集合の収束について議論したいため，集合間の距離を導入する必要があります．
$A,B\subset \mathbb{R}^{d}$ に対し，Hausdorff 距離を

d_{H}(A,B):=\max\left\{\sup_{a\in A}\inf_{b\in B}\|a-b\|,\sup_{b\in B}\inf_{a\in A}\|a-b\|\right\}

で定めます．Hausdorff 距離に関して以下が成り立ちます．

• $(\mathscr{A}_{k},d_{H})$ は完備可分距離空間
• $(\mathscr{A}_{k}(M),d_{H})$ はコンパクト距離空間

一部の証明は付録に載せましたが，詳しい内容は例えば塩谷 (2024) を参照してください．

主定理

目標は以下の定理を示すことです．

定理
以下を仮定する．

• $k>1$ の場合，$j=1,\dots,k-1$ に対して，$m_{j}(P)>m_{k}(P)$
• $P[\|x\|^{2}]<\infty$

このとき，$\mathscr{A}_{k}^{*}\neq\emptyset$ で，$A_{n}\in\arg\min_{A\in\mathscr{A}_{k}}\mathbb{P}_{n}\phi_{A}$ を満たす可測写像 $A_{n}$ が存在すれば，$\inf_{A\in\mathscr{A}_{k}^{*}}d_{H}(A_{n},A)\to0$ と $m_{k}(\mathbb{P}_{n})\to m_{k}(P)$ が確率1で成立する．

定理の主張は次の通りです．
データ $X_{1},\dots,X_{n}\overset{i.i.d.}{\sim}P$ による経験損失

\mathbb{P}_{n}\phi_{A}=\frac{1}{n}\sum\limits_{i=1}^{n}\min_{a\in A}\|X_{i}-a\|^{2}

を最小化するような代表点の集合 $A_{n}$ は，真の損失 $P\phi_{A}$ の下限 $m_{k}(P)$ を達成する集合 $A^{\star}\in\mathscr{A}_{k}^{*}$ のいずれかに $n\to\infty$ の極限で収束します．
また，そのときの損失の値 $m_{k}(\mathbb{P}_{n})$ も $m_{k}(P)$ に収束します．

証明

$A_{n}\in\arg\inf_{A\in\mathscr{A}_{k}}\mathbb{P}_{n}\phi_{A}$ を満たす写像 $A_{n}$ が可測であるための十分条件はいくつか知られていますが，その一つは $(\Omega,\mathcal{F},P)$ が完備確率空間であること，$(\mathscr{A}_{k},d_{H})$ が完備可分距離空間であることです．例えば Bogachev (2007) Theorem 6.9.13 を参照してください．

$\inf_{A\in\mathscr{A}_{k}^{*}}d_{H}(A_{n},A)\to0$ については，Van der Vaart (1998) Theorem 5.14 （と Problem 5.23）から従う以下の定理の適用を考えます．

定理 A
コンパクト距離空間 $(\Theta,d)$ の各点で定義された可測関数 $\phi_{\theta}:\mathbb{R}^{d}\to\R$ は以下を満たすと仮定する．

1. 各点 $x\in\mathbb{R}^{d}$ で，$\theta\to\phi_\theta(x)$ は連続
2. ある $\delta>0$ が存在して，任意の半径 $\delta$ 以下の開球 $U\subset\Theta$ に対し，$\inf_{\theta\in U}\phi_{\theta}$ は可測で，$P\inf_{\theta\in U}m_{\theta}>-\infty$
3. $\Theta_{0}:=\{\theta_{0}\in\Theta\mid P\phi_{\theta_0}=\inf_{\theta\in\Theta}P\phi_{\theta}\}\neq\emptyset$

このとき，$\theta_{n}\in\arg\inf_{\theta\in\Theta}\mathbb{P}_{n}\phi_{\theta}$ を満たす任意の可測写像に対し，$\inf_{\theta\in\Theta_{0}}d(\theta_{n},\theta)\to0$ が確率1で成立．

ここでは，$\Theta=\mathscr{A}_{k},d=d_{H},\Theta_{0}=\mathscr{A}_{k}^{*}$ です．2つ目の条件は $\phi_{A}$ の非負性と $(\mathscr{A}_{k},d_{H})$ の可分性から直ちに従いますが，残りの条件は自明ではありません．そもそも，$(\mathscr{A}_{k},d_{H})$ はコンパクトではありません．

以下の方針に基づいて，コンパクト距離空間上の議論に持ち込みます．

1. $M>0$ に対して，$\phi:\mathscr{A}(M)\to[0,\infty),A\mapsto \phi_{A}$ の連続性を示す．

2. $M>0$ に対して，$\Phi:\mathscr{A}(M)\to[0,\infty),A\mapsto P\phi_{A}$ の連続性を示す．

   ここまで示すと，$(\mathscr{A}_{k}(M),d_{H})$ のコンパクト性と，$\Phi$ の連続性から，$\mathscr{A}_{k}^{*}(M)\neq\emptyset$ がわかります． 次からのステップで，$\mathscr{A}_{k}^{*}(M)\neq\emptyset$ を使って$\mathscr{A}_{k}^{*}\neq\emptyset$ を示しますが，少し技巧的です．

3. 十分大きく $M>0$ をとると，$A\cap B(M)=\emptyset$ を満たす（つまり原点から離れた代表点しかもたない） $A\in\mathscr{A}_{k}$ に対して，$P\phi_{A}>P\phi_{A'}$ となるような $A'\in\mathscr{A}_{k}(M)$ が存在することを示します．

4. さらに大きく $M>0$ をとると，$A\not\subset B(5M)$ を満たす（つまり原点から離れた代表点を1つでももつ）$A\in\mathscr{A}_{k}$ に対して，$P\phi_{A}>P\phi_{A'}$ となるような $A'\in\mathscr{A}_{k}(5M)$ が存在することを示します．

5. ステップ4の $M>0$ に対して，$m_{k}(P)=\min_{A\in B(5M)}P\phi_{A}$ を示します．

   $\mathbb{P}_{n}$ にも似たような手続きを行います．

6. 十分大きく $M>0$ をとると，十分大きいすべての $n$ に対して，$A_{n}\cap B(M)\neq\emptyset$ が確率1で成立することを示します．

7. さらに大きく $M>0$ をとると，十分大きいすべての $n$ に対して，$A_{n}\not\subset B(5M)$ が確率1で成立することを示します．

以上より，十分大きい $n$ 以降を考えることで，$(\Theta,d)$ としてコンパクト距離空間 $(\mathscr{A}_{k}^{*}(5M),d_{H})$ が取れて，定理 A が適用できるようになりました．

$m_{k}(\mathbb{P}_{n})\to m_{k}(P)$ は補題8とステップ 5,7 から従います．

ステップ 1~2

命題3
$M>0$ とする．各点 $x\in\R^{d}$ で $\phi:\mathscr{A}(M)\to[0,\infty),A\mapsto \min_{a\in A}\|x-a\|^{2}$ は連続．
また，$P[\|x\|^{2}]<\infty$ を仮定すると，$\Phi:\mathscr{A}(M)\to[0,\infty),A\mapsto P\left[\min_{a\in A}\|x-a\|^{2}\right]$ も連続．

証明

$\phi$ の連続性：

任意の $\varepsilon>0$ に対し，ある $\delta>0$ が存在し，$d_{H}(A,B)<\delta$ を満たすすべての $A,B\in\mathscr{A}(M)$ に対して，$|\phi(A)-\phi(B)|<\varepsilon$ となることを示す．

ある $a_{0}\in A$ が存在し，$\min_{a\in A}\|x-a\|^{2}=\|x-a_{0}\|^{2}$ となる．ここで，$d_{H}(A,B)<\delta$ とすると，ある $b_{0}\in B$ が存在して，$\|a_{0}-b_{0}\|<\delta$ が成り立つ．

\begin{align*}
\phi(B)
&=\|x-b_{0}\|^{2}\\
&=\|(x-a_{0})+(a_{0}-b_{0})\|^{2}\\
&=\|x-a_{0}\|^{2}+2\langle x-a_{0},a_{0}-b_{0} \rangle+\|a_{0}-b_{0}\|^{2}\\
&\leq\phi(A)+2\|x-a_0\|\|a_{0}-b_{0}\|+\|a_{0}-b_{0}\|^{2}\\
&<\phi(A)+2\delta(\|x\|+M)+\delta^{2}
\end{align*}

より，$\phi(B)-\phi(A)<2\delta(\|x\|+M)+\delta^{2}$ である．$A$ と $B$ の役割を入れ替えることで，$|\phi(A)-\phi(B)|<2\delta(\|x\|+M)+\delta^{2}$ となる．よって，任意の $\varepsilon>0$ に対して， $2\delta(\|x\|+M)+\delta^{2}<\varepsilon$ を満たすように $\delta$ を十分小さくとることで，$d_{H}(A,B)<\delta$ を満たすすべての $A,B\in\mathscr{A}(M)$ に対して，$|\phi(A)-\phi(B)|<\varepsilon$ が成り立つ．

$\Phi$ の連続性：

$\phi$ の連続性から，$d_{H}(A,B)<\delta$ を満たすすべての $A,B\in\mathscr{A}(M)$ に対して，

\begin{align*}
|\Phi(A)-\Phi(B)|
&=\left| P\left[\min_{a\in A}\|x-a\|^{2}-\min_{b\in B}\|x-b\|^{2}\right] \right|\\
&< 2\delta P\left[\|x\|\right]+2\delta{M}+\delta^{2}
\end{align*}

が成り立つので $\Phi$ の連続性が従う（証明終わり）．

ステップ 3~5

補題4
$P[\|x\|^{2}]<\infty$ を仮定する．ある $M>0$ が存在して，$\#{A'}\leq k,A'\cap B(M)=\emptyset$ を満たす任意の $A'\subset\R^{d}$ に対し，$P\left[\min_{a\in A'}\|x-a\|^{2}\right]>\min_{A\in\mathscr{A}_{k}(M)}P\left[\min_{a\in A}\|x-a\|^{2}\right]$
が成立する．

証明

背理法で示す．任意の $M>0$ に対して，$\#{A'}\leq k,A'\cap B(M)=\emptyset$ を満たす $A'\subset\R^{d}$ が存在し，

P\left[\min_{a\in A'}\|x-a\|^{2}\right]\leq\min_{A\in\mathscr{A}_{k}(M)}P\left[\min_{a\in A}\|x-a\|^{2}\right]

が成立することを仮定する．$P1_{B(r)}>0$ となるような $r>0$ をとる．$M$ を $M>r$ かつ $P[\|x\|^{2}]< (M-r)^{2}P1_{B(r)}$ を満たすように十分大きくとる．仮定より，

\begin{align*}
P[\|x\|^{2}]
&\geq\min_{A\in\mathscr{A}_{k}(M)}P\left[\min_{a\in A}\|x-a\|^{2}\right]\\
&\geq P\left[\min_{a\in A'}\|x-a\|^{2}\right]\\
&\geq P\left[\min_{a\in A'}\|x-a\|^{2}1_{B(r)}\right]\\
&\geq (M-r)^{2}P1_{B(r)}
\end{align*}

が成立し $P[\|x\|^{2}]< (M-r)^{2}P1_{B(r)}$ に矛盾する（証明終わり）．

補題5
以下を仮定する．

• $P[\|x\|^{2}]<\infty$
• $j=1,\dots,k-1$ に対し，$m_{j}(P)>m_{k}(P)$

このとき，ある $M>0$ が存在して，$\#{A'}\leq k,A'\not\subset B(5M)$ を満たす任意の $A'\subset\R$ に対し，
$P\left[\min_{a\in A'}\|x-a\|^{2}\right]>\min_{A\in\mathscr{A}_{k}(5M)}P\left[\min_{a\in A}\|x-a\|^{2}\right]$
が成立する．

証明

背理法で示す．任意の $M>0$ に対して，$\#{A'}\leq k,A'\not\subset B(5M)$ を満たす $A'\subset\R^{d}$ が存在し，

P\left[\min_{a\in A'}\|x-a\|^{2}\right]\leq\min_{A\in\mathscr{A}_{k}(5M)}P\left[\min_{a\in A}\|x-a\|^{2}\right]

が成立することを仮定する．そのような $A'$ 全体を $\mathscr{A}_{k}'$ とすると，

m_{k}(P)=\inf_{A'\in\mathscr{A}_{k}'}P\left[\min_{a\in A'}\|x-a\|^{2}\right]

である．

補題4を満たすような $M>0$ をとる．$\varepsilon+m_{k}(P)<m_{k-1}(P)$ を満たす $\varepsilon>0$ に対して，$4P[\|x\|^{2}1_{\|x\|\geq 2M}]<\varepsilon$ となるように，$M$ をさらに大きくとる．補題4より，$a_{1}\in A'\cap B(M)$ が存在するので，

\begin{align*}
P[\|x-a_{1}\|^{2}1_{\{\|x\|\geq2M\}}]
&\leq P[(\|x\|+\|a_{1}\|)^{2}1_{\{\|x\|\geq2M\}}]\\
&\leq P[(2\|x\|)^{2}1_{\{\|x\|\geq2M\}}]\\
&\leq 4P[\|x\|^{2}1_{\|x\|\geq2M}]
\end{align*}

が成り立つ．また，任意の $\|x\|<2M$ を満たす $x\in\R^{d}$ に対して，

\min_{a\in A'\cap B(5M)}\|x-a\|^{2}\leq\|x-a_{1}\|^{2}< (3M)^{2}\leq\min_{a\in A'\backslash B(5M)}\|x-a\|^{2}

に注意すると，

\begin{align*}
m_{k-1}(P)
&\leq P\left[\min_{a\in A'\cap B(5M)}\|x-a\|^{2}\right]\\
&=P\left[\min_{a\in A'\cap B(5M)}\|x-a\|^{2}1_{\|x\|\geq 2M}\right]+P\left[\min_{a\in A'\cap B(5M)}\|x-a\|^{2}1_{\|x\|<2M}\right]\\
&\leq P\left[\|x-a_{1}\|^{2}1_{\|x\|\geq 2M}\right]+P\left[\min_{a\in A'}\|x-a\|^{2}\right]\\
&\leq 4P[\|x\|^{2}1_{\|x\|\geq2M}]+P\left[\min_{a\in A'}\|x-a\|^{2}\right]\\
&<\varepsilon+P\left[\min_{a\in A'}\|x-a\|^{2}\right]
\end{align*}

が成り立つ．$\mathscr{A}_{k}'$ に関して下限をとると，$m_{k-1}(P)\leq \varepsilon+m_{k}(P)$ となり，$\varepsilon+m_{k}(P)<m_{k-1}(P)$ に矛盾する（証明終わり）．

命題6
以下を仮定する．

• $P[\|x\|^{2}]<\infty$
• $j=1,\dots,k-1$ に対し，$m_{j}(P)>m_{k}(P)$

このとき，ある が存在して，$\min_{A\in\mathscr{A}_{k}(5M)}P\left[\min_{a\in A}\|x-a\|^{2}\right]=m_{k}(P).$

証明

補題5を満たすような $M>0$ をとる．

\min_{A\in\mathscr{A}_{k}(5M)}P\left[\min_{a\in A}\|x-a\|^{2}\right]=m_{k}(P)

を示せばよい．

\min_{A\in\mathscr{A}_{k}(5M)}P\left[\min_{a\in A}\|x-a\|^{2}\right]\leq m_{k}(P)

のみ示せば十分．補題5より，任意の $\varepsilon>0$ に対して，ある $A'\in\mathscr{A}_{k}$ が存在して，

m_{k}(P)>P\left[\min_{a\in A'}\|x-a\|^{2}\right]-\varepsilon\geq\min_{A\in\mathscr{A}_{k}(5M)}P\left[\min_{a\in A}\|x-a\|^{2}\right]-\varepsilon

が成り立つので，$m_{k}(P)\geq\min_{A\in\mathscr{A}_{k}(5M)}P\left[\min_{a\in A}\|x-a\|^{2}\right]$ である（証明終わり）．

ステップ 6~7

命題7
$P[\|x\|^{2}]<\infty$ を仮定する．ある $M>0$ が存在して，
$P\left(\bigcup_{n=1}^{\infty}\bigcap_{m=n}^{\infty}\left\{\omega\in\Omega\,\middle|\,A_{m}(\omega)\cap B(M)\neq\emptyset\right\}\right)=1.$

証明

N:=\bigcap_{n=1}^{\infty}\bigcup_{m=n}^{\infty}\left\{\omega\in\Omega\,\middle|\, A_{m}(\omega)\cap B(M)=\emptyset\right\}

が零集合になることを示せばよい．

$P1_{B(r)}>0$ となるような $r>0$ をとって，$M>r$ を以下を満たすようにとる．

(M-r)^{2}P1_{B(r)}>P\left[\|x\|^{2}\right]

$\omega\in N$ を固定して議論する．

$n_{1}<n_{2}<\cdots$ を満たす部分列 $\{n_{m}\}\subset\mathbb{N}$ で，$A_{n_{m}}\cap B(M)=\emptyset$ を満たすものがとれる．このとき，任意の $A_{0}\in\mathscr{A}_{k}$ に対して，$\mathbb{P}_{n_{m}}[\min_{a\in A_{n_{m}}}\|x-a\|^{2}]\leq\mathbb{P}_{n_{m}}[\min_{a\in A_{0}}\|x-a\|^{2}]$ が成立している．特に，$A_{0}=\{0\}$ とすると，$\mathbb{P}_{n_{m}}\left[\min_{a\in A_{0}}\|x-a\|^{2}\right]=\mathbb{P}_{n_{m}}\left[\|x\|^{2}\right]$である．また，

\begin{align*}
\mathbb{P}_{n_{m}}\left[\min_{a\in A_{n_{m}}}\|x-a\|^{2}\right]
&\geq\mathbb{P}_{n_{m}}\left[\min_{a\in A_{n_{m}}}\|x-a\|^{2}1_{B(r)}\right]\\
&\geq \mathbb{P}_{n_{m}}\left[(M-r)^{2}1_{B(r)}\right]\\
&=(M-r)^{2}\mathbb{P}_{n_{m}}1_{B(r)}
\end{align*}

が成り立つので，$(M-r)^{2}\mathbb{P}_{n_{m}}1_{B(r)}\leq\mathbb{P}_{n_{m}}[\|x\|^{2}]$ である．
$\mathbb{P}_{n_{m}}1_{B(r)}\to P1_{B(r)},\mathbb{P}_{n_{m}}[\|x\|^{2}]\to P[\|x\|^{2}]$ を仮定して，両辺の上極限をとると，

(M-r)^{2}P1_{B(r)}
=\limsup_{m\to\infty}(M-r)^{2}\mathbb{P}_{n_{m}}1_{B(r)}
\leq\limsup_{m\to\infty}\mathbb{P}_{n_{m}}\left[\|x\|^{2}\right]
=P[\|x\|^{2}]

が得られるが，これは $(M-r)^{2}P1_{B(r)}>P\left[\|x\|^{2}\right]$ に矛盾する．仮定はいずれも確率1で満たされるので，$N$ は零集合（証明終わり）．

十分大きい $M>0$ に対して，

\min_{A\in\mathscr{A}_{k-1}(5M)}\mathbb{P}_{n}\left[\min_{a\in A}\|x-a\|^{2}\right]\asarrow m_{k-1}(P)

が命題6と以下の補題から従います．

補題8
$P[\|x\|^{2}]<\infty$ を仮定する．$M>0,k\in\mathbb{N}$ に対し，$\mathcal{F}:=\left\{f_{A}:\R^{d}\to[0,\infty),x\mapsto\min_{a\in A}\|x-a\|^{2}\,\middle|\,A\in \mathscr{A}_{k}(M)\right\}$ は $P$-Glivenko-Cantelli.

証明

関数クラス $\mathcal{F}$ が $P$-Glivenko-Cantelli になるための十分条件はいくつかあるが，ここでは，Van der Vaart (1998) Example 19.8 の十分条件

• $\mathscr{A}_{k}(M)$ はコンパクト距離空間
• $\mathscr{A}_{k}(M)\to[0,\infty),A\mapsto f_{A}(x)$ が各点 $x\in\R^{d}$ で連続
• 可積分関数 $F:\R^{d}\to[0,\infty)$ で，任意の $x\in\R^{d},A\in\mathscr{A}_{k}(M)$ に対し，$f_{A}(x)\leq F(x)$ を満たすもの（Envelop 関数）が存在

を用いる．最初の2条件は塩谷（2024）定理 2.10（Blaschke の定理）と命題3から従う．最後の条件を確かめる．$F(x)=(\|x\|+M)^{2}$ とする．

f_{A}(x)=\min_{a\in A}\|x-a\|^{2}\leq\min_{a\in A}(\|x\|+\|a\|)^{2}\leq\min_{a\in A}(\|x\|+M)^{2}=F(x)

である．$PF<\infty$ を示せば証明が完了する．

PF=P[\|x\|^{2}]+2MP[\|x\|]+M^{2}\leq P[\|x\|^{2}]+2MP[\|x\|^{2}]^{1/2}+M^{2}<\infty

よって，$\mathcal{F}$ は $P$-Glivenko-Cantelli（証明終わり）.

命題9
以下を仮定する．

• $P[\|x\|^{2}]<\infty$
• $j=1,\dots,k-1$ に対し，$m_{j}(P)>m_{k}(P)$

このとき，ある $M>0$ が存在して，
$P\left(\bigcup_{n=1}^{\infty}\bigcap_{m=n}^{\infty}\left\{\omega\in\Omega\,\middle|\,A_{m}(\omega)\subset B(5M)\right\}\right)=1.$

証明
$k=1$ の場合は，命題7から直ちに従う．$k>1$ の場合を示す．

N:=\bigcap_{n=1}^{\infty}\bigcup_{m=n}^{\infty}\left\{\omega\in\Omega\,\middle|\, A_{m}(\omega)\not\subset B(5M)\right\}

が零集合になることを示せばよい．

命題7の $M>0$ をとる．$\varepsilon+m_{k}(P)<m_{k-1}(P)$ を満たすようなある $\varepsilon>0$ に対し

4P\left[\|x\|^{2}1_{\{\|x\|\geq2M\}}\right]<\varepsilon

を満たすように $M$ をさらに大きく取り直す．

$\omega\in N$ を固定して議論する．

$a_{1}\in A_{n}\cap B(M)$ の存在を仮定すると，

\begin{align*}
\Pn[\|x-a_{1}\|^{2}1_{\{\|x\|\geq2M\}}]
&\leq\Pn[(\|x\|+\|a_{1}\|)^{2}1_{\{\|x\|\geq2M\}}]
\leq\Pn[4\|x\|^{2}1_{\{\|x\|\geq2M\}}]
\end{align*}

が成り立つ．

$n_{1}<n_{2}<\cdots$ を満たす部分列 $\{n_{m}\}\subset\mathbb{N}$ で，$A_{n_{m}}\not\subset B(5M)$ を満たすものがとれる．任意の $\|x\|<2M$ を満たす $x\in\R^{d}$ に対して，

\min_{a\in A_{n_{m}}\cap B(5M)}\|x-a\|^{2}\leq\|x-a_{1}\|^{2}< (3M)^{2}\leq\min_{a\in A_{n_{m}}\backslash B(5M)}\|x-a\|^{2}

に注意すると，

\begin{align*}
&\min_{A\in\mathscr{A}_{k-1}(5M)}\Pn\left[\min_{a\in A_{n_{m}}}\|x-a\|^{2}\right]\\
&\leq \mathbb{P}_{n_{m}}\left[\min_{a\in A_{n_{m}}\cap B(5M)}\|x-a\|^{2}\right]\\
&=\mathbb{P}_{n_{m}}\left[\min_{a\in A_{n_{m}}\cap B(5M)}\|x-a\|^{2}1_{\|x\|\geq 2M}\right]
+\mathbb{P}_{n_{m}}\left[\min_{a\in A_{n_{m}}\cap B(5M)}\|x-a\|^{2}1_{\|x\|<2M}\right]\\
&\leq\mathbb{P}_{n_{m}}\left[\|x-a_{1}\|^{2}1_{\|x\|\geq 2M}\right]
+\mathbb{P}_{n_{m}}\left[\min_{a\in A_{n_{m}}}\|x-a\|^{2}\right]\\
&\leq 4\mathbb{P}_{n_{m}}[\|x\|^{2}1_{\|x\|\geq2M}]+\mathbb{P}_{n_{m}}\left[\min_{a\in A^{*}}\|x-a\|^{2}\right]
\end{align*}

が成り立つ．ただし，$A^{*}\in\mathscr{A}_{k}^{*}$ である．

\begin{align*}
\min_{A\in\mathscr{A}_{k-1}(5M)}\mathbb{P}_{n_{m}}\left[\min_{a\in A}\|x-a\|^{2}\right]\to m_{k-1}(P),\\
\mathbb{P}_{n_{m}}\left[\min_{a\in A^{*}}\|x-a\|^{2}\right]\to P\left[\min_{a\in A^{*}}\|x-a\|^{2}\right]
\end{align*}

を仮定して，両辺の上極限をとると，

m_{k-1}(P)\leq\varepsilon+m_{k}(P)

となるが，これは $\varepsilon+m_{k}(P)<m_{k-1}(P)$ に矛盾する．命題6を満たすようにさらに大きく $M>0$ をとりなおすことで，仮定はいずれも確率1で満たされるので，$N$ は零集合（証明終わり）．

参考文献

Bogachev, Vladimir I (2007). "Measure Theory". Springer.
Pollard, David (1981). "Strong consistency of $K$-means clustering". The Annals of Statistics, 9(1), 135-140.
塩谷隆 (2024). "測度距離空間の幾何学への招待". サイエンス社.
Terada, Yoshikazu (2014). "Strong consistency of reduced $K$-means clustering". Scandinavian Journal of Statistics, 41(4), 913-931.
Van der Vaart, Aad W (1998). "Asymptotic Statistics". Cambridge University Press.

付録

Hausdorff距離 に関するいくつかの結果を証明します．

命題10 Hausdorff 距離
$\mathscr{A}$ を $\R^{d}$ のコンパクト集合全体とすると，$(\mathscr{A},d_{H})$ は距離空間．

証明
$A,B\in\mathscr{A}$ に対し，

d_{H}(A,B)=\max\left\{\max_{a\in A}\min_{b\in B}\|a-b\|,\max_{b\in B}\min_{a\in A}\|a-b\|\right\}

である．

非負性と対称性は明らかなので，非退化性と三角不等式を示す．

非退化性：
$A,B\in\mathscr{A}$ に対し，$d_{H}(A,B)=0$ とする．$\max_{a\in A}\min_{b\in B}\|a-b\|=0$ より，任意の $a\in A$ に対し，ある $b\in B$ が存在して，$\|a-b\|=0\Rightarrow a=b$ となる．よって，$A\subset B$ である．$B\subset A$ も$\max_{b\in B}\min_{a\in A}\|a-b\|=0$ から従うので，$A=B$ が成り立つ．

三角不等式：
$A,B,C\in\mathscr{A}$ とする．

\begin{align*}
\max_{a\in A}\min_{b\in B}\|a-b\|
&\leq\max_{a\in A}\min_{c\in C}\left(\|a-c\|+\min_{b\in B}\|b-c\|\right)\\
&\leq\max_{a\in A}\min_{c\in C}\|a-c\|+\max_{c\in C}\min_{b\in B}\|b-c\|\\
&\leq d_{H}(A,C)+d_{H}(B,C)
\end{align*}

である．$\max_{b\in B}\min_{a\in A}|a-b|$ も同様に評価して，

\begin{align*}
d_{H}(A,B)
&\leq d_{H}(A,C)+d_{H}(B,C)
\end{align*}

が従う．（証明終わり）．

$B(M)$ はコンパクトなので，塩谷 (2024) 定理 2.10（Blaschke の定理）より，$(\mathscr{A}(M),d_{H})$ はコンパクト距離空間になります．$\mathscr{A}_{k}(M)$ が $\mathscr{A}(M)$ の閉部分集合になることが以下の命題の証明と同様にして示されるので，$(\mathscr{A}_{k}(M),d_{H})$ もまたコンパクト距離空間です．

命題11
$(\mathscr{A}_{k},d_{H})$ は完備可分距離空間

証明
完備性：
塩谷 (2024) 補題 2.9 より，$\mathbb{R}^{d}$ 上の閉集合全体は Hausdorff 距離に関して完備拡張距離空間になるので，$\mathscr{A}_{k}$ が閉部分集合になることを示せば十分．
$\{A_{n}\}\subset\mathscr{A}_{k}$ はある $A=\{a_{1},\dots,a_{l}\}\subset\mathbb{R}^{d}$ に収束するとする．$\#A\leq k$ を背理法で示す．$\#A\geq k+1$ を仮定する． 任意の $\varepsilon>0$ に対して，十分大きく $n$ をとると，
$d_{H}(A_{n},A)<\varepsilon$ である．このとき，任意の $a_{i}\in A$ はある $a'\in A_{n}$ を中心とした半径 $\varepsilon$ の開球に含まれる．特に $\#{A_{n}}\leq k$ より，少なくとも $A$ の2点を開球に含むような $a'\in A_{n}$ が存在するが，$\varepsilon/2<\min_{i\neq j}|a_{i}-a_{j}|$ となる $\varepsilon$ をとると，そのような $a'\in A_{n}$ の存在に矛盾が生じる．よって，$\#A\leq k$ である．

可分性：
可算集合

\mathscr{B}_{k}:=\{B\subset\mathbb{Q}^{d}\mid \#{B}\leq k\}\subset\mathscr{A}_{k}

が $\mathscr{A}_{k}$ で稠密なことを示す．任意の $A\in\mathscr{A}_{k}$ に収束する $\{B_{n}\}\subset\mathscr{B}_{k}$ の存在を示せばよい．$a\in A$ に対し，$q_{n}(a)\to a$ を満たす $\{q_{n}(a)\}\subset\mathbb{Q}^{d}$ が存在する．$B_{n}:=\{q_{n}(a)\mid a\in A\}$ とすると，任意の $\varepsilon>0$ に対し，十分大きく $n$ をとると，$\|q_{n}(a)-a\|<\varepsilon$ が任意の $a\in A$ で成り立つので，$d_{H}(A,B_{n})<\varepsilon$ となる．よって，$d_{H}(A,B_{n})\to0$ となり，$\mathscr{B}_{k}$ は $\mathscr{A}_{k}$ で稠密（証明終わり）．