WEKO3
アイテム
文字列の集合上の確率分布における中央文字列および中心文字列に対する整数計画問題
https://ipsj.ixsq.nii.ac.jp/records/164480
https://ipsj.ixsq.nii.ac.jp/records/1644802c47ab27-ae44-4c22-8da3-44b3f0b186b6
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-MPS16108007.pdf (416.6 kB)
|
Copyright (c) 2016 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2016-06-27 | |||||||||
| タイトル | ||||||||||
| タイトル | 文字列の集合上の確率分布における中央文字列および中心文字列に対する整数計画問題 | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 京都大学化学研究所 | ||||||||||
| 著者所属 | ||||||||||
| 理化学研究所生命システム研究センター | ||||||||||
| 著者名 |
林田, 守広
× 林田, 守広
× 小谷野, 仁
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 数や数スベクトルからなるデータセットに対して，平均はデータの中心を把握するための最も基本的な尺度である．しかし，文字列からなるデータセットに対しては平均が定義されないため，データの中心の尺度として，中央文字列や中心文字列がしばしば用いられる．しかし，数データに対する平均を計算することと異なり，文字列データに対する中央文字列や中心文字列を求めることは簡単ではなく，中心文字列については厳密解を求めることが保証されているアルゴリズムは知られていない．本研究において，我々は，まず，文字列データに対する中央文字列と中心文字列の定義を，所与のアルファベットから作られる全ての文字列の集合上の確率分布に対する定義に一般化する．これは，数データの平均が数や数ベクトルの集合上の確率分布の期待値に一般化されることに対応している．我々は，次に，整数線形計画法を用いて，文字列の集合上の確率分布に対する中央文字列と中心文字列の厳密解を求める方法を開発する．これらの方法は，文字列の集合がレーベンシュタイン距離によって距離空間をなしている場合には，レーベンシュタイン距離が三角不等式を満たすことを利用して，より高速なものに改良される．最後に，数値実験を行い，提案した方法の実際の応用における有効性を検討する． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN10505667 | |||||||||
| 書誌情報 |
研究報告数理モデル化と問題解決（MPS） 巻 2016-MPS-108, 号 7, p. 1-6, 発行日 2016-06-27 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8833 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
