Chapter 11
Clustering of Menus
It has been asserted in previous chapters that menu structure and organization have a great impact on performance. It has also been asserted that menu organization should in some way convey a meaningful mental model of the system. The question then is how to generate good menus. Good menu organization can dramatically facilitate the search process by taking advantage of the user's knowledge about relationships among items. The menu may be organized by similarity, by hierarchical relationships, by categorization, and by clustering of items. In Chapter 8 it was concluded that organization is one of the primary factors driving the depth vs. breadth trade-off and that menu organization is important both within and between menu frames.
In this chapter methods of organizing menus will be discussed. Several issues arise regarding the source of organizing information. The first question pertains to whether organizing information is inherent in the menu items or is imposed by the task. In the first case, the database of items itself contains some sort of clustering information that can be used to organize the menu. In this case, the object is to discover the inherent organization from within. In a sense the menu items are self-organizing. Alternatively, procedural knowledge may be inferred from tasks being performed that impose an organization and sequencing of functions. In this case, the object is to discover structure in the task that imposes organization from without. Menu items are organized by task needs.
The second question is whether the organizing information should come from system designers or system users. In the first case, designers organize menus and cluster items according to their knowledge of the system. Designers are experts in how the system works and are most knowledgeable about its functionality. Database experts organize the items into clusters and categories according to their extensive knowledge about how the database is constructed. For example, databases for medical information, periodicals, and encyclopedic information are organized by those who have a vast knowledge of the subject matter domain. If experts were the only users of such systems, there would be little question as to who should organize the menu. Experts would cluster items and create structures that reflected their best knowledge of the system or database. Unfortunately, this is no small task in itself.
However, systems are in general not only used by subject matter experts but also by day-to-day users of varying levels of familiarity with the system. The user's conception of how a menu is organized or should be organized to perform a certain task may be quite different from the designer's. Similarly for databases, the user's conception of how information should be organized may be quite different from the scientific or technical organization of the information. Designers of easy-to-use systems for consumer products realize that the layout of controls should conform to user expectation rather than internal machine efficiency. Consequently, it is imperative to elicit user expectations and conceptions about how things work as basic input into the design of menus. One way to tap the information about how to organize a menu is to look at access of items in a current system. Frequency of access and the order in which items are selected provide hard data that can be used to organize a menu system.
What kind of knowledge is used to organize the menu? Cognitive psychologists make a distinction between procedural knowledge and declarative knowledge (Anderson, 1980). Declarative knowledge essentially consists of known facts about the world. For example, knowing that "run" is the first item on the menu is a fact . Declarative knowledge tends to be static and can easily be expressed verbally. Procedure knowledge, on the other hand, consists of the production rules about how to perform a task. Production rules consist of a condition and an action. When the condition is met, the action is performed. For example, knowing how to start the program by selecting "run" is procedural knowledge. The condition is wanting to start the program; the action is selecting "run." Because procedural knowledge is more action oriented, it is more difficult to express verbally.
Menu systems are composed of both declarative and procedural knowledge. The categorical structure of the system generally reflects declarative knowledge. The hierarchical structure of the categories, such as the animal kingdom shown in Figure 8.1, is factual information. The properties of the objects dictate their location in the menu structure. Consequently, menus of objects rely heavily on declarative knowledge.
Action oriented menus rely on procedural information. An item is an appropriate action given a particular condition. The user, for example, may select "stop" if the program is running. The conditional nature of items is conveyed in the hierarchical ordering of the paths in a network menu. Consequently, menus composed of functions and procedures contain information about the ordering of actions and rely heavily on procedural knowledge.
Both declarative and procedural knowledge may be represented in different types of data structures. Figure 11.1 shows four types of data structures investigated by Durding, Becker, and Gould (1977). Sets of items tend to be organized in terms of hierarchies, networks, lists, or tables. The hierarchical structure of a book for example, is represented in the table of contents, the network of communication between friends may be represented in a graph, etc. The inherent organization within a set of terms should be apparent to the user and should be structured in the appropriate way. It is hypothesized that the greater the congruency between the inherent organization of the data and its representation by the computer, the easier it will be for the user to comprehend and use the information.
A series of experiments by Durding, et al. showed that when subjects were given the terms shown in Figure 11.1 they systematically organized them on the basis of the semantic relationships inherent in them. The utility of these structures was demonstrated in a second experiment. It was shown that given skeleton structures of the appropriate type, subjects could efficiently fit items into the structure. Finally, they showed that subjects had difficulty in preserving relations when they had to organize the items into inappropriate structures. The lesson to be learned, is straight forward. The inherent structure of the items conveyed by their semantic relations should be conveyed by their organization on the screen.
Consequently, it is important to capture the inherent organization in the items displayed. From a design perspective, the question then is how to capture the appropriate knowledge to organize the menu. The next section discusses procedures for eliciting such information for hierarchical structures.
11.2 Hierarchical Clustering Methods
Imagine that a person has an unorganized set of menu items. How can they be organized? One easy method is that of clustering. But clustering may proceed in either a top-down or bottom-up manner. The approaches are illustrated in Figure 11.2. In the top-down approach the designer thinks of first order categories. Then each category is further divided into subordinate categories and so on until the actual menu items are categorized. In the bottom-up approach the designer thinks of all of the menu items first. Similar items are clustered together in groups. Then groups of items are further clustered into larger groups and so on until all groups are combined.
The top-down approach is conceptually driven in that the person has a set of concepts in mind that serve to generate categories. Lindsey and Norman (1977) note that top-down processing of information helps to structure expectations about incoming data. Top-down processing emphasizes the differences between pieces of information. Items are discriminated from one another along categorical boundaries and conceptual dimensions. On the other hand, bottom-up processing is thought of a data driven in that inspection of the items results in grouping and clustering. Bottom-up processing emphasizes the similarities among items. Items are grouped into larger and larger categories depending on common aspects.
The children's book Benny's Animals and How He Put Them Together by Selsam (1966) illustrates top-down and bottom-up processing when thinking about animals. In the story Benny takes a large pile of pictures of animals and begins to group them in a bottom-up process. Benny put birds, butterflies, and bats in one pile because they all had wings. In another pile he put worms and snakes because they were long and thin. Obviously, Benny was focusing on surface similarities.
The next day Benny's father took him to see Professor Wood at the museum. Professor Wood looked at the piles and proceeded to explain how the animals are grouped by underlying structure not by looks. He provides a top-down conceptualization by saying that the first distinction is whether an animal has a backbone. After this is done, the pile of animals with backbones is divided into fish, amphibians, reptiles, birds, and mammals; and the top-down process continues until all of the pictures have been classified. The professor is obviously emphasizing fundamental distinctions.
The tendency to consider a system from the top-down or bottom-up approach probably depends on one's expertise and perspective. From the perspective of computer programming, current thinking advocates a top-down stepwise refinement of processes. The main program loop is first considered. Then processing is subdivided into higher level modules which are in turn broken into smaller and more refined components. High level distinctions help the programmer structure the program. However, from the user's perspective of working on a particular task, top-down conceptualization may not be productive. The user's thinking is at the level of specific commands and operations rather than at higher level conceptual processes. Although Benny's clustering of animals has no scientific merit, it may be superior for many search tasks (e.g., find pictures of animals to illustrate flight.)
The greater the knowledge of surface detail and the range of specific items, the more likely it is that a person organizes the system by bottom-up clustering. The greater the knowledge of system wide perspective, the more likely it is that a person organizes the system by top-down categorization. But it has been noted that users of most menu systems are forced to consider the system from a top-down manner due to the hierarchical organization of menus (Somberg, Boggs, & Picardi, 1982). High level categories are presented to the user over and over on every traversal down the menu tree. Low level items are generally hidden and the user may never be aware of their vast number.
The question is whether menus should be generated using a top-down approach or a bottom-up approach. Chin (1986, 1987) directly compared the top-down and bottom-up clustering procedures. Twenty-five commands for an automatic teller machine were listed on cards. Some cards contained a brief description of the command. Subjects sorted the cards in either a top-down or bottom-up task. In the top-down group, subjects inspected all of the cards one at a time. They were then asked to construct hierarchical trees by first dividing the deck of cards into meaningful groups. Next they were asked to name each groups and list them in a meaningful, logical order. These groups were then further subdivided and the newly created groups were labeled and listed in a meaningful, logical order. This process was continued until the terminal nodes were reached.
In the bottom-up group, subjects inspected all of the cards spread out on a table. They were then told to form a large number of small groups of commands. Next they were asked to name each group and to list the commands within each group in a logical order. Clusters were then aggregated into larger groups. The larger groups were assigned names and the subordinate groups were listed in a meaningful order. This continued until all groups were joined at a root node.
It was predicted that the bottom-up sorting task would emphasize similarities among commands and result in larger terminal clusters than the top-down task. As expected the bottom-up task resulted in an average of 3.74 items at the terminal group which was significantly greater than the average of 2.35 for the top-down task. It was also predicted that the top-down task would result in greater menu depth. This was also confirmed. Consequently, the top-down and bottom-up methods tap different aspects of menu organization which result in different hierarchical structures.
Clustering data were aggregated across subjects using a hierarchical cluster analysis to create a menu tree based on the groups. Figure 11.3 shows the dendrogram resulting from the top-down sorting task and Figure 11.4 for the bottom-up task. The bottom-up sorting reveals a major division between object-oriented commands (e.g., "$60 Cash", "$80 Save") and action-oriented commands (e.g., "Checking to Savings", "Deposit to Savings"). The top-down sort reveals greater breadth at the top with 5 groups, cash withdrawal, save amount, payments, checking and savings account functions, and process commands.
Each dendrogram shows the hierarchical structure as well as the degree to which items are closely joined. Groupings are tighter to the extent that they occur closer to the left and looser to the extent that they are delayed and occur more to the right. Consequently, the items "$60 Save" and "$80 Save" are tightly clustered as compared to the commands "Checking to Savings" and "Savings to Checking." Inspection of the two dendrograms reveals some interesting differences. First, top-down clustering results in looser groups than bottom-up clustering. Again, in top-down clustering it is hypothesized that subjects look for dissimilarities; whereas, in bottom-up clustering they attend to similarities. Second, the top-down task resulted in more terminal nodes (17) than the bottom-up (13). Bottom-up sorting yields a smaller number of terminal nodes containing a larger number of items than top-down sorting.
The conclusion suggested here is that both the bottom-up and top-down sorting tasks should be used. Each captures an important aspect of the menu structure that can be effectively combined to generate the menu. Bottom-up sorting results in a tighter structure with greater breadth at the bottom of the tree while top-down sorting results in greater breadth at the top of the tree. Integrating the results from the two types of sorts as well as rating data on frequency and order, Chin generated a menu with two levels as shown in Figure 11.5.
Although clustering procedures have been experimentally tested in only small menu systems, in principle it can easily accommodate larger numbers of items. One of the virtues of clustering is that the clustering task itself can be partitioned into smaller tasks for different teams to work on. Clustering methods form the basis of top-down design of large systems and the categorization of large knowledge databases.
A second approach to menu organization is to lay out items in physical space. Menu items are essentially placed at coordinates in space whose dimensions represent psychological factors . The coordinates may be found directly by asking subjects to place the items in a physical space or indirectly from a multidimensional scaling of similarity measures. The dimensions of the space are assumed to have semantic meaning and serve as an organizing principle for users. Furthermore, the spatial representation may in some way capture the user's cognitive structure of the task or knowledge base.
The general methodology for determining an organization is first to obtain subjective estimates of the relatedness of all pairs of items. Measures of relatedness are then treated as distances in an n-dimensional space. Second, the obtained distance matrix is analyzed using a multidimensional scaling technique. Finally, the resulting multidimensional representation is translated into a physical layout or structure of the menu items.
McDonald, Stone, Liebelt, & Karat (1982) used a multidimensional scaling of items to design menus for a text editor. Users experienced with text editing made similarity ratings of editing functions. Menus were then designed so that similar items were closer together in lists. Performance of novice users was tested on the semantically organized menus and for comparison purposes on random menus. Although novices made fewer errors on the semantically organized menus than on the randomized menus, the difference was small. It could be that cognitive structures of the experienced users were not of great use to the novice users who may have organized the functions differently.
Menus may be laid out according to different semantic spaces based on the type of psychological distance among items. For example, items may be related because they are similar in type or because they frequently occur together. The utility of a particular menu layout depends on the task to be performed. Tasks may require users to pick groups of similar items (e.g., documents on the related topics, inventory items in the same department) or complementary items (e.g., paint brush tool and a particular color, font and point size). In an experiment by McDonald, Dayton, and McDonald (1986) subjects rated pairs of food items on the basis of similarity ("How similar are these foods?") and on the basis of co-occurrence ("How well do these two foods go together?"). The ratings were analyzed using nonmetric multidimensional scaling. The menu items were placed at the resulting coordinates with boxes placed around them to serve as selectable areas on a touch screen. The space between the items was then reduced while preserving the ordinal relations among the items within and between clusters. Although the items were clustered, they did not use the keyboard are efficiently. Layouts were scattered and irregular in comparison to the standard tight rectangular arrangement of keyboards.
Nevertheless, the results confirmed the utility of the menu organization. Subjects using the frequency layout and the similarity layout were able to perform selection tasks faster than subjects using menus that they had personally arranged. Furthermore, subjects using the frequency layout performed better filling orders with complementary items (e.g., Hamburger, French Fries, and Coke). Subjects using the similarity layout tended to perform better filling orders with similar items (e.g., Coke, Root Beer, and Iced Tea); however, this difference was not significant.
In a similar experiment, McDonald, Molander, and Noel (1988) replicated these findings using rectangular menu layouts. A simulated annealing analysis was used on the previous similarity and frequency ratings to lay out the 24 food items into a 4 by 6 rectangular array (see Figure 11.6). In addition, color codes were assigned to five similarity and frequency clusters. Four menu layouts resulted: (a) frequency layout with redundant color coding of complementary clusters, (b) frequency layout with color coding of similarity clusters, (c) similarity layout with redundant color coding of similarity clusters, and (d) similarity layout with color coding of complementary clusters.
The results confirmed the previous findings that performance is facilitated when subjects used menus whose semantic space supported the particular task required. Subjects using the similarity layout filled orders for similar items faster than for complementary items and subjects using the frequency of co-occurrence layout filled orders for complimentary items faster than for similar items. On the other hand, color coding did not facilitate performance. It is likely in the present case that color reduced the readability of the items and obscured the effect. The authors suggest that redundant color coding may be beneficial particularly for the frequency layout by helping to clarify complex organizations of items. But there is no indication that double semantic coding (e.g., physical layout based on frequency of co-occurrence and color coding based on similarity) facilitated performance in selecting multiple items.
These results strongly suggest that when designers organize menus, they need to take into consideration the type of tasks performed by the users. It is likely that in real-world applications menu layouts based on frequency of co-occurrence are in general superior to layouts based on similarity. Although users may naturally cluster items based on similarity, menu selections in most systems are highly contingent on other items selected. This raises some question about the appropriateness of user derived semantic structures. Ratings of item relatedness by the users may result in structures that are in some sense meaningful, but not appropriate to the task at hand. Empirically derived measures of frequency of co-occurrence performing a given task may be more appropriate and are discussed in a later section.
Spatial structure may also be used to generate a hierarchical ordering of items. An experiment on problem solving by Carroll, Thomas, Miller, and Friedman (1980) illustrates this approach. The experiment required subjects to place 12 library procedures in a two dimensional matrix while at the same time satisfying 24 functional design requirements. The library procedures were hypothetical and listed only by letter rather than explicitly (e.g., cataloging a book, shelving a book). Functional requirements had to do with the facilitation of one procedure by another (e.g., cataloging a book facilitates shelving a book), the priority of procedures (e.g., signing a book out has higher priority than tidying up the reading room), use of resources (e.g., storing and retrieving use the same people). One dimension of the matrix represented priority (from high to low) and the other time (from earlier to later). Carroll et al. varied the amount of prior information available to the subjects in four different conditions. In the simultaneous condition, subjects received all 24 functional requirements on one page and placed the 12 tasks in the matrix. In the explicit structures condition, subjects were given a hierarchical description of the relationships among three procedure sets; then they were shown 4 functional requirements and placed the 12 tasks; they were shown another 4 and placed the 12 tasks a second time; and so on until all 24 requirements had been shown and the subjects had placed the 12 tasks 6 times. In the implicit structures condition, subjects were given the same functional requirements but without the hierarchical description. Finally, in a non-structured condition, subjects received the sets of functional requirements in a random fashion with no logical sequence.
Solutions differed in terms of the degree of hierarchical organization in the matrix. Carrol et al. used a cluster ratio (the mean of between-cluster distances divided by the mean of within-cluster distances) as a measure of hierarchical organization. The cluster ratio also reflects the extent to which clusters are well-defined with a high similarity among items within a cluster and high dissimilarity between clusters. The results indicated that the explicit structures condition yielded the highest cluster ratio and the nonstructured condition gave the lowest. The more knowledge about the functional task requirements, the greater the hierarchical structure. Over the six solutions, the explicit structures condition showed the greatest stability. The nonstructured condition showed the greatest changes. Results such as these suggest that users can provide information for organizing menus as long as they are knowledgeable about the functional requirements.
In a second part of the study by Chin (1986), subjects rated ATM commands on three dimensions: temporal order (first-last), frequency of use (seldom-often), and in/out box metaphor (in-out). The ratings varied significantly among items. For example, "End Transaction" was seen as last in order and often used. Deposit commands were on the "in" side of the box and withdraw functions on the "out" side. The rating data were subjected to the hierarchical clustering analysis and resulted in another dendrogram of the 25 ATM commands. However, the logic of its clustering was not readily apparent.
A subsequent study by Chin and Norman (1988) specifically investigated the elicitation of the both declarative and procedural knowledge in structuring menus for ATM command and enhanced function telephones. Declarative knowledge was elicited by having subjects place items on a large 14 x 10 grid. Items were clustered on the basis of their proximity to one another. Procedural knowledge was elicited by having subjects draw directional lines connecting commands. Procedural knowledge was added to the structure by weighting distances in the multidimensional solution. While structures resulting declarative knowledge were logical, procedural knowledge seemed to add very little additional information.
Semantic clustering methods have often proved to be more work than they are worth. They are generally limited to small sets of items; and the number of pairwise ratings required in even moderate sets of items can be prohibitive. The dimensional solution is too often without clear meaning or practical use. And the resulting hierarchical menu tree may be a hodgepodge of noise. One of the main problems is the reliance on the user to provide structure. When the user is highly knowledgeable about the items, it may be possible to extract a coherent organization of items. However, this occurs in only selected and usually trivial cases such as with food items. Less familiar items such as the functions of a word processor or options in a communication program may be rated by highly experienced users. However, the resulting semantic space may have little utility to other users let alone novices. To make matters even worse, the menu items that compose real-world systems are generally unknown or unfamiliar to potential users prior to acceptance of the system. Menu items are often a product of system architecture rather than having a life of their own. Consequently, users can only rarely contribute in any meaningful way to the initial organization of the system. Organization of menu items must rely on the semantic knowledge of the designer who is hopefully an expert in the task domain. On the other hand, when menus are composed of well understood concepts such as the tools in a graphics program (e.g., paint brush, pencil, text, etc.), user knowledge may add to menu organization. When possible, semantic scaling should be used by designers as an exploratory tool for deriving cognitive structures to aid in the design of menus.
There are many situations in which knowledge about how items should be organized exists prior to system design and is inherent in the database. In this case experts in the subject matter domain can be used to generate the structure. On the other hand, there are cases where the knowledge does not exist prior to design. In essence, the structure is a result of the design and there are no experts except the system analyst. Prior to the first design of electronic spreadsheets, graphics packages, and disk operating systems, no potential uses had a good conception of what the menu items were, let along how they should be organized. Knowledge about the system must be learned from the system itself. Consequently, it is important that users experienced with the operations of the system be used to organize the menu structure.
The difference between the knowledge of the expert and the novice is illustrated by a study by Snyder, Happ, Malcus, Paap, and Lewis (1985). They used a clustering task to structure a menu. Nine experts and ten novices looked at 43 MS-DOS commands printed on cards with a brief definition and example. Subjects were asked to combine them into any number of groups of any size. After this sorting, subjects were asked to label the groups. If a group could not be labeled, a letter was assigned as the label for the group. Subjects then subdivided the groups into smaller groups if they wished. This method may be considered a hybrid of the top-down and bottom-up processes in that subjects started with the total set to form groups in a bottom-up manner, but once these groups were composed, they were subdivided in a top-down manner. Additional relational information was collected by having subjects make pairwise similarity ratings between the groups. An analysis the data was conducted to generate a two level menu system. It was designed such that all commands could be reached by starting from one of several dominating nodes at the top and traversing one link. The networks generated by novices included 71 links and 11 dominating nodes. The networks of experts were composed of 75 links and 10 dominating nodes. But the striking difference between the novices and experts was that only 28 links and one dominating node were the same between the two networks. In effect, experts had maintained 28 links that the novices created, broke 43 old links, and added 47 new ones. These findings suggest that a fundamental restructuring of the internal mental model of how systems are organized occurs with experience.
Many users are not concerned with the overall clustering of items or the semantic space. Rather they are only interested in following a relatively small number of paths through the menu structure. Such paths are solutions to user requests such as "Show me how to print this document? "Show me how to change the clock?" When the user is performing such tasks via menu traversal, the structure of the menu should minimize the number of selections required to go from one function or object to another as discussed in Chapter 10. In hierarchical menus, this is accomplished by a placing frequently selected items at the top of a hierarchy and by placing infrequently selected items at more remote locations at the bottom of the menu.
11.5.1 Command Frequency. When hierarchical menus are constructed for ordered directories there is no semantic structure on which to base the hierarchy. In such cases, one may dynamically generate the menu according to the frequency of access in order to minimize the expected number of nodes traversed. Often the display has a fixed menu size of M items. The question is how to divide up the list for optimal performance. Witten, Cleary, and Greenberg (1984) present top-down menu splitting algorithms. The best of their algorithms splits a list of ordered items into M parts which have approximately equal total probabilities. The first split is made as close as possible to 1/M of the total probability. The second split is made as close possible to 1/(M-1) of the remaining probability after the first split and so on. Parng and Goodman (1987) extended this work and compared a bottom-up algorithm and a two-way algorithm. The bottom-up algorithm creates a subtree that yields a minimum sum of M adjacent access probabilities. The two-way algorithm combines the top-down and bottom-up approaches by alternating between the top-down menu splitting procedure and the bottom-up subtree building whenever it is appropriate. The top-down algorithm was designed to balance the probabilities in the trees. The bottom-up algorithm was designed to generate full menu trees in which all of the menus are of maximum size. Parng and Douglas found that the two-way algorithm was somewhat superior to the top-down. The bottom-up algorithm was the worst in terms of the average number of selections to reach a target item.
Menu structure based solely on frequency is not likely to capture or convey either declarative or procedural knowledge. The only advantage is efficiency in errorless menu traversal. Unfortunately, since the menus may contain little in the way of semantic structure, it is likely that users will easily get lost.
11.5.2 Command Transitions. In network menus where the user may be cycling back and forth between items, the distance between adjacent items should be as short as possible. For example, in a word processor , the path between the options to cut and to paste should be as short as possible. Typically, however, the user must select the text, go to a list of editing options and select the option to cut. Then the user must back out of the menu to select an insertion point and then go back to the list of editing options and select the paste option. When hierarchical structures are used in networks they often require the user to go down the tree to an item, climb back out, and then go back down to select the item in the same region of the tree. Although command keys can be used to overcome this sort of problem, a less memory demanding approach would be to temporarily elevate the most likely items to the top. Or to allow the user to reenter the tree at the same point where it was left. The last menu frame, becomes the default starting frame.
The design problem is to identify typical paths through the menu. A task analysis can help as discussed in Chapter 3. The task analysis, however, is generated by knowledgeable users and relies on their ability to anticipate the types of tasks performed. This approach represents rational design. Unfortunately, rational design often misses reality. The designers simply may not foresee an important task that users frequently perform. However, empirical methods can be used to identify such tasks and their paths through the menu. Given an existing menu and sufficient data, one may identify frequently traversed paths. Price (1982) gives a good example of how path data may be used in the evolution of a system. She describes a CAD system using very broad command menu including 276 items. In the original system, 120 selections were displayed in the top and right margins of screens. Several "levels" of the menu were displayed and users could move from one to another. Price collected data over approximately 200 hours of interaction and recorded over 22,500 commands. A data log file contained a complete record of commands. Data were summarized in tables listing the frequency of occurrence of commands following other commands. In essence, these tables constituted a large command transition table listing the number of times one command followed another command.
The initial tables revealed patterns for the most frequent commands that were more or less context independent (e.g., commands to refresh the screen and to expand, contract, or shift the current view). Due to the pervasive nature of these commands, the frequency tables were recomputed with these commands ignored. The new tables indicated that for many commands it was possible to identify only a small group of commands that were likely to follow. Price notes for example that the "GET" command occurs 2238 times and was followed by 43 different commands. However, the 12 most frequent commands following "GET" occurred 95% of the time. Over all commands, an average of only 7 commands accounted for 95% of the commands to follow.
These results were used to design a new system with three primary menus: a constant menu, a dynamic menu, and an menu of menus. The constant menu contained the most frequent context independent commands, as well as, the help command. The constant menu contained a total of 11 commands. Dynamic menus were constructed on the basis of the command transition frequencies. Of the 276 commands, 88 resulted in a change of the dynamic menu. There were 31 such dynamic menus containing from 2 to 22 commands. In addition, there were 14 commands that were followed by one of a small predictable group of commands or the same command. These 14 commands temporarily added 1 to 3 items to the current dynamic menu. Finally, the menu of menus was used to access any command that did not appear on either the constant menu of the dynamic menu. It consisted of a hierarchical menu of 24 command categories containing from 3 to 26 commands per category. Once a command was selected from the menu of menus, the dynamic menu displayed the list of commands most likely to follow the selected command. Selection of commands from the constant menu left the dynamic menu unchanged.
The new menu was tested in a simulation using the original data log file. The design indicated that only 11% of the menu selections would require the use of the menu of menus. 37% of the commands could be selected from the current dynamic menu, 50% of the commands would be selected from the constant menu, and the remaining 2% of commands were user defined macros. The average dynamic menu contained 13 commands, the constant menu 11 commands, and one command to bring up the menu of menus. Thus a total of 25 commands were displayed on average.
The generation of menus from command transitions captures the procedural knowledge of the system. Although a command language may allow the user to follow any command with any other command, the procedural knowledge about the system dictates what sequence is actually appropriate. It is suggested that menus should convey procedural knowledge about the system in the way that they are displayed. Hierarchical menus do this automatically. In broad pull-down menus, however, procedural information is often missing and the user does not know in what order selections must be made in order to perform a task. Well designed menus convey procedure as well as breadth of choice.
Menus are inherently data structures that contain knowledge about the domain of items. Menu design rests heavily on the elicitation of that knowledge from users and its incorporation in the organization of menus. Three approaches to menu organization were presented. The clustering approach is a relatively simple procedure for generating hierarchical structures. The top-down variant of clustering starts with the total set and successively subdivides items according to some organizing principles. The bottom-up variant starts with forming a number of clusters of items and then forming clusters of clusterings.
The second approach is to extract a semantic space from user assessments of similarity or relatedness among items. This approach has been used for hierarchical structures but it is probably best suited for organizing items within single menu frames. The third approach is to use observed frequency and sequence information to structure the menu in terms of efficiency. This approach may be devoid of semantic knowledge about the menu since it is based only on frequency of use.
All three approaches have considerable merit in eliciting relational information from the users that can be used to organize menus. Each method captures a different aspect of organizing knowledge and must be used appropriately in the design of real systems. Whatever the organizing principle, it must fit the task to be performed by the user.
It is clear that the quality of organization depends on the amount of knowledge of the individuals organizing the menu. It is important that designers solicit input from knowledgeable users rather than just any users and to remember that menu organization should be congruent with the way in which users think about the system.
The organization and layout of menus is extremely important in design. It determines not only the superficial "look and feel" of the system, but its very essence. Menu organization contains the declarative and procedure knowledge that drives the system. Consequently, the challenge is to generate and organize the system according to principles of efficient menu design and at the same time project a knowledge structure that in some meaningful way guides the user through the system.