質的データを扱うクラスタリングにおける最適化アプローチの研究

处理定性数据的聚类优化方法研究

• 批准号: 13J08653
• 负责人: 鮏川 矩義
• 金额: $ 0.77万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2013
• 资助国家: 日本
• 起止时间: 2013-04-01 至 2015-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13J08653/
• 关键词: クラスタリング; 組合せ最適化; アルゴリズム; 計算複雑性; NP-困難

本研究では，「質的データを扱うクラスタリングにおける最適化アプローチの研究」と題し，クリーク分割問題を効率よく解くための定式化とアルゴリズムについて研究を行なうことを目的とした．クリーク分割問題は質的データのクラスタリングに対する有効なモデルであるが，応用場面から生じる中規模程度の入力例ですら求解が困難であり，実際，理論的にも難しいこと（NP-困難性）が知られている．本年度は，理論と実験の両面からクリーク分割問題の難しさを解析・理解し，応用場面に役立つアルゴリズムの構築を目指し，以下の成果を得た．クリーク分割問題の難しさは，その数理最適化問題としての定式化の大規模性にある．この定式化は自然かつ素直であるが，特に大量の制約式を扱うという弱点を持つ．本年度は，制約式の冗長性に着目し，それらを検出するための理論的な枠組みについて研究した．具体的には，制約式が冗長になるための十分条件を導出した．これらの結果と昨年度までに得られた結果をソルバーに組み込むことで，実用的な時間で解ける入力例の規模が大幅に拡大されることを確認した．一方，応用場面から生じる入力例の難しさを知るために，計算量の解析を行なった．ここでは，近年コミュニティ検出の分野で注目され，クリーク分割問題の特殊ケースとなる問題がNP-困難であることを証明した．また，上述のクリーク分割問題の定式化を頂点彩色問題に応用し，疎グラフに強力な定式化を得たり，冗長な制約式に関する解析をクリーク分割問題と似た構造を有する線形順序付け問題に応用したりと，得られた成果を他の組合せ問題に拡張することにも精力的に取り組んだ．

This study is aimed at the research on the optimization of the quality of the data and the efficiency of the data segmentation problem. The partition problem is difficult to solve in terms of the quality of the problem, and in fact, the theoretical problem is difficult to solve in terms of the NP-difficulty. This year, we analyzed and understood the difficulties of segmentation problem in theory and practice, and pointed out the construction of segmentation problem in application field. The following achievements were obtained. The partition problem is difficult to solve, and the mathematical optimization problem is formulated and large-scale. This kind of formalization is natural and straightforward, especially a large number of constraints. This year, the length of the constraint is focused on, and the theory of the constraint is studied. The concrete, restrictive expression is lengthy and the very conditions are derived. The results of this study were confirmed by the results of the study. A party, the use of the scene from generation to generation into the force of the case is difficult to know, calculate the amount of analysis. In recent years, the problem of NP-difficulty has been proved. The problem of segmentation and the problem of vertex color are solved by using the method of strong formalization and lengthy constraint. The problem of segmentation and the problem of linear sequence are solved by using the method of strong formalization and long constraint.

项目成果

推移性制約の冗長性について

关于传递性约束中的冗余

• 发表时间: 2014
• 作者: 鮏川 矩義;水野眞治
• 通讯作者: 水野眞治

Fractional programming formulation for the vertex coloring problem

顶点着色问题的分数阶规划公式

• DOI: 10.1016/j.ipl.2014.06.010
• 发表时间: 2014
• 期刊: Information Processing Letters
• 影响因子: 0.5
• 作者: Tomomi Matsui;Noriyoshi Sukegawa;and Atsushi Miyauchi
• 通讯作者: and Atsushi Miyauchi

Redundant constraints in the standard formulation for the clique partitioning problem

派系划分问题标准公式中的冗余约束

• DOI: 10.1007/s11590-014-0754-6
• 发表时间: 2015
• 期刊: Optimization Letters
• 影响因子: 1.6
• 作者: Atsushi Miyauchi;Yuni Iwamasa;Takuro Fukunaga;and Naonori Kakimura;Atsushi Miyauchi and Yasushi Kawase;Atsushi Miyauchi and Noriyoshi Sukegawa
• 通讯作者: Atsushi Miyauchi and Noriyoshi Sukegawa

Lagrangian relaxation and pegging test for the clique partitioning problem

• DOI: 10.1007/s11634-013-0135-5
• 发表时间: 2013-05
• 期刊: Advances in Data Analysis and Classification
• 影响因子: 1.6
• 作者: Noriyoshi Sukegawa;Yoshitsugu Yamamoto;Liyuan Zhang