萌芽的閉包を枚挙する分枝限定法について

• Item type: SIG Technical Reports(1)
• 公開日: 2009-12-10
• タイトル: 萌芽的閉包を枚挙する分枝限定法について
• タイトル / 言語: en
• タイトル: A Branch-and-Bound Algorithm for Extracting Concice and Rare Concepts
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者名: 中島, 健志; 原口, 誠; 大久保, 好章
• 著者名(英): Takeshi, Nakajima; Makoto, Haraguchi; Yoshiaki, Okubo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，低頻度の形式概念抽出問題について議論する．顕在パターンマイニング・コントラストセットマイニング・クロスオーバ概念抽出等の研究に見られる通り，レア概念・低頻度パターンの重要性が認識されている一方で，概念の意味解釈の困難さの問題が同時に存在する．すなわち，外延の小さなレア概念は，一般に多くの属性から成る内包を伴うことから，その明確な解釈を与えることが容易ではない．こうした問題に対処すべく，本稿では，抽出すべきレア概念を 『少数の一般的な属性で特徴付けられる概念の解釈・理解は容易である』 との考えのもとに定め，それらを簡潔なレア形式概念として定式化する．さらに，分枝限定法に基づくレア形式概念抽出アルゴリズムを提案し，計算機実験により，容易に解釈可能なレア概念が抽出できることを確認する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we present an algorithm for finding concepts (closures) with smaller supports. As suggested by the study of emerging patterns, contrast sets or crossover concepts, we regard less frequent and rare concepts. However, we have several difficulties when we try to find rare concepts. In general, te lengths of rare concepts become longer, involving many attributes at various levels of generality. Consequently, it becomes harder to understand what the concepts mean. In order to solve the above problems, we make a restriction about formation processes of concepts, where the formation is a flow of adding attributes to the present concepts already formed. The present concepts work as conditions for several candidate attributes to be added to them. Given such a present concept, we prohibit adding attributes strongly correlated with the present concept. As a result, the detected concepts has lower supports and consist of only attributes directing at more specific concepts through the formation processes. We design an algorithm is designed as a top-N closure enumerator using branch-and-bound pruning rules so that it can reach concepts with lower supports by avoiding useless combination of correlated attributes in a huge space of concepts. We experimentally show the effectiveness of algorithm and the conceptual clarity of detected concepts because of their shorter length in spite of their lower supports.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12055912
• 書誌情報: 研究報告バイオ情報学（BIO）; 巻 2009-BIO-19, 号 14, p. 1-8, 発行日 2009-12-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会