著者

宇野 毅明

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.31, pp.55-62, 2003-04-18

被引用文献数

5

---

グラフG=(V, E)の頂点集合Sの任意の2頂点間に枝があるとき、Sをクリークとよぶ。また、2部グラフG=(V_1∪V_2, E)の頂点集合Sの任意の頂点v_1 ⋴ V_1とv_2 ⋴ V_2の間に枝があるとき、Sを2部クリークとよぶ。本稿では,巨大で疎なグラフ極大クリークと極大2部クリークを列挙する,実用的に高速なアルゴリズムを提案する。グラフの最大次数を△とすると,本稿の改良により,極大クリーク1つあたりの計算時間がO(|V||E|)からO(△^4)に,極大2部クリークはO(|V||E|)からO(△^3)に改善された。計算機実験により,ある程度ランダムな入力に対しては,1つあたりO (△^2)時間程度しかかからないことを示し、さらに現実のデータに対しても高速であることを示す。

著者

宇野 毅明

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2001, no.93, pp.33-40, 2001-09-25

参考文献数

7

被引用文献数

1

---

議会においては 各党が保有する議席数 法案決定に必要な賛成の票数によって 各党の発言力は変化する. その発言力を数理的なモデルを用いて表現したものが投票力指数である. いくつかのモデルが提案されており それぞれについて その指数を計算するアルゴリズムが研究されている. 本稿では これらのアルゴリズムの改良方法を示し 1つの党の指数計算と同じ計算量で すべての党の指数を計算するアルゴリズムを提案する.In a council, the power of parties changes as the number of persons in the parties, and the number of votes to win. Power indices are indices representing power of parties in the mathematical way by using mathematical models. There proposed several models, and algorithms for computing indices for these models. In this paper, we propose an improvement for these algorithms, and propose improved algorithms for computing indices of all parties running in the time for computing indices of constant number of parties.

著者

Demaine Erik D. Demaine Martin L. 上原 隆平 宇野 毅明 宇野 裕之

出版者

京都大学

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1744, pp.48-55, 2011-06

著者

前川 浩基 内田 将史 大内 章子 宇野 毅明 羽室 行信

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.28, 2014

---

Twitterのユーザ関係データに対して我々が開発したデータ研磨手法を適用することで、潜在的な近接関係の補完、およびノイズを除去が可能となり、ユーザのクラスタを鮮明化することができる。この手法を、女性の三年育休問題に関するTwitter投稿データに適用することで、ユーザの意見の変化検出を試みる。

著者

武富 有香 松田 智裕 須田 永遠 宇野 毅明

雑誌

じんもんこん2022論文集

巻号頁・発行日

vol.2022, pp.213-220, 2022-12-02

---

#metoo 運動以降,ソーシャルメディア上にあらわれるようになった誹謗中傷のメカニズムとオンライン上の言説空間の全体像を理解するために,性暴力のトピックについて語る人々の書きぶりや言い回しにそって語りを類型化し,コメントにラベルをつけて分析を試みる.まず,性暴力の告白やその暴力の被害者に関するYahoo!Japan ニュース上の記事に対するコメントを読み,類型を作成する.この類型にしたがってコメントにアノテーションを行い結果を観察すると,得られた結果と社会学および哲学の既存研究の知見との対応が見出せると同時に,その既存研究に新たな仮説を付け加えることができる.本研究では質的に読まれていたコーパスを量的に扱えるようにする情報学的なアプローチをとる一方で,類型化とアノテーションの作業,すなわち精緻にテクストを読む技術が必要な部分は人手で行う.この手法を用いることで類型に質的な深みを与えることができ,この明確な解釈性を持った類型によってコーパスを”測る”ことが可能となる.

著者

和佐 州洋 有村 博紀 宇野 毅明

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2014-AL-148, no.17, pp.1-6, 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 つたり,ならし定数時間で列挙可能である.

著者

坂井 明日香 丸橋 弘明 羽室 行信 笹嶋 宗彦 加藤 直樹 宇野 毅明

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会論文誌 (ISSN:13460714)

巻号頁・発行日

vol.36, no.1, pp.WI2-I_1-12, 2021-01-01 (Released:2021-01-01)

参考文献数

12

---

Recently, data-driven sales management is widely recognized and sales at the real super-market is not the exception. For designing such strategies, first of all, we have to analyze consumers’ behavior. However, such an analysis is difficult, especially for the managers of the real shops, since they only have customers’ data of their own shops. Generally, the customers buy things not only from the managers’ shops but also other shops. The goal of this research is to develop a general method to transfer sales promotion strategy, derived from analysis on wide area, to local real shop. The authors analyzed such consumers’ characteristics who buy olive oils in Kansai region. For the analysis, we used QPR(Quick Purchase Report system, developed and managed by MACROMILL, Inc). Firstly, we divided the consumers on the QPR into five clusters, according to the simultaneous buying pattern. Then, we analyzed each of the clusters and found some emerging patterns of the purchasing behavior. Observing the patterns, we designed a marketing strategy for the real shop in Hyogo prefecture belonging Kansai district. Finally, we carried out an experiment at the shop to evaluate whether the strategy promotes the sales of the olive oil or not for six weeks. The result of the experiment showed that the marketing strategy is effective in one view. At the same time, we learned many lessons from the research, especially difficulty of the evaluation at the real shop.

著者

杉山 佳奈美 久保山 哲二 三輪 洋文 宇野 毅明

雑誌

じんもんこん2022論文集

巻号頁・発行日

vol.2022, pp.289-294, 2022-12-02

---

選挙公報のテキストデータに対して文書クラスタリングを適用した. クラスタリング手法には、 文書間類似度により形成されるネットワーク構造から密な部分構造を抽出するマイクロクラスタリン グと、代表的なトピックモデルである LDAの2種類を利用した. クラスタリング結果を比較したとこ ろ, マイクロクラスタリングではトピックの解釈が容易な解像度が高いクラスタ, 特に政党に関して より類似度が高いクラスタが多数得られることが示された. さらにマイクロクラスタリングで抽出さ れた文書クラスタを元に回帰分析を行い, 個人票志向の候補者の傾向を解析した. その結果, LDA を 用いた先行研究にあった人手によるトピック解釈の過程を経ることなく, 選挙制度改革前後の変化や 政党ごとの特色について先行研究の主張を支持する結果が得られた.

著者

宇野 毅明

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2020-AL-177, no.2, pp.1-7, 2020-03-09

---

データ研磨は,データのゆらぎを除去することで中小規模の構造を明確化し,マイニングアルゴリズムの効率や精度を高める手法である.例えば,ネットワーククラスタリングの場合,グラフの密な部分をクリークにし,疎な部分を独立集合とすることで,クラスタ構造を明確にする.通常のクラスタリングが,比較的大きなクラスタを見つけることが上手であるのに対して,データ研磨によるクラスタリングは,小さくてまとまりの良いクラスタを網羅的に,かつ独立性高く,適切な個数で見つけることができる.実際にそのクラスタは意味解釈がしやすく,新聞記事やツイッターのクラスタリングによりトピックを網羅的に見つけることが可能である.また,アルゴリズムの挙動も極めて安定しており,大規模なデータでも数十の反復で収束に至ることがほとんどである.データ研磨のアルゴリズムの基本的なデザインはシンプルであり,根拠となるデータに対する観察も明らかである.一方,収束性や得られた解と数理構造との対応は不明瞭であり,いわば実行可能仮説寄りのモデルである.本稿では,データ研磨アルゴリズムの数理的な側面を明らかにすべく,その挙動に関する数理的な解析や確率的な解析を行い,データ研磨アルゴリズムの現実データでの挙動の良さを数理的に裏付ける.

著者

中原 孝信 宇野 毅明 羽室 行信

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2013, no.27, pp.1-8, 2013-10-30

---

本研究は,Twitter の投稿内容に,データ研磨技術を用いたマイクロクラスタリングを利用することで,単語の共起関係に基づいたクラスタによる概念を構築する.そして興味対象となるツイートをできる限り多く被覆するような少数のクラスタを,ナップサック制約付き最大被覆問題を用いて抽出することで,投稿内容の要約を行う.抽出されたクラスタは,ある特定のツイート群の文章を特徴付ける単語のグループとして捉えることができ,それらを概念として扱う事で,単語を独立に扱った場合に比べて,すぐれた要約になっていることを示す.計算実験では,テレビアニメーション番組「宇宙兄弟」に関する投稿内容を対象にして提案手法を適用した.This research proposes a method to detect the contents of Twitter posts by analyzing the contents of tweets posted by viewers watching a specific TV program whenever the number of posts increase dramatically and then to summarize that content. First the proposed method creates concepts from clusters based on the co-occurrence of words. Then posts during tweet bursts are taken to be tweets of interest, and a minimal number of clusters that cover as much as possible those tweets are extracted using a knapsack-constrained maximum covering problem. A computational experiment shows the effectiveness of the proposed method with reference to a TV animation program "Space Brothers."

著者

Boris Aronov 浅野哲夫 菊地洋右 SubhasC.Nandy 笹原 慎司 宇野 毅明

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2005, no.26, pp.63-69, 2005-03-17

参考文献数

2

---

n×nの行列に整数0 ... n2-1を配置し、どの行和、列和も等しいものをsemimagic squareとよばれる。ここでは列和、行和のかわりにk×kの部分行列に含まれる要素の和を考え、この和が等しいn×n行列をzero k×k-discrepancy matrixとよぶ。そしてこのような行列はkとnがともに偶数であるとき存在し、kとnが互いに素であるとき存在しないことを示す。さらに、k m●2を整数としたときn=k*であるならばzerok×k-discrepancy matrix の存在がいえる。このzero k×k discrepancy matrixの恒星にはconstant-gap matricesを用いる。また、constant-gap matricesの特徴づけを行なう。A semimagic square of order n is an n×n matrix containning the integers 0,...,n2-1arranged in such a way that each row and column add up to the same value.We generalize this notion to that of a zero k×k-discrepancy matrix by replacing the requiremento tha the sum of each row and each column be the same by that of requiring that the sum of the entries in each k×k square contiguous sub matrix be the same.We show that such matrices exist if k and n are both even,and do not if kand n are are relatively prime.Further,the existence is also guaranteed whenever n=k ●,for some integers k,m●2. A class of matirices,called constant-gap matrices plays an important role.We give a characterization of such matrices.

著者

久保 琢磨 宇野 毅明

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.17, pp.57-60, 2008-03-05

被引用文献数

3

---

近年,組合せ最適化の実社会への適用を目的とする動きが活発となっているが,一般ユーザが容易に最適化を利用できるまでには至っていない.本研究方針は,中小規模の問題に対し,ユーザ自身が容易に最適化を利用できるしくみづくりとしている.今回はスタッフスケジューリングに焦点をあて,勤務スケジュール作成者のスケジュール作成作業の負担を軽減させる為に,あるビジネスホテルが抱える問題を対象に,スケジュール作成者にとって,容易に調整可能なスケジュールを作成することを目的とする.Recently, the movement to apply combinatorial optimization to practical problem has been active. However, general users can't easily use optimization. The direction of our research is that general users can lightly use optimization. In this paper, we focus the problem called staff scheduling and we want to reduce workload of a staff which make a schedule for every staff. Then, we aim to make an easily adjustable schedule to practical problem which the staff in certain business hotel has.

著者

中原 孝信 大内 章子 宇野 毅明 羽室 行信

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.30, 2016

著者

宇野毅明 中原孝信 前川浩基 羽室行信

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2014-AL-146, no.2, pp.1-8, 2014-01-23

---

近年の IT 技術の発達により,ビッグデータを用いたデータ解析はますますその重要性を増している.しかし,ビッグデータ解析には,データの大きさ以外にも多様性という大きな困難がある.多様なデータは,それぞれ異なる特徴を持つグループから構成されているため,全体的に解析することが困難であり,まずグループ構造の解明が重要である.既存のクラスタリング手法やパターンマイニングによってグループ構造の解明にアプローチすると,解が大量,少数のグループしか見つけられない,類似する大量の解を生成,見つかるグループの大きさに大きなばらつきがある,計算コストが大きすぎる,といった難点にぶつかることになる.本稿では,グラフクラスタリング問題に対して,そもそもデータがどのようになっていればグループ構造が抽出しやすいかを考え,ノイズの少ない明確なデータを定義し,ノイズ混じりの生データを,そのグループ構造を壊さないように明確なデータへと変換する,データ研磨という手法を紹介する.また,データ研磨アルゴリズムとデータ研磨を行ったグラフが持つ数理的な構造を紹介し,将来的に 「明確なデータ」 を研究するための礎とする.

著者

有村 博紀 宇野 毅明 湊 真一 平田 耕一 伊藤 公人 下薗 真一 喜田 拓也

出版者

北海道大学

雑誌

基盤研究(A)

巻号頁・発行日

2012-04-01

---

本研究では,実世界と情報世界が融合した巨大な情報空間から有用な知識を効率よくとりだすための大規模半構造マイニング技術の確立を目指す.とくに,大規模規模知識基盤形成システムのための基礎技術として,超高速半構造マイニングエンジンと,時空間情報を用いた半構造マイニング技術の研究開発,周辺技術として,確率的情報スキーマの導入と,知識連係技術と知識索引技術の研究開発を行った.開発した技術の実装と最適化によりプロトタイプシステムの構築を行った.