研究者データベース

有村 博紀(アリムラ ヒロキ)
情報科学研究院 情報理工学部門 知識ソフトウェア科学分野
教授

基本情報

所属

  • 情報科学研究院 情報理工学部門 知識ソフトウェア科学分野

職名

  • 教授

学位

  • 博士(理学)(九州大学)

ホームページURL

J-Global ID

プロフィール

  • 1990年九州大学大学院修士課程修了.同年,九州工業大学助手.その後,九州工業大学講師および助教授,九州大学大学院助教授および准教授などを経て,2004年から北海道大学情報科学研究科教授,現在に至る.博士(理学).1999~2002年 JST PREST「情報と知」(領域総括:安西祐一郎)研究員.2007~2011年度 文科省グローバルCOEプログラム「知の創出を支える次世代IT基盤拠点」拠点リーダー.2013〜2014年度 北海道大学知識メディアラボラトリー長. 2016〜2017年度 北海道大学ビッグデータ・サイバーセキュリティ グローバルステーション (GSB) 拠点長. 2015年度および2018年〜現在 北海道大学共同プロジェクト拠点「知識メディアラボラトリー」リーダー.

    現在,人工知能と, データマイニング,機械学習, 情報検索,アルゴリズム等の研究に従事.電子情報通信学会,情報処理学会,日本データベース学会, 人工知能学会会員, ACM.

研究キーワード

  • グラフ   ランダムフォレスト   決定木   データマイニング   列挙アルゴリズム   非貪欲な学習アルゴリズム   機械学習における説明可能性   時空間データ   接尾辞配列   人工知能   情報科学   帰納論理プログラミング   知識発見   Artificial Intelligence   Computer Science   接尾辞木   ビッグデータ   inductive logic programming   データ構造   アルゴリズム   文字列アルゴリズム   半構造データ   機械学習   知識獲得   XML   ウェブマイニング   情報抽出   パターン発見   グラフマイニング   文字列照合   データベース   圧縮   ストリーム処理   情報検索   

研究分野

  • 情報通信 / データベース / データマイニング・情報検索
  • 情報通信 / 知能情報学 / 人工知能・機械学習
  • 情報通信 / 情報学基礎論 / アルゴリズム

職歴

  • 2019年04月 - 現在 北海道大学 大学院・情報科学研究科 教授(改組のため)
  • 2018年04月 - 現在 北海道大学共同プロジェクト拠点 知識メディアラボラトリー リーダー(拠点長)
  • 2016年04月 - 現在 北海道大学「ビッグデータ・サイバーセキュリティ グローバルステーション」 教授(PI)
  • 2008年01月 - 現在 国立情報学研究所 連携研究部門 客員教授
  • 2004年04月 - 2019年03月 北海道大学 大学院・情報科学研究科 教授
  • 2016年04月 - 2018年03月 北海道大学「ビッグデータ・サイバーセキュリティ グローバルステーション」 拠点長
  • 2015年04月 - 2017年03月 北海道大学共同プロジェクト拠点 知識メディアラボラトリー リーダー(拠点長)
  • 2013年04月 - 2015年03月 北海道大学知識メディアラボラトリー ラボラトリー長
  • 2007年07月 - 2012年03月 北海道大学情報科学研究科 グローバルCOEプログラム「知の創出を支える次世代IT基盤拠点」 拠点リーダー
  • 2005年03月 - 2005年06月 リヨン大学第1訪問研究員(文科省)
  • 1996年04月 - 2004年03月 九州大学 大学院システム情報科学研究科 助教授(2000年から組織改編により准教授)
  • 2002年04月 - 2003年03月 九州大学 情報基盤センター研究部 兼任准教授
  • 2001年04月 - 2002年03月 九州大学 付属図書館研究開発室 兼任准教授
  • 1999年10月 - 2002年03月 科学技術事業団さきがけ研究21 「情報と知」領域 研究員
  • 1996年06月 - 1996年10月 ヘルシンキ大学訪問研究員(学振特定国交流研究員).
  • 1995年04月 - 1996年03月 九州工業大学 情報工学部 助教授
  • 1994年04月 - 1995年03月 九州工業大学 情報工学部 講師
  • 1990年04月 - 1994年03月 九州工業大学 情報工学部 助手

学歴

  • 1994年06月 - 1994年06月   博士(理学)   九州大学大学院総合理工学研究科
  • 1988年04月 - 1990年03月   九州大学   大学院総合理工学研究科   情報システム学専攻修士課程
  • 1984年04月 - 1988年03月   九州大学   理学部   物理学科

所属学協会

  • 電子情報通信学会   人工知能学会   情報処理学会   ACM   Information and Communication Engineers (IEICE)   The institute of Electronics   

研究活動情報

論文

  • 最大クリークサイズが定数であるグラフに対する独立点集合のならし定数時間列挙
    栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀
    電子情報通信学会コンピューテーション研究会 2019年11月 [査読無し][通常論文]
  • Yusaku Kaneta, Takeaki Uno, Hiroki Arimura
    String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7-9, 2019, Proceedings 241 - 257 Springer 2019年10月 [査読有り][通常論文]
  • Kunihiro Wasa, Katsuhisa Yamanaka, Hiroki Arimur
    IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences E102-D 3 464 - 469 2019年03月 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
    CoRR abs/1906.09680 2019年 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
    CoRR abs/1903.02161 2019年 [査読有り][通常論文]
  • Yoichi Sasaki, Tetsuo Shibuya, Kimihito Ito, Hiroki Arimura
    IEICE Transactions 102-A 9 1159 - 1170 2019年 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
    Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, Pisa, Italy, July 23-25, 2019, Proceedings 339 - 351 Springer 2019年 [査読有り][通常論文]
  • Kentaro Kanamori, Satoshi Hara, Masakazu Ishihata, Hiroki Arimura
    CoRR abs/1906.01876 2019年 [査読有り][通常論文]
  • Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato, Kunihiko Sadakane
    Algorithms 11 8 2018年08月 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Alessio Conte, Hiroki Arimura, Takeaki Uno
    CoRR abs/1806.04307 2018年 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
    CoRR abs/1802.07863 2018年 [査読有り][通常論文]
  • KURITA Kazuhiro, WASA Kunihiro, UNO Takeaki, ARIMURA Hiroki
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 101 9 1383 - 1391 一般社団法人 電子情報通信学会 2018年 [査読無し][通常論文]
     

    In this study, we address a problem pertaining to the induced matching enumeration. An edge set M is an induced matching of a graph G=(V,E). The enumeration of matchings has been widely studied in literature; however, there few studies on induced matching. A straightforward algorithm takes O2) time for each solution that is coming from the time to generate a subproblem, where Δ is the maximum degree in an input graph. To generate a subproblem, an algorithm picks up an edge e and generates two graphs, the one is obtained by removing e from G, the other is obtained by removing e, adjacent edge to e, and edges adjacent to adjacent edge of e. Since this operation needs O2) time, a straightforward algorithm enumerates all induced matchings in O2) time per solution. We investigated local structures that enable us to generate subproblems within a short time and proved that the time complexity will be O(1) if the input graph is C4-free. A graph is C4-free if and only if none of its subgraphs have a cycle of length four.

  • Kazuhiro Kurita, Kunihiro Wasa, Alessio Conte, Takeaki Uno, Hiroki Arimura
    Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings 201 - 213 Springer 2018年 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
    The 29th International Symposium on Algorithms and Computation (ISAAC 2018) 8 - 13 2018年 [査読有り][通常論文]
  • Iku Ohama, Issei Sato, Takuya Kida, Hiroki Arimura
    Proc. the 31st Annual Conference on Neural Information Processing Systems (NIPS2017) 2017年12月 [査読有り][通常論文]
  • Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100A 9 1785 - 1793 2017年09月01日 [査読有り][通常論文]
     
    We present a new data structure called the packed compact trie (packed c-trie) which stores a set S of k strings of total length n in n log + O(k log n) bits of space and supports fast pattern matching queries and updates, where is the alphabet size. Assume that = log n letters are packed in a single machine word on the standard word RAM model, and let f (k n) denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores k integers from universe [1 n] in O(k log n) bits of space. Then, given a string of length m, our packed c-tries support pattern matching queries and insert/delete operations in O( m f (k n)) worst-case time and in O( m + f (k n)) expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. We also discuss applications of our packed c-tries.
  • Junpei Komiyama, Masakazu Ishihata, Hiroki Arimura, Takashi Nishibayashi, Shin-Ichi Minato
    Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 129685 897 - 906 2017年08月13日 [査読有り][通常論文]
     
    Emerging patterns are patterns whose support significantly differs between two databases. We study the problem of listing emerging patterns with a multiple testing guarantee. Recently, Terada et al. proposed the Limitless Arity Multiple-testing Procedure (LAMP) that controls the family-wise error rate (FWER) in statistical association mining. LAMP reduces the number of "untestable" hypotheses without compromising its statistical power. Still, FWER is restrictive, and as a result, its statistical power is inherently unsatisfying when the number of patterns is large. On the other hand, the false discovery rate (FDR) is less restrictive than FWER, and thus controlling FDR yields a larger number of significant patterns. We propose two emerging pattern mining methods: the first one controls FWER, and the second one controls FDR. The effectiveness of the methods is verified in computer simulations with real-world datasets.
  • Iku Ohama, Hiromi Iida, Takuya Kida, Hiroki Arimura
    Proc. the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017) 2578 - 2584 2017年08月 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
    CoRR abs/1707.02740 2017年 [査読有り][通常論文]
  • Takuya Takagi, Keisuke Goto, Yuta Fujishige, Shunsuke Inenaga, Hiroki Arimura
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10508 304 - 316 2017年 [査読有り][通常論文]
     
    In this paper, we propose a novel approach to combine compact directed acyclic word graphs (CDAWGs) and grammar-based compression. This leads us to an efficient self-index, called Linear-size CDAWGs (L-CDAWGs), which can be represented with O(ẽT log n) bits of space allowing for O(log n) -time random and O(1)-time sequential accesses to edge labels, and O(m log σ + occ) -time pattern matching. Here, ẽT is the number of all extensions of maximal repeats in T, n and m are respectively the lengths of the text T and a given pattern, σ is the alphabet size, and occ is the number of occurrences of the pattern in T. The repetitiveness measure ẽT is known to be much smaller than the text length n for highly repetitive text. For constant alphabets, our L-CDAWGs achieve O(m + occ ) pattern matching time with O(eT r log n) bits of space, which improves the pattern matching time of Belazzougui et al.’s run-length BWT-CDAWGs by a factor of log log n, with the same space complexity. Here, eT r is the number of right extensions of maximal repeats in T. As a byproduct, our result gives a way of constructing a straight-line program (SLP) of size O(ẽT) for a given text T in O(n + ẽT log σ) time.
  • Mayumbo Nyirenda, Ryosuke Omori, Heidi L. Tessmer, Hiroki Arimura, Kimihito Ito
    PLOS ONE 11 11 e0166107  2016年11月 [査読有り][通常論文]
     
    The prediction of the lineage dynamics of influenza B viruses for the next season is one of the largest obstacles for constructing an appropriate influenza trivalent vaccine. Seasonal fluctuation of transmissibility and epidemiological interference between the two major influenza B lineages make the lineage dynamics complicated. Here we construct a parsimonious model describing the lineage dynamics while taking into account seasonal fluctuation of transmissibility and epidemiological interference. Using this model we estimated the epidemiological and evolutional parameters with the time-series data of the lineage specific isolates in Japan from the 2010-2011 season to the 2014-2015 season. The basic reproduction number is similar between Victoria and Yamagata, with a minimum value during one year as 0.82 (95% highest posterior density (HPD): 0.77-0.87) for the Yamagata and 0.83 (95% HPD: 0.74-0.92) for Victoria, the amplitude of seasonal variation of the basic reproduction number is 0.77 (95% HPD: 0.66-0.87) for Yamagata and 1.05 (95% HPD: 0.89-1.02) for Victoria. The duration for which the acquired immunity is effective against infection by the Yamagata lineage is shorter than the acquired immunity for Victoria, 424.1days (95% HPD: 317.4-561.5days). The reduction rate of susceptibility due to immune cross-reaction is 0.51 (95% HPD: 0.084-0.92) for the immunity obtained from the infection with Yamagata against the infection with Victoria and 0.62 (95% HPD: 0.42-0.80) for the immunity obtained from the infection with Victoria against the infection with Yamagata. Using estimated parameters, we predicted the dominant lineage in 2015-2016 season. The accuracy of this prediction is 68.8% if the emergence timings of the two lineages are known and 61.4% if the emergence timings are unknown. Estimated seasonal variation of the lineage specific reproduction number can narrow down the range of emergence timing, with an accuracy of 64.6% if the emergence times are assumed to be the time at which the estimated reproduction number exceeds one.
  • Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura, Shin-ichi Minato
    DISCRETE APPLIED MATHEMATICS 212 61 - 80 2016年10月 [査読有り][通常論文]
     
    The manipulation of large sequence data is one of the most important problems in string processing. In this paper, we discuss a new data structure for storing and manipulating sets of strings, called Sequence Binary Decision Diagrams (sequence BDDs), which has recently been introduced by Loekito et al. (2010) as a descendant of both acyclic DFAs (ADFAs) and binary decision diagrams (BDDs). Sequence BDDs can compactly represent sets of sequences similarly to minimal ADFAs, and allow efficient set operations inherited from BDDs. We study fundamental properties of sequence BDDs, such as the characterization of minimal sequence BDDs by reduced sequence BDDs, non-trivial relationships between sizes of minimal sequence BDDs and minimal ADFAs, the complexities of minimization, Boolean set operations, and sequence BDD construction. We also show experimental results for real and artificial data sets. (C) 2014 Elsevier B.V. All rights reserved.
  • Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura
    Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM'16), Leibniz International Proceedings in Informatics (LIPIcs) 54 22:1 - 22:13 2016年06月 [査読有り][通常論文]
  • Iku Ohama, Hiromi Iida, Takuya Kida, Hiroki Arimura
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E99D 4 1139 - 1152 2016年04月 [査読有り][通常論文]
     
    Latent variable models for relational data enable us to extract the co-cluster structures underlying observed relational data. The Infinite Relational Model (IRM) is a well-known relational model for discovering co-cluster structures with an unknown number of clusters. The IRM assumes that the link probability between two objects (e.g., a customer and an item) depends only on their cluster assignment. However, relational models based on this assumption often lead us to extract many non-informative and unexpected clusters. This is because the underlying co-cluster structures in real-world relationships are often destroyed by structured noise that blurs the cluster structure stochastically depending on the pair of related objects. To overcome this problem, in this paper, we propose an extended IRM that simultaneously estimates denoised clear co-cluster structure and a structured noise component. In other words, our proposed model jointly estimates cluster assignment and noise level for each object. We also present posterior probabilities for running collapsed Gibbs sampling to infer the model. Experiments on real-world datasets show that our model extracts a clear co-cluster structure. Moreover, we confirm that the estimated noise levels enable us to extract representative objects for each cluster.
  • Mayumbo Nyirenda, Hiroki Arimura, Kimihito Ito
    PROCEEDINGS OF 2016 5TH INTERNATIONAL CONFERENCE ON MULTIMEDIA COMPUTING AND SYSTEMS (ICMCS) 189 - 194 2016年 [査読有り][通常論文]
     
    Data access of a massive collection of geographic spatial data is one of the serious bottlenecks in large-scale datacentric applications in the big data era such as data assimilation and urban data analytic systems. In this paper, we consider the issue of implementation of distributed spatial indices, specifically quad trees, on a distributed computing system in the shared-nothing memory approach. We discuss static and dynamic partitioning and allocation strategies for data and queries across distributed nodes. Using scale-down parallel data load and search experiments with a small distributed processor system as proof-of-concept, we show that the proposed approach with a collection of small indices of distributed shared-nothing memory is more efficient than the conventional approach with a single processor with a large external index. We also observed that the proposed tree-based partitioning and assignment strategy using sampling reduces query time than other conventional partitioning strategies used in databases. We also discuss how to allocate a collection of small tree indices among distributed processors. These results suggest that the use of parallelized access to databases with spatial indexing functions can enhance the throughput of large-scale data-centric applications.
  • Kunihiro Wasa, Katsuhisa Yamanaka, Hiroki Arimura
    LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS, LATA 2016 9618 330 - 342 2016年 [査読有り][通常論文]
     
    A reconfiguration problem asks when we are given two feasible solutions A and B, whether there exists a reconfiguration sequence (A(0) = A, A(1),..., A(l) = B) such that (i) A(0),..., A(l) are feasible solutions and (ii) we can obtain A(i) from A(i-1) under the prescribed rule (the reconfiguration rule) for each i = 1,..., l. In this paper, we address the reconfiguration problem for induced trees, where an induced tree is a connected and acyclic induced graph of an input graph. This paper treats the following two rules as the prescribed rules: Token Jumping; removing u from an induced tree and adding v to the tree, and Token Sliding; removing u from an induced tree and adding v adjacent to u to the tree, where u and v are vertices in an input graph. As the main results, we show (I) the reconfiguration problem is PSPACE-complete, (II) the reconfiguration problem is W[1]-hard when parameterized by both the size of induced trees and the length of the reconfiguration sequence, and (III) there exists an FPT algorithm when parameterized by both the size of induced trees and the maximum degree of an input graph, under each of Token Jumping and TOKEN SLIDING.
  • Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura
    Combinatorial Algorithms 9843 213 - 225 2016年 [査読有り][通常論文]
     
    We present a new data structure called the packed compact trie (packed c-trie) which stores a set S of k strings of total length n in n log sigma + O(k log n) bits of space and supports fast pattern matching queries and updates, where sigma is the alphabet size. Assume that a = log(sigma) n letters are packed in a single machine word on the standard word RAM model, and let f (k, n) denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores k integers from universe [1, n] in O (k log n) bits of space. Then, given a string of length m, our packed c- tries support pattern matching queries and insert/delete operations in O(m/alpha f (k, n)) worst-case time and in O(m/alpha + f (k, n)) expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. We also discuss applications of our packed c-tries.
  • 二部グラフ中に含まれる弦二部誘導グラフの列挙
    和佐 州洋, 有村 博紀, 宇野 毅明, 平田 耕一
    第154回情報処理学会アルゴリズム研究会 154 1 - 8 2015年09月 [査読無し][通常論文]
  • 大規模軌跡データからの群パターン発見のための実用的アルゴリズム
    耿 暁亮, 宇野 毅明, 有村 博紀
    Transactions of IPSJ 56 4 1292 - 1304 2015年04月 [査読有り][通常論文]
  • Yoichi Sasaki, Tetsuo Shibuya, Kimihito Ito, Hiroki Arimura
    SIMILARITY SEARCH AND APPLICATIONS, SISAP 2015 9371 191 - 203 2015年 [査読有り][通常論文]
     
    In this paper, we study approximate point subset match (APSM) problem with minimum RMSD score under translation, rotation, and one-to-one correspondence in d-dimension. Since this problem seems computationally much harder than the previously studied APSM problems with translation only or distance evaluation only, we focus on speed-up of exhaustive search algorithms that can find all approximate matches. First, we present an efficient branch-and-bound algorithm using a novel lower bound function of the minimum RMSD score. Next, we present another algorithm that runs fast with high probability when a set of parameters are fixed. Experimental results on real 3-D molecular data sets showed that our branch-and-bound algorithm achieved significant speed-up over the naive algorithm still keeping the advantage of generating all answers.
  • 文字列の圧縮列挙索引技術とパターン照合技術
    伝住周平, 有村博紀, 定兼邦彦
    電子情報通信学会誌 97 12 1080 - 1085 2014年12月 [査読有り][通常論文]
  • Xiaoliang Geng, Takuya Takagi, Hiroki Arimura, Takeaki Uno
    Proceedings of the 5th ACM SIGSPATIAL International Workshop on GeoStreaming, IWGS 2014 53 - 61 2014年11月04日 [査読有り][通常論文]
     
    In this paper, we consider the problem of mining the complete set of spatio-temporal patterns, called maximal-duration flock patterns (Gudmundsson and van Kreveld, Proc. ACM GIS 2006) from massive mobile GPS location streams. Such algorithms are useful for mining and analysis of real-time geographic streams in geographic information systems. Although a polynomial time algorithm exists for finding a maximal-duration flock pattern from a collection of trajectories, it has not been known whether it is possible to find all maximal-duration flock patterns with theoretical guarantee of its computational complexity. For this problem, we present efficient depth-first algorithms for finding all maximal-duration patterns in a collection of trajectories without duplicates that run in polynomial time per discovered pattern using polynomial space in the total size of input trajectories. To achieve the output-sensitive complexity above, our algorithms adopt depth-first search strategy to avoid the use of exponentially large memory. We also propose a speed-up technique using geometric indexes. Finally, we show experimental results on artificial data to evaluate the proposed algorithms.
  • Hirohito Sasakawa, Hiroki Harada, David A. Du Verle, Hiroki Arimura, Koji Tsuda, Jun Sakuma
    Proceedings of the ACM Conference on Computer and Communications Security 21 - 30 2014年11月03日 [査読有り][通常論文]
     
    Various string matching problems can be solved by means of a deterministic finite automaton (DFA) or a non-deterministic finite automaton (NFA). In non-oblivious cases, DFAs are often preferred for their run-time efficiency despite larger sizes. In oblivious cases, however, the inevitable computation and communication costs associated with the automaton size are more favorable to NFAs. We propose oblivious protocols for NFA evaluation based on homomorphic encryption and demonstrate that our method can be orders of magnitude faster than DFA-based methods, making it applicable to real-life scenarios, such as privacy-preserving detection of viral infection using genomic data.
  • Ryutaro Kurai, Norihito Yasuda, Hiroki Arimura, Shinobu Nagayama, Shin-ichi Minato
    Proc. Prague Stringology Conference 2014 (PSC'14) 3 - 16 2014年09月 [査読有り][通常論文]
  • K-縮退グラフに含まれる誘導木の列挙
    和佐州洋, 有村博紀, 宇野毅明
    第148回情報処理学会アルゴリズム研究会 148 17 1 - 6 2014年06月 [査読無し][通常論文]
  • Kunihiro Wasa, Yusaku Kaneta, Takeaki Uno, Hiroki Arimura
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E97D 3 421 - 430 2014年03月 [査読有り][通常論文]
     
    By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is originally introduced by (Ferreira, Grossi, and Rizzi, ESA' 11, 275-286, 2011) for general graphs. Based on reverse search technique (Avis and Fukuda, Discrete Appl. Math., vol.65, pp.21-46, 1996), we present the first constant delay enumeration algorithm that lists all k-subtrees of an input rooted tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al's algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees.
  • Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato, Kunihiko Sadakane
    EXPERIMENTAL ALGORITHMS, SEA 2014 8504 187 - 198 2014年 [査読有り][通常論文]
     
    In many real-life problems, we are often faced with manipulating families of sets. Manipulation of large-scale set families is one of the important fundamental techniques for web information retrieval, integration, and mining. For this purpose, a special type of binary decision diagrams (BDDs), called Zero-suppressed BDDs (ZDDs), is used. However, current techniques for storing ZDDs require a huge amount of memory and membership operations are slow. This paper introduces DenseZDD, a compressed index for static ZDDs. Our technique not only indexes set families compactly but also executes fast member membership operations. We also propose a hybrid method of DenseZDD and ordinary ZDDs to allow for dynamic indices.
  • Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
    ALGORITHMS AND COMPUTATION, ISAAC 2014 8889 94 - 102 2014年 [査読有り][通常論文]
     
    In this paper, we address the problem of enumerating all induced subtrees in an input k-degenerate graph, where an induced subtree is an acyclic and connected induced subgraph. A graph G = (V, E) is a k-degenerate graph if for any its induced subgraph has a vertex whose degree is less than or equal to k, and many real-world graphs have small degeneracies, or very close to small degeneracies. Although, the studies are on subgraphs enumeration, such as trees, paths, and matchings, but the problem addresses the subgraph enumeration, such as enumeration of subgraphs that are trees. Their induced subgraph versions have not been studied well. One of few examples is for chordless paths and cycles. Our motivation is to reduce the time complexity close to O(1) for each solution. This type of optimal algorithms is proposed many subgraph classes such as trees, and spanning trees. Induced subtrees are fundamental object thus it should be studied deeply and there possibly exist some efficient algorithms. Our algorithm utilizes nice properties of k-degeneracy to state an effective amortized analysis. As a result, the time complexity is reduced to O(k) time per induced subtree. The problem is solved in constant time for each in planar graphs, as a corollary.
  • Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagrams
    Shuhei Denzumi, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato
    In Proc. of Prague Stringology Conference 2013 (PSC2013) 157 - 167 2013年09月 [査読有り][通常論文]
  • 長さ極大な群れパターンを軌跡集合から効率良く発見するアルゴリズム
    有村 博紀, 耿 暁亮, 宇野 毅明
    第144回情報処理学会アルゴリズム研究会 2013-AL-144 3 1 - 8 2013年05月 [査読無し][通常論文]
  • Succinct Indices Based on Zero-Suppressed Binary Decision Diagrams
    Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Kunihiko Sadakane, Shin-ichi Minato
    電子情報通信学会コンピュテーション研究会, 信学技報 112 498 23 - 30 2013年03月 [査読無し][通常論文]
  • 山本 潤, 岩森利弘, 星 直樹, 阿部拓三, 坂岡桂一郎, 亀井佳彦, 高木省吾, 沼本 修, 阪 幸宏, 桜井泰憲, 末岡和久, 有村博紀, 渡邉日出海
    水産技術 5 2 171 - 174 2013年02月 [査読有り][通常論文]
     
    We developed a battery powered compact 2000m class ROV (Remotely Operated Vehicle) system with a High-Definition video camera. It does not require specialized equipment to operate. It can be operated using only general purpose equipment. This system mainly consists of a shipboard controller, a vehicle and a launcher. A thin, light optical fiber cable (diameter 9mm, length 2,500m), the primary cable, transfers control data and video images between the shipboard controller and the launcher. The secondary cable, a composite cable (diameter 14.2mm, length 50m), transfers control data and video images and supplies power to the vehicle from the six packs of lithium-ion batteries, which are mounted in the launcher. The launcher is suspended by a rope from the support ship, and the depth of the launcher is adjusted by changing the length of the rope using a general purpose rewinder.
    Although initially, we had some trouble due to the launcher rope and the primary cable getting tangled, a newly-designed instrument that restricts the movement of the carabiner, and the use of a low expansion rope, facilitated smoother operation and an easier recovery of the ROV.
  • Kunihiro Wasa, Kouichi Hirata, Takeaki Uno, Hiroki Arimura
    SIMILARITY SEARCH AND APPLICATIONS (SISAP) 8199 73 - 84 2013年 [査読有り][通常論文]
     
    In this paper, we study efficient computation of tree similarity for ordered trees based on compressed subtree enumeration. The compressed subtree enumeration is a new paradigm of enumeration algorithms that enumerates all subtrees of an input tree T in the form of their compressed bit signatures. For the task of enumerating all compressed bit signatures of k-subtrees in an ordered tree T, we first present an enumeration algorithm in O(k)-delay, and then, present another enumeration algorithm in constant-delay using O(n) time preprocessing that directly outputs bit signatures. These algorithms are designed based on bit-parallel speed-up technique for signature maintenance. By experiments on real and artificial datasets, both algorithms showed approximately 22% to 36% speed-up over the algorithms without bit-parallel signature maintenance.
  • Iku Ohama, Hiromi Iida, Takuya Kida, Hiroki Arimura
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7819 2 147 - 159 2013年 [査読有り][通常論文]
     
    The Infinite Relational Model (IRM) introduced by Kemp et al. (Proc. AAAI2006) is one of the well-known probabilistic generative models for the co-clustering of relational data. The IRM describes the relationship among objects based on a stochastic block structure with infinitely many clusters. Although the IRM is flexible enough to learn a hidden structure with an unknown number of clusters, it sometimes fails to detect the structure if there is a large amount of noise or outliers. To overcome this problem, in this paper we propose an extension of the IRM by introducing a subset mechanism that selects a part of the data according to the interaction among objects. We also present posterior probabilities for running collapsed Gibbs sampling to learn the model from the given data. Finally, we ran experiments on synthetic and real-world datasets, and we showed that the proposed model is superior to the IRM in an environment with noise. © Springer-Verlag 2013.
  • Kunihiro Wasa, Takeaki Uno, Kouichi Hirata, Hiroki Arimura
    DISCOVERY SCIENCE 8140 308 - 323 2013年 [査読有り][通常論文]
     
    In this paper, we study the problem of finding all tree-like substructure contained in a hypergraph, with potential applications to substructure mining from relational data. We employ the class of connected and Berge acyclic sub-hypergraphs as definition of tree-like substructures, which is the most restricted notion of acyclicities for hypergraphs. Then, we present an efficient depth-first algorithm that finds all connected and Berge acyclic sub-hypergraphs S in a hypergraph H with m hyperedges and n vertices in O(nm(2)) time per solution (delay) using O(N) space, where N = parallel to H parallel to is the total input size. To achieve efficient enumeration, we use the notion of the maximum border set. This result gives the first polynomial delay and time algorithm for enumeration of connected and Berge-acyclic sub-hypergraphs. We also present an incremental enumeration algorithm that finds all solutions S in O(Delta MB(S)tau(m)) = O(rd .tau (m)) delay using O(N) space and preprocessing, whose delay depends only on the difference of solutions, where S is the enumerated sub-hypergraph, Delta MB(S) is the number of newly added hyperedges to the maximum border of S, r and d are the rank and degree of H, respectively, and tau(m) = ((log logm)(2)/log log logm).
  • 超グラフ中に含まれる非巡回部分超グラフの効率よい列挙,
    和佐州洋, 有村博紀, 宇野毅明, 平田耕一
    第88回人工知能基本問題研究会 88 85 - 90 2013年01月 [査読無し][通常論文]
  • Ryo Yoshinaka, Jun Kawahara, Shuhei Denzumi, Hiroki Arimura, Shin-ichi Minato
    INFORMATION PROCESSING LETTERS 112 16 636 - 640 2012年08月 [査読有り][通常論文]
     
    In this article, we disprove the long-standing conjecture, proposed by R.E. Bryant in 1986, that his binary decision diagram (BDD) algorithm computes any binary operation on two Boolean functions in linear time in the input-output sizes. We present Boolean functions for which the time required by Bryant's algorithm is a quadratic of the input-output sizes for all nontrivial binary operations, such as boolean AND, boolean OR, and circle plus. For the operations boolean AND and boolean OR. we show an even stronger counterexample where the output BDD size is constant, but the computation time is still a quadratic of the input BDD size. In addition, we present experimental results to support our theoretical observations. (C) 2012 Elsevier B.V. All rights reserved.
  • Yusaku Kaneta, Hiroki Arimura, Rajeev Raman
    Journal of Discrete Algorithms 14 119 - 135 2012年07月 [査読有り][通常論文]
     
    In this paper, we consider the unordered pseudo-tree matching problem, which is a problem of, given two unordered labeled trees P and T, finding all occurrences of P in T via such many-to-one matchings that preserve node labels and parent-child relationship. This problem is closely related to the tree pattern matching problem for XPath queries with child axis only. If m> w, we present an efficient algorithm that solves the problem in O(nmlog(w)/w) time using O(hm/w+mlog(w)/w) space and O(mlog(w)) preprocessing on a unit-cost arithmetic RAM model with addition, where m is the number of nodes in P, n is the number of nodes in T, h is the height of T, and w is the word length, and we assume that w≥logn. We also discuss a modification of our algorithm for the unordered tree homeomorphism problem, which corresponds to the tree pattern matching problem for XPath queries with descendant axis only. © 2011 Elsevier B.V.
  • Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura, Yoshikazu Miyanaga
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E95D 7 1847 - 1857 2012年07月 [査読有り][通常論文]
     
    In this paper, we propose a novel architecture for large-scale regular expression matching, called dynamically reconfigurable bit-parallel NFA architecture (Dynamic BP-NFA), which allows dynamic loading of regular expressions on-the-fly as well as efficient pattern matching for fast data streams. This is the first dynamically reconfigurable hardware with guaranteed performance for the class of extended patterns, which is a subclass of regular expressions consisting of union of characters and its repeat. This class allows operators such as character classes, gaps, optional characters, and bounded and unbounded repeats of character classes. The key to our architecture is the use of bit-parallel pattern matching approach, in which the information of an input non-deterministic finite automaton (NFA) is first compactly encoded in bit-masks stored in a collection of registers and block RAMs. Then, the NFA is efficiently simulated by a fixed circuitry using bitwise Boolean and arithmetic operations consuming one input character per clock regardless of the actual contents of an input text. Experimental results showed that our hardwares for both string and extended patterns were comparable to previous dynamically reconfigurable hardwares in their performances.
  • 笹川 裕人, 金田 悠作, 有村 博紀
    日本データベース学会論文誌 11 1 55 - 60 日本データベース学会 2012年06月 [査読無し][通常論文]
  • 伝住 周平, 有村 博紀, 湊 真一
    電子情報通信学会技術研究報告 : 信学技報 112 93 9 - 16 電子情報通信学会 2012年06月 [査読無し][通常論文]
  • 木に含まれる限定サイズ部分木の列挙
    和佐 州洋, 宇野 毅明, 有村 博紀
    第140回情報処理学会アルゴリズム研究会 2012-AL-140 4 1 - 8 2012年05月 [査読無し][通常論文]
  • Kunihiro Wasa, Yusaku Kaneta, Takeaki Uno, Hiroki Arimura
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7434 347 - 359 2012年 [査読有り][通常論文]
     
    By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the ksubtree enumeration problem, originally introduced by (Ferreira, Grossi, and Rizzi, ESA'11, 275-286, 2011), where an input graph is a tree of n nodes. Based on reverse search technique, we present the first constant delay enumeration algorithm that lists all k-subtrees of an input tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al's algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees. © 2012 Springer-Verlag.
  • Xiaoliang Geng, Hiroki Arimura, Takeaki Uno
    Proceedings of the 2012 IIAI International Conference on Advanced Applied Informatics, IIAIAAI 2012 60 - 65 2012年 [査読有り][通常論文]
     
    In this paper, we consider data mining from large discrete trajectory data. We study closed pattern mining for the class of trajectory envelope patterns. First, we introduce the basic definition of trajectory data. Then, we present a depthfirst search algorithm that finds all trajectory envelope patterns in a given database that satisfies constrants on maximum width, minimum length, and minimum frequency. Finally, we ran experiments on a real trajectory dataset to evaluate our algorithm. © 2012 IEEE.
  • Hirohito Sasakawa, Hiroki Arimura
    Proceedings of the 2012 IIAI International Conference on Advanced Applied Informatics, IIAIAAI 2012 66 - 71 2012年 [査読有り][通常論文]
     
    In this paper, we study massive trajectory search based on string matching technology. We first propose byteoriented encoding scheme for trajectory data allowing multiresolution search. Then, we present an efficient bit-parallel trajectory matching algorithm on byte-oriented encoded texts based on Extended SHIFT-AND method (Navarro and Raffinot, RECOMB 2001). Finally, we ran experiments on the real world trajectory data to evaluate the efficiency of the proposed algorithm. The results showed good performance enough for real applications. © 2012 IEEE.
  • High-speed String and Regular Expression Matching on FPGA
    Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura
    Proc. of Asia Pacific Signal and Information Processing Association Annual Summit and Conference 2011 (APSIPA ASC 2011 2011年10月 [査読有り][通常論文]
  • Yusaku Kaneta, Hiroki Arimura
    COMBINATORIAL ALGORITHMS 6460 68 - 81 2011年 [査読有り][通常論文]
     
    In this paper, we consider the unordered pseudo-tree matching problem, which is a problem of, given two unordered labeled trees P and T, finding all occurrences of P in via such many-one embeddings that preserve node labels and parent-child relationship. This problem is closely related to tree pattern matching problem for XPath queries with child axis only. If m > we present an efficient algorithm that solves the problem in O(nm log(w)/w) time using O(hm/w + m log(w)/w) space and O(m log(w)) preprocessing on a unit-cost arithmetic RAM model with addition, where in is the number of nodes in P, n is the number of nodes in T, h is the height of T, and w is the word length. We also discuss a modification of our algorithm for the unordered tree homeomorphism problem, which corresponds to a tree pattern matching problem for XPath queries with descendant axis only.
  • Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura, Shin-ichi Minato
    PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2011 147 - 161 2011年 [査読有り][通常論文]
     
    Manipulation of large sequence data is one of the most important problems in string processing. Recently, Loekito et al. (Knowl. Inf. Syst., 24(2), 235-268, 2009) have introduced a new data structure, called Sequence Binary Decision Diagrams (SeqBDDs, or SDDs), which are descendants of both acyclic DFAs (ADFAs) and binary decision diagrams (BDDs). SDDs can compactly represent sets of sequences as well as minimal ADFAs, while SDDs allow efficient set operations inherited from BDDs. A novel feature of the SDDs is that different SDDs can share equivalent subgraphs and duplicated computation in common to save the time and space in various operations. In this paper, we study fundamental properties of SDDs. In particular, we first present non-trivial relationships between sizes of minimum SDDs and minimal ADFAs. We then analyze the complexities of algorithms for Boolean set operations, called the binary synthesis. Finally, we show experimental results to confirm the results of the theoretical analysis on real data sets.
  • Shuhei Denzumi, Hiroki Arimura, Shin-ichi Minato
    ERLANG 11: PROCEEDINGS OF THE 2011 ACM SIGPLAN ERLANG WORKSHOP 90 - 91 2011年 [査読有り][通常論文]
     
    In this paper, we present an implementation of Erlang of an efficient index structure, called Sequence Binary Decision Diagrams (SeqBDDs), for knowledge discovery in large sequence data. Recently, Loekito, Bailey, and Pei (KAIS, 2009) proposed SeqBDD. SeqBDDs are a compact indices for efficiently representing the set of sequences. Furthermore, SeqBDDs provide a rich collection of operations for sets of sequences, which are useful for implementing sequence mining algorithms. We propose SeqBDDs as powerful framework for string processing and Erlang is appropriate language for SeqBDD. SeqBDD system heavily uses hash tables to avoid redundant memory and computation. We implemented SeqBDD package with ETS for hash tables.
  • Takashi Uemura, Hiroki Arimura
    COMBINATORIAL PATTERN MATCHING, 22ND ANNUAL SYMPOSIUM, CPM 2011 6661 246 - 260 2011年 [査読有り][通常論文]
     
    The sparse suffix trees (SST), introduced by (Karkkainen and Ukkonen, COCOON 1996), is the suffix tree for a subset of all suffixes of an input text T of length n. In this paper, we study a special case that an input string is a sequence of k codewords drawn from a regular prefix code Delta subset of Sigma(+) recognized by a finite automaton, and index points locate on the code boundaries. In this case, we present an online algorithm that constructs the sparse suffix tree for an input string T on any variable-length regular prefix code, called the code suffix tree (CST), in O(n + m) time and O(k) additional space for a fixed base alphabet Sigma, where m is the size of an automaton for.. Furthermore, we present a modified algorithm for l-truncated version of code suffix trees that runs in the same time and space complexities. Hence, these results generalize the previous results (Inenaga and Takeda, CPM 2006) for word suffix trees and (Na, Apostolico, Iliopoulos, and Park, Theor. Comp. Sci., 304, 2003) for truncated suffix trees on arbitrary variable-length regular prefix codes, such as Huffman codes and multi-byte codes (e.g. UTF-8).
  • Hiroki Arimura, Raoul Medina, Jean-Marc Petit, Franz Baader, Jean-François Boulicaut, Bruno Crémilleux, Luc De Raedt, Khaled Elbassioni, Alain Gely, Bart Goethals, Sergei Kuznetsov, Dominique Laurent, Hong-Cheu Liu, Joao Marques-Silva, Rokia Missaoui, Siegfried Nijssen, Lhouari Nourine, Marie-Christine Rousset, Lakhdar Sais, Thomas Schiex, Takeaki Uno, Jef Wijsen
    Proceedings - IEEE International Conference on Data Mining, ICDM liii - liv 2011年 [査読有り][通常論文]
  • Takashi Katoh, Hiroki Arimura, Kouichi Hirata
    NEW FRONTIERS IN ARTIFICIAL INTELLIGENCE 6284 331 - 344 2010年 [査読有り][通常論文]
     
    In this paper, we introduce the class of k-partite episodes, which are time-series patterns of the form < A(1), ... , A(k)> for sets A(i) (1 <= i <= k) of events meaning that, in an input event sequence, every event of A(i) is followed by every event of A(i+1) for every 1 <= i < k. Then, we present a backtracking algorithm KPAR and its modification KPAR2 that find all of the frequent k-partite episodes from an input event sequence without duplication. By theoretical analysis, we show that these two algorithms run in polynomial delay and polynomial space in total input size.
  • Yusaku Kaneta, Shin-ichi Minato, Hiroki Arimura
    STRING PROCESSING AND INFORMATION RETRIEVAL 6393 372 - 384 2010年 [査読有り][通常論文]
     
    In this paper, we extend the SHIFT-AND approach by Baeza-Yates and Gonnet (CACM 35(10), 1992) to the matching problem for network expressions, which are regular expressions without Kleene-closure and useful in applications such as bioinformatics and event stream processing. Following the study of Navarro (RECOMB, 2001) on the extended string matching, we introduce new operations called Scatter, Gather, and Propagate to efficiently compute epsilon-moves of the Thompson NFA using the Extended SHIFT-AND approach with integer addition. By using these operations and a property called the bi-monotonicity of the Thompson NFA, we present an efficient algorithm for the network expression matching that runs in O(ndm/w) time using O(dm) preprocessing and O(dm/w) space, where m and d are the length and the depth of a given network expression, n is the length of an input text, and w is the word length of the underlying computer. Furthermore, we show a modified matching algorithm for the class of regular expressions that runs in O(ndm log(m)/w) time.
  • Hiroki Arimura
    Lecture Notes in Electrical Engineering 62 353 - 358 2010年 [査読有り][通常論文]
     
    In this paper, we review recent advances in efficient algorithms for semi-structured data mining, that is, discovery of rules and patterns from structured data such as sets, sequences, trees, and graphs. After introducing basic definitions and problems, We present efficent algorithms for frequent and maximal pattern mining for classes of sets, sequences, and trees. In particular, we explain general techniques, called the rightmost expansion and PPC-extension, which are powerful tools for designing efficient algorithms. We also give examples of applications of semi-structured data mining to real world data. © 2011 Springer Science+Business Media B.V.
  • Yusaku Kaneta, Shingo Yoshizawa, Shin-Ichi Minato, Hiroki Arimura, Yoshikazu Miyanaga
    Proceedings - 2010 International Conference on Field-Programmable Technology, FPT'10 21 - 28 2010年 [査読有り][通常論文]
     
    In this paper, we propose a novel FPGA-based architecture for large-scale regular expression matching, called dynamic reconfigurable bit-parallel NFA architecture (Dynamic BP-NFA) that allows dynamic reconfiguration of the patterns using bit-parallel NFA-simulation. This is the first dynamic reconfigurable FPGA-based hardware with guaranteed performance for the class of extended patterns, where an extended pattern is a restricted regular expression in linear form consisting of letters, classes of letters, don't cares, optional letters, bounded and unbounded length gaps and repeatable letters. The key to our architecture is the use of bit-parallel pattern matching approach that has been developed in string matching communities for the decades. In this approach, the information of an input NFA is compactly encoded in bit-masks stored in a collection of registers and block RAMs. Then, the NFA is efficiently simulated by a fixed circuitry using a combination of bit- and arithmetic-operations on these bit-masks consuming one input letter per clock. As compared with the previous approaches of DFA-based dynamic reconfigurable architectures, experimental results show that the proposed architecture achieves higher throughput for the class of exact string patterns and comparable for the class of extended patterns. © 2010 IEEE.
  • Tatsuya Asai, Seishi Okamoto, Hiroki Arimura
    NEW FRONTIERS IN APPLIED DATA MINING 5433 13 - + 2009年 [査読有り][通常論文]
     
    In this paper, we study the problem the problem of sorting a large collection of strings in external memory. Based on adaptive construction of a summary data structure, called adaptive synopsis trie, we present a practical string sorting algorithm DISTSTRSORT, which is suitable for sorting string collections of large size in external memory, and also suitable for more complex string processing problems in text and semi-structured databases such as counting, aggregation, and statistics. Case analyses of the algorithm and experiments on real datasets show the efficiency of our algorithm in realistic setting.
  • Takuya Kida, Tomoya Saito, Hiroki Arimura
    NEW FRONTIERS IN APPLIED DATA MINING 5433 1 - 12 2009年 [査読有り][通常論文]
     
    In this paper, we study a complex time-series patten matching problem over a multi-dimension continuos data stream. For each data stream, a pattern is given as a sequence of predicates, which specify a sequence of element sets on the stream. The pattern matching problem over such a multi-dimension data stream, is to find all occurrences where all predicates in the pattern. We consider four types of data streams especially: textual, categorical, ordered, and numeric, that is, those are a sequence of streings, concepts with taxonomic information, small integers, and real numbers (or large integers), respectiively. We also present that time complexities to do pattern matching for those data types.
  • Takashi Katoh, Hiroki Arimura, Kouichi Hirata
    ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PROCEEDINGS 5476 172 - + 2009年 [査読有り][通常論文]
     
    In this paper, we study the problem of raining frequent diamond episodes efficiently from an input event sequence with sliding a window. Here, a diamond episode is of the form a bar right arrow E bar right arrow b, which means that every event of E follows an event a and is followed by an event b. Then, we design a polynomial-delay and polynomial-space algorithm POLYFREQDMD that finds all of the frequent diamond episodes without duplicates from an event sequence in O(vertical bar E vertical bar(2)n) time per an episode and in O(vertical bar E vertical bar + n) space, where Sigma and n are an alphabet and the length the event sequence, respectively. Finally, we give experimental results on artificial event sequences with varying several raining parameters to evaluate the efficiency of the algorithm.
  • Hideyuki Ohtani, Takuya Kida, Takeaki Uno, Hiroki Arimura
    Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication, ICUIMC'09 457 - 464 2009年 [査読有り][通常論文]
     
    Recently, knowledge discovery in large data increases its importance in various fields. Especially, data mining from time-series data gains much attention. This paper studies the problem of finding frequent episodes appearing in a sequence of events. We propose an efficient depth-first search algorithm for mining frequent serial episodes in a given event sequence using the notion of right-minimal occurrences. Then, we present some techniques for speeding up the algorithm, namely, occurrence-deliver and tail-redundancy pruning. Finally, we ran experiments on real datasets to evaluate the usefulness of the proposed methods. Copyright 2009 ACM.
  • Takashi Katoh, Hiroki Arimura, Kouichi Hirata
    DISCOVERY SCIENCE, PROCEEDINGS 5808 136 - + 2009年 [査読有り][通常論文]
     
    In this paper, first we introduce a bipartite episode of the form A bar right arrow B for two sets A and B of events, which means that every event of A is followed by every event of B. Then, we present an algorithm that finds all frequent bipartite episodes from an input sequence without duplication in O(vertical bar Sigma vertical bar . N) time per an episode and in O(vertical bar Sigma vertical bar(2)n) space, where Sigma is an alphabet, N is total input size of S, and n is the length of S. Finally, we give experimental results on artificial and real sequences to evaluate the efficiency of the algorithm.
  • 上村 卓史, 喜田 拓也, 有村 博紀
    電子情報通信学会論文誌. D, 情報・システム 91 3 595 - 607 一般社団法人電子情報通信学会 2008年03月 [査読無し][通常論文]
  • Takeaki Uno, Hiroki Arimura
    ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PROCEEDINGS 5012 357 - + 2008年 [査読有り][通常論文]
     
    Mining frequently appearing patterns in a database is a basic problem in recent informatics, especially in data mining. Particularly, when the input database is a collection of subsets of an itemset, called transaction, the problem is called the frequent itemset mining problem, and it has been extensively studied. The items in a frequent itemset appear in many records simultaneously, thus they can be considered to be a cluster with respect to these records. However, in this sense, the condition that every item appears in each record is quite strong. We should allow for several missing items in these records. In this paper, we approach this problem from the algorithm theory, and consider the model that can be solved efficiently and possibly valuable in practice. We introduce ambiguous frequent itemsets which allow missing items in their occurrence records. More precisely, for given thresholds theta and sigma, an ambiguous frequent itemset P has a transaction set T, |T| >= sigma, such that on average, transactions in T include ratio theta of items of P. We formulate the problem of enumerating ambiguous frequent itemsets, and propose an efficient polynomial delay polynomial space algorithm. The practical performance is evaluated by computational experiments. Our algorithm can be naturally extended to the weighted version of the problem. The weighted version is a natural extension of the ordinary frequent itemset to weighted transaction databases, and is equivalent to finding submatrices with large average weights in their cells. An implementation is available at the author's homepage(1).
  • Shin-ichi Minato, Takeaki Uno, Hiroki Arimura
    ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PROCEEDINGS 5012 234 - + 2008年 [査読有り][通常論文]
     
    Frequent itemset mining is one of the fundamental techniques for data mining and knowledge discovery. In the last decade, a number of efficient algorithms have been presented for frequent itemset mining, but most of them focused on only enumerating the itemsets that satisfy the given conditions, and how to store and index the mining result in order to ensure an efficient data analysis is a different matter. In this paper, we propose a fast algorithm for generating very large-scale all/closed/maximal frequent itemsets using Zero-suppressed BDDs (ZBDDs), a compact graph-based data structure. Our method, "LCM over ZBDDs," is based on one of the most efficient state-of-the-art algorithms proposed thus far. Not only does it enumerate/list the itemsets, but it also generates a compact output data structure on the main memory. The result can be efficiently postprocessed by using algebraic ZBDD operations. The original LCM is known as an output linear time algorithm, but our new method requires a sub-linear time for the number of frequent patterns when the ZBDD-based data compression works well. Our method will greatly accelerate the data mining process and this will leads to a new style of on-memory processing for dealing with knowledge discovery problems.
  • Hiroki Arimura
    ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PROCEEDINGS 5012 2 - + 2008年 [査読有り][通常論文]
     
    In this talk, we study effcient algorithms that find frequent patterns and maximal (or closed) patterns from large collections of semi-structured data. We review basic techniques developed by the authors, called the rightmost expansion and the PPC-extension, respectively, for designing efficient frequent and maximal/closed pattern mining algorithms for large semi-structured data. Then, we discuss their applications to design of polynomial-delay and polynomial-space algorithms for frequent and maximal pattern mining of sets, sequences, trees, and graphs.
  • Takashi Uemura, Daisuke Ikeda, Hiroki Arimura
    DISCOVERY SCIENCE, PROCEEDINGS 5255 319 - + 2008年 [査読有り][通常論文]
     
    In this paper, we study a content-based spam detection for a specific type of spans, called blog and bulletin board spans. We develop an efficient unsupervised algorithm DCE that detects span documents from a mixture of spam and non-span documents using an entropy-like measure, called the document complexity. Using suffix trees, the algorithm computes the document complexity for all documents in linear time w.r.t. the total length of input documents. Experimental results showed that our algorithm especially works well for detecting word salad spans, which are believed to be difficult to detect automatically.
  • 擬似頻出アイテムの集合の多項式遅延列挙アルゴリズム
    宇野 毅明, 有村 博紀
    第4回 人工知能学会 データマイニングと統計数理研究会(SIG-DMSM), 2007 2007年07月 [査読無し][招待有り]
  • Tatsuya Asai, Kenji Abe, Shinji Kawasoe, Hiroki Arimura, Setsuo Arikawa
    NEW FRONTIERS IN ARTIFICIAL INTELLIGENCE 3609 29 - + 2007年 [査読有り][通常論文]
     
    In this paper, we study an online data mining problem from streams of semi-structured data such as XML data. Modeling semi-structured data and patterns as labeled ordered trees, we present an online algorithm StreamT that receives fragments of an unseen possibly infinite semi-structured data in the document order through a data stream, and can return the current set of frequent patterns immediately on request at any time. We give modifications of the algorithm to other online mining models. Furthermore we implement our algorithms in different online models and candidate management strategies, then show empirical analyses to evaluate the algorithms.
  • Takeaki Uno, Hiroki Arimura
    DISCOVERY SCIENCE, PROCEEDINGS 4755 219 - + 2007年 [査読有り][通常論文]
     
    Mining frequently appearing patterns in a database is a basic problem in informatics, especially in data mining. Particularly, when the input database is a collection of subsets of an itemset, the problem is called the frequent itemset mining problem, and has been extensively studied. In the real-world use, one of difficulties of frequent itemset mining is that real-world data is often incorrect, or missing some parts. It causes that some records which should include a pattern do not have it. To deal with real-world problems, one can use an ambiguous inclusion relation and find patterns which are mostly included in many records. However, computational difficulty have prevented such problems from being actively used in practice. In this paper, we use an alternative inclusion relation in which we consider an itemset P to be included in an itemset T if at most k items of P are not included in T, i.e., vertical bar P\T vertical bar <= k. We address the problem of enumerating frequent itemsets under this inclusion relation and propose an efficient polynomial delay polynomial space algorithm. Moreover, To enable us to skip many small non-valuable frequent itemsets, we propose an algorithm for directly enumerating frequent itemsets of a certain size.
  • Hiroki Arimura, Takeaki Uno, Shinichi Shimozon
    DISCOVERY SCIENCE, PROCEEDINGS 4755 42 - + 2007年 [査読有り][通常論文]
     
    A geometric graph is a labeled graph whose vertices are points in the 2D plane with an isomorphism invariant under geometric transformations such as translation, rotation, and scaling. While Kuramochi and Karypis (ICDM2002) extensively studied the frequent pattern mining problem for geometric subgraphs, the maximal graph mining has not been considered so far. In this paper, we study the maximal (or closed) graph mining problem for the general class of geometric graphs in the 2D plane by extending the framework of Kuramochi and Karypis. Combining techniques of canonical encoding and a depth-first search tree for the class of maximal patterns, we present a polynomial delay and polynomial space algorithm, MaxGeo, that enumerates all maximal subgraphs in a given input geometric graph without duplicates. This is the first result establishing the output-sensitive complexity of closed graph mining for geometric graphs. We also show that the frequent graph mining problem is also solvable in polynomial delay and polynomial time.
  • Tomoya Saito, Takuya Kida, Hiroki Arimura
    2007 IEEE INTERNATIONAL WORKSHOP ON DATABASES FOR NEXT GENERATION RESEARCHERS 13 - + 2007年 [査読有り][通常論文]
     
    In this paper, we study a complex pattern matching problem over a single continuous stream of numerical values. Based on bit-parallel technique for string matching, we propose an efficient algorithm called BPS (Bit-Parallel matching on Streams) that finds the set of all occurrences of a given pattem of length m in an input stream of length n in 0 (1/w mn) time for ordered values and in 0 (1/w mn log m) time for real values over a fixed data range, where w is the bit-width of registers. This time complex properly improves the time complexity, 0 (ran) of the previous algorithms. The keys of the algorithm are fast NFA simulation based on bit-parallel operation and hit predicate table lookup technique. We also present empirical analysis to evaluate the performance of the algorithm showing that the proposed algorithm is twice as fast as and more stable than the previous algorithms.
  • 大規模テキストマイニングのための特徴部分列抽出と極大パター ン発見を組み合わせた効率的アルゴリズム,
    有村 博紀, 宇野 毅明
    第63回人工知能学会人工知能基礎問題研究会 45 - 52 2006年09月 [査読無し][通常論文]
  • 2次元離散テキストからの効率よい極大パターンマイニング
    下薗 真一, 宇野 毅明, 有村 博紀
    第63回人工知能学会人工知能基本問題研究会 2006年09月 [査読無し][招待有り]
  • 上村 卓史, 喜田 拓也, 有村 博紀
    情報科学技術レターズ 5 5 - 8 FIT(電子情報通信学会・情報処理学会)運営委員会 2006年08月 [査読無し][通常論文]
  • Joerg Rothe, Hiroki Arimura
    JOURNAL OF UNIVERSAL COMPUTER SCIENCE 12 6 579 - 580 2006年 [査読有り][通常論文]
  • H Arimura, S Jain
    THEORETICAL COMPUTER SCIENCE 348 1 1 - 2 2005年12月 [査読無し][招待有り]
  • 有村 博紀
    電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 88 3 563 - 575 一般社団法人電子情報通信学会 2005年03月 [査読無し][通常論文]
  • 宇野 毅明, 有村 博紀
    統計数理 53 2 317 - 329 統計数理研究所 2005年 [査読無し][通常論文]
  • 有村 博紀, 喜田 拓也
    情報処理 46 1 4 - 11 一般社団法人情報処理学会 2005年01月 [査読無し][通常論文]
  • S Minato, H Arimura
    International Workshop on Challenges in Web Information Retrieval and Integration, Proceedings 4 - 11 2005年 [査読有り][通常論文]
     
    Manipulation of large-scale combinatorial data is one of the important fundamental technique for web information retrieval, integration, and mining. In this paper we propose a new approach based on BDDs (Binary Decision Diagrams) for database analysis problems. BDDs are graph-based representation of Boolean functions, now widely used in system design and verification area. Here we focus on Zero-suppressed BDDs (ZBDDs), a special type of BDDs, which are suitable for handling large-scale sets of combinations. Using ZBDDs, we can implicitly enumerate combinatorial item set data and efficiently compute set operations over the ZBDDs. We present some encouraging experimental results of frequent item set mining problem for practical benchmark examples, some of which have never been generated by previous method.
  • Satoshi Morinaga, Hiroki Arimura, Takahiro Ikeda, Yosuke Sakao, Susumu Akamine
    Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 666 - 671 2005年 [査読有り][通常論文]
     
    We propose a new text mining system which extracts characteristic contents from given documents. We define Key semantics as characteristic sub-structures of syntactic dependencies in the given documents, and consider the following three tasks in this paper: 1) Key semantics extraction: extracting characteristic syntactic dependency structures not only as ordered trees but also as unordered trees and free trees, 2) Redundancy reduction: from the result of extraction, deleting redundant dependency structures such as sub-structures or equivalent structures of the others, and 3) Phrase/sentence reconstruction: generating a phrase or sentence in a natural language corresponding to the extracted structure. Our system is a combination of natural language processing techniques and tree mining techniques. The system consists of the following five units: 1) syntactic dependency analysis unit, 2) input filters, 3) characteristic ordered subtree extraction unit, 4) output filters, and 5) phrase/sentence reconstruction unit. Although ordered trees are extracted in the third unit, the overall behavior of the system can be switched into the extraction of ordered trees, unordered trees, or free trees depending on which of the input filters is/are applied in the second step. The output filters delete redundant trees from the extraction, result for efficient knowledge discovery. Finally, phrases or sentences corresponding to the extracted subtrees are reconstructed by utilizing the input documents. We demonstrate the validity of our system by showing experimental results using real data collected at a help desk and TDT pilot corpus. Copyright 2005 ACM.
  • H Arimura, T Uno
    ALGORITHMS AND COMPUTATION 3827 724 - 737 2005年 [査読有り][通常論文]
     
    In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in (Parida et al., CPM'01), (Pisanti et al.,MFCS'03) and (Pelfrene et al., CPM'03), its output-polynomial time computability is still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n with O(n(3)) time per motif with O(n(2)) space and O(n(3)) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lowerbound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach.
  • T Asai, K Abe, S Kawasoe, H Sakamoto, H Arimura, S Arikawa
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E87D 12 2754 - 2763 2004年12月 [査読有り][通常論文]
     
    In this paper, we consider a data mining problem for semistructured data. Modeling semi-structured data as labeled ordered trees, we present an efficient algorithm for discovering frequent substructures from a large collection of semi-structured data. By extending the enumeration technique developed by Bayardo (SIGMOD'98) for discovering long itemsets, our algorithm scales almost linearly in the total size of maximal tree patterns contained in an input collection depending mildly on the size of the longest pattern. We also developed several pruning techniques that significantly speed-up the search. Experiments on Web data show that our algorithm runs efficiently on real-life datasets combined with proposed pruning techniques in the wide range of parameters.
  • 頻出・飽和・極大頻出集合の効率的な列挙アルゴリズムとその実装
    宇野 毅明, 有村 博紀
    日本ソフトウェア科学会, 第4回データマイニングワークショップ 47 - 54 2004年09月 [査読無し][通常論文]
  • 山田 泰寛, 池田 大輔, 坂本 比呂志, 有村 博紀
    人工知能学会誌 19 3 302 - 310 社団法人人工知能学会 2004年05月01日 [査読無し][通常論文]
  • LCM: 頻出飽和アイテム集合を列挙する高速なアルゴリズム
    宇野 毅明, 内田 雄三, 浅井 達哉, 有村 博紀
    第54回人工知能学会人工知能基礎論研究会 23 - 29 2004年03月 [査読無し][通常論文]
  • 半構造データマイニングのための高速な無順序木パターン発見手法
    房延慎二, 浅井達哉, 有村博紀, 宇野毅明, 中野眞一
    第15回データ工学ワークショップ(DEWS2004) 2004年03月 [査読無し][通常論文]
  • Practical Techniques for Speeding Up Enumeration Algorithms for Frequent Itemset Mining Problems
    宇野 毅明, 浅井 達哉, 有村 博紀, 内田 雄三
    第94回情報処理学会アルゴリズム研究会 49 - 56 2004年03月 [査読無し][通常論文]
  • 浅井 達哉, 有村 博紀
    電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 87 2 79 - 96 一般社団法人電子情報通信学会 2004年02月 [査読無し][通常論文]
  • Takeaki Uno, Masashi Kiyomi, Hiroki Arimura
    FIMI '04, Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations, Brighton, UK, November 1, 2004 CEUR-WS.org 2004年 [査読有り][通常論文]
  • T Uno, T Asai, Y Uchida, H Arimura
    DISCOVERY SCIENCE, PROCEEDINGS 3245 16 - 31 2004年 [査読有り][通常論文]
     
    The class of closed patterns is a well known condensed representations of frequent patterns, and have recently attracted considerable interest. In this paper, we propose an efficient algorithm LCM (Linear time Closed pattern Miner) for mining frequent closed patterns from large transaction databases. The main theoretical contribution is our proposed prefix-preserving closure extension of closed patterns, which enables us to search all frequent closed patterns in a depth-first manner, in linear time for the number of frequent closed patterns. Our algorithm do not need any storage space for the previously obtained patterns, while the existing algorithms needs it. Performance comparisons of LCM with straightforward algorithms demonstrate the advantages of our prefix-preserving closure extension.
  • H Sakamoto, K Hirata, H Arimura
    THEORETICAL COMPUTER SCIENCE 298 1 21 - 50 2003年04月 [査読有り][通常論文]
     
    The elementary formal system (EFS) is a kind of logic programs which directly manipulates strings, and the learnability of the subclass called hereditary EFSs (HEFSs) has been investigated in the frameworks of the PAC-learning, query-learning, and inductive inference models. The hierarchy of HEFS is expressed by HEFS(m,k,t,r), where m, k, t and r denote the number of clauses, the occurrences of variables in the head, the number of atoms in the body, and the arity of predicate symbols. The present paper deals with the learnability of HEFS in the query learning model using equivalence queries and additional queries such as membership, predicate membership, entailment membership, and dependency queries. We show that the class HEFS(*, k, t, r) is polynomial-time learnable with the equivalence and predicate membership queries and the class HEFS(*,k,*,r) with termination property is polynomial-time learnable with the equivalence, entailment membership, and dependency queries for the unbounded parameter *. A lowerbound on the number of queries is presented. We also show that the class HEFS(*,k,t,r) is hard to learn with the equivalence and membership queries under the cryptographic assumptions. Furthermore, the learnability of the class of unions of regular pattern languages, which is a subclass of HEFSs, is investigated. The bounded unions of regular pattern languages are polynomial-time predictable with membership query. However, all unbounded unions of regular pattern languages are not polynomial-time predictable with membership queries if neither are the DNF formulas. (C) 2002 Published by Elsevier Science B.V.
  • Takeaki Uno, Tatsuya Asai, Yuzo Uchida, Hiroki Arimura
    FIMI '03, Frequent Itemset Mining Implementations, Proceedings of the ICDM 2003 Workshop on Frequent Itemset Mining Implementations, 19 December 2003, Melbourne, Florida, USA CEUR-WS.org 2003年 [査読有り][通常論文]
  • T Asai, H Arimura, T Uno, S Nakano
    DISCOVERY SCIENCE, PROCEEDINGS 2843 47 - 61 2003年 [査読有り][通常論文]
     
    In this paper, we study a frequent substructure discovery problem in semi-structured data. We present an efficient algorithm Unot that computes all frequent labeled unordered trees appearing in a large collection of data trees with frequency above a user-specified threshold. The keys of the algorithm are efficient enumeration of all unordered trees in canonical form and incremental computation of their occurrences. We then show that Unot discovers each frequent pattern T in O(kb(2)m) per pattern, where k is the size of T, b is the branching factor of the data trees, and m is the total number of occurrences of T in the data trees.
  • 有村 博紀, 坂本 比呂志
    応用数理 12 4 366 - 378 一般社団法人日本応用数理学会 2002年12月25日 [査読無し][通常論文]
  • 池田 大輔, 坂本 比呂志, 有村 博紀
    システム/制御/情報 : システム制御情報学会誌 46 4 177 - 183 システム制御情報学会 2002年04月15日 [査読無し][通常論文]
  • T Asai, K Abe, S Kawaoe, H Arimura, H Sakamoto, S Arikawa
    PROCEEDINGS OF THE SECOND SIAM INTERNATIONAL CONFERENCE ON DATA MINING 158 - 174 2002年 [査読有り][通常論文]
  • Kenji Abe, Shinji Kawasoe, Tatsuya Asai, Hiroki Arimura, Setsuo Arikawa
    Principles of Data Mining and Knowledge Discovery, 6th European Conference, PKDD 2002, Helsinki, Finland, August 19-23, 2002, Proceedings 1 - 14 Springer 2002年 [査読有り][通常論文]
  • T Asai, H Arimura, K Abe, S Kawasoe, S Arikawa
    2002 IEEE INTERNATIONAL CONFERENCE ON DATA MINING, PROCEEDINGS 27 - 34 2002年 [査読有り][通常論文]
     
    In this paper, we study an online data mining problem from streams of semi-structured data such as XML data. Modeling semi-structured data and patterns as labeled ordered trees, we present an online algorithm StreamT that receives fragments of an unseen possibly infinite semi-structured data in the document order through a data stream, and can return the current set of frequent patterns immediately on request at any time. A crucial part of our algorithm is the incremental maintenance of the occurrences of possibly frequent patterns using a tree sweeping technique. We give modifications of the algorithm to other online mining model. We present theoretical and empirical analyses to evaluate the performance of the algorithm.
  • Hiroshi Sakamoto, Hiroki Arimura, Setsuo Arikawa
    Progress in Discovery Science, Final Report of the Japanese Discovery Science Project 586 - 599 Springer 2002年 [査読有り][通常論文]
  • Hiroki Arimura, Hiroshi Sakamoto, Setsuo Arikawa
    Progress in Discovery Science, Final Report of the Japanese Discovery Science Project 123 - 139 Springer 2002年 [査読有り][通常論文]
  • H Arimura
    COMBINATORIAL PATTERN MATCHING 2373 17 - 19 2002年 [査読有り][通常論文]
  • Mining Frequent Substructures from Web
    Kenji Abe, Shinji Kawasoe, Tatsuya Asai, Hiroki Arimura, Hiroshi Sakamoto, Setsuo Arikawa
    Active Mining - New Directions of Data Mining 79 83 - 94 2002年 [査読有り][通常論文]
  • Efficiently Mining Frequent Substructures from Semi-structured Data
    Tatsuya Asai, Kenji Abe, Shinji Kawasoe, Hiroshi Sakamoto, Hiroki Arimura, Setsuo Arikawa
    Proc. International Workshop on Informations & Electrical Engineering (IWIE2002) 59 - 64 2002年 [査読有り][通常論文]
  • 安積 裕樹, 川副 真治, 安部 潤一郎, 有村 博紀, 有川 節夫
    情報処理学会論文誌. 数理モデル化と応用 42 14 14 - 24 一般社団法人情報処理学会 2001年12月15日 [査読無し][通常論文]
     
    本稿では, 分散記憶型並列計算機上での効率の良い全文索引構築法について考察する.接尾辞配列は, 最近提案された高機能全文索引であり, 情報検索や遺伝子情報などに広い応用を持つ.本稿では, 分散記憶型並列計算機上での効率の良い接尾辞配列構築法を提案する.Baeza-Yates-Gonnet-Sinder(BGS)アルゴリズムは, 最も広く使われている外部記憶上の構築アルゴリズムである.このBGSアルゴリズムを並列化し, 効率の良い並列構築アルゴリズムを与える.このアルゴリズムは, 並列計算機時間と通信量に関して, BGSの最適な並列化になっており, 従来からあるBGSの並列版のRiberio-Kitajima-Ziviani(RKZ)アルゴリズムに比べてより高速である.
  • 村上 義継, 坂本 比呂志, 有村 博紀, 有川 節夫
    情報処理学会論文誌. 数理モデル化と応用 42 14 39 - 49 一般社団法人情報処理学会 2001年12月 [査読無し][通常論文]
  • 坂本 比呂志, 有村 博紀
    人工知能学会誌 16 2 233 - 238 社団法人人工知能学会 2001年03月01日 [査読無し][通常論文]
  • 那須川 哲哉, 河野 浩之, 有村 博紀
    人工知能学会誌 16 2 201 - 211 社団法人人工知能学会 2001年03月01日 [査読無し][通常論文]
  • Akihiro Yamamoto, Kimihito Ito, Akira Ishino, Hiroki Arimura
    Inductive Logic Programming, 11th International Conference, ILP 2001, Strasbourg, France, September 9-11, 2001, Proceedings 240 - 247 Springer 2001年 [査読有り][通常論文]
  • Hiroshi Sakamoto, Yoshitsugu Murakami, Hiroki Arimura, Setsuo Arikawa
    Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference, May 21-23, 2001, Key West, Florida, USA 264 - 268 AAAI Press 2001年 [査読有り][通常論文]
  • Katsuaki Taniguchi, Hiroshi Sakamoto, Hiroki Arimura, Shinichi Shimozono, Setsuo Arikawa
    Discovery Science, 4th International Conference, DS 2001, Washington, DC, USA, November 25-28, 2001, Proceedings 378 - 388 Springer 2001年 [査読有り][通常論文]
  • Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, Kunsoo Park
    Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1-4, 2001 Proceedings 181 - 192 Springer 2001年 [査読有り][通常論文]
  • Hiroki Arimura, Hiroki Asaka, Hiroshi Sakamoto, Setsuo Arikawa
    Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1-4, 2001 Proceedings 152 - 156 Springer 2001年 [査読有り][通常論文]
  • Hiroki Arimura, Hiroshi Sakamoto, Setsuo Arikawa
    Algorithmic Learning Theory, 12th International Conference, ALT 2001, Washington, DC, USA, November 25-28, 2001, Proceedings 315 - 331 Springer 2001年 [査読有り][通常論文]
  • T Shinohara, H Arimura
    THEORETICAL COMPUTER SCIENCE 241 1-2 191 - 209 2000年06月 [査読有り][通常論文]
     
    A pattern is a string consisting of constant symbols and variables. The language of a pattern is the set of constant strings obtained by substituting nonempty constant strings for variables in the pattern. In this paper we consider the inductive inference of unbounded unions of pattern languages from positive data. For any fixed k, the class of unions of at most k pattern languages is already shown to be inferable from positive data. The class of unbounded unions is not inferable, because any pattern with at least one variable defines an infinite language and any constant string defines a singleton Set consisting of itself, and therefore, the class of unions becomes super-finite, that is, it contains all the finite languages and at least one infinite language. In this paper, we consider several restrictions on patterns to investigate the inferability of unbounded unions of their languages from positive data. A proper pattern contains at least one variable. A regular pattern contains at most one occurrence of every variable. Although the class of unbounded unions of proper pattern languages is not super-finite, it is shown not to be inferable from positive data, even if patterns are restricted to be regular or one-variable. When regular patterns are restricted to be of the form "xwy", where x and y are variables and w is a constant string, the class of unbounded unions is shown to be inferable from positive data. When regular patterns do not contain more than l consecutive occurrences of constant symbols, for some fixed l, the class of unbounded unions is shown to be inferable from positive data. Extended pattern languages, where substitutions of the empty string for some variables are allowed, are also considered from the viewpoint of relationship to the inferability of unbounded unions of non-extended pattern languages. (C) 2000 Elsevier Science B.V. All rights reserved.
  • Tatsuya Akutsu, Hiroki Arimura, Shinichi Shimozono
    RECOMB 2000 1 - 7 2000年 [査読有り][通常論文]
  • R Fujino, H Arimura, S Arikawa
    KNOWLEDGE DISCOVERY AND DATA MINING, PROCEEDINGS 1805 281 - 293 2000年 [査読有り][通常論文]
     
    This paper considers the problem of finding all frequent phrase association patterns in a large collection of unstructured texts, where a phrase association pattern is a set of consecutive sequences of arbitrary number of keywords which appear together in a document. For the ordered and the unordered versions of phrase association patterns, we present efficient algorithms, called Levelwise-Scan, based on the sequential counting technique of Apriori algorithm. To cope with the problem of the huge feature space of phrase association patterns, the algorithm uses the generalized suffix tree and the pattern matching automaton. By theoretical and empirical analyses, we show that the algorithms runs quickly on most random texts for a wide range of parameter values and scales up for large disk-resident text databases.
  • H Arimura, J Abe, R Fujino, H Sakamoto, S Shimozono, S Arikawa
    2000 KYOTO INTERNATIONAL CONFERENCE ON DIGITAL LIBRARIES: RESEARCH AND PRACTICE, PROCEEDINGS 220 - 226 2000年 [査読有り][通常論文]
     
    This paper describes applications of the optimized pattern discovery framework to text and Web mining. In particular, we introduce a class of simple combinatorial patterns over phrases, called proximity phrase association patterns, and consider the problem of finding the patterns that optimize a given statistical measure within the whole class of patterns in a large collection of unstructured texts. For this class of patterns, we develop fast and robust text mining algorithms based on techniques in computational geometry and string matching. Finally, we successfully apply the developed text mining algorithms to the experiments on interactive document browsing in a large text database and keyword discovery from Web bases.
  • Hiroki Arimura, Hiroshi Sakamoto, Setsuo Arikawa
    Inductive Logic Programming, 10th International Conference, ILP 2000, Work-in-progress reports, London, UK, July 2000, Proceedings CEUR-WS.org 2000年 [査読有り][通常論文]
  • H Sakamoto, H Arimura, S Arikawa
    GRAMMATICAL INFERENCE: ALGORITHMS AND APPLICATIONS 1891 241 - 255 2000年 [査読有り][通常論文]
     
    Two models for simple translation between ordered trees are introduced. First is that output is obtained from input by renaming labels and deleting nodes. Several decision problems on the translation are proved to be tractable and intractable. Second is term rewriting system, called k-variable linear translation. The efficient learnability of this system using membership and equivalence queries is shown.
  • S Shimozono, H Arimura, S Arikawa
    NEW GENERATION COMPUTING 18 1 49 - 60 2000年 [査読有り][通常論文]
     
    We study efficient discovery of proximity word-association patterns, defined by a sequence of strings and a proximity gap, from a collection of texts with the positive and the negative labels. We present an algorithm that finds all d-strings k-proximity word-association patterns that maximize the number of texts whose matching agree with their labels. It runs in expected time complexity O(k(d-1) n log(d) n) and space O(k(d-1)n) with the total length n of texts, if texts are uniformly random strings. We also show that the problem to find one of the best word-association patterns with arbitrarily many strings is MAX SNP-hard.
  • T Takae, M Chikamune, H Arimura, A Shinohara, H Inoue, S Takeya, K Uezono, T Kawasaki
    DISCOVERY SCIENCE, PROCEEDINGS 1721 359 - 361 1999年 [査読有り][通常論文]
  • H Arimura, A Wataki, R Fujino, S Araikawa
    ALGORITHMIC LEARNING THEORY 1501 247 - 261 1998年 [査読有り][通常論文]
     
    We consider a data mining problem in a large collection of unstructured texts based on association rules over subwords of texts. A tare-words association pattern is an expression such as (TATA, 30, AGGAGGT) --> C that expresses a rule that if a text contains a subword TATA followed by another subword AGGAGGT with distance no more than 30 letters then a property C will hold with high probability. The optimized confidence pattern problem is to compute frequent patterns (alpha, kappa, beta) that optimize the confidence with respect to a given collection of texts. Although this problem is solved in polynomial time by a straightforward algorithm that enumerates all the possible patterns in time O(n(5)), we focus-on the development of more efficient algorithms that can be applied to large text databases. We present an algorithm that solves the optimized confidence pattern problem in time O(max{k, m}n(2)) and space O(kn), where m and n are the number and the total length of classification examples, respectively, and Ic is a small constant around 30 similar to 50. This algorithm combines the suffix tree data structure in combinatorial string matching and the orthogonal range query technique in computational geometry for fast computation. Furthermore for most random texts like DNA sequences, we show that a modification of the algorithm runs very efficiently in time O(knlog(3) n) and space O(kn). We also discuss some heuristics such as' sampling and pruning as practical improvement. Then, we evaluate the efficiency and the performance of the algorithm with experiments on;genetic sequences. A relationship with efficient Agnostic PAC-learning is also discussed.
  • H Arimura, A Wataki, R Fujino, S Shimozono, S Arikawa
    DISCOVERY SCIENCE 1532 393 - 394 1998年 [査読有り][通常論文]
     
    In this poster, we present demonstration of a prototype system for efficient discovery of combinatorial patterns, called proximity word-association patterns, from a collection of texts. The algorithm computes the best k-proximity d-word patterns in almost linear expected time in the total input length n, which is drastically faster than a straightforward algorithm of O(n(2d+l)) time complexity.
  • H Ishizaka, H Arimura, T Shinohara
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 23 1-2 101 - 115 1998年 [査読有り][通常論文]
     
    This paper is concerned with the problem of finding a hypothesis in TP2 consistent with given positive and negative examples. The hypothesis class TP2 consists of all sets of at most two tree patterns and represents the class of unions of at most two tree pattern languages. Especially, we consider the problem from the point of view of the consistency problem for TP2. The consistency problem is a problem for deciding whether there exists a consistent hypothesis with given positive and negative examples within some fixed hypothesis space. Efficient solvability of that problem is closely related to the possibility of efficient machine learning or machine discovery. Unfortunately, however, the consistency problem is known to be NP-complete for many hypothesis spaces. In this paper, the problem for the class TP2 is also shown to be NP-complete. In order to overcome this computational hardness, we try to use additional information obtained by making queries. First, we give an algorithm that, using restricted subset queries, solves the consistency problem for TP2 in time polynomial in the total size of given positive and negative examples. Next, we show that each subset query made by the algorithm can be replaced by several membership queries under some condition on a set of function symbols. As a result, we have that the consistency problem for TP2 is solved in polynomial time using membership queries.
  • H Arimura, S Shimozono
    ALGORITHMS AND COMPUTATIONS 1533 39 - 48 1998年 [査読有り][通常論文]
     
    We study the efficient discovery of word-association patterns, defined by a sequence of strings and a proximity gap, from a collection of texts with binary labels. We present an algorithm that finds all d strings and Ic proximity word-association patterns that maximizes agreement with the labels. It runs in expected time complexity O(k(d-1)nlog(d+1) n) and O(k(d-1)n) space with the total length n of texts, if texts are uniformly random strings. We also show that the problem to find a best word-association pattern with arbitrarily many strings is MAX SNP-hard.
  • H Arimura, H Ishizaka, T Shinohara
    THEORETICAL COMPUTER SCIENCE 185 1 47 - 62 1997年10月 [査読有り][通常論文]
     
    This paper investigates efficient learning of TPk, the class of collections of at most k first-order terms, where each collection defines the union of the sets of ground instances of each first-order term in the collection. We present an algorithm that exactly learns every concept in TPk in polynomial time in k and n using equivalence and membership queries, where n is the size of the longest counterexample given so far. We also show some lower bound results on the number of queries, and apply our result to learning restricted version of logic programs whose computational mechanisms are only disjunctive definition and unification.
  • H ARIMURA, T SHINOHARA, S OTSUKI
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E75D 4 426 - 434 1992年07月 [査読有り][通常論文]
     
    In this paper, we consider the polynomial time inferability from positive data for unions of two tree pattern languages. A tree pattern is a structured pattern known as a term in logic programming, and a tree pattern language is the set of all ground instances of a tree pattern. We present a polynomial time algorithm to find a minimal union of two tree pattern languages containing given examples. Our algorithm can be considered as a natural extension of Plotkin's least generalization algorithm, which finds a minimal single tree pattern language. By using this algorithm, we can realize a consistent and conservative polynomial time inference machine that identifies unions of two tree pattern languages from positive data in the limit.
  • Iku Ohama, Takuya Kida, Hiroki Arimur
    Proc. 2015 SIAM International Conference on Data Mining (SDM'15) 9  [査読有り][通常論文]

書籍

  • 言語処理学事典
    有村 博紀 (担当:分担執筆範囲:「半構造化されたテキストからの情報抽出」)
    共立出版 2009年12月
  • Computational Challenges of Massive Data Sets and Randomness in Computation, Special Issue on the First and Second Japanese-German Frontiers of Science Symposia
    Hiroki Arimura 
    Journal of Universal Computer Science, Vol. 12, issue 6, 579-761 2006年07月
  • 人工知能学辞典,(編)人工知能学会,共立出版,2005.
    有村 博紀 (担当:分担執筆範囲:小項目「テキストマイニング」)
    共立出版 2005年12月
  • 第11回計算論的学習理論国際会議会議録
    有村 博紀 (担当:編者(編著者))
    Springer-Verlag 2000年10月

その他活動・業績

  • 岩下 洋哲, 高木 拓也, 鈴木 浩史, 後藤 啓介, 大堀 耕太郎, 有村 博紀 人工知能基本問題研究会 111 40 -45 2020年01月29日 [査読無し][通常論文]
  • Subgraph Enumeration: Efficient Algorithms and Empirical Studies
    Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura The 2nd International Workshop on Enumeration Problems & Application 2018年11月06日 [査読無し][通常論文]
  • 栗田 和宏, Alessio Conte, 和佐 州洋, 宇野 毅明, 有村 博紀 第80回全国大会講演論文集 2018 (1) 347 -348 2018年03月13日 [査読無し][通常論文]
     
    内周はグラフに含まれる最小の閉路長を表し,グラフの内周を計算する問題はよく研究されている.ItaiとRodehは一般グラフの内周を計算する非自明な最初のアルゴリズムを開発した.このアルゴリズムは最悪時O(nm)時間で動作し,平均時間O(n^2)時間で動作する.重みなし平面グラフに対しては,DjidjevがO(n^{5/4} log n)時間アルゴリズムを与え,Changらがこのアルゴリズムを改良し線形時間アルゴリズムを与えた.我々の知る限りでは大きな内周を持つ連結な部分グラフを列挙するアルゴリズムは存在しない.本論文では,これらの問題を解く列挙アルゴリズムを与える.このアルゴリズムの単純な拡張により,k以上の内周を持つ重み付きグラフの部分グラフや非連結なグラフの列挙も可能である.
  • 坂上 陽規, 栗田 和宏, 瀧川 一学, 有村 博紀 人工知能基本問題研究会 105 63 -68 2018年01月28日 [査読無し][通常論文]
  • 金森憲太朗, 石畠正和, 湊真一, 有村博紀 人工知能学会人工知能基本問題研究会資料 105th 50‐57 2018年01月22日 [査読無し][通常論文]
  • 坂上陽規, 瀧川一学, 有村博紀 人工知能学会全国大会論文集(CD-ROM) 32nd (0) ROMBUNNO.3Pin1.10 -3Pin110 2018年 [査読無し][通常論文]
     
    <p>グラフ断片決定木(graph frangmented decision trees)は,テストとしてグラフパターンの拡張演算を持つような決定木であり,グラフ決定リストのような1次のグラフパターンをもつグラフ分類規則とみなせる.われわれは,先行研究(坂上他,第105回SIGFPAI研究会)で,gSpanのようなグラフパターン列挙手法を用いずに,グラフ断片決定木を貪欲にトップダウン構築する学習アルゴリズムGFDTを提案した.本稿では,GFDTアルゴリズムをgSpanのようなグラフ属性発見器として用いて,集約学習器(ランダムフォレストRF)と組み合わせた場合の性能を実験的に評価する.実データを用いた実験では,gSpanとRFを組み合わせた手法と比較し,その有用性を調べた.</p>
  • 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 117 (369) 111 -117 2017年12月21日 [査読無し][通常論文]
  • 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 117 (370) 111 -117 2017年12月21日 [査読無し][通常論文]
  • 和佐 州洋, 山中 克久, 有村 博紀 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 115 (84) 81 -86 2015年06月12日 [査読無し][通常論文]
  • 和佐 州洋, 有村 博紀, 宇野 毅明 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 114 (80) 101 -106 2014年06月13日 [査読無し][通常論文]
     
    本稿では,k- 縮退グラフに含まれる誘導木 (連結かつ非巡回な誘導部分グラフ) を,効率よく列挙するアルゴリズムを与える.グラフ G=(V,E) が k-縮退 (k-degenerate) であるとは,G の任意の部分グラフが高々 k の次数を持つ頂点を含むときをいう.これまで,制約のある誘導部分グラフの列挙に関しては,連結な誘導グラフ (Avis,Fukuda,DAM,1996) や,コードレスパス,コードレスサイクル (宇野,第 92 回アルゴリズム研究会,2003) の列挙に関する先行研究があるが,誘導木については知られていない.最大次数が d のとき,誘導木 1 つ当たり O(d) 遅延の列挙アルゴリズムは容易に構成できるが,これをどの程度まで改善できるかは未解決の問題である.我々のアルゴリズムは,入力グラフ G が k- 縮退グラフであるとき,誘導木を 1 つ当たりならし O(k) 時間で列挙する.系として,k が定数ならば,誘導木を 1 つたり,ならし定数時間で列挙可能である.
  • 和佐 州洋, 有村 博紀, 宇野 毅明 電子情報通信学会技術研究報告. COMP, コンピュテーション 114 (80) 101 -106 2014年06月06日 [査読無し][通常論文]
     
    本稿では,k-縮退グラフに含まれる誘導木(連結かつ非巡回な誘導部分グラフ)を,効率よく列挙するアルゴリズムを与える.グラフG=(V,E)がk-縮退(k-degenerate)であるとは,Gの任意の部分グラフが高々kの次数を持つ頂点を含むときをいう.これまで,制約のある誘導部分グラフの列挙に関しては,連結な誘導グラフ(Avis, Fukuda, DAM, 1996)や,コードレスパス,コードレスサイクル(宇野,第92回アルゴリズム研究会,2003)の列挙に関する先行研究があるが,誘導木については知られていない.最大次数がdのとき,誘導木1つ当たりO(d)遅延の列挙アルゴリズムは容易に構成できるが,これをどの程度まで改善できるかは未解決の問題である.我々のアルゴリズムは,入力グラフGがk-縮退グラフであるとき,誘導木を1つ当たりならしO(k)時間で列挙する.系として,kが定数ならば,誘導木を1つたり,ならし定数時間で列挙可能である.
  • 伝住 周平, 川原 純, 津田 宏治, 有村 博紀, 湊 真一, 定兼 邦彦 電子情報通信学会技術研究報告. COMP, コンピュテーション 112 (498) 23 -30 2013年03月11日 [査読無し][通常論文]
     
    多くの実問題の中において,集合族を扱う必要に迫られることはままあることである.大規模な集合族を操作することはウェブからの情報抽出や,情報統合,データマイニングに対する重要な基盤技術である.こういった目的に対し,ゼロサプレス型二分決定グラフ(ZDD)と呼ばれる特別な二分決定グラフ(BDD)が使用されることがある.しかしながらZDDを格納するためには巨大なメモリ領域が必要であり,また所属性判定演算も低速であるという問題がある.本論文では静的なZDDを圧縮した索引である密集ゼロサプレス型二分決定グラフ(DenseZDD)を導大する.この技術では集合族をコンパクトに索引化するだけではなく所属性判定演算も高速に行えるようになる.さらに,DenseZDDと通常のZDDの混成手法により動的な索引を実現する方法も提案する.
  • 和佐 州洋, 有村 博紀, 宇野 毅明, 平田 耕一 研究報告アルゴリズム(AL) 2013 (6) 1 -8 2013年02月22日 [査読無し][通常論文]
     
    本稿では,入力超グラフH = (ν,ε)から超辺縮約をくり返し適用して得られる連結でベルジュ非巡回な部分超グラフの族を考え,そのような部分超グラフすべてを効率よく列挙する初めての多項式遅延と多項式領域列挙アルゴリズムを与える.アルゴリズムは,解となる部分超グラフSの1個あたりO(k1,5mn)時間とO(N)語の領域で,解を列挙する.ここに,k = |S|であり,N = |ε|,m = |ε|,n = |ν|である.そのために,この族に対する還元系列を用いた特徴づけを与える.In this paper we study the problem of enumerating all connected and Berge-acyclic hyperedge-contracted sub-hypergraphs in an input hypergraph. We present the first polynomial delay and polynomial space enumeration algorithm for the problem.
  • 高木 拓也, 上村 卓史, 有村 博紀 情報処理学会研究報告. AL, アルゴリズム研究会報告 2012 (9) 1 -8 2012年10月26日 [査読無し][通常論文]
     
    長さ N のテキストの K ? N 個の索引点に対する接尾辞木を疎接尾辞木 (sparse suffix tree) といい, O(K) 語の領域しか使用しないため,さまざまな応用に用いられている.上村と有村 (Proc. CPM2011, LNCS 6661, 2011) は,長さ N ビットのハフマン圧縮テキストが入力として与えられたとき,その疎接尾辞木を O(σ) 前処理時間と O(K+σ) 語の領域を用いて,オンライン構築するアルゴリズムを与えている.本稿では,ビット並列計算と簡潔トライ構造からなる詰め込み文字列 (packed string) 技法を用いて,長さ O(N) ビットのハフマン圧縮テキストに対して,疎接尾辞木を O(σ) 前処理時間と O(K+σ) 語の領域を用いて, O(?N/w?√w+K√w) 時間でオンライン構築するアルゴリズムを与える.ここに, w は計算機のレジスタ長 (ビット) であり, σ は符号中の符号語長さの総和である.これは,疎接尾辞木のオンライン構築で初めて, O(N) 時間より少ない計算時間を達成したアルゴリズムである.提案手法は, K≦O(N/√w) のときに従来手法より高速である.また,一般の有限接頭符号上や,単語アルファベット上の符号化テキストに対しても拡張可能である.
  • 和佐 州洋, 宇野 毅明, 有村 博紀 電子情報通信学会技術研究報告. COMP, コンピュテーション 112 (24) 25 -32 2012年05月07日 [査読無し][通常論文]
     
    近年,膨大な量の木やグラフといった半構造データからパターンを発見する要求が高まっている.Ferreiraと,Grossi, Rizzi (ESA'11, 275-286, 2011)は,k-部分木列挙問題を考察し,O(k)ならし時間列挙アルゴリズムを与えた.これは,入力グラフGの中に含まれる非巡回なk頂点の連結部分グラフを重複なくすべて出力する問題である.本稿では,入力を木に限定した場合のk-部分木列挙問題を考察する.主結果として,逆探索法に基づき,この問題に対するk-部分木のならし定数時間列挙アルゴリズムを与える.さらに,木に対するグラフモチーフ問題への応用に問しても議論する.
  • 大濱 郁, 飯田 裕美, 喜田 拓也, 有村 博紀 電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習 111 (480) 1 -8 2012年03月05日 [査読無し][通常論文]
     
    本稿では,関係の有無の持つ意味が非対称であり,関係を生成する機会に個体差があるような関係データを分析するための,新しい生成モデルを提案する.提案するモデルでは,各オブジェクトに対して他オブジェクトとの遭遇しやすさを表すパラメータが組み込まれている.そして,サブセットクラスタリングのアイデアに基づき,オブジェクト同士が遭遇した時は,クラスタ固有の分布から,遭遇しなかった場合は,全データで共通の分布から関係が生成される.そのため,購買履歴のようにリンクと非リンクのもつ意味が非対称であり,オブジェクト毎に関係を生成する機会に個体差があるような関係データにおいて,それら非対称性や個体差を吸収してクラスタリングを行うことができる.本稿では,人工データ,実データを用いた実験により,提案するモデルの有効性を示す.
  • 和佐 州洋, 有村 博紀, 伊藤 公人 情報科学技術フォーラム講演論文集 10 (2) 577 -578 2011年09月07日 [査読無し][通常論文]
     
    本稿では,分岐数を限定しない根付き木の確率的生成モデルを提案する.
  • 大濱 郁, 喜田 拓也, 有村 博紀, 阿部 敏久 電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習 110 (476) 9 -16 2011年03月21日 [査読無し][通常論文]
     
    我々は,人間行動履歴の地理的クラスタリングについて議論する.本論文では,この問題を,二次元時系列データのセグメンテーション問題として定式化し,二つのクラスタリング手法,LS-linHMMとX-linHMMを提案する.前者のLS-linHMMは,線形制約付きHMMを用いたクラスタリングと情報量規準を用いたモデル選択を組み合わせ,クラスタ数の自動推定を行う.また,X-linHMMは,x-meansのアイデアを取り入れた2状態線形HMMによる階層的クラスタリングであり,LS-linHMMよりも高速なクラスタリングを実現している.今回,これらの手法を,GPSタグ付き写真コンテンツのクラスタリングに適用することを試みる.また,実データを用いた実験により,単純なx-meansよりも提案手法が効果的に動作することを確認した.
  • 有村 博紀 電子情報通信学会総合大会講演論文集 2011 (2) "SSS -30"-"SSS-31" 2011年02月28日 [査読無し][通常論文]
  • 藤兼 靖之, 金田 悠作, 有村 博紀 電子情報通信学会総合大会講演論文集 2011 (1) 2011年02月28日 [査読無し][通常論文]
  • 柳橋 史成, 伊藤 公人, 有村 博紀 人工知能基本問題研究会 80 25 -31 2010年11月17日 [査読無し][通常論文]
  • 「おめでとうソサイエティ論文賞」ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの効率的解析手法
    湊真一, 有村博紀 電子情報通信学会 情報・システムソサイエティ誌 15 (3) 15 2010年11月 [査読無し][招待有り]
  • 河東 孝, 有村 博紀, 平田 耕一 人工知能基本問題研究会 79 27 -30 2010年09月24日 [査読無し][通常論文]
  • 金田 悠作, 湊 真一, 有村 博紀 情報処理学会研究報告 2010 (1) 2010年06月 [査読無し][通常論文]
  • 金田 悠作, 湊 真一, 有村 博紀 電子情報通信学会技術研究報告. COMP, コンピュテーション 110 (37) 23 -29 2010年05月12日 [査読無し][通常論文]
     
    正規表現は,アルファべットΣの文字と,結合"・"と選択"|"だけから構成されるとき,非巡回正規表現(acyclic regular expression)と呼ばれる.本稿では,非巡回正規表現のクラスに対して,長さmと深さdをもつ非巡回正規表現と長さnをもつ入力テキストを入力として受け取り,O(md)の前処理時間とO(md/w)領域を用いて,O(nmd/w)時間で正規表現照合問題を解く効率よいアルゴリズムを与える.このために,正規表現と等価な非決定性有限オートマトン(NFA)の状態遷移計算をビット演算と加減算を用いて模倣する分配集積演算と呼ぶビット並列計算手法を開発し,WuとManberらのSHIFT-AND手法(CACM 35(10), 1992)を,非巡回正規表現パターンに拡張している.本結果は,定数深さの非巡回正規表現に対して,O(m/w)領域を達成しつつ,一般の正規表現照合に対するBilleのアルゴリズム(ICALP, 2006)のよりも時間計算量が小さい.
  • 金田 悠作, 湊 真一, 有村 博紀 電子情報通信学会総合大会講演論文集 2010 (1) 2010年03月02日 [査読無し][通常論文]
  • 河東 孝, 有村 博紀, 平田 耕一 人工知能基本問題研究会 76 13 -17 2010年01月27日 [査読無し][通常論文]
  • 金 在成, 吉澤 真吾, 金田 悠作, 湊 真一, 有村 博紀, 宮永 喜一 電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム 109 (395) 31 -34 2010年01月19日 [査読無し][通常論文]
     
    FPGA(Field Programmable Gate Array)は製造後も論理回路を再構成することが可能であり,近年ではLSI設計分野以外の研究者や開発者がFPGAを利用して専用計算機の構築する研究例が多く見られる.しかしながら,FPGA研究に参入するには専門のハードウェア知識の習得や設計環境の整備等の障壁を乗り越える必要がある.本報告では,異分野共同研究を円滑に実施するためのeラーニングと連携した遠隔FPGAシステムの開発を行った.本システムは利用者がコンピュータを用意するのみで遠隔でFPGAの設計教育,研究開発,実証利用を行うことができる.本システムの構成およびシステムを利用した共同研究実施例を述べる.
  • 金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一 電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム 109 (395) 131 -136 2010年01月19日 [査読無し][通常論文]
     
    本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成される非消去的正規表現のクラスに対して,O(md log b+m|Σ|)前処理時間とO(md log b/w+m|Σ|/w)領域を用いて,O(mdn log b/w)実行時間の効率的な正規表現照合アルゴリズムを与える.これはd,b,|Σ|が定数の場合に,O(mn/w)実行時間とO(m/w)領域の高速なアルゴリズムを与える.ここで,nは入力長を表し,mと,d,bは,それぞれ,パターンの長さと,深さ,最大戻り幅を,wは計算機のワード長,|Σ|はアルファベットの要素数を表す.さらに,このアルゴリズムを用いて,回路の再構成を伴わずにパターンの変更を可能なハードウェア実装のアーキテクチャを示す.
  • 金 在成, 吉澤 真吾, 金田 悠作, 湊 真一, 有村 博紀, 宮永 喜一 電子情報通信学会技術研究報告. CPSY, コンピュータシステム 109 (394) 31 -34 2010年01月19日 [査読無し][通常論文]
     
    FPGA (Field Programmable Gate Array)は製造後も論理回路を再構成することが可能であり,近年ではLSI設計分野以外の研究者や開発者がFPGAを利用して専用計算機の構築する研究例が多く見られる.しかしながら,FPGA研究に参入するには専門のハードウェア知識の習得や設計環境の整備等の障壁を乗り越える必要がある.本報告では,異分野共同研究を円滑に実施するためのeラーニングと連携した遠隔FPGAシステムの開発を行った.本システムは利用者がコンピュータを用意するのみで遠隔でFPGAの設計教育,研究開発実証利用を行うことができる.本システムの構成およびシステムを利用した共同研究実施例を述べる.
  • 金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一 電子情報通信学会技術研究報告. CPSY, コンピュータシステム 109 (394) 131 -136 2010年01月19日 [査読無し][通常論文]
     
    本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成される非消去的正規表現のクラスに対して,O(md log b+m|Σ|)前処理時間とO(md log b/ω+m|Σ|/ω)領域を用いて,O(mdn log b/ω)実行時間の効率的な正規表現照合アルゴリズムを与える.これはd,b,|Σ]|が定数の場合に,O(mn/ω)実行時間とO(m/ω)領域の高速なアルゴリズムを与える.ここで,nは入力長を表し,mと,d,bは,それぞれ,パターンの長さと,深さ,最大戻り幅を,ωは計算機のワード長,|Σ|はアルファベットの要素数を表す.さらに,このアルゴリズムを用いて,回路の再構成を伴わずにパターンの変更を可能なハードウェア実装のアーキテクチャを示す.
  • 金 在成, 吉澤 真吾, 金田 悠作, 湊 真一, 有村 博紀, 宮永 喜一 電子情報通信学会技術研究報告. VLD, VLSI設計技術 109 (393) 31 -34 2010年01月19日 [査読無し][通常論文]
     
    FPGA (Field Programmable Gate Array)は製造後も論理回路を再構成することが可能であり,近年ではLSI設計分野以外の研究者や開発者がFPGAを利用して専用計算機の構築する研究例が多く見られる.しかしながら,FPGA研究に参入するには専門のハードウェア知識の習得や設計環境の整備等の障壁を乗り越える必要がある.本報告では,異分野共同研究を円滑に実施するためのeラーニングと連携した遠隔FPGAシステムの開発を行った.本システムは利用者がコンピュータを用意するのみで遠隔でFPGAの設計教育,研究開発,実証利用を行うことができる.本システムの構成およびシステムを利用した共同研究実施例を述べる.
  • 金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一 電子情報通信学会技術研究報告. VLD, VLSI設計技術 109 (393) 131 -136 2010年01月19日 [査読無し][通常論文]
     
    本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成させる非消去的正規表現のクラスに対して,O(mdlogb+m|Σ|)前処理時間とO(mdlogb/w+m|Σ|/w)領域を用いて,O(mdlogb/w)領域の高速なアルゴリズムを与える.ここで,nは入力長を表わし,mとd,bは,それぞれ,パターンの長さと,深さ,最大戻り幅を,wは計算機のワード長,|Σ|はアルファベットの要素数を表わす.さらに,このアルゴリズムを用いて,回路の再構成を伴わずにパターンの変更を可能なハードウェア実装のアーキテクチャをしめす.
  • 上村 卓史, 池田 大輔, 有村 博紀 電子情報通信学会総合大会講演論文集 2009 (1) 2009年03月04日 [査読無し][通常論文]
  • 金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一 電子情報通信学会総合大会講演論文集 2009 (1) 2009年03月04日 [査読無し][通常論文]
  • 柳橋 史成, 伊藤 公人, 有村 博紀 情報処理学会研究報告. BIO, バイオ情報学 2009 (25) 29 -32 2009年02月26日 [査読無し][通常論文]
     
    本稿では、葉にラベルを持つ木に対し、枝におけるラベルの差異が最小となるように、内部頂点にラベルを割り当てる問題(OTLAP)を考察する。全ての割り当てを試す自明なアルゴリズムを用いた場合、頂点数nの木にm種類のラベルを最適に割り当てるときの時間計算量はO(m^n)であり,頂点数nの指数時間を要する。そこで本稿では、入力の木に対して,多項式時間で最適ラベリングを計算する動的計画法アルゴリズムDPAOを与える。アルゴリズムの時間計算量は,O(km^2n)時間であり,木の頂点数nに関して線形である.ここに,kは木の最大次数とする.また、提案手法をインフルエンザウイルスの進化系統樹における仮想的分類単位の最適ラベリング問題に応用する。
  • 筒井 淳平, 有村 博紀 情報処理学会研究報告. データベース・システム研究会報告 2008 (88) 241 -246 2008年09月14日 [査読無し][通常論文]
     
    本稿では,GUI上でのXQuery問合せの対話的な構築と編集を考察する.Braga等によるXQueryの視覚言語表現XQBEに基づき,問合せの内部表現として木構造表現TQを提案し,さらに,GUI上での図像表現XQUBEを提案する.解析では,クラスTQとXQUBEが,XQueryの自然な部分クラスTQ-XQueryを表現することを示す.また,この図像表現を用いた具体例に基づく編集と,演示による学習について議論する.
  • 上村 卓史, 池田 大輔, 有村 博紀 電子情報通信学会技術研究報告. DE, データ工学 108 (211) 15 -16 2008年09月14日 [査読無し][通常論文]
     
    本稿では,ブログや掲示板を対象とした内容ベースの効率よいスパムポスト検出手法を提案する.本手法は,与えられた文書集合に対して接尾辞木を用いた確率モデル(確率接尾辞木)を構築し,この文書集合上の推定された出現確率を利用して検出を行う.実際のウェブ上の掲示板データを用いた計算機実験では,提案手法の有効性を示した.特に,現在の技術では検出が比較的困難なスパムであるワードサラダに対する有効性が示された.
  • 上村 卓史, 喜田 拓也, 有村 博紀 情報処理学会論文誌. データベース 1 (1) 49 -60 2008年06月26日 [査読無し][通常論文]
     
    インターネットからの効率的な情報収集においてウェブブラウザの果たす役割は大きい.しかし,膨大な文書の検索および閲覧はユーザにとっていまだ大きな負担である.本論文では,情報収集の補助を目的として,ユーザが閲覧するウェブページからのキーワード抽出という問題について考察する.ここでのキーワードとは,任意の単語の連結(単語Nグラム)である.このため,接尾辞木をもとにした,任意の単語Nグラムを線形領域で表すデータ構造である単語Nグラム木を提案し,これを利用した高速な抽出アルゴリズムを与える.また,抽出されたキーワードを利用することで,得られたキーワードの表示,関連するウェブサイトの表示,検索語の入力候補の提示といった,ユーザのウェブ閲覧を補助するインタフェースを実現する手法を示す.
  • 大谷 英行, 喜田 拓也, 宇野 毅明, 有村 博紀 情報処理学会研究報告. データベース・システム研究会報告 2008 (56) 113 -120 2008年06月12日 [査読無し][通常論文]
     
    巨大なデータ集合の中から,有用な知識や情報を発見するデータマイニングは,現代の様々な分野で重要な技術であり,特に,時系列データを対象とした時系列データマイニングが注目を集めている.本論文では,頻出時系列エピソード発見問題を研究する.これは,与えられた系列データから,最大窓幅wの制約の元で,頻出エピソードと呼ばれる頻出する部分系列を効率的に取り出す問題である.本稿では,高速な頻出集合発見アルゴリズムLCMを元にして,エピソード発見のための深さ優先型探索アルゴリズムといくつかの高速化手法を提示し,計算機実験で評価する.技法の一部は,高速系列パターン発見エンジンLCM_seqに実装されており,本稿はこれらの技法の系列マイニングにおける有効性について考察する.
  • 大谷 英行, 喜田 拓也, 宇野 毅明, 有村 博紀 情報処理学会研究報告. 情報学基礎研究会報告 2008 (56) 113 -120 2008年06月12日 [査読無し][通常論文]
     
    巨大なデータ集合の中から,有用な知識や情報を発見するデータマイニングは,現代の様々な分野で重要な技術であり,特に,時系列データを対象とした時系列データマイニングが注目を集めている.本論文では,頻出時系列エピソード発見問題を研究する.これは,与えられた系列データから,最大窓幅wの制約の元で,頻出エピソードと呼ばれる頻出する部分系列を効率的に取り出す問題である.本稿では,高速な頻出集合発見アルゴリズムLCMを元にして,エピソード発見のための深さ優先型探索アルゴリズムといくつかの高速化手法を提示し,計算機実験で評価する.技法の一部は,高速系列パターン発見エンジンLCM_seqに実装されており,本稿はこれらの技法の系列マイニングにおける有効性について考察する.
  • 筒井 淳平, 有村 博紀 電子情報通信学会技術研究報告. COMP, コンピュテーション 108 (11) 35 -40 2008年04月11日 [査読無し][通常論文]
     
    本稿では,未知の歩行π_*をグラフの正例から学習する問題を考察する.ここでは,学習モデルとしてAngluinの質問学習モデル(Angluin, Machine Learning 2, 1988)を採用する.任意のグラフGはπ_*が埋め込まれているとき,π_*の正例であるといい,それ以外のとき,π_*の負例であるという.所属性質問とは,任意のグラフを与えて,それが正例であるか,負例であるかを問うことである.主結果として,辺が重ならないような(辺非重複)埋め込み写像だけを許した歩行のクラスに対して,未知の歩行を一つの正例とO(m+n)個の所属性質問から学習する多項式時間アルゴリズムを与えた.ここで,mは未知の歩行の長さであり,nは正例として与えられたグラフのサイズである.さらに,頂点が重ならないような場合と辺が重ならないような場合の両方のクラスで,未知の歩行を正負例だけから予測する問題は,DNF(積和形論理式)の正負例からの予測問題と同程度に難しいことがわかった.
  • 伊藤 公人, 谷口 剛, 村上 悌治, 有村 博紀, 原口 誠 情報処理学会研究報告. BIO, バイオ情報学 2008 (15) 79 -86 2008年03月03日 [査読無し][通常論文]
     
    塩基やアミノ酸の多重配列アライメントから,同時に変異する傾向にある塩基または残基位置の集合を高速に列挙する手法を提案する.本研究では,共変異の検出において,1)条件付きエントロピーH(i|j)を指標として用いることが有効であること,2)条件付きエントロピーH(i|j)の指標を条件付き同時エントロピーH(i_1…i_m|j)へと自然に拡張することにより,三つ以上の位置における共変異を検出可能であること,3)条件付き同時エントロピーの単調性を利用した枝刈り規則と,位置集合と配列集合に関する閉包性を用いることにより,共変異位置集合の列挙アルゴリズムを著しく高速化することが可能であることを示す.
  • 有村 博紀 学術月報 60 (12) 1004 -1008 2007年12月 [査読無し][通常論文]
  • 斉藤 智哉, 喜田 拓也, 有村 博紀 情報科学技術フォーラム一般講演論文集 6 (2) 43 -44 2007年08月22日 [査読無し][通常論文]
  • 上村 卓史, 喜田 拓也, 有村 博紀 情報科学技術フォーラム一般講演論文集 6 (2) 45 -46 2007年08月22日 [査読無し][通常論文]
  • 筒井 淳平, 金田 悠作, 有村 博紀 人工知能基本問題研究会 66 13 -20 2007年07月13日 [査読無し][通常論文]
  • 有村 博紀, 宇野 毅明, 下菌 真一 人工知能基本問題研究会 66 21 -28 2007年07月13日 [査読無し][通常論文]
  • 上村 卓史, 喜田 拓也, 有村 博紀 電子情報通信学会技術研究報告. COMP, コンピュテーション 107 (24) 71 -78 2007年04月19日 [査読無し][通常論文]
     
    高度なテキスト検索処理においては,テキストの特性(プロパティ)を考慮し,ある条件を満たす区間のみを対象として検索を行うという要求が存在する.本論文では,このプロパティを考慮した索引構造を構築する問題に取り組む.2006年にAmirらは,プロパティに属する区間に含まれる部分文字列のみを格納するプロパティ付き接尾辞木PSTを提案した.彼らの構築アルゴリズムは,接尾辞木から不要なノードを削除することでプロパティ付き接尾辞木を得るものである.本論文では,PSTの線形時間構築への第一歩として,必要な部分と不要な部分との境界となる位置を見つけるための新たなアルゴリズムを提案する.アルゴリズム全体の線形時間性の証明は今後の課題である.
  • 阿久津 達也, 有村 博紀, 下薗 真一 情報処理学会研究報告. BIO, バイオ情報学 2007 (21) 49 -56 2007年03月05日 [査読無し][通常論文]
     
    局所マルチプルアラインメントは、複数のDNA配列、もしくは、タンパク質配列が入力された時に、スコアが最適となるように、それぞれの配列から固定長の領域を選ぶという問題であり、モチーフ検出などの応用を持つ。本稿では、相対エントロピースコア、SPスコア、および、M.Liらにより提案された相対エントロピーに類似したスコアの3種類について、いずれのスコアを用いても局所マルチプルアラインメントがNP困難であることを示す。特に、相対エントロピースコアのもとでこの問題がAPX困難であることを示す。また、SPスコアを用いた場合などに対する近似アルゴリズムも示す。
  • 有村 博紀, 宇野 毅明, 下薗 真一 人工知能基本問題研究会 63 45 -52 2006年09月08日 [査読無し][通常論文]
  • 浅井 達哉, 岡本 青史, 有村 博紀 情報科学技術フォーラム一般講演論文集 5 (2) 103 -106 2006年08月21日 [査読無し][通常論文]
  • 有村 博紀, 宇野 毅明 知識ベ-スシステム研究会 73 105 -110 2006年03月09日 [査読無し][通常論文]
  • 湊 真一, 有村 博紀 電子情報通信学会論文誌. D, 情報・システム 89 (2) 172 -182 2006年02月01日 [査読無し][通常論文]
     
    大規模なトランザクションデータを,計算機上でコンパクトに表現して効率的に処理することは,データマイニングにおける重要な基盤技術の一つである.本論文では,VLSI CADの分野で大規模論理関数データの表現法として広く用いられている二分決定グラフ(BDD: Binary Decision Diagrams)をデータマイニングの分野に応用する方法を提案する.BDDの中でも「ゼロサプレス型BDD」(ZBDD: Zero-suppressed BDD)と呼ばれるデータ構造は,大規模な組合せ集合データを非明示的に列挙し,効率良く演算処理することができる.このZBDDを用いて,トランザクションデータベースに関する種々の計算処理を行う手法について述べ,実験結果を示す.
  • 有村 博紀, 宇野 毅明 電子情報通信学会技術研究報告. COMP, コンピュテーション 105 (273) 31 -38 2005年09月08日 [査読無し][通常論文]
     
    モチーフとは定数文字と一文字ワイルドカードoからなるABoBoBCのような文字列である.極大モチーフ列挙問題とは, 与えられた文字列上に指定回数以上出現し, しかもより長いモチーフに含まれないようなモチーフをすべて列挙する問題であり, 分子生物学や時系列解析に広い応用をもつ.本論文では, ワイルドカードをもつモチーフの族に対して, 入力文字列長の多項式領域と多項式遅延時間を達成する効率よい極大モチーフ列挙アルゴリズムを与える.具体的には, このアルゴリズムは, 極大モチーフに対する全域木上の深さ優先探索を用いて, すべての極大モチーフを一つあたりO(mn^2)時間とO(lm)領域を用いて列挙する.ここに, nは入力文字列の長さであり, 列挙される極大モチーフxに対して, m=|L(x)|はxの入力文字列中の出現数であり, l=|x|はxの長さである.さらに, 頻出および極大モチーフ数の下限を与え, 単純な列挙方式の限界を示す.
  • 有村 博紀, 宇野 毅明 人工知能基本問題研究会 57 33 -40 2004年11月04日 [査読無し][通常論文]
  • 有村 博紀, 宇野 毅明 情報処理学会研究報告. AL, アルゴリズム研究会報告 2004 (101) 75 -82 2004年10月14日 [査読無し][通常論文]
     
    本稿では,系列データベースにおける飽和パターンの新しいクラスを導入し,頻出飽和系列パターンの列挙問題を考察する.位置出現に関する飽和系列パターン(position-closed sequence patterns)は,データベース中で同じ出現位置をもつような同値なパターンの中で最も「くわしい」情報をもつ代表元パターンであり,通常の文書出現に関するものよりも弱い概念の飽和系列パターンである.本稿では,与えられた系列データベース上のすべての頻出飽和系列パターンを一つあたり入力サイズの多項式時間で重複なしに列挙する効率よいアルゴリズムE_<NUM>C_<LOSED>S_<EQ>を与える.これにより,出現位置に関する頻出飽和系列パターンの列挙問題が出力多項式時間で解けることが示される.この結果は,未解決の問題である文書出現に関する飽和系列パターンの多項式時間列挙に,一歩近づくものである.
  • 有村 博紀, 宇野 毅明 電子情報通信学会技術研究報告. COMP, コンピュテーション 104 (339) 15 -22 2004年10月08日 [査読無し][通常論文]
     
    本稿では,系列データベースにおける飽和パターンの新しいクラスを導入し,頻出飽和系列パターンの列挙問題を考察する.位置出現に関する飽和系列パターン(position-closed sequence patterns)は,データベース中で同じ出現位置をもつような同値なパターンの中で最も「くわしい」情報をもつ代表元パターンであり,通常の文書出現に間するものよりも弱い概念の飽和系列パターンである.本稿では,与えられた系列データベース上のすべての頻出飽和系列パターンを一つあたり入力サイズの多項式時間で重複なしに列挙する効率よいアルゴリズムENUMCLOSEDSEQを与える.これにより,出現位置に関する頻出飽和系列パターンの列挙問題が出力多項式時間で解けることが示される.この結果は,未解決の問題である文書出現に関する飽和系列パターンの多項式時間列挙に,一歩近づくものである.
  • 森永 聡, 有村 博紀, 池田 崇博, 坂尾 要祐, 赤峯 享 情報科学技術フォーラム一般講演論文集 3 (2) 125 -126 2004年08月20日 [査読無し][通常論文]
  • 喜田 拓也, 有村 博紀 人工知能基本問題研究会 56 73 -78 2004年07月25日 [査読無し][通常論文]
  • 浅井 達哉, 房延 慎二, 有村 博紀, 宇野 毅明, 中野 眞一 数理解析研究所講究録 1375 113 -119 2004年05月 [査読無し][通常論文]
  • 浅井 達哉, 房延 慎二, 有村 博紀 人工知能基礎論研究会 54 1 -8 2004年03月03日 [査読無し][通常論文]
  • 浅井 達哉, 房延 慎二, 有村 博紀, 宇野 毅明, 中野 眞一 電子情報通信学会技術研究報告. COMP, コンピュテーション 103 (622) 77 -84 2004年01月22日 [査読無し][通常論文]
     
    本稿では,XML文書に代表される半構造データからのデータマイニング問題を考察する.我々は,半構造データのモデルとしてラベルつき無順序木を採用し,与えられた半構造データの集積から出現頻度の高い部分構造を発見するアルゴリズムUNOTを開発した.このアルゴリズムは,逆探索に基づいて無順序木パターンを高速に列挙し,各パターンの出現リストを漸増的に計算することにより,パターン1つあたりO(kb^2m)時間ですべての頻出無順序木パターンTを計算する.ここに,kはTの大きさであり,bはデータ木の最大枝分かれ数,mはTのデータ木への総出現数である.
  • 浅井 達哉, 有村 博紀, 宇野 毅明, 中野 眞一 電子情報通信学会技術研究報告. DE, データ工学 103 (355) 33 -38 2003年10月01日 [査読無し][通常論文]
  • 浅井 準哉, 有村 博紀, 宇野 毅明, 中野 眞一 電子情報通信学会技術研究報告. DC, ディペンダブルコンピューティング 103 (357) 33 -38 2003年10月01日 [査読無し][通常論文]
     
    本稿では,XML文書に代表される半構造データからのデータマイニング問題を考察する.我々は,半構造データのモデルとしてラベルつき無順序木を採用し,与えられた半構造データの集積から出現頻度の高い部分構造を発見するアルゴリズムUNOTを開発した.このアルゴリズムは,逆探索に基づいて無順序木パターンを高速に列挙し,各パターンの出現リストを漸増的に計算することにより,パターン1つあたりO(kb^2m)時間ですべての頻出無順序木パターンTを計算する.ここに,kはTの大きさであり,bはデータ木の最大枝分かれ数,mはTのデータ木への総出現数である.
  • 浅井 準哉, 有村 博紀, 宇野 毅明, 中野 眞一 電子情報通信学会技術研究報告. DE, データ工学 103 (355) 33 -38 2003年10月01日 [査読無し][通常論文]
     
    本稿では,XML文書に代表される半構造データからのデータマイニング問題を考察する.我々は,半構造データのモデルとしてラベルつき無順序木を採用し,与えられた半構造データの集積から出現頻度の高い部分構造を発見するアルゴリズムUNOTを開発した.このアルゴリズムは,逆探索に基づいて無順序木パターンを高速に列挙し,各パターンの出現リストを漸増的に計算することにより,パターン1つあたりO(kb^2m)時間ですべての頻出無順序木パターンTを計算する.ここに,kはTの大きさであり,bはデータ木の最大枝分かれ数,mはTのデータ木への総出現数である.
  • 有村 博紀 人工知能学会誌 18 (5) 531 -536 2003年09月01日 [査読無し][通常論文]
  • 宇野 毅明, 有村 博紀, 浅井 達哉 電子情報通信学会技術研究報告. AI, 人工知能と知識処理 103 (243) 19 -24 2003年07月24日 [査読無し][通常論文]
     
    顧客の売上データのような,アイテムの部分集合族により定められるデータに対して,その族のある一定数以上の要素に合まれるアイテム集合を頻出集合とよぶ.頻出集合はデークマイニングの分野への応用を持つ.近年,極大な頻出集合と,同じような頻出集合を1つにまとめて扱うclosed item setが注目されている.それぞれを列挙することにより,頻出集合の中から意味のある部分を効率よく抽出できるからである.本稿では,極大2部クリークを列挙することにより. closed item setを高速に列挙する手法と,それを用いて極大頻出集合を列挙する手法を提案する.さらに,ベンチマーク問題を用いた計算実験により,既存の手法よりも高速であることを示す.
  • 浅井 達哉, 有村 博紀, 宇野 毅明, 中野 眞一 電子情報通信学会技術研究報告. AI, 人工知能と知識処理 103 (243) 31 -36 2003年07月24日 [査読無し][通常論文]
     
    本稿では,XML文書に代表される半構造データからのデータマイニング問題を考察する.我々は,半構造データのモデルとしてラベルつき無順序木を採用し,与えられた半構造データの集積から出現頻度の高い部分構造を発見するアルゴリズムUNOTを開発した.このアルゴリズムは,逆探索に基づいて無順序木パターンを高速に列挙し,各パターンの出現リストを漸増的に計算することにより,パターン1つあたりO(kb^2m)時間ですべての頻出無順序木パダーンTを計算する.ここに,kはTの大きさであり,bはデータ木の最大枝分かれ数,mはTのデータ木への総出現数である.
  • 森川 裕章, 浅井 達哉, 有村 博紀 情報処理学会研究報告. データベース・システム研究会報告 2003 (71) 211 -218 2003年07月16日 [査読無し][通常論文]
     
    最近研究が盛んなスタック有限状態機械(pushdown stack finite state machine)方式のオンラインXPath問合せ機構について,既存方式に比べて簡潔で拡張性が高い方式を提案し,実装と評価実験を行なった.
  • 森川 裕章, 浅井 達哉, 有村 博紀 電子情報通信学会技術研究報告. DE, データ工学 103 (191) 19 -24 2003年07月10日 [査読無し][通常論文]
     
    最近研究が盛んなスタック有限状態機械(pushdown stack finite state machine)方式のオンラインXPath問合せ機構について,既存方式に比べて簡潔で拡張性が高い方式を提案し,実装と評価実験を行なった.
  • 浅井 達哉, 安部 賢治, 川副 真治, 有村 博紀, 有川 節夫 数理解析研究所講究録 1325 81 -86 2003年05月 [査読無し][通常論文]
  • 有村 博紀, 浅井 達哉 Computer today 20 (2) 43 -48 2003年03月 [査読無し][通常論文]
  • 浅井 達哉, 有村 博紀, 安部 賢治, 川副 真治, 有川 節夫 電子情報通信学会技術研究報告. DC, ディペンダブルコンピューティング 102 (377) 19 -24 2002年10月10日 [査読無し][通常論文]
     
    本稿では,半構造データのストリームに対するオンライン型データマイニング問題を考察する.我々は,半構造データとパターンのモデルとしてラベルつき順序木を採用し,与えられた半構造データストリームから,任意の時点で現在の頻出パターンを出力するオンライン型半構造データマイニングアルゴリズムStreamTを開発した.このアルゴリズムでは,掃木枝を右へ動かすことによりパターンの出現を漸増的に検知する.我々は,アルゴリズムが無限のデータストリームに対して,有限の資源しか用いずに効率的に働くことを示した.
  • 浅井 達哉, 有村 博紀, 安部 賢治, 川副 真治, 有川 節夫 電子情報通信学会技術研究報告. DE, データ工学 102 (375) 19 -24 2002年10月10日 [査読無し][通常論文]
     
    本稿では,半構造データのストリームに対するオンライン型データマイニング問題を考察する.我々は,半構造データとパターンのモデルとしてラベルつき順序木を採用し,与えられた半構造データストリームから,任意の時点で現在の頻出パターンを出力するオンライン型半構造データマイニングアルゴリズムStreamTを開発した.このアルゴリズムでは,掃木枝を右へ動かすことによりパターンの出現を漸増的に検知する.我々は,アルゴリズムが無限のデータストリームに対して,有限の資源しか用いずに効率的に働くことを示した.
  • 浅井 達哉, 安部 賢治, 川副 真治, 有村 博紀, 有川 節夫 電子情報通信学会技術研究報告. DE, データ工学 101 (342) 1 -8 2001年10月04日 [査読無し][通常論文]
     
    本稿では, 半構造データベースからのデータマイニングを考察する.我々は半構造データマイニングを, 与えられた半構造データの集積から出現頻度の高い部分構造を発見する問題と定式化し, 頻出する部分構造パターンを発見する効率よいアルゴリズムを与える.このアルゴリズムは, Bayardo(SIGMOD'98)による集合枚挙木に基づくアイテム集合の枚挙法を, 順序木の枚挙へ拡張することにより実現している.さらに, ウェブデータ上で実験を行い, 開発したアルゴリズムの有効性を確認した.
  • 有村 博紀, 安部 潤一郎, 坂本 弘呂志, 有川 節夫 情報基盤センター年報 1 25 -27 2001年10月 [査読無し][通常論文]
  • 有村 博紀 電子情報通信学会ソサイエティ大会講演論文集 2001 388 -389 2001年08月29日 [査読無し][通常論文]
  • 平田 耕一, 坂本 比呂志, 有村 博紀 数理解析研究所講究録 1205 142 -147 2001年05月 [査読無し][通常論文]
  • 安積 裕樹, 安部 潤一郎, 有村 博紀, 有川 節夫 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2001 (27) 29 -32 2001年03月15日 [査読無し][通常論文]
     
    本論文では,分散記憶型並列計算機上での効率のよい全文索引構築法について提案する.接尾辞配列は,最近提案された高機能全文索引であり,情報検索や遺伝子情報などに広い応用をもつ.Baeza-Yates-Gonnet-Sinder(BGS)アルゴリズムは,最も広く使われている外部記憶上の接尾辞配列構築アルゴリズムである.このBGSアルゴリズムを並列化し,効率のよい並列接尾辞配列構築アルゴリズムを与える.提案アルゴリズムは,並列計算機時間と通信量に関して,BGSの最適な並列化になっており,従来からあるBGSの並列版のRiberio-Kitajima-Ziviani(RKZ)アルゴリズムに比べてより高速である.
  • 村上 義継, 坂本 比呂志, 有村 博紀, 有川 節夫 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2001 (27) 21 -24 2001年03月 [査読無し][通常論文]
  • 有村 博紀 電子情報通信学会技術研究報告. IT, 情報理論 100 (332) 1 -6 2000年10月03日 [査読無し][通常論文]
     
    データマイニング(DataMining)は, データベースからの知識発見とも呼ばれ, データベースに蓄積された一見無意味にみえる大量のデータから, 自明でない規則性やパターンを半自動的にとりだす方法についての科学的研究である.データマイニングの研究は, 1990年代初頭から顕在化し, 現在, ビジネス分野や科学技術分野をはじめとするさまざまな対象領域で, その適用が盛んにおこなわれている.本稿では, テキストデータとウェブデータを対象としたデータマイニング研究の最新動向について解説する.
  • 坂本 比呂志, 有村 博紀, 有川 節夫 人工知能基礎論研究会 31 -35 2000年07月15日 [査読無し][通常論文]
  • 高江 徹, 安部 潤一郎, 坂本 比呂志, 有村 博紀, 井上 仁, 武谷 俊一, 上園 慶子, 川崎 晃一 人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 14 311 -314 2000年07月03日 [査読無し][通常論文]
  • 安部 潤一郎, 藤野 亮一, 下薗 真一, 有村 博紀, 有川 節夫 人工知能学会誌 15 (4) 618 -628 2000年07月01日 [査読無し][通常論文]
     
    This paper describes applications of text data mining to interactive document browsing and web mining. We develop a fast text data mining method based on optimal pattern discovery, and make experiments on large collections of documents and Web pages to evaluate the proposed method.
  • 有村 博紀, 平田 耕一 人工知能学会誌 14 (5) 790 -799 1999年09月01日 [査読無し][通常論文]
     
    一階論理式の学習は, 歴史的に帰納論理プログラミング(ILP, Inductive Logic Programming)として発展してきた. ILPは, 一階論理に基づいた機械学習の研究であり, 表現言語として一階論理を用いることで, 従来の機械学習システムでは難しい構造データや背景知識を統一的な扱いを可能にすることを目標としている. 従来, ILP研究は応用面の研究が中心だったが, この数年, 意味論や学習理論の立場から, 新しい理論的研究が進んでいる. 本稿では, 論理プログラムおよび一階ホーン文の多項式時間学習に焦点を当て, 基本的概念と最新の理論的成果を紹介したい.
  • 安部 潤一郎, 笠井 透, 有村 博紀 人工知能基礎論研究会 91 -94 1999年07月07日 [査読無し][通常論文]
  • 藤野 亮一, 有村 博紀, 有川 節夫 人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 13 405 -408 1999年06月15日 [査読無し][通常論文]
  • 板井 力, 笠井 透, 有村 博紀, 有川 節夫 人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 13 521 -524 1999年06月15日 [査読無し][通常論文]
  • 笠井 透, 有村 博紀, 有川 節夫 数理解析研究所講究録 1093 81 -86 1999年04月 [査読無し][通常論文]
  • 笠井 透, 有村 博紀, 有川 節夫 全国大会講演論文集 58 (3) "3 -49"-"3-50" 1999年03月09日 [査読無し][通常論文]
  • 阿久津 達也, 有村 博紀, 下薗 真一 合同研究会AIシンポジウム 25 -30 1999年 [査読無し][通常論文]
  • 高江 徹, 近棟 稔, 有村 博紀, 篠原 歩, 井上 仁, 武谷 俊一, 上園 慶子, 川崎 晃一 全国大会講演論文集 1721 (4) 359 -361 1999年 [査読無し][通常論文]
  • 下薗 真一, 有村 博紀, 有川 節夫 電子情報通信学会技術研究報告. COMP, コンピュテーション 98 (432) 9 -16 1998年11月20日 [査読無し][通常論文]
     
    与えられた大量の文書の集積から, 分類精度を最大にする文字列パタンを見つける問題を考察する.複数の文字列の近接した出現を記述する近接語相関パタンを導入し, 文字出現が独立で一様な確率分布にしたがうランダムテキストに対して, 分類精度を最大化する近接度がkでd個の語からなる語相関パタンを平均計算時間O(k^<d-1>nlog^<d+1>n)および領域O(k^<d-1>n)で計算するアルゴリズムを与える.このアルゴリズムは, すべての部分語を枚挙する自明なアルゴリズムの時間計算量O(n^<2d+1>)に対して, 著しい高速化を達成しており, 遺伝子情報データのようなほぼランダムなテキストに対するデータマイニング問題に適用可能である.この結果は, 任意個数の語からなる近接相関パタンに対して, 分類精度最適化問題が多項式時間近似スキームをもたない事実と対照的である.
  • 笠井 透, 有村 博紀, 篠原 武 全国大会講演論文集 57 (1) 280 -281 1998年10月05日 [査読無し][通常論文]
  • 笠井 透, 有村 博紀, 篠原 武 Research reports on information science and electrical engineering of Kyushu University 3 (2) 185 -190 1998年09月 [査読無し][通常論文]
  • 笠井 透, 有村 博紀, 藤野 亮一, 有川 節夫 情報処理学会研究報告. データベース・システム研究会報告 98 (57) 151 -156 1998年07月08日 [査読無し][通常論文]
     
    与えられた大量の文書の集積から, 分類精度を最大化にする文字列パタンを見つける問題を考察する.複数の文字列の近接した出現を記述する近接語相関パタンを導入し, 一様確率で生成されたランダムテキストに対して, 分類精度を最大にする(d, k)-語相関パタンを平均計算時間O(k^<d-1>nlog^<d+1>nおよび領域O(k^<d-1>n)で計算するアルゴリズムを与える.さらに, 大規模テキストデータ向けの索引構造である接尾語配列上での実装方法についても考察する.
  • 渡木 厚, 有村 博紀, 藤野 亮一, 有川 節夫 数理解析研究所講究録 1041 175 -182 1998年04月 [査読無し][通常論文]
  • 稲子 希望, 有村 博紀 数理解析研究所講究録 1041 183 -190 1998年04月 [査読無し][通常論文]
  • 有村 博紀, 渡木 厚, 下薗 真一 電子情報通信学会技術研究報告. COMP, コンピュテーション 97 (356) 95 -102 1997年10月31日 [査読無し][通常論文]
     
    与えられた大量の文書の集積から, 分類精度を最大にする文字列パタンを見つける問題を考察する. 二つの文字列の近接した出現を要求する二語相関パタンを導入し, 分類精度を最大化する最適パタンをO(n^2) 時間および領域O(kn) 領域で計算するアルゴリズムを与える. また, 相関パターンの語数を制限しない場合, 分類精度の最大化問題が多項式時間での任意の近似が困難であることを示す.
  • 有村 博紀, 渡木 厚, 藤野 亮一, 有川 節夫 全国大会講演論文集 55 (3) 395 -396 1997年09月24日 [査読無し][通常論文]
     
    本研究では, 大量の文書の集積から, 分類精度を最適化するパタンを見つける問題を考察する。二語相関パタンとよばれる単純なパタンを仮説としたとき, 分類精度を最大化する最適パタンをO(n^2)時間および領域O(kn)領域で計算するアルゴリズムを与える。
  • 峯 恒憲, 佐藤 周行, 正代 隆義, 廣川 佐千男, 有村 博紀, 森 雅生, 篠原 歩, 竹田 正幸 情報処理学会研究報告. DD, [デジタル・ドキュメント] 7 (49) 39 -46 1997年05月23日 [査読無し][通常論文]
     
    九州大学では、毎年およそ2,300人の新入生が情報処理の入門教育を受講する。これらの学生は、Windows95の動くパソコン上で、プログラミングを始めとする情報処理の基礎を学ぶ。個人差が大きくなりがちな情報処理を学ぶ学生の習熟度に対処するため、講義をサポートし、かつ、講義時間外に利用できる自学自習用のホームページを用意した。このページでは、我々のこれまでの情報処理教育の経験から得た講義のエッセンスを再現(Lecture Capture)している。しかし、プログラムが如何に動作するかを理解させることは難しかった。そこで、我々は、プログラムの動作の理解を助ける機能として、「プログラムアニメーションコンパイララ」と呼ぶPascalプログラムをJava Appletに変換するシミュレータを開発した。これにより、Webのブラウザを通してプログラムの動きを体験し、実感してもらえるようになった。本稿では、本システムのアイデアと概要、並びに今後の開発予定について報告する。
  • 池田 大輔, 有村 博紀 数理解析研究所講究録 992 207 -214 1997年05月 [査読無し][通常論文]
  • 有川 節夫, 有村 博紀 人工知能学会誌 12 (2) 332 -333 1997年03月01日 [査読無し][通常論文]
  • 杉本 典子, 平田 耕一, 有村 博紀 人工知能学会誌 12 (2) 334 -337 1997年03月01日 [査読無し][通常論文]
  • 有村 博紀, 篠原 武 数理解析研究所講究録 950 246 -249 1996年05月 [査読無し][通常論文]
  • 有村 博紀, 篠原 武 全国大会講演論文集 51 (3) 135 -136 1995年09月20日 [査読無し][通常論文]
     
    機械学習や帰納推論,仮説推論等における重要な推論手法の一つが,概念の汎化である.概念の汎化とは,いくつかの具体例が与えられたときに,それらを説明するより一般的な概念を見つけることであり,構成的学習において有効な手法である.とくに帰納論理プログラミング等の論理プログラムの学習の分野では,汎化にもとづく学習システムについて活発な研究がおこなわれている.本研究では,論理プログラムを背景知識の存在のもとで汎化する問題について議論する.とくに,高々k個の制約確定節からなる集合のうちで,例として与えられたすべての確定節を導き,背景知識Bのもとで含意に関して極小なものを見つける問題を考察し,この問題を多項式時間で解くアルゴリズムを与える.これは[2]の結果を複数の節からなる論理プログラムに拡張するものである.さらに,論理プログラムの学習への応用について述べる.
  • 宮崎 哲司, 平田 博明, 古賀 寿憲, 深町 修一, 有村 博紀, 篠原 武 全国大会講演論文集 51 (4) 239 -240 1995年09月20日 [査読無し][通常論文]
     
    情報検索の問題の1つとして,パターン照合問題がある.パターン照合間題とは,パターンおよびテキストという2つの文字列が与えられたとき,テキスト中におけるパターンのすべての出現を見つけだす問題である.このパターン照合問題を解くアルゴリズムに,Aho-Corasick法がある.Aho-Corasick法の特長は,パターンよりパターン照合機械という一種の有限オートマトンを作り,そのパターン照合機械をテキスト上で1回走査させるだけで複数のパターンを同時に検出できることである.Aho-Corasick法を用いて実際に検索を行う際に問題になるのが,ディスクからテキストを読み込むのに要する時間である.この間題に対して,テキストをあらかじめ圧縮しておき,その圧縮されたテキストを復号せずに検索する方法が提案されている.日本語テキストには,ひらがな,カタカナ,漢字,記号といった複数の文字種が存在し,テキスト中では同じ文字種が連続して出現するという性質がある.この性質を利用して,文字種ごとに圧縮符号を割り当てることにする.このとき,異なる文字種間で同じ符号が割り当てられる可能性があるので,文字種を保持する必要がある.文字種の変わり目に文字種が変わることを示すシフトコードを用いる.この方法により,文字種を考慮に入れずに全体で圧縮符号を割り当てた場合より圧縮率はよくなる.本稿では,Aho-Corasick法のパターン照合機械を拡張し,シフトコード付き圧縮符号によって圧縮された日本語テキストのためのパターン照合機械を設計した.これを用いて日本語テキストを対象として実験を行った結果,圧縮率は69.7%,走査時間は78.3%に短縮できた.
  • 山口 美千代, 篠原 武, 藤野 亮一, 有村 博紀, 有川 節夫 情報処理学会研究報告. 情報学基礎研究会報告 95 (76) 33 -40 1995年07月28日 [査読無し][通常論文]
     
    正則パターンとは定数と互いに異なる変数からなる文字列であり,その正則パターン中の変数を空文字を含む定数文字列で置き換えて得られる定数文字列全体を表わす.本研究では,正例のみから複数のパターンを同時に学習するk極小多重汎化アルゴリズムを,アミノ酸配列からのタンパク質モチーフ発見に応用する.まず,このk極小多重汎化アルゴリズムに例の集合から例外となる文字列を積極的に検出する探索戦略を組み込み,次にその有用性を膜貫通領域を対象とした実験で実証する.実験では,この探索戦略を用いた学習アルゴリズムが,従来からの探索戦略に比較して高い精度の仮説を,安定して,より短い時間で見つけることを確認した.
  • 有村 博紀, 石坂 裕毅, 篠原 武 人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 9 73 -76 1995年07月24日 [査読無し][通常論文]
  • 篠原 武, 藤野 亮一, 有村 博紀, 有川 節夫 人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 9 93 -96 1995年07月24日 [査読無し][通常論文]
  • 深町 修一, 下薗 真一, 有村 博紀, 篠原 武 電子情報通信学会技術研究報告. NLC, 言語理解とコミュニケーション 95 (29) 41 -48 1995年05月12日 [査読無し][通常論文]
     
    もとのアルファベットからより小さなサイズkのアルファベットへの写像は,k-indexingと呼ばれ,損失のある圧縮符号とみなすことができる.損失のある符号を用いて圧縮されたテキスト上での文字列パターン照合は,圧縮率が高くなるために高速化が期待できるが,誤検出の可能性がある.2^n-indexingを用いると,nビットの固定長符号で,長さlのパターンの誤検出の期待値がほぼ<1/2>^<nl>となるような圧縮を行うことができる.文字ごとの照合に対する最適化,さらに2-gram,3-gramに対する最適化を行い,実際の英文テキストを用いて実験を行った.
  • 沼尾 正行, 有村 博紀, 原口 誠, 平田 耕一, 斉藤 和巳, 諏訪 正樹, 月本 洋, 元田 浩 人工知能学会誌 9 (2) 318 -320 1994年03月01日 [査読無し][通常論文]
  • 有村 博紀, 篠原 武 人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 7 123 -126 1993年07月20日 [査読無し][通常論文]
  • 石坂 裕毅, 有村 博紀, 篠原 武 人工知能学会誌 8 (4) 419 -426 1993年07月01日 [査読無し][通常論文]
     
    We consider the polynomial time inferability of primitive Prologs from positive facts. The class of primitive Prologs is a proper subclass of that of linear Prologs which is known to be inferable from only positive facts. In this paper, we discuss the polynomial time inferability of the subclass using minimal multiple generalizations. The minimal multiple generalization is a natural extension of the least generalization given by Plotkin in 1970. The minimal multiple generalization generalizes given first order words by several words, while the least generalization does by a single word. The property of the minimal multiple generalization makes it possible to perform fine generalization and to construct the heads of several clauses in a target program at the same time. We give an outline of a consistent polynomial time inference algorithm which identifies the class of primitive Prologs in the limit. The algorithm infers the heads of clauses in a target program as a minimal multiple generalization of a set of given positive facts. Furthermore, we give a similar result on the inferability of a subclass of context-free transformations which includes several well-known Prolog programs.
  • 有村 博紀 人工知能学会誌 6 (5) 1991年09月01日 [査読無し][通常論文]

受賞

  • 2019年01月 人工知能学会 研究会優秀賞
     整数計画法に基づく学習済み決定木の公平性を考慮した編集法 
    受賞者: 金森憲太朗;有村博紀
  • 2016年06月 情報処理学会 論文賞
     大規模軌跡データからの群パターン発見のための実用的アルゴリズム 
    受賞者: 耿暁亮;宇野毅明;有村博紀
  • 2016年03月 情報処理学会 2016年度(平成28年度)山下記念研究賞
     三次元空間における効率良い近似点集合マッチングと分子パターン照合への応用 
    受賞者: 佐々木 耀一
  • 2013年06月 人工知能学会 研究会優秀賞
     超グラフ中に含まれる非巡回部分超グラフの効率よい列挙 
    受賞者: 和佐 州洋;有村 博紀;宇野 毅明;平田 耕一
  • 2010年06月 電子情報通信学会 情報・システムソサイエティ 論文賞(先見論文)
     「ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの 効率的解析手法」 
    受賞者: 湊真一;有村博紀
  • 2005年02月 日本データベース学会 上林記念研究奨励賞
     
    受賞者: 有村 博紀
  • 2004年11月 2nd Workshop on Frequent Itemset Mining Implementations (FIMI'04), in conjunction with IEEE ICDM'04 BEST IMPLEMENTATION AWARD
     
    受賞者: Takeaki Uno;Masashi Kiyomi;Hiroki Arimura
  • 2004年11月 人工知能学会 2004年研究会優秀賞
     「大規模系列データから代表的な頻出エピソードを発見するための効率よいアルゴリズム」 
    受賞者: 有村博紀;宇野毅明
  • 2004年07月 電子情報通信学会DE研究会第15回データ工学ワークショップ DEWS2004優秀論文賞
     「半構造データマイニングのための高速な無順序木パターン発見手法」 
    受賞者: 房延慎二;浅井達哉;有村博紀;宇野毅明;中野眞一
  • 2003年06月 電子情報通信学会DE研究会第14回データ工学ワークショップ DEWS2003最優秀論文賞
     「領域効率の良い頻出データアイテム発見アルゴリズム」 
    受賞者: 川副真治;有村博紀
  • 2002年05月 電子情報通信学会DE研究会第14回データ工学ワークショップ DEWS2002優秀論文賞
     
    受賞者: 浅井達哉;安部賢治;川副真治;坂本比呂志;有村博紀;有川節夫
  • 2001年05月 人工知能学会 2000年度論文賞
     「テキストデータからの高速データマイニング」, 安部潤一郎, 藤野亮一, 下薗真一, 有村博紀, 有川節夫(2000年7月掲載) 
    受賞者: 安部潤一郎;藤野亮一;下薗真一;有村博紀;有川節夫
  • 2000年04月 PAKDD2000 Paper with Merit Award
     "Discovering unordered and ordered phrase association patterns for text mining" 
    受賞者: Ryoichi Fujino;Hiroki Arimura;Setsuo Arikawa
  • 1999年12月 人工知能学会 1999年度全国大会優秀論文賞
     「 大規模テキストデータからの探索的文書ブラウジング」 
    受賞者: 板井力;笠井透;有村博紀;有川節夫
  • 1998年03月 情報処理学会 第55回全国大会大会優秀賞
     「最適パタン発見に基づくテキストデータマイニング」 
    受賞者: 有村博紀;渡木厚;藤野亮一;有川節夫
  • 1992年07月 人工知能学会 全国大会優秀論文賞
     「極小汎化に基づくPROLOGプログラムの正事実からの多項式時間推論」 
    受賞者: 有村博紀;石坂裕毅;篠原武
  • 1992年06月 人工知能学会 1992年度研究奨励賞
     「Polynomial Time Inference of Unions of Tree Pattern Languages」 
    受賞者: 有村博紀;石坂裕毅;篠原武
  • 情報処理学会 全国大会 学生奨励賞
     三次元空間における効率良い近似点集合マッチングと分子パターン照合への応用 
    受賞者: 佐々木 耀一

共同研究・競争的資金等の研究課題

  • 大規模実世界時空間データストリーム処理のための高度検索・発見技術の展開
    文部科学省:科学研究費補助金(挑戦的研究(萌芽))
    研究期間 : 2018年06月 -2021年03月 
    代表者 : 有村 博紀
  • 実世界知識基盤形成のための次世代半構造マイニング技術の研究
    文部科学省:科学研究費補助金 基盤研究(A)
    研究期間 : 2016年04月 -2020年03月 
    代表者 : 有村 博紀
  • 大規模実世界時空間データストリーム処理のための超高速な検索・発見技術の研究
    文部科学省:科学研究費補助金 挑戦的萌芽研究
    研究期間 : 2015年 -2017年 
    代表者 : 有村 博紀
  • 文部科学省:科学研究費補助金(基盤研究(A))
    研究期間 : 2012年 -2015年 
    代表者 : 有村 博紀
  • 文部科学省:科学研究費補助金(新学術領域研究(研究領域提案型))
    研究期間 : 2013年 -2014年 
    代表者 : 有村 博紀
  • 文部科学省:科学研究費補助金(基盤研究(A))
    研究期間 : 2007年 -2011年 
    代表者 : 有村 博紀, 喜田 拓也, 湊 真一, 伊藤 公人, 宇野 毅明, 平田 耕一
     
    本研究では,ネットワーク上の大規模半構造データからの知識獲得のための超高速な半構造マイニングエンジン技術と,これを現実の多様な半構造データに適用するためのさまざまな周辺技術を開発した.さらに,開発した技術の計算機上への実装を行い,大規模半構造データからの知識発見実験を行った.
  • 文部科学省:科学研究費補助金(特別推進研究)
    研究期間 : 2005年 -2007年 
    代表者 : 有村 博紀, 喜田 拓也, 湊 真一, 伊藤 公人
     
    本研究では,WWW(ウェブ)などの大規模半構造データからの知識基盤形成のための超高速半構造パターン発見技術とその周辺技術の研究開発を行う.本研究では,次の項目に関して研究開発を行った.(1)超高速半構造マイニングエンジンの研究として,変数付き系列モチーフや属性木等の有用かつ自明でない半構造データ族に対して,性能保障をもつ効率よいパターン発見アルゴリズムを開発した.これらの計算量を理論的に明らかにし,さらにこの枠組みを一般化することで,平面幾何グラフ,2次元画像パターン,伸張を許す極大系列パターン,近似アイテム集合等の半構造データ族に対して,効率よい多項式時間遅延・多項式領域アルゴリズムを開発した.統計的マイニングに関して,自然言語処理分野や,人獣共通感染症領域での遺伝子解析応用への応用を行った.(有村,伊藤,喜田).(2)知識基盤形成のための大規模知識索引技術として,ZBDD技術を用いた圧縮知識索引機構と,その上で対称パターンの発見や,飽和集合発見を行う高速アルゴリズムを開発し,様々な効率化技術を開発した(湊,有村).(3)半自動知識連係技術として,ビット並列手法に基づく多次元数値ストリームデータや,例からの学習を用いた情報抽出技術などネットワークからの情報抽出や高速半構造ストリーム処理に基づく効率よい情報収集技術を開発した.(伊藤,喜田,有村).(4)開発した知識発見・知識連携・知識索引技術に関して,これまでのアルゴリズム実装と,評価実験,理論的解析に基づき,知識発見ツールの集合として知識獲得プロトタイプシステムを構築し,適用実験を行った(湊・伊藤・喜田・有村).
  • 文部科学省:科学研究費補助金(萌芽研究)
    研究期間 : 2004年 -2005年 
    代表者 : 有村 博紀, 坂本 比呂志, 坂本 比呂志
     
    本研究では,半構造データに対する高速なXPath処理法を提案した.これまでに,データを効率的に圧縮する手法として知られている算術符号化を半構造データの検索に応用した,逆算術符号化が提案されている.これは,木構造データ上のパスの依存関係を,データを圧縮したまま復号化することなく検査できる手法であり,この関係性を利用することで,パスによる問い合わせを高速に処理できる.しかしながら,この問い合わせで利用可能なパスの形式は限定されているため,一般のXPathの問い合わせは処理が困難である.そこで本研究では,このような逆算術符号化にノード間の先祖子孫関係を判定可能な範囲ラベルを導入することにより,より複雑な問い合わせ処理を高速に実現するための手法を提案する.評価実験の結果,300MB程度のXMLデータに対してテキストを直接処理する既存の手法と比較し,数十から百倍の高速化を達成した.また,本研究では,畳み込みカーネルのアイディアに基づいた,ラベル付き順序木に対するこれまでにない新しいカーネル関数を提案した.まず,畳み込みカーネルの枠組みにおいてラベル付き順序木に対して任意の部分グラフを部分構造として用いた場合の,効率の良いカーネル計算のアルゴリズムを提案し,曖昧なラベルや構造を取り込むような拡張を行った.さらに,より一般的な木構造として,順序のないラベル付き根付き木に対するカーネルを考えた場合には,カーネルの計算が#P-完全問題であることを示した.
  • 文部科学省:科学研究費補助金(特定領域研究「情報爆発」)(領域代表:喜連川優)
    研究期間 : 2004年 -2005年 
    代表者 : 有村 博紀, トーマス ツォイクマン, 竹田 正幸, 坂本 比呂志, 篠原 歩, 下薗 真一, 湊 真一, 喜田 拓也
     
    本研究は,大量のウェブページやXML等の大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの実現方式を明らかにすることを目標としている.その鍵になる技術として,最適パターン発見を木やグラフ構造に拡張し,計算量理論と計算学習理論の最新の成果を援用しながら,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムの開発に取り組んだ.平成17年度は,初年度から昨年度までの研究成果と統合し,最適半構造マイニングのプロトタイプシステム構築を目指した.研究項目としては,有用な情報源の発見,特徴的なパターンの発見,情報の抽出の3つの情報獲得問題に加えて,昨年度から新たに研究を開始した知識索引問題について取り組んだ.今年度得られた具体的な結果のうち主要なものは以下のとおりである.(1)大規模なトランザクションデータによく見られる疎な組み合わせ集合データを効率よく扱うことのできるデータ構造であるZBDD(Zero-suppress BDD)をベースに,その構造の元で重み付き積和集合を計算可能なZBDDパッケージツールVSOP(Valued Sum-Of-Products)の開発を推し進め,頻出するパターン集合を表現するZBDDを単純直交分解する機能を追加した.これにより,そのデータに内包された意味的構造を自動抽出することが可能になった.(湊)(2)パターン発見アルゴリズムによる分類・予測の長期的ふるまいに関する理論保証を与えることに成功した.(ツォイクマン)(3)系列データからの極大モチーフパターンを効率よく枚挙するアルゴリズムを得た.(有村:H13-H16代表)(4)Arc構造付きテキストに対する高速なパターン照合アルゴリズムを得た.(喜田)
  • 文部科学省:科学研究費補助金(基盤研究(B))
    研究期間 : 2003年 -2005年 
    代表者 : 有村 博紀, 池田 大輔, 石野 明, 篠原 歩, 竹田 正幸, 笠原 義晃, 喜田 拓也
     
    ネットワーク上を時間的に変化しながら流れる大量半構造データストリームから有用な情報を効率よく獲得する超高速オンライン型データマイニング・システムの研究開発を行った.最終年度である平成17年度は,前年度までに研究開発した基礎理論の深化と,ネットワークデータへの応用の両面から,ストリーム指向パターン照合と半構造データマイニング,さらに,応用としてネットワーク不正侵入検出などの問題について,以下のように研究開発を行った.また,3年間の研究成果の発表・出版を行った.(1)半構造データストリームマイニングの調査と定式化:ネットワーク侵入検出やデータストリームマイニング等の実際のデータストリーム応用を解析し(池田・笠原・喜田),ストリームマイニングに関する最新の技術動向の調査を行った.また,昨年度までの調査結果を出版した(喜田・有村).(2)ストリーム指向半構造パターン照合技術の開発:データストリームを左から右へ一方向逐次走査に基づいた新しいストリーム検索技術について研究した.特に,XMLテキスト高速な木パターン照合処理技術と,シソーラアスやアノテーション等のメタデータを附加したストリームデータ検索技術を開発することに成功した(竹田・篠原・石野・喜田).(3)系列パターン発見に関して,長大な系列データを対象とした効率よいパターン発見アルゴリズムを開発した(篠原・竹田・有村).また,部分文字列の頻度に基づくパターン抽出手法について,そのパターン抽出性能と計算性能の改良を行った(池田・笠原・喜田).さらに,前年度に開発したワイルドカードをもつ極大パターンに対する高速パターンアルゴリズムに関する研究成果が出版された.また,昨年度の研究で開発した系列パターン発見アルゴリズムがH17年6月に,2004年人工知能学会研究会優秀賞を受賞した(篠原・竹田・有村).さらに,前年度までに,研究項目2と3で開発した半構造パターン照合技法とオンライン発見手法を元に開発した,ストリームデータに関する半構造データ族に対する高速半構造パターン発見アルゴリズムの研究成果の論文集への採択が決定した(有村・喜田).(4)応用研究として,現実の大規模高速ネットワークにおいて,実際に大量ネットワークデータに対するオンラインデータ収集と解析を行い,ネットワーク不正侵入検出に関する研究を行った(笠原・池田).
  • 文部科学省:科学研究費補助金(特定領域研究「情報学」)(領域代表者: 安西祐一郎)
    研究期間 : 2001年 -2003年 
    代表者 : 有村 博紀, 下薗 真一, 篠原 歩, 竹田 正幸
     
    ネットワーク上に分散したウェブページやXML等の半構造データの急速な増大に対して,これらのコンテンツに直接アクセスするための効率良い手法の開発が緊急の課題となっている.本研究では,大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの開発を目指す.そのための鍵となる技術として,最適パターン発見を木やグラフ構造に拡張して,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムを開発する.さらに,ウェブマイニングを(a)有用な情報源の発見,および(b)特徴的なパターンの発見,(c)情報抽出の3つの過程ととらえ,これらを有機的に結合して,半構造データを対象とした知識獲得システムの効率良い実現方式を明らかにすることを目標とする.また,計算量理論と計算学習理論の最新成果を援用し,計算量に徹底的に配慮した高速なアルゴリズムの開発を目指すのも特色である.平成14年度は,次の研究成果を得た.(a)「有用な情報源の発見」に関しては,従来より表現力の高いパターンである可変長変数パターン(VLDCパターン)に対する新しいテキスト索引構造を開発し,これを用いて,効率よい最適化マイニングアルゴリズムを開発した.(b)「特徴的なパターンの発見」に関しては,XML-MessagingとSOAPへの応用を目指して,昨年開発した半構造データマイニング手法FREQTを元に,高速な半構造データストリームマイニングSTREAMTを開発した.これは,非常に少なく資源を使いながらデータストリームを監視し、有用なパターンを逐次報告するアルゴリズムである.また,FREQTの最適化マイニングへの拡張と理論的性能解析を行い,この方式の最適性を示した.(c)「情報抽出」に関しては,XMLデータ処理の基本技術である符号語列上のパターン照合機械技術を開発し,XMLパターン検索への応用を考察した.
  • 最適パターン発見にもとづく高速テキストデータマイニングの研究
    科学技術事業団 (JST):さきがけ研究21「情報と知」(領域代表者: 安西祐一郎)
    研究期間 : 1999年10月 -2002年03月 
    代表者 : 有村 博紀
  • 文部科学省:科学研究費補助金(基盤研究(B))
    研究期間 : 1999年 -2001年 
    代表者 : 有村 博紀, 篠原 歩, 竹田 正幸, 正代 隆義, 石野 明, 平田 耕一
     
    本研究では,以下の三つの研究項目について研究を展開した.1.半構造化文書からのデータマイニング方式.大量テキストからのテキストマイニング問題を考察し,これを情報検索の逆問題として定式化し,とくに,雑音の多い不完全なデータにおける頑健なパターン発見のために,統計的尺度を最適化するパターンを発見する最適パターン発見の枠組みを採用した.近接部分語パターンと呼ばれる単純なテキストパターンに対して,ランダムテキスト上できわめて高速にはたらく,最適パターン発見アルゴリズムを開発し,ウェブからのキーワード獲得問題や,対話的文書ブラウジングに適用した.さらに,ウェブやXMLデータなどの大規模半構造化文書を,「半構造化文書=テキスト+構造+属性データ」ととらえて,テキストマイニングの枠組みを木やグラフ構造に拡張した.2.大量テキストデータに対する高速パターン照合方式.現実の大規模テキストデータベースシステムでは,大量のテキストデータを格納するため,テキストを圧縮して扱うことが多い.そのため,圧縮データ上のパターン照合アルゴリズムに力点をおいて研究した.これは,圧縮されたデータを陽に展開することなくパターン照合を行おうとするものである.本アプローチの独創的な点は,単にデータを圧縮することで記憶領域を削減するだけでなく,さらに,圧縮することでパターン照合そのものを高速化させるという狙いをもつことである.本研究では,一連の研究を通じて,一番目の目標だけでなく,二番目の目標も達成できることを実証した.さらに,既存のさまざまな圧縮方式に対して,その圧縮方式に適した圧縮照合アルゴリズムを開発すると同時に,より高い見地から多様な圧縮照合アルゴリズムを統一的にとらえる枠組みを提案することに成功した.3.機械学習に基づくデータマイニング方式.一連の半構造化文書からの情報抽出問題を理論的に定式化し,与えられたデータからパターンを発見する問題の学習可能性と限界を理論的に明らかにした.次に,Tree Wrapperや生垣とよばれる木と文字列の双方の性質をもつ木構造パターンに対して,半構造化文書からの情報抽出のための効率よい情報抽出アルゴリズムを開発した.さらに,実際のウェブデータを対象として,さまざまなタイプの半構造化文書から,利用者が必要とする情報を獲得するという情報獲得実験を行い,その有効性を検証した.
  • 文部科学省:科学研究費補助金(奨励研究(A))
    研究期間 : 1999年 -2000年 
    代表者 : 有村 博紀
     
    本研究の目的は,大規模知識データベースから,複雑な知識構造を効率よく獲得するシステムの実現方法を明らかにすることである.大規模知識データベースは,(i)大量の(ii)非均質なデータを含み,同時に(iii)その多くは正例だけを含むので,従来の知識獲得手法は適用できない.そこで,本研究では,このような大規模知識データベースに適用可能な新しい学習手法について研究をおこなった.本年度は,以下の項目について研究を実施した.(1)前年度に開発した一般的な知識獲得手法を,ネットワーク上の半構造データからの知識獲得に応用した.具体的には,ネットワーク上でのデータ交換および記述言語として急速に利用が進んでいるXMLデータを対象とし,与えられたXMLデータから,対話によって,データ変換規則を効率良く発見するアルゴリズムを開発する.(ICGI 2000;人工知能学会誌Vol.16,No.2)(2)さらに(1)項の半構造データからのパターン発見アルゴリズムを,前年度に開発したテキストデータからのパターン発見手法と融合し,構造と内容の両方を利用した知識獲得手法を開発した.さらに,この手法の時間計算量と質問計算量を理論的に解析した.(PAKDD 2000;RECOMB 2000;ビット別冊)(3)開発した知識獲得手法の有効性を計算機実験を通じて評価する.開発中の知識獲得システムを,本研究で得たパターン発見手続きの導入によって拡張した.さらに,ネットワーク上に分散したウェブページからの知識獲得実験をおこなった.(Kyoto ICDL2000;人工知能学会誌Vol.15,No.4)
  • 文部科学省:科学研究費補助金(奨励研究(A))
    研究期間 : 1997年 -1998年 
    代表者 : 有村 博紀
     
    本研究では,構造化データからの対話的な知識獲得について,基礎的な研究をおこなった[1,3].まず,オブジェクト指向データベース等の複合オブジェクト(complex object)の単純なモデルとして,述語論理の一階項(first-order term)を考えた.さらに,能動的学習(active learning)の枠組みのもとで,さまざまな構造化パタン族に対して,効率的なパタン発見手法の開発と,発見問題の本質的複雑さの探求をおこない,次の結果を得た[1,3,2].1. 2個の一階項からなる簡単なパタンでさえ,効率よい学習が困難なことを示した.その一方で,所属性質問を用いて実験をおこなうことで,この種のパタンが効率よく多項式時間で同定できることを示した.2. 上記の結果を2個以上の一階項からなるパタンに拡張して,所属性質問を用いた効率よい学習アルゴリズムを与えた.このアルゴリズムは構造化データの学習における基本的機構を確立するもので,所属性質問を用いるさまざまな学習モデルに適用可能である.3. ACH(k)(acyclic constrained Horn programs of bounded arity k)と呼ばれる一階ホーン論理式の族(再帰論理プログラムの一種)が,含意に基づく学習(能動学習の一種)の枠組みで多項式時間学習可能であることを示した[1].さらに,質問計算量に関する下限定理と学習困難性を示して,一般的な一階ホーン論理式の学習には,質問の利用が不可欠なことを明らかにした.以上の結果は,構造化データからの知識獲得の本質的難しさを明らかにするものである.同時に,対話による知識ベース構築のための基本的方法論を与えるものである.
  • 文部科学省:科学研究費補助金(重点領域研究)
    研究期間 : 1997年 -1997年 
    代表者 : 有村 博紀, 正代 隆義, 有川 節夫
     
    データマイニング(Data Mining)は,データベースからの知識発見とも呼ばれ,現在,ビジネス分野や科学技術分野等,さまざまな対象領域で,その適用が盛んにおこなわれている.しかし,現在のデータマイニングの対象は関係データベースが中心であり,現在急速に利用が進みつつあるテキストデータベースやオブジェクト指向データベースに関しては,明示的な構造をもたない,あるいは非均質な構造しかもたない,膨大なデータの集積であるなどの理由から,従来の手法をそのまま適用することができないため,ほとんど研究がおこなわれていない.そこで本研究では,ここにあげたような非構造的データや構造データからのデータマイニングについて研究した.平成9年度は,具体的にはつぎの問題に中心に研究した.1.高速パターン発見アルゴリズムの研究:近年発展著しいテキストデータベースを対象に,高速なパターン発見アルゴリズムを開発した.とくに,単純なパタンに仮説を制限する代わりに,誤差や欠落を含む不完全データにたいしても働くような,頑健かつ高速な手法を開発することができた.また,確率的サンプリングを用いた高速化や効率的な探索の枝刈り法についても成果を得た.2.属性効率のよいパタン発見アルゴリズム:テキストデータベースにおいては,属性に対応する部分列や語彙の数は膨大になる.本項では,1変数パタンと呼ばれる単純な規則を対象に,発見に必要な具体例が,発見対象に関連しない属性数にはほとんど依存しないような,「属性効率がよい」パタン発見アルゴリズムを開発し,この族が多項式オンライン学習可能であることを示した.3.構造化データからの対話を用いた知識獲得:本項では,構造化データからの対話的な知識獲得について基礎的な研究をおこなった.関係データベースではさまざまな演繹質問や統合性制約が一階ホーン論理式として表される.主結果として,一階ホーン論理式の部分族ACH(k)に対する多項式時間学習アルゴリズムを与え,さらに,これが質問計算量に関してほぼ最適であることを示した.他にも,テキストデータベース用の質問言語の計算量と表現力を調べ,完全に特徴づけた.また,本年度に1項のテキストデータマイニング・システムの小規模プロトタイプを試験的に実装し,問題点の洗い出しをした.次年度は,これに基づいて効果的な実装法を研究し,分子生物学のデータを対象として大規模な知識獲得実験をおこないたい.
  • 文部科学省:科学研究費補助金(奨励研究(A))
    研究期間 : 1996年 -1996年 
    代表者 : 有村 博紀
     
    本研究の目的は,CADデータベースやマルチメディアデータベースのように,大量の非均質なデータを含み,同時に,主に正例だけを含むようなデータベースに対しても適用可能な,新しい学習手法を開発することである。具体的な学習手法としては,申請者らが開発した「極小多重汎化」手法を採用し,大規模科学データベースを対象として,高速な極小多重汎化手続きを開発することを目指して研究をおこなった.具体的には,極小多重汎化をデータベースを対象に拡張し,高速な学習手続きを開発した.1.まず,データの理論的モデルの基盤として,関係データベースをとりあげ,知識表現の立場からこれを概念階層の導入によって拡張した.こうして拡張されたデータベースを対象として,高速な極小多重汎化手続きを開発することに成功した.この手法の能力と適用限界を理論的に調べた.2.さらにこの汎化手続きを計算機上に実装し,その有用性をデータベースからの知識獲得に関する計算機実験を通じて確認した.この際,確率的選択を含む数種の経験的発見法を導入により,実際的な効率の向上をはかった.3.近年のマルチメディア等の高度データベースの急激な発展に対処するため,上で開発した拡張データベースにテキストデータかたの知識獲得手続きを組み込むための基礎的研究をおこなった.文字列パターンとよばれる表現をとりあげ,パターンへの概念階層の組み込みと高速汎化アルゴリズムの開発をおこなった.4.また,複数概念の個数にあらかじめ上限を与えない場合の学習可能性について理論的考察をおこない,正例からの学習の可能性と上限を明らかにした.5.背景知識を許した関係記述言語である基本形式体系の計算量についても考察した.
  • 文部科学省:科学研究費補助金(奨励研究(A))
    研究期間 : 1995年 -1995年 
    代表者 : 有村 博紀
     
    本研究では,大規模オブジェクト指向データベースを対象とした知識獲得システムの実現方法をあきらかにすることを目的として,研究をおこなった.このために申請者が提案した学習手法である極小多重汎化を,データベースを対象に拡張し,高速な学習手続きを開発した.具体的には,つぎの研究をおこなった.(1)オブジェクト指向データベースにおける概念継承と背景知識を統一的にあつかうために,背景知識として論理プロブラムが与えられた場合に,与えられデータベースの極小汎化を求める問題を考察し,高速な汎化手続きを開発した.さらに,この汎化手続きによって,制限された述語論理プログラムのクラスが,正例だけから多項式時間極限可能であることを示した.(2)計算量理論の立場から,最も単純な体系である原子式の極小多重汎化問題を考察し,未知仮説の正確な同定に必要な時間計算量と質問情報量を理論的に明らかにした.これにより,正確な同定を高速におこなうには,知識獲得システム自身が決定実験をおこない,必要な例を動的に得る仕組みが必要なことがわかった.(3)開発中の知識獲得システムを,本研究で得た汎化手続きの導入によって拡張し,遺伝子配列と蛋白質に関するオブジェクト指向データベースを対象として知識獲得実験をおこなった.この計算機実験によって,開発した汎化手続きの実際のデータベースにおける有効性を検証した.

教育活動情報

主要な担当授業

  • コンピュータサイエンス演習Ⅱ
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 工学部
  • 情報知識ネットワーク特論
    開講年度 : 2018年
    課程区分 : 修士課程
    開講学部 : 情報科学研究科
    キーワード : 情報検索,パターン照合アルゴリズム,パターン発見,データマイニング,半構造データ
  • プログラム理論と言語
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 工学部
  • 大学院共通授業科目(一般科目):自然科学・応用科学
    開講年度 : 2018年
    課程区分 : 修士課程
    開講学部 : 大学院共通科目
  • 情報知識ネットワーク特論
    開講年度 : 2018年
    課程区分 : 博士後期課程
    開講学部 : 情報科学研究科
    キーワード : 情報検索,パターン照合アルゴリズム,パターン発見,データマイニング,半構造データ
  • コンピュータアーキテクチャ
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : ハードウェア構成、機械語命令、ノイマン型計算機、並列計算機、スーパーコンピュータ、ファームウェア、マイクロプロセッサ、パイプライン処理、キャッシュメモリ、プロセス、スレッド、スケジューリング、割り込み、デッドロック、メモリ管理、仮想メモリ、ページング、ファイルシステム
  • アルゴリズムとデータ構造
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : 計算量,ソート,探索,グラフ,文字列照合
  • オペレーティングシステム
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : プロセス、スレッド、スケジューリング、リソース、デッドロック、メモリ管理、スワッピング、仮想メモリ、ページング、セグメンテーション、I/O、インタフェース、ファイルシステム
  • 情報理工学演習Ⅲ
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : データ構造,アルゴリズム,ソート,再帰,音声音響信号処理,画像信号処理,画像認識,コンピュータグラフィクス
  • 複合情報工学
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : ハードウェア構成、機械語命令、ノイマン型計算機、並列計算機、スーパーコンピュータ、ファームウェア、マイクロプロセッサ、パイプライン処理、キャッシュメモリ、プロセス、スレッド、スケジューリング、割り込み、デッドロック、メモリ管理、仮想メモリ、ページング、ファイルシステム
  • 情報理論
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : 情報量、エントロピー、情報源、通信路、符号化、データ圧縮
  • コンピュータシステム
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : ハードウェア構成、機械語命令、ノイマン型計算機、並列計算機、スーパーコンピュータ、ファームウェア、マイクロプロセッサ、パイプライン処理、キャッシュメモリ、プロセス、スレッド、スケジューリング、割り込み、デッドロック、メモリ管理、仮想メモリ、ページング、ファイルシステム
  • 情報理工学演習Ⅰ
    開講年度 : 2018年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : コンピュータシステム、ネットワークとクラウド、計算機アーキテクチャ、オペレーティングシステム、コンピュータネットワーク、Web技術、クラウド技術

大学運営

学内役職歴

  • 2013年4月1日 - 2015年3月31日 知識メディア・ラボラトリー長

委員歴

  • 2011年 - 2019年09月   日本学術振興会   先端科学シンポジウム専門委員(Frontiers of Science Symposia)
  • 2017年06月 - 2019年05月   人工知能学会   代議員
  • 2017年06月 - 2019年03月   文部科学省   情報科学技術委員会委員
  • 2015年06月 - 2016年05月   人工知能学会   2016年度全国大会 プログラム委員長
  • 2014年06月 - 2016年05月   人工知能学会   理事
  • 2008年05月 - 2014年04月   電子情報通信学会コンピュテーション研究専門委員会   専門委員
  • 2008年 - 2014年   JSTさきがけ「知の創生と情報社会」,領域(領域統括:中島秀之)   アドバイザー
  • 2007年 - 2013年09月   発見科学国際会議(International Conference on Discovery Science)   運営委員会委員(Steering committee member, International Conference on Discovery Science)
  • 2006年05月 - 2008年04月   電子情報通信学会コンピュテーション研究専門委員会   副委員長   電子情報通信学会コンピュテーション研究会
  • 2006年04月 - 2008年03月   人工知能学会 人工知能基礎問題研究会   主査
  • 2008年 - 2008年   日本学術振興会先端科学シンポジウム   PGM (UJFoS2008)   Frontiers of Science Symposia, Planning Group Member.
  • 2006年 - 2007年   JST CRDS 科学技術未来戦略ワークショップ「予測と発見」   分科会Bリーダー
  • 2006年 - 2007年   人工知能学会   人工知能基礎問題研究会主査(H18-H19)   人工知能学会
  • 2006年 - 2006年   1st Int'l Workshop on Data Mining and Statistical Science (DMSS-2006), Sapporo   Chair
  • 2004年 - 2006年   人工知能学会   評議員(H16-H17)   人工知能学会
  • 2004年 - 2006年   情報処理学会   データベース研究会研究運営委員   情報処理学会
  • 2004年 - 2006年   人工知能学会人工知能基礎問題研究会   幹事   人工知能学会人工知能基礎問題研究会
  • 2003年 - 2005年   日本学術振興会先端科学シンポジウム   PGM (JGFoS'04, JGFoS'05)
  • 1999年 - 2000年   the 11th International Conference on Algorithmic Learning Theory (ALT'00, Sydney)   PC co-chair

社会貢献活動

  • 公開講座(一部は道民カレッジと連携)
    期間 : 2009年09月 - 2011年11月
    役割 : 講師
    主催者・発行元 : 北海道大学 大学院情報科学研究科
    イベント・番組・新聞雑誌名 : COE公開講座「くらしの中の情報科学」ー ネットワークからナノテク・ゲノムまで ー


Copyright © MEDIA FUSION Co.,Ltd. All rights reserved.