別解出力をサポートした高速 k-means の C++ 実装を公開
二年ほど前，k-means をさらに速くする - ny23の日記 で書いた三角不等式を利用した高速 k-means の C++ 実装を公開した．以下の三つの論文を組み合わせた実装になっている．二年前の実装と比べると別解が出力できるようになったのが大きな違い．
- G. Hamerly. Making k-means even faster. (SDM 2010)
- D. Arthur and S. Vassilvitskii. k-means++: the advantages of careful seeding. (SODA 2007)
- [New] Y. Cui et al. Non-redundant multi-view clustering via orthogonalization. (ICDM, 2007)
前者二つを実装したのが二年前，別解出力をサポートしたのも一年以上前になる．別解は，クラスタリングした後，各点を所属クラスタのクラスタ中心に射影して，直交成分のみを次のクラスタリングの入力とすることで得られる．その他の特徴として，高次元で疎な入力に対してデータ構造を最適化してあるので（次元圧縮しなくても）大抵の入力は受けつけるようになっている．
今まで公開を躊躇っていたのは以下のような理由だった．
- 個々のアルゴリズムの特許を確認するのが億劫 (参考: オープンソースとアルゴリズムの特許 - ny23の日記)．
- 自分の研究で使って論文を書いてからにしよう．
- いまさら k-means って誰得なのか．
何故二年間も放置して今更公開するかというと，
- 年度末の某全国大会でソフトウェアの開発・公開*1に関して話をすることになった．
- 指導している学生が高速な実装を必要としていた（コードの完成度を上げる必要があった）．
- 誰得かは自分で判断しなくて良い．少なくとも学生得．
という理由．ソフトウェアの公開について話をするのに自分が躊躇していても仕方ないし，ハッタリとして公開ソフトウェアの数を増やしておくのも良いと思って，公開することにした．
公開にあたって必要だった作業をまとめると，
- 名前を決める．
- 入出力のフォーマット（インタフェース）を整理．
- コマンドラインオプションを整備．
- ビルドツールへの対応．
- コードの整理（valgrind でメモリリークを撲滅，clang -Weverything の警告をなるべく消す）
- バージョン管理システムへの登録．
- ホームページの作成．
で大体一日ぐらい．
名前については略称をベースにした名前を幾つか考えて，検索して被ってなさそうなものにした．その他の作業については，インタフェースの表裏を意識する: GNU getopt & autotools - ny23の日記で整備した線形分類器のリポジトリ（ホームページも）をひな形としてコピーして編集*2して済ませた．だいぶ負荷が下がってきた感じだ．
-
余談ながら，今回話をすることになった某全国大会には，ここ数年，個人的な事情があったり別件の会議が重なったりで参加しておらず，疎遠になっていた．今年も地方開催で日程中に東京で別件の用事があることから参加しないつもりでいたので，このような形で参加することになるとは予想外だった．
今回は本大会も懇親会も招待扱いになるそうで，可能なら参加したいのだけど日帰り参加（というか移動時間＞滞在時間ぐらいのとんぼ返りスケジュール）になりそうだ（現在の状態だと地方開催が続く限り参加は自粛）．楽しくないのでせめて駅近の担々麺でも食べて帰ろうかと考えているところ．
