平成１４年度第１回KSMAP

日時：５月２０日（月）　１５：００ 〜 １７：００ 

場所：京都大学工学部8号館3階 共同5号室

       会場への案内  

  「割当て問題に対するオークションアルゴリズム」
    西澤 秀隆 （大阪大学大学院大基礎工学研究科システム人間系専攻） 講演要旨

  「ウェーブレット解析手法を用いた建築内部空間画像とその知覚イメージの相関分析」
    宮高 泰匡 （京都大学大学院工学研究科建築学専攻） 講演要旨

  「データの論理的解析におけるルール集合の解析について」
    辻 弘貴 （京都大学大学院情報学研究科数理工学専攻） 講演要旨

  「平滑化法と正則化法を用いたSOCCPの解法」
    林 俊介 （京都大学大学院情報学研究科数理工学専攻） 講演要旨

マッチング問題や割当て問題はグラフ理論，最適化理論における代表的な問題であり， 割当て問題には様々なアルゴリズムが提案されている． 本研究では，1979年にBertsekasの開発したオークションアルゴリズムにつ いて考察し，多次元割当て問題に適用できるような拡張を提案する． また, これらのオークションアルゴリズムを, ２次元割当て問題と多次元割当て問題の一例である３次元割当て問題に適用した 計算機実験の結果についても報告する.

人が空間を体験する際には、五感機能の一つである視覚による認知が重要だと 考えられる。本研究では「人が空間を認知する際には一体どんな特徴に注目し、 どのように知覚しているのか？」をテーマとして、建築内部空間が観察者に与え る印象と画像から得られる大まかな物理的特性の相関分析を行った。

まず建築内部空間のサンプル画像に対して形容詞対を用いてアンケートを取り 、空間について一般的な印象量の測定を行った。次にウェーブレット解析により 空間の画像特徴の抽出・定量化を行った。さらに、決定木アルゴリズムを用いて 画像特徴と印象量の対応関係を表すルールセットを生成し、最後にルールセット の分析をすることによって相関関係の吟味と考察を行った。

近年, 大量のデータから意味のある知識を抽出する研究が盛んである. 本報告では, データ集合からルール形式の知識を発見することを試みる. データ集合は複数個の属性を持つデータベクトルからなり, 各データベクトルはそれぞれ正または負の決定クラスに属する. ルールは条件部と結論部からなり, 「条件部をみたすデータは結論部の決定クラスに属する」ことを主張する. ルールは, 支持度と信頼度という評価指数によって評価される. 支持度はデータ集合内で条件部を満たしているデータの割合であり, 信頼度は条件部を満たすデータの中で結論部をも満たすデータの割合である.

本報告では, 強い分類能力を持つルール集合を生成する. ルール集合の分類能力は, ルールを節点に持つ決定木を構成し, それを分類器とすることにより, 未知のデータに対するクラスの誤分類の 割合に基づいて測定する. いくつかのデータ集合に対する計算実験により, 提案手法と既存のルール集合生成アルゴリズムとの性能を比較し, 提案手法の有効性を確かめた.

二次錐相補性問題(SOCCP)は非線形相補性問題(NCP)や 二次錐計画問題(SOCP)を含む幅広いクラスの問題である． 最近，福島，Luo，TsengらはSOCCPに対する平滑化関数の ヤコビ行列を陽に計算し，そのヤコビ行列が正則であるための条件を導いた． 本発表では，まずはSOCCPを等価な最小化問題に再定式化して解く 手法の紹介を行う．次に，その等価な最小化問題に対して平滑化法と正則化法を 組み合わせた手法を提案する． さらに，SOCCPに含まれる関数が単調性を持つときに， このアルゴリズムが大域的収束することを示す． また，そのアルゴリズムの有用性を確かめるために行った 幾つかの数値実験の結果についても報告する．