Markov Chain Models for Menu Item Prediction

Markov Chain Models for Menu Item Prediction

Tao Lin (Department of Computer Science, Sichuan University, Chengdu, China), Tian-Tian Xie (Department of Computer Science, Sichuan University, Chengdu, China), Yi Mou (Department of Computer Science, Sichuan University, Chengdu, China) and Ning-Jiu Tang (Department of Computer Science, Sichuan University, Chengdu, China)
Copyright: © 2013 |Pages: 20
DOI: 10.4018/ijthi.2013100105
OnDemand PDF Download:
No Current Special Offers


With the increase in the number of menu items and the menu structure complexity, users have to spend more time in locating menu items when using menu-based interfaces, which tends to result in the decrease of task performance and the increase of mental load. How to reduce the navigation time has been a great challenge in the HCI (human-computer interaction) field. Recently, adaptive menu techniques have been explored in response to the challenge, and menu item prediction plays a crucial role in the techniques. Unfortunately, there still lacks effective prediction models for menu items. This paper explores the potential of three prediction models (i.e., Absolute Distribution Markov Chain, Probability Summation Markov Chain and Weighted Markov Chain based on Genetic Algorithm) in predicting the most possible N (Top-N) menu items based on the users’ historical menu item clicks. And the results show that Weighted Markov Chain based on Genetic Algorithm can obtain the highest prediction accuracy and significantly decrease navigation time by 22.6% when N equals 4 as compared to the static counterpart.
Article Preview


With the increase in menu items and the menu structure complexity, users have to spend more time and efforts in locating menu items when using WIMP (windows, icons, menus, pointer) interfaces, and this tends to cause the decrease in task performance and extra mental load. How to decrease the visual search time of menu items and improve task performance has been an open problem in the HCI (human-computer interaction) field. Although some research efforts have been made to solve the problem, most of them focused on the optimization of static menu structure such as menu item grouping (Lee & MacGregor, 1985; Norman, 1991), layout (Cockburn, Gutwin, & Greenberg, 2007) and format (Parkinson, Sisson, & Snowberry, 1985; Shih & Goonetilleke, 1998). These approaches can decrease the navigation time and improve task performance to some extent, but their efficacy is evidently decreasing with the increase of menu structure complexity and the number of menu items.

A few more efforts have also been made to explore adaptive menu technologies in response to the challenge. Adaptive menu technologies usually rely on three approaches: spatial, graphical or ephemeral. Spatial approaches (Findlater & McGrenere, 2008; Mitchell & Shneiderman, 1989) re-organize menu items to reduce navigation time and, to a lesser degree, to aid visual search. For example, an adaptive split menu moves or copies the most frequently and/or recently used items to the top of the menu for easier access (Gajos, Czerwinski, Tan, & Weld, 2006). The main drawback of this approach is that spatial consistency cannot be maintained (Cockburn et al., 2007). For graphical approaches, they reduce navigation time through changing the background of predicted items(Gajos et al., 2005; Gajos et al., 2006; Tsandilas & Schraefel, 2005).

As an alternative to spatial and graphical adaptation, Findlater, Moffatt, McGrenere, and Dawson (2009) proposed the use of a temporal dimension and introduced ephemeral adaptation as a new adaptive menu technique to reduce navigation time. Ephemeral adaptive approaches use a combination of abrupt and gradual onset to provide initial adaptive support, which then gradually fades away; The goal is to draw the user’s attention to a subset of adaptively predicted items, thus, reducing visual search time. To demonstrate the benefit of ephemeral adaptation, they further compared the effects of two predefined conditions of prediction accuracy (50% VS. 79%). The results show that when the accuracy with which the adaptive algorithm predicts the users’ needs is relatively high (79%), ephemeral adaptation significantly offers better performance and user satisfaction benefits over traditional static menus, and a performance benefit over a graphical adaptation technique, whereas it does not, when adaptive accuracy is low (50%). It suggests that obtaining high prediction accuracy of menu items is crucial to the success of adaptive menus. However, there still lacks an effective prediction method of menu items based on historical menu click data.

Markov chain models have been widely applied in other areas such as weather forecast (Gabriel & Neumann, 1962), and user navigation pattern (Borges & Levene, 2000) with great success. All menu items of a system in nature constitute a discrete finite space and each menu clicking corresponds to a transition between two states. Markov chain was applied to predict menu items in our study. Specifically, we first explored three approaches based on Markov chain (i.e., Absolute Distribution Markov Chain, Probability Summation Markov Chain and Weighted Markov Chain based on Genetic Algorithm), along with Top-N techniques, and compared them with previous prediction methods from diverse areas of computer science, including Most Recently Used (MRU), Most Frequently Used (MFU), Split Recency and Frequency(SR&F) (Findlater & McGrenere, 2004), Combined Recency and Frequency(CRF) (Lee et al., 1999) and AccessRank (Fitchett & Cockburn, 2012). Secondly, we compared the visual search time and user preferences between the static and highlighting menu display based on a prediction method selected to verify that the selected prediction method was effective.

Complete Article List

Search this Journal:
Volume 18: 4 Issues (2022): 1 Released, 3 Forthcoming
Volume 17: 4 Issues (2021)
Volume 16: 4 Issues (2020)
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing