著者

水田 孝信 小林 悟 加藤徳史

雑誌

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

巻号頁・発行日

vol.2008, no.41(2008-MPS-069), pp.35-38, 2008-05-09

---

株価予測モデルにおける過剰適合について調べた。定量的分析を行うために、中間層が 1 層のニューラルネットワークを用いて中間層の数と汎化誤差の関係を調べた。その結果、中間層が多すぎると汎化誤差が上昇し、過剰適合が発生することが分かった。この現象は、株価予測モデルが “複雑すぎる” ために予測能力が低下することが起こりうることを示している。また、学習させるファクターが異なる 2 つのモデルの予測リターンを比べた結果、適切な学習を行ったときに最も予測が似てしまうことが分かった。

著者

小泉 和真 冨永 和人

出版者

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

雑誌

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

巻号頁・発行日

vol.2007, no.128, pp.93-96, 2007-12-21

---

人工化学とは仮想的な化学系を表現する計算モデルである.我々は文字列のパターンマッチと組み換えに基づく人工化学を提案している.人工化学を用いた一般的な研究では,設定をシミュレータに与えて計算機実験を行い,その結果を得る.これに対して我々は,とある結果を引き起こす設定がいかなるものであるか推論する手法の確立を目指している.本研究では,この目的のために自動推論器の試作を行なった.この推論器は,人工化学系の初期状態と目的の分子を与えろと,その分子の生成可能性を判定する.推論器の実装にはオブジェクト指向言語 Ruby を用いた.作成した推論器によって例題を解き,推論器が期待通りに動作することを確認した.Artificial chemistries are models of virtual chemical systems. We proposed an artificial chem istry based on string pattern matching and recombination. A general research methodology using an artificial chemistry is to give a set-up to a simulator and run a simulation to obtain results. In contrast, we attempt to establish a methodology to infer a set-up to cause a desired result. This study built a prototypical reasoning software, which decides whether a target molecules are produced in a given system of our artificial chemistry, implemented with Ruby, an object-oriented language. We solved example problems with the software, thereby confirmed that it worked as expected.

著者

乾 伸雄 品野 勇治 小谷 善行

雑誌

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

巻号頁・発行日

vol.2004, no.92(2004-MPS-051), pp.5-8, 2004-09-13

---

本論文では、しりとり全体に含まれる文字数を最長とする文字数最大しりとり問題をネットワークフロー問題としてモデル化し、LPベースの分枝限定法による解法および実験結果について述べる。単語数を最大にする最長しりとり問題に対して、問題を記述するための変数が最大単語長に比例して多くなる特徴を持つ。実験は実際の辞書に含まれる単語について行った。実験の結果、最長しりとり問題と同じく文字数最大しりとり問題は現実的な時間で解ける問題であることがわかった。

著者

古川園 智樹 井庭 崇

雑誌

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

巻号頁・発行日

vol.2006, no.29(2006-MPS-058), pp.93-96, 2006-03-17

---

本稿は,1816 年から2000 年の間において,国家間の同盟のネットワークがどのように変化したのかを明らかにする.分析の結果,第2 次世界大戦以降の米国を中心とする同盟ネットワークは,スモールワールド・ネットワークであることが明らかになった.

著者

下田 明宏 涌井 智寛 星野 哲男 畠山 正行 荒木 俊郎

雑誌

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

巻号頁・発行日

vol.2005, no.37(2005-MPS-054), pp.17-22, 2005-05-10

---

DNA計算の分野において計算アルゴリズムが幾つか提案されている.提案されたDNA計算アルゴリズムは分子生物学的なDNA計算は実験によって実現されるものであり,実験を行って検証しなければならない.しかし実験にはいくつかの困難があり容易ではない.そこでDNA計算シミュレータがこれらの実験の前段階として有効である.しかし現存するシミュレータは種類も少なく,また,時間的に連なる複数の操作手続きを連続して実行できるようには作られていない.そこで我々は連なった操作が行える様な仕組みを実現したDNA計算シミュレータを開発した.開発したシミュレータを既存のVNAシミュレータと比較した.その結果,計算精度は共通機能についてはほぼ同じ精度であることが分かった.それに加えて,開発したシミュレータは,連続した操作を実現した以外にも幾つかの新しい特徴を持っている.それは入出力のDNA分子の種類数を大幅に増やしたために,DNA分子のうち従来のシミュレータでは無視されていたごく少数のDNA分子も保持でき,シミュレーションに組み入れられたことである.今後の課題は本シミュレータの妥当性と実現性を分子生物学的な実験と比較して検証すること,及び,他の複雑な計算シミュレーションに応用できるように機能を拡張することである.

著者

謝孟春 奥村 喜臣

出版者

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

雑誌

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

巻号頁・発行日

vol.2006, no.29, pp.101-104, 2006-03-17

参考文献数

7

---

自動車の台数は年々増加し、通勤時の主要道路や、長期休暇期間中の有名観光地への道路では、渋滞は避けられない問題として浮かび上がってきた。その改善策を考慮する手段として、交通シミュレーションが挙げられる。本研究では、セルオートマトンを用いて交通流シミュレータを構築し、"御坊IC"周辺の交通流をシミュレーションする。セルオートマトンはそれぞれのセルが局所近傍則に従い相互に影響を及ぼしあうので、全体として複雑に振舞う体系である。ここでは、自動車は視界距離内における前方の自動車を認識し、安全距離を保ちながら、セル領域上の前方へ移動する。対象領域は阪和道、国道42号線と、その両者をつなぐ道路を対象とする。セルオートマトンによるシミュレーションで得られたデータと実際のデータを比較し、高速道路の開通が一般道路の渋滞緩和への影響を分析する。With the continuous increasing of vehicles, traffic congestion is a more and more serious problem to deal with. Traffic simulation is tool for traffic analysis and is helpful to find ways for easing traffic jams. The object of this research is to create a Traffic Simulator using cellar automata and to simulate traffic flow around "Gobo Interchange". In CA, each cell examines the state of neighboring cells, with a simple rule then to change the state of a cell depending on the state of neighboring cells. On the whole, however, very complicated behavior is exhibited because each cell mutually influences the neighboring cells. The model area, we have taken Hanwa expressway, National highway 42 and the roadway that connect them. In the system is loaded a function of "Interchange" with counters to record the number of vehicles. The analysis shows the approximative agreement of the simulated data with the actual data, confirming the effectiveness of the simulator.

著者

森本 孝紀 徳丸 正孝 村中 徳明 今西 茂

出版者

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

雑誌

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

巻号頁・発行日

vol.2005, no.20, pp.45-48, 2005-03-10

参考文献数

3

被引用文献数

1

---

被災道路復旧計画問題とは,被害を受けた道路網の交通機能を,効率的に回復させるための復旧計画を求める問題である.従来までの被害モデルは簡単化されたものであり,リンク単位で被害を発生させていた.そこで本研究では,現実の被害状況をもとに被害を「通行止め」と「通行規制」の2種類の状態をモデル化する.また,GAのコーディングを改良することで,通行止めとなる被害箇所の多階復旧を可能としている.さらに,GAの適用方法に関する検討実験を行い,その有効性を示す.Damaged Road Restoration Scheduling Problem is a problem to request the restoration schedule that recover efficiently for a traffic function of the damaged road network. The damage model until the past was the simplified one, and damage was caused each link. In this research, damage is modeled based on an actual damage situation, two kinds of states, "closed to traffic" and "regulation of traffic", is modeled. Moreover, multistory restoration is enabled by improving the method of coding GA in "closed to traffic". In addition, the examination experiment concerning the method of applying GA is conducted, and the effectiveness is shown.

著者

住川 裕岳 宮代 隆平 中森 眞理雄

出版者

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

雑誌

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

巻号頁・発行日

vol.2007, no.64, pp.5-8, 2007-06-25

参考文献数

9

---

本研究では、スポーツスケジューリング問題の一種である巡回トーナメント問題を扱う。巡回トーナメント問題とは、ホーム&アウェイ形式の二重総当りリーグ戦を行うスポーツにおいて、各チームの移動距離の総和を最小化した試合日程を構築する問題である。この問題では、巡回セールスマン問題の難しさに加え、あるチームの対戦順序が他チームの対戦順序に影響を与えており、問題の難易度を増している。これまでの研究により、巡回トーナメント問題に対してはシミュレーテッド・アニーリングが有効であることが示されていたが、本研究ではタブーサーチを用いて最適化を行った。計算機実験の結果、既存のアルゴリズムによる結果に匹敵する質の良い解が得られた。The traveling tournament problem is a well known benchmark problem in sports scheduling. This problem has both an optimization aspect like the traveling salesman problem and a feasibility aspect as in many scheduling/timetabling problems. Since the traveling tournament problem was established, a number of researchers have tackled the problem with various optimization techniques. Recent researches indicated that simulated annealing algorithms are effective for the traveling tournament problem, and few results by tabu search are reported so far. In this manuscript, we propose a tabu search algorithm for the traveling tournament problem. Our computational experiments show that the proposed algorithm generates good solutions, which are competitive with solutions by simulated annealing algorithms.

著者

仙石 浩明 吉原 郁夫 今川 徹三

出版者

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

雑誌

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

巻号頁・発行日

vol.1995, no.66, pp.19-26, 1995-07-19

参考文献数

4

被引用文献数

3

---

遺伝的アルゴリズム()は、探索が大域的、制約条件の変化に柔軟、などの長所があり、開発・保守工数を削減できるが、遺伝子コーディング法、交差方法などを問題毎に考案しなければならない。一方、従来から広く用いられてきたヒューリスティック探索法は、人手で解かれていたような問題を解く場合は、容易にアルゴリズムを作ることができる。しかし実問題に適用するには、より詳細な知識を組み込むなどのチューンアップが必須であり、開発・保守工数がかかるという短所がある。そこで、ヒューリスティック探索において探索木の分枝選択に優先順位を定め、この優先順位をGAで最適化する手法を提案する。本提案手法をバス仕業ダイヤ作成システムに応用し、実用上十分な仕業ダイヤ作成が可能となった。本システムは実際にダイヤ改正で使われた。Genetic Algorithms (GAs) have advantages in ability to search globally and flexibly, but we have to design the gene coding and the crossover method depending on each problem. On the other hand heuristic search algorithms are easy to develop and have been widely used to solve the problems, which have been conventionally solved manually, but for practical applications, we have to tune up the algorithms, for example, adding knowledge in detail, adjusting parameters, and so on. In this paper, we present a method using GA as an optimizer of the heuristic search. In our method, GA tunes the priorities of choosing branches in search tree, with which heuristic search algorithm can find optimal solutions. We apply our method to bus drivers scheduling systems. It can generate enough practical schedules, and is already used for revising drivers schedules.

著者

安藤類央 武藤佳恭

出版者

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

雑誌

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

巻号頁・発行日

vol.2006, no.29, pp.77-80, 2006-03-17

---

本論文では、N色グラフ彩色可能判定問題に関して、パラモジュレーション(等号調整導出)をベースにした定理証明に、Hot List Strategyと呼ばれる計算戦略を適用することの有効性を示す。同計算戦略を用いると、等価代入の手法によっては目的する節が導出される前に冗長な節生成が起きる場合について、冗長な節の生成(遅延)によるCPU時間の削減を行うことが可能になる。グラフのN彩色判定問題において、等号調整導出による推論が適用できること、さらに等号調整導出の推論プロセスは、Hot List Strategyに対して効果的な適合をすることを示した。評価実験では、非ハミルトングラフであるぺテルセングラフを対象にし、彩色判定の際の生成節数やCPU時間を測定し、その結果推論の遅延と計算コストを削減できることが明らかになった。In this paper, we discuss the effectiveness of applying hot list strategy for paramodulation based N-coloring graph problem. This ATP (automated theorem proving) strategy reduces is designed to deal with a substantial delay in going to a retained conclusion, which makes it possible to reduce the CPU time occurred by redundant generated clauses. We show that paramodulation could used for formulating graph coloring problem and hot list strategy is suitable for controlling paramoudlation based resolution. In experiment, CPU time and the number of generated clauses is presented in solving coloring problem of Petersen graphs.

著者

鬼塚健太郎

雑誌

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

巻号頁・発行日

vol.1998, no.27(1997-MPS-018), pp.67-72, 1998-03-20

---

近年になって、発達してきたストーリー性のあるマルチシナリオゲームにおいて、プレイヤーにとって、自由度の高いシナリオゲームを作るためのモデリング手法について考える。シナリオ中の登場人物、欧界設定、登場人物の行動についてモデル化し、新しいゲームの可能性を探る。

著者

坂口 琢哉 石崎 俊

出版者

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

雑誌

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

巻号頁・発行日

vol.2004, no.130, pp.9-12, 2004-12-20

参考文献数

9

---

大規模なスポーツのリーグ戦などで試合日程を作成する際,考慮すべき要素の一つに各チームの移動距離の最小化が挙げられる.本稿ではこの問題を組み合わせ最適化問題と捉え,ニューラルネットワークを用いて総移動距離の短い試合日程を作成するモデルを提案した.提案モデルにおいて,試合日程作成のために必要不可欠な制約は制約層のニューロン,一方チームの長距離移動抑制や連続した同一対戦試合の禁止といった付加的な条件は側抑制として符号化した.また,本モデルを日本のプロ野球のセ・リーグ公式戦日程に適用した結果,総移動距離が現状に対し約60%であるような試合日程を作成できた.When creating the schedule of a major sports league or so, the minimization of total travel cost for each team is one of the most important factors we should consider. In this study we regarded this problem as combinational optimization problem, proposed a model with neural network architecture creating a schedule with keeping total travel cost low. We encoded several constraints essential for consistent scheduling as neurons in a constraint layer, while additional factors inhibiting long-range travel or same match-up series as lateral inhibition. We applied this model to the schedule of NPB(Nippon Professional Baseball) Central League, and succeeded to create a schedule in which total travel cost was about 60% compared to the real schedule.

著者

長尾 年恭

雑誌

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

巻号頁・発行日

vol.1997, no.30(1996-MPS-012), pp.1-7, 1997-03-24

---

On 5:46Am January 17 1995 devastating earthquake with magnitude 7.2 hit western Japan. This earthquake was finally named "Hanshin-Awaji earthquake disaster" and lost over 5 500 people. Were we able to predict this earthquake? We introduce the method of earthquake prediction by monitoring electro magnetic phenomena especially telluric current measurements.

著者

久保 琢磨 宇野 毅明

出版者

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

雑誌

情報処理学会研究報告数理モデル化と問題解決(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.

著者

池田 諭 品野 勇治 中森 眞理雄

出版者

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

雑誌

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

巻号頁・発行日

vol.2002, no.19, pp.17-20, 2002-03-04

---

与えられたグラフG=(V E)が連結か否かを判定することを考える.O(|V|+|E|)のメモリ領域を用いることが出来るならば,O(|V|+|E|)の手間で連結性が判定できることがR.E.Tarjanによって示されている.本論文の目的は,分散システム上で動作する連結性判定分散アルゴリズムを求めることである.本論文では,R.Aleliunas R.M.Karp R.J.Lipton L.Lovaaszおよび C.Rackoff による?RW を用いる手法を取り上げている.そして,簡単な前処理をすることが可能な状況ならば,O(|V|^2 ?log|V|)の手間でほぼ確実に無向グラフの連結性が判定出来ることを示した.また,有向グラフの場合もグラフの直径と次数の上界が分かっているならば同様にして多項式オーダーで判定できることを示した.We consider the reachability problem for directed and undirected graphs. Let G=(V,E) be a directed graph. In [1], R. E. Tarjan has showed the algorithm of O(|V|+|E|) sapce and time complexity. We show a probablistic distributed algorithm for this problem in space O(1) and time O(|V|^2 \log |V|). In this paper,\ we discuss a variant of the algorithm which based on random walk, due to R.Aleliunas, R.M.Karp, R.J.Lipton, L.Lovaasz, and C.Rackoff. We show an improvement of their algorithm from O(|V|^3 log |V|) to O(|V|^2 log |V|) in time helped with a simple preprocessing. In a directed graph,\ we also show their original algorithm run in time O(|V|^2log|V|),\ if the diameter and the degree of the graph is bounded.

著者

田中 秀俊

出版者

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

雑誌

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

巻号頁・発行日

vol.1999, no.76, pp.9-12, 1999-09-21

---

風速分布を単純な混合モデルである対角共分散混合ガウシアンモデルで分類し、その分類の変遷を隠れマルコフモデルで解析して風速の区間推定を試みた。気象庁の提供している高層気象観測データから、1993年∼1997年の鹿児島上空を選んで実験したところ、地表から高度20kmまでにわたっておよそ70%の確率で風速が20m/s以下であるような2週間が予想可能という結果を得た。Wind profiles are classified by mixture Gaussian model and the transition of the classes are analyzed by hidden Markov model so that wind speed could be predicted. Wind profile data from 1993 to 1997 at Kagoshima which are provided by Japan Meteorological Agency indicate that we can estimate consecutive 2 weeks when every wind speed checkpoint from the ground through 20km height are less than 20m/s in about 70% probability.

著者

松本 光弘 清原 良三 沼尾 正行 栗原 聡

出版者

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

雑誌

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

巻号頁・発行日

vol.2008, no.126, pp.53-56, 2008-12-10

被引用文献数

1

---

近年,携帯電話は高機能化しており,様々なアプリケーションを利用することができる.その一方,多くのアプリケーションの中から必要なものを選択する必要があり,携帯電話の操作は複雑になっている.しかしながら,携帯電話はユーザが素早く且つ手軽に所望のアプリケーションを利用できることが非常に重要である.一方,携帯電話の利用に関して,ユーザは時刻や位置,それまでの操作の状況や日々のスケジュールなどの,様々な外的要因に依存して利用する傾向がある.このような外的要因に基づく携帯電話の特徴的な利用パターンを抽出できれば,ユーザが所望するアプリケーションを予測することができる.本論文では,時空間的利用履歴を基にしたアプリケーション推薦するシステムを構築し,頻度のみを用いたアプリケーション推薦システムと比較することで,本システムの評価を行った.Recently, cellular phones are made high performance, because they provide with various application. On the other hand, a user must select the application one wants to use from among a complex application menu structure. A cellular phone might be used in various contexts and, therefore, it is very important that users can find the desired application easily and quickly. Besides, users use some applications depending on a variety of external factor(e.g. time, location, process of operation and dairy schedule et.al). Hence, there are some patterns in our daily behavior. So, if the habitual operation patterns can be extracted, this means that we can predict the operation of cellular phone. In this paper, we built an Application Recommendation System Based on Temporal-spatial History Log, and compared with a conventional frequency based application recommendation system.

著者

宮村(中村) 浩子 宮代隆平 七夕高也 品野勇治 斎藤 隆文

出版者

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

雑誌

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

巻号頁・発行日

vol.2007, no.19, pp.45-48, 2007-03-03

参考文献数

8

---

大規模な階層データを,限られた空間内へ効率的に表現する適応的表示法を提案する.階層データは属性値をもつノードと親子関係を表わすリンクから構成されており,それぞれをプリミティブで表すことで構造を視覚的に捉えられる.しかし,大規模階層データを表示する際に,隣り合うノードやリンクが重なり合ってしまう問題がある.そこで本論文では,大規模階層データを木構造で表す際に,ノードの密集具合に応じて木の表現方法を選択する適応的表示を提案する.さらに本提案手法を大規模分枝限定木に適用し,その効果を検証する.We propose an adaptive visualization technique for a large-scale hierarchical dataset within limited display space. A hierarchical dataset has nodes and links that represent the parents/child relationship. These nodes and links are described using graphics primitives. When the number of these primitives is large, it is difficult to recognize the structure of the hierarchical data, because many primitives are overlapped within a limited region. In this context, we propose an adaptive visualization technique for hierarchical datasets. The proposed technique selects an appropriate graph style based on the density of the nodes. In addition, we demonstrate the effectiveness of the proposed method by applying it to the growing process of a large branch-and-bound tree

著者

上山薫 上島 康孝 左毅 北 栄輔

出版者

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

雑誌

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

巻号頁・発行日

vol.2008, no.126, pp.139-142, 2008-12-10

参考文献数

3

---

本研究ではペイジアンネットワーク (BN) を用いた株価指数の変動予測について述べる.最初に 2007 年 1 月から 10 月の予測を行ったところ,テクニカル分析よりも高い的中率を示した.続いて,2007 年と日本のバブル崩壊期の的中率の変化を詳しく調査したところ,的中率の低下をもとに,問題が顕在化した時期でなく,問題の原因が生じた時期をある程度推測できることが分かった.This paper describes the application of the prediction of stock index by using Bayesian network. In the prediction of FTSE100 in 2007 January - October, the prediction accuracy of Bayesian network was better than that of technical analysis. Next, one observed the history of the prediction accuracy of index in 2007 and during the years of the asset-inflated economy in Japan. The results indicated that the reduction of prediction accuracy is effective for finding the reasons of the problems.

著者

遠里 由佳子 松田 秀雄 橋本 昭洋

出版者

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

雑誌

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

巻号頁・発行日

vol.1999, no.76, pp.41-44, 1999-09-21

---

正例として与えられた文字列集合からそれらの特徴を表す極小でかつ既約なパターンの組を求める問題をMINL問題と呼び,パターンの組の数を予め制限することにより,この問題を解く多項式時間アルゴリズムが知られている.同じ機能を持つ遺伝子を同じ文字で表すと,このアルゴリズムは遺伝子クラスタの機能分類に応用できるが,遺伝子の機能は階層的に分類されているため,どの階層の機能分類を使うか指定しないとこのアルゴリズムを適用することができない.そこで,本研究では,パターン間に概念階層を導入し,情報量というパターンの評価基準を使ってMINL問題を近似的に解く多項式時間アルゴリズムを提案し,実際に遺伝子クラスタの機能分類に適用した結果をもとに性能評価を行う.The MINL problem is a problem that finds a minimum and reduced set of patterns explaining a given set of positive example strings. By restricting the number of patterns to be a fixed constant in advance, a polynomial time algorithm that solves this problem is known. This algorithm is applicable to determining gene clusters based on functional classification if genes having the same function are expressed with the same character. However, since gene function is typically classified hierarchically, the above algorithm can only be applied on a single level of the classification hierarchy. In this paper, we extend the MINL problem to cover hierarchical classifications, and propose a novel polynomial time algorithm utilizing entropy to solve the extended problem. In an experiment, we applied our method to gene cluster analysis of actual gene data.