Incremental prediction of configurator input values based on association rules – A case study Dietmar Jannach and Lukas Kalabis TU Dortmund Dortmund, Germany dietmar.jannach@tu-dortmund.de, lukas.kalabis@tu-dortmund.de Abstract static definition of defaults, this framework also supports the definition of rules that determine the proposed default value In many configurator applications, the user is re- for a field based on the inputs already made in the current quired to specify a multitude of configuration op- session. tions interactively. One way of making the config- Our own anecdotal experiences with using predefined de- uration process more convenient for the user is to fault values provided by the domain expert in the domain of pre-fill the input or selection fields of the user inter- interactive advisory systems however showed that such static face with appropriate defaults. Possible strategies rules can have different limitations. First, domain experts of- to determine default values for example include the ten define what should be the default selection for an input selection based on domain knowledge or the usage field merely based on gut feeling and intuition. Second, in of statistics. some domains, the most appropriate default value changes In this paper we analyze whether or not the dy- over time, for example due to technological advances or a namic selection of defaults based on automatically changing marketing strategy. The rules determining the de- determined association rules can help to predict the faults in the configurator applications are however not always most probable next input value in an interactive updated accordingly. and incremental configuration process. We base In this work we propose to use association rules [Agrawal our analysis on the data obtained with a real-world and Srikant, 1994], which can be automatically learned from configurator application. The value of choosing de- past configuration sessions, to dynamically choose the most faults more intelligently is determined by measur- appropriate default values. We evaluate the value of apply- ing the number of correctly predicted inputs in the ing this self-adapting default selection strategy by counting configuration process and by comparing this num- the number of correct and wrong predictions when replay- ber to a default strategy based on simple value fre- ing past interactive configuration sessions and comparing our quencies. strategy to a statistics-based baseline strategy. The analysis of the approach is based on a real-world configuration data base. 1 Introduction In many industrial sectors, the products on the market can be 2 Mining input value patterns customized to a customer’s individual needs in a variety of Figure 1 shows a schematic but typical fragment of a user in- ways. Accordingly, the interactive preference elicitation and terface for a configurator, in which the user of the system – in product configuration process can become time-consuming our case a sales representative – incrementally enters the pref- and cumbersome, because the user of the configurator appli- erences of the customer. In our real-world database from the cation is often required to enter input or make selections for roofing industry, on average more than two dozens of such several dozens of parameters. parameters have to be entered during the configuration pro- Providing suitable default inputs or default selections for cess. The database comprises more than 9,000 past roofing the individual options represents one common way to make configurations. the configuration process more convenient for the user. How The goal of our work is to try to detect patterns co- the system chooses the pre-set default value can be based on occurring input values in these past configurations and exploit different strategies. One simple strategy for input fields with these patterns to predict the next input values in the interac- a predefined set of options could be simply selecting the first tive configuration process. value of the list. Alternatively, one could use the value that Association rules have been traditionally used in data min- was chosen most frequently in the past (also by other users). ing scenarios and in particular for shopping basket analysis. In some systems – such as the A DVISOR S UITE sales ad- With the help of algorithms such as Apriori [Agrawal and visory framework [Felfernig et al., 2006] – the selection of Srikant, 1994], rules of the following form can be extracted the default values is based on domain knowledge. Beside the from past buying transactions: tiple rules are in principle applicable (but suggest different right hand side values), we choose the rule with the highest confidence value. In combination with the sliding window strategy, we also apply a relaxation strategy in case we can- not find a matching rule. If, for example, no rule with the left hand side {Basic-Model = A, Color = White} can be found in a window of size 2, we calculate all subsets of the left hand side and take the rule with the highest confidence value. Overall, in contrast to default selection B where all values can be set at the beginning, in scheme C, the defaults are de- termined dynamically based on the previous inputs. 4 Evaluation Figure 1: Schematic user interface fragment. Metric. As an evaluation metric, we count the number of clicks that are required to configure the customized product variant. Note that we have one full default configuration for {milk, bread} ⇒ {butter} scheme A and one for scheme B. To measure the number of [support=60%, confidence=80% ] required clicks, we iterate through all 9,000 past transactions The rule states that whenever customers purchase milk and and check for each transactions how many of the input field bread, they also buy butter. Support and confidence are mea- values are different from this default configuration. The con- sures for the strength or quality of a rule. The support metric figuration effort thus corresponds to the average number of describes in how many of all existing transactions the itemset values that have to be changed. {milk,bread,butter} appeared. The confidence measure cor- For scheme C, we “replay” the configuration process for responds to the percentage of transactions in which milk and each of the past configuration sessions and predict the input bread appeared and where butter (the right hand side of the field value one after the other based on the association rules. rule) was also part of the transaction. In case the prediction of the next input was correct, we move In our problem setting, a completed configuration corre- the sliding window forward and predict the next input. In case sponds to a flat list of assignments of values to the more than the prediction was wrong, we increase the counter of required two dozen input variables, that is, our configuration problem clicks, correct the input value to the one given in the current is relatively simple when compared, for example, to classical past transaction and proceed with predicting the next input component port configuration models [Mittal and Frayman, field. 1989]. Applying association rule mining algorithms such as Results. Due to the fact that the choice of the basic roof Apriori (as used in our work) or FP-Growth [Han et al., 2000] model, which has to be done as a first step, considerably in- is therefore straightforward and the goal of the mining pro- fluences the available choice for the rest of the configuration cess is to detect patterns such as process, we have learned a set of association rules for each of {Basic-Model = A, Color = White} ⇒ {Warranty = 3yr.} these basic models. In addition, we have experimented with As an overall result of the mining process, a set of such different window sizes as well as minimum support values. association rules can be determined. Usually, a minimum Figure 2 exemplarily shows the results for one of the basic support value has to be set in order to only take significant models. patterns into account. On average, 27,5 input values were set for a configuration of this model type. Using the simplistic default selection 3 Default selection schemes scheme A (pick the first value in the list), on average a bit more than 15 values have to be set (changed) manually by the In our evaluation, we compared three schemes for determin- user1 . However, if we apply scheme B (pick the most fre- ing the default value: (A) take a random value (the first in quent value), a very strong improvement can be observed and the list of options); (B) the most frequent value from the past only about 6 of the 27 values were not properly predicted, transactions is taken as a default; (C) the selection is based on which strongly indicates that there are some configurations association rules. options, which are very popular and that there is a long tail of For scheme C, a “sliding window” strategy was applied. configurations which is very seldom sold. Note that we assume in our application that we have a strict Regarding the dynamic prediction scheme C, we experi- order in which the inputs are entered (from top to the bottom). mented with different settings and in particular varied the pa- In scheme C, the defaults therefore depend on the previous rameters window size and minimum support (MS), see Figure inputs. If we, for example look for a value for the warranty 2. With respect to the window size, we can observe that a field, we look for rules that have the previous inputs (such as larger window size, which in turn means that we learn longer the color) in the left hand side of the rule. The window size rules, helps to improve the predictive accuracy of our rule- describes how many of the last n inputs we take into account. based approach. The best results in our experiments were Taking all previous inputs into account might be impractical achieved with window sizes 5 and 6. Further tests showed as the set of detected association rules might not contain rules 1 that have 20 or more inputs on the left hand side. When mul- The median number of input values is 5. Figure 2: Results for one representative basic model. that beyond this window size no further improvements could seconds (that is, below 0.5 seconds for each field) even for be observed. The time required for the (offline) rule mining the largest window sizes considered in the experiments. The process however significantly goes up when the maximum times needed for the offline model-building phase strongly length of the rules to be learned is increased. depend on the minimum support size. While at the 10% level With respect to the MS value, lower threshold values lead model-building takes a few seconds, the calculations at the to better results and the best predictions were achieved with 3% level can take a few hours on a standard desktop PC. MS values at 3% and 4%. Lower MS values mean that also rules for “rare combinations” are learned and included in the 5 Previous works rule base. Again, further decreasing the MS value leads to marginal improvements at the price of a much larger rule In [Ardissono et al., 2002], an advanced approach to person- base. Overall, we can see that the accuracy consistently in- alizing the preference elicitation process in a configurator ap- creases when the MS value is lowered. For the window sizes, plication was proposed. In particular, their system exploits in contrast, we could observe that further increasing this pa- stereotypical user modeling techniques to assess the user’s rameter does not always lead to better results. preferences and properties throughout the interaction process. For the particular basic model for which we show the re- In contrast to our work, in their approach the goal is also to sults in Figure 2, we can see an overall improvement from find personalized defaults which depend on the individual be- 5,92 to 4,73 required clicks. At first glance, this might not havior of the user. Another approach to personalize the inter- look too impressive. Note however, that the good results that action process with the goal to reduce the complexity of the were achieved with the comparably simple scheme B are due overall process for the end user based on user profiles and to the very unbalanced distribution of the available input val- personalized recommendations was proposed in [Stegmann ues in the past configurations. Figure 3 shows a typical exam- et al., 2003] and [Stegmann et al., 2006]. ple for a “yes/no“ question. For three out of four user input Currently, personalization of the default proposal process fields, such a lopsided distribution could be observed. is beyond the scope of our work but could be relatively easy implemented by learning user-specific rule models for situa- tions, in which enough data is available for personalization. Recently, in [Tiihonen and Felfernig, 2010] and [Felfernig et al., 2010] a knowledge-based approach to personalizing the user interaction process for configurator applications was presented. Beside the automatic generation of “repair pro- posals” for situations in which the customer requirements are inconsistent (as also discussed in [Felfernig et al., 2001]), the authors propose different (probabilistic and statistics-based) techniques to determine suitable feature values as proposed earlier already in [Cöster et al., 2002]. The goal of their work is similar to ours, although different techniques are employed and for example metrics for measuring the “distance” be- Figure 3: Value distribution for field “standard height (y/n)”. tween configurations as well as feature weights are exploited. Unfortunately, no empirical evaluation of their proposal was Across all basic models, an average reduction of required yet done. However, [Felfernig et al., 2010] also consider the clicks of 11.88% was observed. A first analysis showed that question that the proposed feature values have to be consis- the achieved improvements do not so much depend on the tent with the configuration knowledge base and the current, number of available training samples but rather on the diver- partial configuration. In our current work, this aspect was not sity of the actually configurations. considered yet. One strategy to deal with this aspect could Running times. The time needed for the generation of be to systematically try to apply different association rules input value predictions based on the previously learned as- (ordered by their confidence) and check whether the configu- sociation rules can be considered to be suitable for an in- ration is still consistent after rule application. teractive configuration scenario. In all our experiments, the In [Geneste and Ruet, 2001], finally, a Case-Based Rea- computation of input values for all fields took at most 10 soning (CBR) approach to reduce the complexity of the in- teraction process was proposed. The main idea is not to start cluster-based help. In In Proceedings of the AH’2002 configurations from scratch, but to reuse and adapt past con- Workshop on Recommendation and Personalization in figurations. The main tasks are therefore to find past similar eCommerce, pages 30–39, Malaga, Spain, 2002. cases based on a similarity metric and a search algorithm, [Felfernig et al., 2001] Alexander Felfernig, Gerhard determine possible adaptations (the adaptation domain) and Friedrich, Dietmar Jannach, and Markus Zanker. then guide the user through the adaptation process using con- Intelligent support for interactive configuration of straint satisfaction techniques. Beside the goal of making the mass-customized products. In Proceedings of the 14th interaction process more efficient, one similarity between our International Conference on Industrial and Engineering work and the work of [Geneste and Ruet, 2001] is that we Applications of Artificial Intelligence and Expert Systems, rely on past configurations to steer the interaction process. pages 746–756, 2001. However, in our work we assume an incremental process in which configurations are developed and refined step by step. [Felfernig et al., 2006] Alexander Felfernig, Gerhard The consideration of the consistency checks before the de- Friedrich, Dietmar Jannach, and Markus Zanker. An in- fault proposal process as done in [Geneste and Ruet, 2001] is tegrated environment for the development of knowledge- currently not supported in our approach. based recommender applications. International Journal of Electronic Commerce, 11:11–34, 2006. 6 Summary and outlook [Felfernig et al., 2010] Alexander Felfernig, Monika Mandl, Juha Tiihonen, Monika Schubert, and Gerhard Leitner. In this work, we have analyzed how association rules mined Personalized user interfaces for product configuration. In from past configurations can be exploited to predict input val- Proceedings of the 15th International Conference on Intel- ues for interactive configuration processes and can thus help ligent User Interfaces, pages 317–320, Hong Kong, China, to make the usage of such systems more comfortable in case 2010. the user has to configure a multitude of options. The evalua- tion on a real-world data set showed that a measurable reduc- [Geneste and Ruet, 2001] L. Geneste and M. Ruet. Experi- tion in required interactions can be achieved when compared ence based configuration. In Proceedings of the Configu- to a simpler statistics-based approach or even in cases when ration Workshop at IJCAI’01, Seattle, USA, 2001. we have a market which is dominated by a few very popular [Han et al., 2000] J. Han, J. Pei, and Y. Yin. Mining frequent configurations. patterns without candidate generation. In Proc. 2000 ACM Among other aspects, our future work includes the analy- SIGMOD Intl. Conference on Management of Data, pages sis of the algorithm on other real-world datasets and the ap- 1–12, Dallas, Texas, 2000. plication of other techniques from data mining and machine [Mittal and Frayman, 1989] S. Mittal and F. Frayman. To- learning for input value prediction in the configuration do- wards a generic model of configuration tasks. In Proc. main. Beside that, our goal is to evaluate prediction strategies 11th Intl. Joint Conference on Artificial Intelligence, pages in which the elements contained in the sliding window not 1395–1401, Detroit, Michigan, 1989. only depend on the chronological order of the inputs but on some relevance weight, assuming that individual inputs are [Stegmann et al., 2003] Rosmary Stegmann, Michael Koch, more predictive than others in the configuration process. In Martin Lacher, Thomas Leckner, and Volker Renneberg. addition, future work could also consider the question if there Generating personalized recommendations in a model- are characteristics of the configuration problem (such as the based product configurator system. In Workshop on Con- domain sizes of the variables) which can help us to automat- figuration at IJCAI’03, Acapulco, Mexico, 2003. ically determine appropriate values for the minimum support [Stegmann et al., 2006] Rosmary Stegmann, Thomas Leck- threshold. ner, Michael Koch, and Johann Schlichter. Customer support for the web-based configuration of individualised References products. International Journal of Mass Customization, [Agrawal and Srikant, 1994] Rakesh Agrawal and Ramakr- 1(2):195–217, 2006. ishnan Srikant. Fast algorithms for mining association [Tiihonen and Felfernig, 2010] Juha Tiihonen and Alexan- rules in large databases. In Proc. of 20th Intl. Conference der Felfernig. Towards recommending configurable of- on Very Large Data Bases, pages 487–499, Santiago de ferings. International Journal of Mass Customization, Chile, Chile, 1994. 3(4):389–406, 2010. [Ardissono et al., 2002] L. Ardissono, A. Felfernig, G. Friedrich, A. Goy, D. Jannach, M. Meyer, G. Petrone, R. Schäfer, W. Schütz, and M. Zanker. Personalising on-line configuration of products and services. In Proc. of the 15th European Conference on Artificial Intelligence, pages 225–229, Lyon, France, 2002. [Cöster et al., 2002] Rickard Cöster, Andreas Gustavsson, Tomas Olsson, sa Rudstrm, and Asa Rudstrm. Enhanc- ing web-based configuration with recommendations and