カーネルK平均法でクラスター重心を見つけることは可能ですか？
仮定します ${x_1, \ldots, x_N}$ はデータポイントであり、見つける必要があります $K$ カーネルK平均法を使用したクラスター。
カーネルを $Ker$ （と混同しないでください $K$ クラスターの数）
しましょう $\phi$ このカーネルによって引き起こされる暗黙のマッピングである。
今なら $\phi$有限次元で、問題ありませんでした。ただし、$phi$ 無限次元であるために、そのようなものはRBFカーネルによって引き起こされました
さて、私がカーネルK平均法について読んだところはどこでも、カーネルK平均法を使用して実行できるとだけ言っています
$||\phi(x_i) - \phi(x_j)||^2 = Ker(x_i, x_i) + Ker(x_j, x_j) - 2Ker(x_i, x_j) \;\; \ldots(1)$
私はこれを理解しましたが、それは私の脳にとってそれほど単純ではなく、カーネルK平均法の明示的なアルゴリズムを誰も与えていないため、次の疑問が残ります。
K重心を初期化するのはどの空間ですか？元の空間、またはによって誘発された空間$\phi$？推測しているのですが、元の空間で初期化するのは、によって引き起こされた空間内のデータポイントを理解することすらできないからです。$\phi$ これらをランダムに初期化するとします $K$ 重心 $\mu_1, \ldots \mu_K$元のスペースでのみ。（間違っていると思ったら訂正してください）
初期化後、すべてのデータポイントをクラスターの1つに割り当てる必要があります。割り当てたいとしましょう$x_n$ クラスターに対しては、これは（1）を使用して簡単に実行できます。 $\mu_k$ = $\text{arg min}_j\; ||\phi(x_n) - \phi(\mu_j)||^2$
クラスターを割り当てた後、新しい重心を計算するにはどうすればよいですか？明らかに私はによって引き起こされた空間で平均をとることができません$\phi$ それは無限の次元なので、私は今何をしますか？
この問題の回避策は何ですか？どういうわけか、図心をまったく保存する必要がないのではないかと思います。しかし、私はこれをどのように達成するかを考えることができません。
カーネルk-meansクラスタリングでクラスター中心を見つけるを読んだ
しかし、コミュニティウィキの回答はどこを説明していません $(1)$ から来た。
回答
カーネルのk-meansは、カーネルによって誘導される特徴空間で動作する通常のk-meansと同等です。したがって、重心は、あなたが言及したように、無限次元である可能性がある特徴空間に住んでいます。カーネルトリックを使用して学習アルゴリズムを定式化する場合、特徴空間に直接触れる必要はありません。特徴空間でのすべての操作は、カーネル関数を使用して暗黙的に実行されます。したがって、カーネルk-meansの重心を直接扱うことはありません。代わりに、以下で説明するように、クラスターの割り当てを処理します。
特徴空間におけるK-means
ロイドのアルゴリズムは、k-means問題を（おおよそ）解くための標準的な方法です。これは、特徴空間で直接機能する一般化です。しましょう$X = \{x_1, \dots, x_n\}$ データポイントになり、 $\phi(\cdot)$ 入力空間から特徴空間に点をマッピングする関数である。
- 初期化 $K$ クラスター $C_1, \dots, C_K$、各クラスター $C_j$ を含むセットです $n_j$ ポイントであり、各ポイントは正確に1つのクラスターのメンバーです。
収束するまで繰り返します（クラスターメンバーシップに変更はありません）。
クラスターごとに $C_j$、図心（特徴空間内）は次のとおりです。
$$\mu_j = \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \tag{1}$$
各ポイントについて $x_i$、インデックスを見つける $a_i$ 重心が（特徴空間で）最も近いクラスターの。
$$a_i = \arg \min_j \ \|\phi(x_i) - \mu_j\|^2 \tag{2}$$
$$= \arg \min_j \ \langle \phi(x_i), \phi(x_i) \rangle + \langle \mu_j, \mu_j \rangle - 2 \langle \phi(x_i), \mu_j \rangle \tag{3}$$
$$= \arg \min_j \ \langle \mu_j, \mu_j \rangle - 2 \langle \phi(x_i), \mu_j \rangle \tag{4}$$
- クラスターを更新します。各ポイントは、最も近い重心を持つクラスターのメンバーになります。
$$C_j = \{x_i \mid a_i = j\}$$
注意： $\langle \cdot, \cdot \rangle$内積を示します。方程式$(3)$ノルムと内積の関係から得られます。第一期$\langle \phi(x_i), \phi(x_i) \rangle$ クラスターに依存しないので、クラスターを削除して方程式を与えることができます $(4)$。
カーネルトリックの使用
カーネル関数があるとしましょう $k(\cdot, \cdot)$特徴空間の内積を計算します。そう$k(x, x') = \langle \phi(x), \phi(x') \rangle$。上記のアルゴリズムの内積をカーネル関数の評価に置き換えることで、特徴空間で暗黙的に動作することができます。これはカーネルトリックと呼ばれます。
まず、方程式の重心の定義を代入して、手順2と3を組み合わせます。 $(1)$ 方程式の最も近い重心検索に $(4)$：
$$\arg \min_j \ \left \langle \frac{1}{n_j} \sum_{x \in C_j} \phi(x), \frac{1}{n_j} \sum_{x' \in C_j} \phi(x') \right \rangle - 2 \left \langle \phi(x_i), \frac{1}{n_j} \sum_{x \in C_j} \phi(x) \right \rangle \tag{5}$$
内積は双線形であるため、これを次のように書き直すことができます。
$$\arg \min_j \ \frac{1}{n_j^2} \sum_{x \in C_j} \sum_{x' \in C_j} \langle \phi(x), \phi(x') \rangle - \frac{2}{n_j} \sum_{x \in C_j} \langle \phi(x_i), \phi(x) \rangle \tag{6}$$
内積をカーネル関数評価に置き換えます。
$$\arg \min_j \ \frac{1}{n_j^2} \sum_{x \in C_j} \sum_{x' \in C_j} k(x, x') - \frac{2}{n_j} \sum_{x \in C_j} k(x_i, x) \tag{7}$$
各ポイントについて $x_i$、これは、特徴空間の重心を明示的に計算せずに、最も近い重心を持つクラスターを見つける方法を示しています。上記のアルゴリズムのステップ2と3の代わりに使用できます。