![[PukiWiki]](image/../../images/logo_diavis.png "[PukiWiki]"){kind=logo}
DIAVIS-wiki
#contents ---- *クラスタリング [#e60dbb49] -クラスタリングは探索的(exploratory)なデータ解析手法であり，客観的にみて正しいものではない． -データの要約として利用すべき クラスタリングを行うためには，レコード間の相違度（dissimilarity）が数値で算出相違度）f(A,B)で表すテーブルがあるとする．自分自身との相違度を0に設定．さらに，相違度f(A,B)たちが三角不等式とよばれる次の式が成り立とき，相違度はデータレコード間の距離（metric）になるという． f(A,B) + f(B,C) >_ f(A,C) また，f(A,B)=f(B,A)であるとき対称，そうでないとき非対称な相違度／距離という． ***関連キーワード [#ce0556c2] -三角不等式（triangular inequality） -距離の種類 --ユークリッド距離（Euclidean distance） --編集距離(editing distance) --キーワード距離（keyword distance） *クラスタリングの分析方法 [#x3d04e54] -階層的手法(hierarchical) --分枝型(divisive) --凝集型(agglomerative) -分割最適化手法(partitioning-optimization) -凝集法（ツリークラスタリング） -Two-way 法（ブロッククラスタリング） **K-means 法 [#cb93d97f] -MacQueen，Anderberg，Forgyらにより提案された非階層型クラスタリング手法の1つ． -クラスタの平均を用い，与えられたクラスタ数K個に分類することから，MacQueenによりこう呼ばれた． -K-平均法（K-means），c-平均法（c-means）とも呼ばれる． -初期状態によって最終結果は大きく影響される． **一般的な場合のクラスタリング [#xffdbfb9] [[クラスタリングとは (クラスター分析とは):http://www.kamishima.net/jp/clustering/]]によれば， >>対象が属性ベクトルで記述されている場合，計算量が k-means法は O(N k) に対し，階層的手法は O(N2) (ユークリッド距離の場合．一般には O(N2 log N)）なので，k-means法を用いる方がよいでしょう． とのこと． *クラスタリングと可視化 [#dc5dafca] **階層的手法 [#l9a8a4cc] -最短距離法 (nearest neighbor method) または 単連結法 (single linkage method) -最長距離法 (furthest neighbor method) または 完全連結法 (complete linkage method) -群平均法 (group average method) -ウォード法 (Ward's method) **VIBE(Visualization by Example) [#i508d45d] -Olsenほか（1993）および，Korfhage(1997) -利用者が入力した主題概念に応じて結果的に文書がクラスタ化される -POI (point of interest) -利用者が，各POIの位置を画面上で指定． -各文書は，各POIによって位置が決定される．一つのPOIしか含まない場合はPOIと重なる． -http://www.crg.cs.nott.ac.uk/research/technologies/visualisation/vrvibe/ -"VR-VIBE: A Virtual Environment for Co-operative Information Retrieval", Steve Benford, Dave Snowdon, Chris Greenhalgh, Rob Ingram, Ian Knox and Chris Brown. To appear Eurographics'95, 30th August - 1st September, Maastricht, The Netherlands, pp 349-360. **SPIREプロジェクト [#o24668f7] -SPIRE(spatial paradigm for information retrieval and exploration) -1994年に開始 -同年，最初のソフトウェアGalaxies作成 -続いて，ThemeSpacesが発表される． +文書集合に対して，前処理を施し，各文書をベクトル化 +ベクトルを標準化．高次元空間中で文書をクラスタ化 +高次元空間におけるベクトルとクラスタの重心とを2次元平面上に射影 *NIRVE (The NIST information retrieval visualization engine) [#ea1ba057] -Cuginiほか 1997 -米国NISTで開発 -検索結果を，文書集合の3次元表現で視覚的に提示する機能を持つ -conceptを表現するkeywordを利用者が特定．文書集合をクラスタに分割． *参考文献および参考サイト [#kd39b348] -福田剛志，森本康彦，徳山豪，データサイエンスシリーズデータマイニング，共立出版，2001 -岸田 和明，文書クラスタリングの技法：文献レビュー Techniques of Document Clustering: A Review --[[http://wwwsoc.nii.ac.jp/mslis/pdf/LIS49033.pdf:http://wwwsoc.nii.ac.jp/mslis/pdf/LIS49033.pdf]] -http://mikilab.doshisha.ac.jp/dia/research/report/2007/0913/004/report20070913004.html -[[クラスタリングとは (クラスター分析とは):http://www.kamishima.net/jp/clustering/]] -[[東大の講義用資料(pdf)?:http://www.bi.s.u-tokyo.ac.jp/bs_pro/japanese/schedule/17/files/Morishita_2005_5_6.pdf]] -[Bradley 98] [[P.S.Bradley and U.M.Fayyad: Refining Initial Points for K-Means Clustering, in Proceedings of the 15th International Conference on Machine Learning, pp.91-99 (1998):http://research.microsoft.com/research/pubs/view.aspx?type=Technical%20Report&id=200]] -[Cutting 92] [[D.R.Cutting, D.R.Karger, J.O.Pedersen, and J.W.Tukey: Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections, in Proceedings of the 15th Annual ACM SIGIR Conference on Research and Development in Information Retrieval, pp.318-329 (1992):http://doi.acm.org/10.1145/133160.133214]]（アカウント登録などが必要） --CiteCeer上の同じ論文（こちらは閲覧可能）．http://citeseer.ist.psu.edu/cutting92scattergather.html -[Dubes 79] R.Dubes and A.K.Jain: Validity Studies in Clustering Methodologies, Pattern Recognition, Vol.11, pp.235-254 (1979) -[Everitt 93] B.S.Everitt: Cluster Analysis, Edward Arnold, third edition (1993) -[Guha 98] S.Guha, R.Rastogi, and K.Shim: CURE: An Efficient Clustering Algorithm for Large Databases, in Proc. of the ACM SIGMOD International Conference on Management of Data, pp.73-80 (1998) -http://www.kde.ics.tut.ac.jp/~sugiyama/wsrc/opencampus2006.html
