遅延評価導入による局所改善クラスタリング法の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 2009-09-03
• タイトル: 遅延評価導入による局所改善クラスタリング法の高速化
• タイトル / 言語: en
• タイトル: Speed-up of Local Improvement Clustering Method by Incorporating Lazy Evaluation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 静岡県立大学
• 著者所属: 静岡県立大学
• 著者所属: 静岡県立大学
• 著者所属: 静岡県立大学
• 著者所属: 静岡県立大学
• 著者所属: 静岡県立大学
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者名: 斉藤, 和巳; 武藤, 伸明; 池田, 哲夫; 入月, 卓也; 永田, 大; 伊藤, かの子
• 著者名(英): Kazumi, Saito; Nobuaki, Mutoh; Tetsuo, Ikeda; Takuya, Iriduki; Dai, Nagata; Kanoko, Ito
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 有限ピボット集合に基づくオブジェクトのクラスタリング問題における代表的な解法として，分割改善法，貪欲改善法，および，局所改善法が挙げられる．局所改善法を用いれば，他の 2 手法と比較して，一般に望ましい品質の解を安定して求められるが，その計算量は大幅に増大する傾向がある．本論文では，このクラスタリング問題がサブモジュラ性と呼ばれる数理構造を持つことを示すとともに，この構造を利用した遅延評価と呼ばれる手法の導入により，局所改善クラスタリングを高速化する新たなアルゴリズムを提案する．3 種の実データを用いた評価実験では，反復改善法や貪欲改善法に匹敵する処理時間で，提案法により安定して優れた解が求まることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We address the problem of clustering objects based on a finite set of candidate pivots. For this problem, the divided improvement method, the greedy improvement method and the local improvement method are representative. Compared with the other two methods, the local improvement method is expected to stably produce better results, but it surely requires a large amount of computational load. In this paper, after showing that this clustering problem has a submodular property, we newly propose an efficient local improvement method by incorporating a technique called lazy evaluation on the submodular problem. In our experiments using three real data sets, we show that the proposed method can stably produce desirable results with computational efficiency comparable to those of the divided improvement method and the greedy improve method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 研究報告数理モデル化と問題解決（MPS）; 巻 2009-MPS-75, 号 25, p. 1-8, 発行日 2009-09-03
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会