@misc{oai:ir.soken.ac.jp:00001437,
 author = {松井, 正一 and マツイ, ショウイチ and MATSUI, Shouichi},
 month = {2016-02-17, 2016-02-17},
 note = {階層メニューは、GUIでコマンドを指定する目的でオフィスアプリケーション、携<br />帯電話、Webアプリケーションなどの様々な分野で広く用いられている。階層メニュ<br />ーは機能が配置されたメニュー項目と下位のメニューを持つメニュー項目が複数配置<br />された構造を持つ。階層メニューの性能としては様々なものが考えられるが、記憶の<br />しやすさなどの使い勝手を考慮しつつ、目的とする機能にできるだけ早く到達できる<br />ことが最も基本とされており、メニューの性能評価で一般的に用いられている。本論<br />文も、この目的とするメニュー項目に辿り着くまでの平均時間を「平均到達時間」と<br />呼び、それを階層メニューの性能とする。この性能は、メニューの構造、レイアウト、<br />色などの多くの要因によって決まる。現在までに、ユーザインタフェース分野で多く<br />の研究が行われ、様々なメニュー方式が提案されている。また、単一階層のメニュー<br />の最適化についてはいくつかの研究が行われてきたが、階層メニューの構造を変更す<br />ることで、性能を向上する最適化問題としてとらえた研究はほとんどない。<br />　単一階層のメニューの最適化に関しては、Liuらは視覚探索のモデルをメニュー設計<br />に適用し、平均到達時間を最小化する設計を試みている。階層メニューに関しては、<br />Amantらは利用頻度の高い項目を、メニュー階層の浅い位置に上げていくという単純<br />な手法でも、30%程度の時間削減が可能なことを示している。これらの研究において最<br />適化問題として扱われている設計問題は、単一階層のメニューのみであり、また階層<br />メニューの設計問題では使い勝手を明示的に考慮していない。これに対して、本論文<br />では、探索・意思決定時間とポインティング時間の双方を考慮し、かつ使い勝手を表<br />す指標も目的関数に採り入れて、平均到達時間と使い勝手を表す指標の加重和を最小<br />化する問題として定式化する。定式化では、ユーザが理想的な行動をした場合の平均<br />到達時間を考える。すなわち、ユーザは目的の項目のあるサプメニューまで誤りなく<br />辿り着くものとし、サブメニュー内の項目を誤りなく選択するものと仮定する。この<br />仮定の下で、ユ?ザの利用頻度に従って、平均到達時間を最小化するメニューを設計<br />する問題として定式化する。<br />　メニュー項目への平均到達時間を最小化する階層メニューの最適化は、木構造のノ<br />ードにメニュー項目を適切に配置する問題として定式化できる。メニューの設計問題<br />は、機能に対応したノード毎に与えられる利用頻度分布の下で、平均到達時間を最小<br />化する問題となる。ただし、使いやすさの観点からは、効率だけを考えた項目の配置<br />は望ましくなく、項目の意味を考慮する必要がある。また、サブメニュー毎の項目数<br />が大きく異なるメニューでは、メニューの粒度が異なるため、使い勝手を損ねると考<br />えられる。この問題に対応するために、「機能の類似度」と「メニューの粒度」という<br />二つの尺度を導入する。機能の類似度はメニュー項目間の機能の類似性を表現するも<br />のであり、二つのメニュー項目に対して類似度が最大の場合に1、最小の場合に0をと<br />る関数として定義する。この尺度を用いて、類似度の低い項目が同一ノードの子ノー<br />ドとして配置されないようにする。メニューの粒度は、子ノードの持つサブメニュー<br />の数から決まる関数として定義する。これは、前述のようにサブメニューの数ができ<br />るだけ均一になるように配置するためのものである。<br />　　また、ポインティング時間はFittsの法則に従うものする。探索・意思決定時間は探<br />索時間と意思決定時間からなり、(1)熟練者は項目の配置を記憶しており探索時間を0<br />と仮定できることから、Hick-Hymanの法則によって意思決定時間をモデル化する。(2) <br />初心者では、探索時間を無視できないことから、項目数に比例する時間がかかるモデ<br />ルを採用する。<br />　先行研究によれば、階層メニューでは１ノードあたりの項目数が少なく、最大レベ<br />ルが大きなメニュー(深いメニュー)よりも、1ノードあたりの項目数が多く、最大レ<br />ベルが小さなメニュー(浅いメニュー)の方が、平均到達時間が短いと報告されてい<br />る。そこで、提案方式では浅いメニューが生成されるような解法を用いる。<br />　対象とする問題は、非常に複雑な組み合わせ最適化問題であり、整数計画法などの厳<br />密解法では、解を求めるために項目数の階乗に比例する時間が必要であり、現実的な<br />時間では解を求めることができない。そこで、良い近似解が短時間で求まる解法を検<br />討した。提案する解法は、遺伝的アルゴリズムに基づくものである。提案方式では浅<br />いメニューが生成されるように、ノードに項目を割り当てていく割当順序を求める方<br />式を採用した。提案手法の探索性能を向上させるために、局所探索も組み入れた方式<br />を提案した。<br />　単一階層のメニューに対しては既存研究でその妥当性、近似精度が検証されている<br />が、複数階層での検証は行われていないことから、モデル化の妥当性、近似精度を検<br />証するために、PDAを用いた被験者実験を行った。19個のメニュー項目からなる小規<br />模なポップアップ型のメニューをPDA上に表示し、10名の被験者により平均到達時間<br />を測定した。この結果、モデルによる平均到達時間の予測値47%に対して、10名の平<br />均は43%となり、提案するモデル化が十分な精度を持つことが確認できた。<br />本論文では、ユーザが理想的な行動をした場合を前提とすることから、被験者実験で<br />はなく、コンピュータシミュレーションにより、提案手法の有効性を確認した。携帯電<br />話のメニューを対象として、利用パターン、モデルで用いるパラメータを様々な値に<br />設定した実験を行い、提案手法により時間を40%以上短縮できるメニュー構造を生成<br />できることを確認した。また、Zipf分布を用いて多様な利用パターンを生成し、多様<br />な利用パターンに対しても、提案手法は平均探索時間を40%から60%程度短縮できる<br />ことを示し、利用パターンに対する頑強性を確認した。<br />　以上により、本論文では、従来最適化問題として扱われてこなかった階層メニュー<br />の設計問題を、平均到達時間と使い勝手を表す指標の加重和を最小化する問題として<br />新たに定式化し、遺伝的アルゴリズムを用いた新しい解法を提案し、モデルの精度を<br />被験者実験で確認し、さらに多様な利用パターンに対して提案手法が有効であること<br />を示した。<br /><b>Abstract</b><br />Hierarchical menus are one of the primary controls for issuing commands in GUIs. The performance of a menu can be measured using many metrics, but the essential measure needs to reflect the time it takes to reach a desired target. Therefore, we used the average selection time to reach targets as a performance index. The performance of a menu depends on many factors, such as the structure, layout, and colors. There have been many studies on novel hierarchical menus, such as split menu, adaptive/adaptable menu, and so on. But there has been little work on improving the performance of a hierarchical menu by changing its structure.<br /> 　Liu et al. used a visual search model to a single level menu design. They used an opti-mization algorithm to minimize the search times. Quiroz et al. used an interactive genetic algorithm (IGA) with the user interfaces defined by XUL, but this was limited to single level menus. Amant et al. presented the concepts to support the analysis of cell phone menu hi-erarchies. They also tried to improve the menu selection time by using a simple best-first search algorithm, and got over 30% savings in selection time. <br /> 　First, we develop a formulation to deal with the menu design problem as an optimization problem. The optimization problem of hierarchical menus is considered one that deals with placing menu items on the nodes of a tree. The time to select the target item is the time to traverse from the root to the target node. The problem is to minimize the average selection time with respect to the given search frequencies of different menu items. <br /> 　We must traverse the tree from the root to the target node to select the desired func-tion.　Search/decision is necessary for the nodes, and pointing is necessary to select an item on a node. 　Therefore, traverse time from the root to a node is expressed, using the search/decision time and the pointing time. The pointing time is modeled using Fitts' law, and the search/decision time is modeled using Hick-Hyman law for an expert, and linear search for a novice. <br /> 　We introduce two metrics:<i>functional similarity</i> and <i>menu granularity,</i> to cope with the difficulties of representing and reasoning about the menu item semantics Functional sim-ilarity is a metric that represents the similarity between two menu items in terms of their functions. We use this metric to avoid placing items with little similarity in the same sub-menu of a node. If items with little similarity are put in the same submenu, it is difficult for a user to remember the menu layout. Menu granularity is a metric that reflects the number of submenus a node has as its descendants. We introduce this metric to avoid placing an item that has many children and an item that has no child as children of the same node. <br />　Due to the usability factors, the optimization as a menu design is so very hard that math-ematical programming can not solve it. Thus, we apply GA to automatically optimize the menu design problem.　Since the previous studies showed that breadth was preferable to depth, we used a kind of breadth-first search algorithm as the core of our proposed GA. An algorithm that places menu items one by one on a usable node can find a good solution. If we have a sufficient number of intermediate nodes, we can search for enough space to find an optimal solution. <br /> 　The accuracy of the models for hierarchical menus with plural levels has not yet been ver-ified. Therefore, we conducted experiments using a PDA to verify the model in hierarchical menus with plural levels. We measured the average selection time using small hierarchical menus that were generated for inexperienced users. There were some participants whose re-duction ratios were lower than expected, but there also were some participants whose reduc-tion ratios were higher than expected. The reduction ratios agreed well with the computedone, and we concluded that the model and the algorithm can be used to optimize hierarchical menus with plural levels. <br /> 　We experimented on the static hierarchical menu of a cellular phone where a small screen and limited input device are assumed by using a wide variety of usage patterns to confirm the effectiveness of the algorithm. We gathered usage frequency data by recording the daily usage of each function for two months, and we generated the usage frequency data from that record.　The record contained the functions that were built into the phone, and the E-mail folders and Web URLs that were added by the user. There were 129 terminal nodes, including the E-mail folders and Web URLs, in the data. We also generated the additional datasets that model different usage patterns. We also tested the robustness of the proposed algorithm by generating usage patterns using Zipf’s law. <br />　By the experiments, we concluded that the proposed algorithm can generate better menus than a forward movement. The difference in reduction ratio between the proposed algorithm and a forward movement is at least 20 points and even 40 points in many cases. The variance in the reduction ratio of the proposed algorithm is small; the standard deviation is less than3.5 points. <br />　The results showed that the algorithms can generate a better menu structure. They were able to reduce the average selection time by over 40% for a wide variety of usage patterns., application/pdf, 総研大甲第1244号},
 title = {遺伝的アルゴリズムを用いた階層メニューの最適化},
 year = {}
}