« 読了：Teugels (1990) 多変量ベルヌーイ分布をどうやって表現するか | メイン | 読了: Gower (1971) 質と量が混じっているときの類似性係数(人呼んでGower距離) »
2019年12月26日 (木)
データの中に量的変数もあればカテゴリカル変数もある、そいつらをひっくるめて多変量解析にかけたい(たとえば個体をクラスタリングしたい)、というような状況をmixed dataの分析と呼ぶことがある。データ解析手法の話題としては比較的マイナーかもしれないけれど、日々の仕事のなかでは全然珍しくない、それどころか、むしろそういうのが通常営業である。
mixed dataのクラスタリング手法としてぱっと思いつくのは、(1)縮約してクラスタリングする(MCAからk-meansとか、Rのclusterdパッケージとか)、(2)距離行列を出してクラスタリングする(Gower距離からk-medoidsとか)、(3)四の五の言わずに潜在クラスモデルを組む、の3つだが、私はMplus信者なので、他の手法も試すとしても、とにかく(3)は絶対にやる。やらいでか。
しかし、こんど仕事の都合で出てきそうな奴は結構大きなデータなので、うっかりMplusなんかに食わせちゃったら、生きている間に終わらない...
Ahmad, A., Khan, S. (2019) Survey of state-of-the-art mixed data clustering algorithms. IEEE Access, 7.
というわけで、mixed dataのクラスタリングについてのサーヴェイ論文。本番では悩んでいる時間がとれなさそうなので、事前の予習のつもりで目を通した。
先行研究レビュー
5つの領域に分けて整理する。
A. 分割型クラスタリング。
k-means法のように、データ点$d_i$について(1)それが属するクラスタの中心$C_i$を定義し、(2)距離$\xi(d_i, C_i)$を定義し、(3)コスト関数$\sum_i^n \xi(d_i, C_i)$を反復で最小化する、というタイプの手法。データ点の数に対して線形だし、並列化可能である。
特徴の型が混合している場合の提案としては以下がある。
- K-prototypeクラスタリング(Huang, 1998,1997): クラスタ中心は、数値特徴については平均、カテゴリカル特徴については最頻値とする。この手法はあまりうまくいかない。最頻値だけでは情報の損失が大きいし、ハミング距離では類似性がうまく表現できないから。[RのclustMixTypeパッケージはこの手法だと思う]
- Ahmed & Dey (2007): まずデータからカテゴリカル特徴の値の類似度を求めておく。また数値特徴にもウェイトを振っておく。[RのDisimForMixedパッケージがこの手法だと思う]
- Huang, Ng, Rong, & Li (2005): W-K-prototypeクラスタリング。特徴に、クラスタ内距離の合計に反比例したウェイトを振る。[Rのwskmパッケージってこれかな? ちがうかも]
- Zao, Dai, & Tang (2007): カテゴリカル特徴のクラスタ中心を定義するのに頻度を使う。
- Modha & Spangler (2003): 個々の特徴について2点間のdistortionを求める。数値特徴は平方ユークリッド距離、カテゴリカル特徴はダミー行列のコサイン距離、で、それらをどうにかしてくっつける。
- Chen & He (2016): Ahmed & Dey (2007)の拡張で、data streamをクラスタリングする。micro-clustersという概念を使う。[よくわからんのでメモ省略]
- Ran, Liu, Wang, & Pan (2016): Ahmed & Dey (2007)の拡張。正規カーネルを使う。
- Ji, Bai, Zhou, Ma, & Wang (2013): Ahmed & Dey (2007)の拡張で、特徴に重みを振って反復のたびに更新する。
- Sangam & Om (2018): K-prototypeクラスタリングなんだけど、距離をもっとうまいこと定義しようという提案。
- Roy & Sharma (2010): Lu, Lu, Fotouhi, Deng, & Brownのfast genetic K-means clustering (FGKA)というのを、Ahmed & Dey (2007) が定義した距離でやりますという提案。
- Choiodi (1990): コスト関数としてユークリッド距離なりハミング距離なりのクラスタ内分散を使う。
- Kacem, Ncir, & Essoussi (2015): K-prototypeクラスタリングをMap-Reduceで並列化する。
- Jan, Kim, Kim, Jung (2018): 空間データのK-prototypeクラスタリングの高速化。
いったん数値特徴データに変換してからk-meansとかやればいいじゃん、というアプローチもある。
- Barcelo-Rico & Jose-Luis (2012): カテゴリカル特徴を極座標系とか球面座標系とかで表現してk-means。[へぇー]
- Wang, Chi, Zhou, & Wong (2015): context-based coupled representationでk-means. [なんのことだかさっぱり]
- Wei, Chow, & Chan (2015): 相互情報量を使って数値に変換してからk-means。[詳細はわからんがありそうな手法だ]
その他の提案として、
- Cheng & Leu (2009): K-prototypeクラスタリングを制約ベースクラスタリングに拡張。この2点は同じクラスタにしろ、というような制約をかける。
- Fuzzyクラスタリングをカテゴリカル特徴に拡張しようという提案もあって...[メモ省略]
さて、partitional clusteringに共通の難題がふたつある。
その1. クラスタ中心の初期値をどうするか...[メモ省略]
その2. クラスタ数をどう決めるか...[メモ省略]
B. 階層クラスタリング。
個体間の距離行列がありリンケージ基準があります、という手法。トップダウンかボトムアップかは問わない。たいていの場合、時間は$O(n^3)$、メモリは$O(n^2)$必要。
特徴の型が混合している場合の提案としては...
- Philip & Ottaway (1983): Gower距離行列で凝集型階層クラスタリング。[これは、まあ、思いつくわね]
- Chiu, Fang, Chen, Wang, & Jeris (2001): クラスタをくっつけたときの対数尤度の減少をクラスタ間の類似性としてBIRCHクラスタリング。[あ...これ、SPSS StatisticsのTwoStep Clusterの元論文といわれているやつだ...]
- Li & Biswas (2002): Goodall類似性というのを使って凝集型階層クラスタリング。
- Hsu, Chen, Su (2007): 「概念階層」に基づいて距離を求めて凝集型階層クラスタリング。[←説明がよく理解できないのだが、領域知識に基づいて距離を定義するらしい。ちょっと面白そうだなあ]
- Hsu & Huang (2008): これも概念階層による距離を使うが、適応共鳴理論(ART)ネットワークでクラスタリングする。[←くわばらくわばら]
- Shih, Jheng, & Lai (2010): いったん数値データに変換してから凝集的階層クラスタリング。
- Lim, Jun, Kim, McLeod (2012): 数値型とカテゴリ型でそれぞれクラスタリングして、あとでくっつける。
- Chae & Yang (2006): Gower距離で凝集型階層クラスタリング。[Philip & Ottaway(1983)とどう違うんだろう？]
C. モデル・ベースのクラスタリング。
データ点がなんらかのモデルに一致しているとみる手法。
- AUTOCLASS (Cheeseman & Shutz, 1996): 有限混合分布。ベイジアンで、特徴の事前分布を仮定する。
- Everitte(1988): これも有限混合分布。
- Lawrence & Krzanowski (1996): これも有限混合モデルなんだけど、等質なconditional gaussianモデルにして計算を速くする。
- Moustaki & Papageorgiou (2005): カテゴリカル特徴をダミー変数に変換して潜在クラス混合モデル。
- Browne & McNicholas (2012): 混合モデル, EMアルゴリズム [←著者らはmixtureパッケージの中の人のようだ]
- Andreopoulos, An, & Wang(2006): bi-level クラスタリング。カテゴリカルデータのクラスタに基づいて数値データをクラスタリングする。
- Hunt & Jorgensen (2003): 混合モデル。[説明が書いてあるんだけど、どこがユニークなのかわからんかった...]
- ClustMD (McParland, & Gormley, 2016) 混合モデル。モンテカルロEMとかGibbsサンプリング。カテゴリカル変数が多いと時間がかかるので、改良が進んでいる。[←RのclustMDパッケージであろう]
- Saadaoui, et al.(2015) 数値変数で張った空間にカテゴリカル変数を写し、主成分分析でどうにかする[よくわからんかった]
- コピュラを使ったクラスタリング... [いくつか紹介されているが、ぜんぜんわからんのでメモ省略]
- Foss, et al. (2016) KAMILAアルゴリズム [これは別途調べるつもりなのでメモ省略]
- Fuzzy クラスタリング ... [いくつか紹介されているがメモ省略]
D. ニューラル・ネットワーク・ベースのクラスタリング。
大きく分けて自己組織化マップ(SOM)と適応共鳴理論(ART)がある。どちらもカテゴリカル変数には工夫が必要。
- Hsu (2006): カテゴリカル変数を概念階層に基づき数値化... [さっぱりわからん。以下, Hsuさんたちのを含めてSOMを使うアプローチがたくさん紹介されているが、よくわからんし疲れてきたのでメモ省略。しかし、SOMが質量混合データに使えるのは魅力的だなあ。Rには SOMbrero というパッケージがあるようだが、これはデータとして$n \times p$数値行列のほかに$p \times q$分割表や$n \times n$非類似性行列が食えるというものらしい、大データだと難しそうだなあ]
- ARTアプローチでは... [2つくらい挙がっている。メモ省略]
E. その他。
- スペクトラル・クラスタリングだと ... [メモ省略]
- 部分空間クラスタリングだと ... [メモ省略]
- 密度ベースクラスタリング(DBSCANとか)だと、Du, Ding, Xue (2017), Ding, Du, Su, Zu, Xue (2017), Liu, Yang, He (83), Milenova & Campos (84), Du et al. (2018). [Rの実装は見当たらない... ガックリ]
- Conceptual clustering ... [メモ省略]
- well-separated partitionの定義を非階層クラスタリングに応用して... [MIXISOというらしい。メモ省略]
- affinity propagation clustering ... [メモ省略]
- [...その他、実にいろいろな話題が出てくる。正直疲れ果てたので一気に省略する]
サーヴェイした結果の分析
結局、一番実用的なのは分割型クラスタリングだろう。単純だしスケールするから。[おいおい、身も蓋もねえな]
混合データのクラスタリング研究の多くは、教師ラベルつきのデータを教師ラベル抜きでクラスタリングして、結果を教師ラベルと比べている。[その比べ方がしょぼいよね、という批判が最後のほうに出てきた]
同じデータでアルゴリズムを比較している研究は見当たらない。みんなそれぞれ好きなデータを使っている。[それではいかんよねという話が最後のほうに出てきた]
ソフトウェアとアプリケーション
Rでは...
- clustmixtypeパッケージ: K-prototypesクラスタリング
- ClustMDパッケージ: 混合モデル
- Gower類似性行列をつくって[cluster::daisy()とかかな]、階層的クラスタリングなりk-medoids法なりに持ち込むという手がある。
- ClustOfVarパッケージも混合データを扱える [←でもこれ変数のクラスタリングでしょ？]
- CluMixパッケージ
- KAMILAパッケージ
- MixClusterパッケージ: コピュラを使うアプローチ
MATLABでは...[略]。
主要な応用分野としては...[めんどくさいのでスキップ]
影響を与える領域と今後の課題
これから影響を与えるであろう領域としては...[略]
今後の課題は:
- 分割クラスタリング: クラスタの中心をどう定義するか、中心からの距離をどう定義するかが課題。クラスタ初期化・クラスタ数決定の方法も課題。
- 階層クラスタリング: 類似度をどう定義するか。
- モデル・ベース・クラスタリング: パラメータ数が少ない適切なモデルの開発が求められる。
- NNベース・クラスタリング: SOMはプアなトポロジーになっちゃってデータにあわないことが多いしARTは計算が大変。他のアプローチもあるんやないか。適応下位空間SOMとか。[←なにそれ]
オープン・クエスチョンとしては... [箇条書きで13個くらい書いてあったけど省略。従来のconstrained clusteringに限らず、もっと領域知識をうまく使う方法を考えたほうがいいんじゃないの、なんて書いてあって、そりゃそうだなあと思った]
... やれやれ、疲れた。
とりあえず概観できたのでありがたいけど、手元に抱えている問題に対してはなんの解決にもなってない... さあどうしよう...
論文：データ解析(2018-) - 読了：Ahmad & Khan (2019) 量質混在データのクラスタリング手法レビュー