Motivated by the importance of customer buying behaviour (such as correlation among product attributes/features of products configured in the past) in planning future configurations, this paper addresses the issue that product evolution (upgrades) usually render information gathered from past buying behaviour at least partially unusable. For instance, relations among features might have been changed, thus making it difficult to configure the same products again. The proposed approach aims to (1) find associations between product attributes based on the analysis of prior customer orders (2) apply configuration rules to prune attribute association rules which are not controlled by customers, and (3) check whether derived attribute association rules from past orders also work for the new upgraded product. Attribute associations consistent with the upgraded product are then used to predict configurations for production planning. We use machine learning algorithms and optimization techniques to address these issues.
Mass customized products (e.g. Automobiles) involve a large number
of product variants which are generated by combining different
predefined features/attributes. Individual product attributes and attribute
combinations control the final consumption of vehicle components
and sub-assemblies during the production [
One way to get customer buying behaviour is by extrapolating the
configurations produced in the past. Due to the high degree of
individualization and continuous changes in the product design,
product evolution (upgrades) usually renders information gathered from
past buying behaviour at least partially unusable. For instance,
relations among features might have been changed, thereby not
allowing configuration of the same products again. In the special case of
a new product, information from existing models (having common
features) is often used to prepare the initial production plan (set of
vehicle configurations). As configuration rules of different products
are not same, it is likely that attribute associations from the existing
model may not be directly applicable to the new product. Thus, we
need a mechanism to validate whether the derived attribute
association rules from past orders also work for the new upgraded product.
These consistent attribute association rules could then be used to
predict future configurations for production planning [
Throughout this paper, we will use the terms attribute association rules or attribute associations to specify quantities reflecting the joint selection of attributes or conditional section of attributes. For example, figure 1 shows that 67% of configurations contain both attribute 1 and attribute 2.
In practice, the use of specific components in the final product
assembly depends on 1) the way they are designed and 2) the way
customers select them. Design or engineering related dependencies
(or restrictions) are well documented in product’s Bill-of-Material
(BOM) or configuration rules. As the product development process
starts well before the actual production, it is possible to know the
product description for a future time (2-3 years in advance) from
BOM [
In order to predict configurations for production planning the information from 1) configuration restrictions and 2) customer buying behaviour should be used together. Any conflicting information between these two sources points to an inconsistency in the planning information. Delay in the detection of such discrepancies may result in a wrong mix of parts being produced, thus hampering production efficiency.
Input
Product configured in the past Attributes 1 2 3 1 0 1 1 1 0 1 1 1
Section 2
Section 2
Section 3 Attribute association
rules (1) (1,2) (1,3) (2,3)
Pruning association
rules (+) Config rule (2 → ¬3) (1) 100% (1,2) 67% (1,3) 67%
Validate attribute associations (1) (1,2) (1,3) attributes). Then, association rules which conflict with configuration restrictions are pruned. In Section 2 we discuss a machine learning algorithm to calculate such association rules. In Section 3 we present optimization models which aim to build a set of future configurations by considering 1) configuration restriction and 2) attribute association rules simultaneously. If we are able to find such a configuration set which matches both of the input parameters, then the result can be used for future production planning. In case of conflicts between configuration restrictions and attribute association rules, further analysis is required and perhaps only a limited set of consistent association rules can be used to predict future configurations. In this case, our focus is to find such a consistent set of attribute association rules and use them to predict future configurations. Section 4 focuses on the system implementation followed by initial computational results, discussed in section 5. 2
A customizable product can be configured using different
combinations of attributes (features). In an automobile, attribute could be
body style, transmission type, sunroof or parking assistance.
Customer buying behaviour can be studied by analysing how product
attributes are associated with each other. Association rule mining has
wide application in data mining for analysing and predicting
customer behaviour [
Let us define our product configuration problem as per [10, Definition 1]: the configuration problem C can be expressed through a triple (X; D; F ), where:
X is a set of product attributes (configuration variables) lets say fx1; :::xng. Where n is the total number of attributes.
D is the set of attributes finite domains d1; d2; :::; dn.
F = ff1; f2; :::; fmg is a set of propositional formulas (rules or restrictions) over attribute set X.
In this paper, we assume that the configuration variables xi 2 X are boolean, hence domain di 2 f0; 1g; 8i 2 X. A configuration is said to be feasible if an assignment for all attributes (i 2 X) is found which fulfils each and every proposition in F . X = x1; :::xn is a set and each di is a set. In this case, each di is a binary set. In other words, fd1; :::; dng is a collection of sets, whereas fx1; :::; xng are the elements of set X.
Let us assume a car is configured using six attributes X = f1; 2; :::; 6g f Automatic Gearbox, Cruise control, Reverse camera, Sunroof, Keyless Go, Parktronic g, D 2 f0; 1g8X, and F = ff1g where
f1 = f2 ! 1g: Cruise control requires Automatic Gearbox. For a given set of boolean variables (attributes) and propositional formulas, finding a feasible configuration is a Boolean Satisfiability problem where the aim is to get an assignment (true or false value) of Boolean variables (X) which satisfies given configuration rules (F ). Configurations from Table 1 can be treated as customer configurations and in the next section we will derive associations between different attributes from these. Table 1 contains a list of some feasi
Association rule mining methodology is used to find the association
between variables in large transactions [
Support(p ) q): This is the proportion of configurations that contain both attribute sets p and q. In Example1, Support (Sunroof; ReverseCamera)= 4/10 = 0.4.
Confidence (p ) q): Given set of configuration which contains attributes set p, this is the proportion of configurations where attribute set q is also selected. In Example1, Confidence (Sunroof ) ReverseCamera) = 4/5 = 0.8. If support and confidence are greater than user specified thresholds, then we call that association rule “interesting”.
After applying rule mining techniques, we get a large number of relations which satisfy our parameter of interestingness, although not all of them are customer driven. Because sales transactions do not explicitly state only customer selectable attributes, it is then our task to identify and remove attribute relations which are driven by the technical nature of the product. For example, in Table 2 (rule # 2) the association between two attributes CruiseCtrl ) AutomaticGearBox is given by Support = 0.3 and confidence = 1. The high confidence between Cruise control and Automatic Gearbox is not really driven by customer buying behaviour, but this is the only way a feasible configuration using attribute Cruise control can be created. This information is stated in the configuration rule (F = ff1g) of Example 1.
In practical scenarios with hundreds of product attributes and thousands of configuration rules, identifying which attribute association rule is controlled by their technical dependencies is non-trivial. Also, it is both error prone and time consuming to analyse and classify a large set of attribute associations manually. As the configuration problem is used to find feasible assignments of product attributes under configuration rules, we use this to state some direct dependencies among attributes. Any two attributes (let’s say p and q) can be combined in a configuration based on the following relations: Depending upon how many relations are satisfied from Table 3 any association rule can be classified in one of 24 possible cases. For example, if we consider Cruise control and Automatic gearbox from example 1, as attribute p and q, then with the given configuration rule, we will not be able to create a configuration which satisfies 3rd relation p ^ :q. If all the four relations are satisfied from Table 3 then we can say that the given attributes are independent of product’s technical influence and any association derived from customer orders actually reflects their buying behaviour.
In the other case, let us assume that the product from Example 1 has been upgraded and new configuration restriction has been added i.e. F = ff1; f2g where f2= Parktronic comes with Reverse camera. Due to this new restriction configuration, O001, O003 and O010 from Table 1 will not be feasible for future product. Then, associations between different product attributes need to be validated against the new configuration rule. In the next section, we discuss a set of optimization models for validating attribute association rules with respect to configuration restrictions. 3
In the task of validating attribute association rules for an upgraded product; our aim is to find one instance of future demand where all derived association rules are satisfied. The future demand estimate can be given in terms of a configuration set where correlation between attributes is controlled by predefined association rules.
If products are defined over sets of boolean attributes, the association rules can be expressed as boolean proposition formulas. For example, support(p; q) can be modelled in a proposition formula to capture the joint selection of the attribute sets p and q. The value of support (p, q) indicates the fraction at which corresponding boolean propositional formula (p ^ q) evaluates as true in the configurations set. Thus, finding a consistent future demand estimate with respect to association rules is equivalent to satisfying a set of propositional formulas with some probability. For example, if support(p; q) = 0:2 then we want a clause (p ^ q) is true 20% of the time in final configurations. The resultant set of propositional formulas can be divided into two sets: 1) propositional formulas derived from the configuration problem (i.e. BOM) which has to evaluate to ”true” for every demand instance 2) propositional formulas generated from association rules which are assigned a probability of being satisfied. If we are able to find a probability distribution on the truth assignments of the boolean variables corresponds to association rules that induces the given probabilities, then we will have an instance of future demand where all calculated association rules are satisfied.
For a given set of boolean variables and set of boolean clauses,
determining whether it is possible to find a probability measure over
truth assignments of the boolean variables that induce the given
assessments is known as Probabilistic Satisfiability (PSAT) problem
[
In this section, we present the optimization model for evaluating the consistency among attributes association rules. Before formulating the mathematical model, let us discuss a small example to understand the underlying problem: Example 2: Let us assume we have discovered a customer behaviour from Table 1 that three different attributes (Reverse Camera (RC), Keyless Go (KG), Parktronic (PA)) are individually selected 60% of the time in prior demand. Now, new configuration restrictions (e.g. Upgraded product) specify that at least two of the attributes (out of three) have to be present in every feasible configuration. Now, is it feasible to assume that the attributes will be selected at the same rate as before?
From given configuration rule in Example 2, at least two attributes have to be present in a feasible configuration, i.e. the following boolean clause has to be true: (RC _ KG), (KG _ PA) and (RC _ PA). If we are able to get a set of configurations where the above rules are satisfied and each attribute is selected 60% of the time in the configuration set, then we can say that derived attribute association rules and configuration restrictions are consistent with the upgraded product.
Before solving the problem of Example 2 let us formulate a general mathematical model to detect consistency among the association rules. The problem of validating association rules with respect to a new configuration rule can be defined as follows: x1 ^ x2.
Let the index i refer to a logical association rule statement (Support or Confidence) defined over n Boolean variables x1; x2; :::xn using Boolean propositional formulas. As an Example from Table 2, x1= fCCg, x2= fSRg, the new variable 1= Support(x1,x2) =
Let the index j refer to a configuration in the set J , the total configuration set (typically of very large size).
i is the probability of ith statement (attributes Support or Confidence) to be true. As an Example from Table 2, 3=0.4 1 if ith statement is true in jth configuration Ai;j = 0 otherwise
Xj = Fraction representing the proportion of j in the total configuration set, a real number between 0 and 1; Zi+ = Positive deviation from target probability i, a real number between 0 and 1 Zi = Negative deviation from target probability i, a real number between 0 and 1
where p^q is equal to support (p ) q). Ap^q;j will take value one if both p and q are present in configuration j, otherwise zero. 3.1.2
Confidence value from association rule mining can be controlled through conditional probability of given attributes. Confidence (p ) q) = support(p ) q)=support(q) = pjq.
X(Ap^q;j j pjqAq;j )Xj + Zp+jq
Zpjq = 0 (6) Above equation controls the confidence (p ) q) by controlling the joint selection of p and q and individual selection of attribute q in the configuration.
Decision variables Zi+; Zi are used to control the absolute deviation for each association rule. The matrix A lists the set of all feasible configurations which we use to match association rule quantity i. At this point let us say that A contains all feasible orders. From model OP T1 if Zi+; Zi are zero 8i then we can say the association rules are consistent among each other and also with configuration rules as we are only considering feasible configurations in the matrix A.
In Example 2, let us assume that x1 = RC, x2 = KG, x3 = PA. Then the configuration constraint can be written as follows: x1 + x2 = 1, x1 + x3 = 1 and x2 + x3 = 1.
any combination of x1, x2, x3 which satisfies the above constraint will be a possible configuration to use by model OP T1 i.e. as a column of A-matrix. In this case, only four possible solutions are available so we can solve this example by explicitly enumerating all possible configurations.
OP TExample2 : Minimize 01
By solving the optimization model OP TExample2, at optimality we get objective function value 0.2 (6= 0). There are multiple optimal solutions and one is X = 0:4; 0:2; 0:4; 0 which means configuration 1, 2 and 3 are used 40%, 20% and 40% of the time respectively and configuration 4 is not used in the final solution. As the objective function value of OP TExample2 model is not equal to zero, we can say that attribute association and configuration rules are not consistent with each other. However, one drawback of the model OP T1 is that it does not explicitly specify how many association rules are satisfied. More specifically, we would like to be able to build a model which satisfies the maximum number of association rules in case of conflicting inputs as presented in Example2. In the next subsection, we discuss one such model. Complex products such as automobile undergo enormous changes through their life cycle. Thus, it is quite likely that some of the association rules derived from past orders may not be consistent with new configurations rules as discussed in our Example2. A relevant question is whether we can maximize the coverage of association rules which can be fulfilled by an upgraded product. The OP T1 model discussed in section 3.1 can only detect if all the association rules are satisfiable or not. If there are conflicts, we need to ideally find the minimum number of association rules, so that if we remove those, then all the remaining association rules become consistent.
With the same definitions of variables as in the OP T1 model, let us formulate the problem as follows:
yi =
OP T2 = Minimize
X yi yi is a binary 0-1 decision variable associated with each association rule (confidence/ support). The variable yi will take value 1 if there is some deviation between selection of attribute association P Aij Xj and the given rate i. For any association rule at a time j only one variable Zi+ or Zi will have a non zero value. Accordingly, yi will take value 0 or 1 from constraint 14. If all association rules are consistent, yi must be zero for all i.
In Example2 the OP T2 model will give objective function value 1 i.e. if we ignore one association rule then we can satisfy the remaining ones in the new product configuration. For example if we take only 2; 3 = 0:6 then we can build a set of feasible configurations which can satisfy both the association rules. 3.3
Model formulation (OP T1) and (OP T2) are designed to express all possible configurations (X). This runs into the hundreds of millions! There are still two different problems with the optimization model (OP T1) and (OP T2): 1. How to consider all possible solutions? Very large number of decision variables. 2. How to build Ai;j matrix? – Do we have to explicitly write all the columns of A? – Can we work with a small set of configurations and add more when needed?
The key for success here is that Aij needs not to be stored or built
explicitly. Based on the need, configurations can be added to Aij to
minimize the objective function. A solution for such a large scale
optimization can be found using column generation [
As discussed in figure 2, the overall problem is divided into two optimization problems. The first problem is to make a selection over known configurations (stored in Aij M atrix) such that attribute association rules can be matched as per objective function. In the next step, we want to know whether there is any feasible configuration (w.r.t. configuration rules ) which improves the master problem objective function value. Let us assume that we have an ’Oracle’ (submodel) which will give us such a configuration each time we ask the question. If no such configuration is found, we conclude that there is no feasible configuration which can improve our current objective function value. The aim of the master problem in both model OP T1 and OP T2 is to find the optimal solution over known configurations (given columns of the Aij -matrix) and the task of the sub model is to add new columns to the Aij -matrix. We will repeat this procedure until no configuration is found that is worth considering. In the next section, we will discuss the formulation of sub model w.r.t. master problem OP T1. In linear programming problems, in each iteration of the simplex algorithm we compute reduced costs to check if any non-basic variable can enter as part of the solution. To do so in model OP T1, we have to evaluate if P wi [xi]j < 0 for any configuration j. Where wi is dual variable and [xi]j is the new jth configuration. As the value of wi will be known from solving model OP T1, if we know the coefficient of jth order [xi]j we can tell whether the given order will improve our objective function or not. Another way to look at this problem is to build the new jth configuration so that P wi [xi]j can be maximized.
Data: wi= Dual variable from the model OP T1, associated with constraints 2 B= Set of constraints derived from configuration rules Decision Variable [xi]j = new configuration for jth column of configuration ma(18) (19) (i.e. x is a feasible configuration)
In this formulation, we assume that configuration restrictions are
modelled as a set of linear constraints as per Eq. 17 [
X wi Dual costs are recomputed by solving the model OP T1 and the process terminates when no more configurations are found to be worth taking in. We use IBM ILOG Cplex engine to solve the sub-problem. The master (OP T1) and the subproblem (OP T 1Sub) may have to be solved multiple times before the terminating criteria is satisfied. The procedures discussed in section 3.1 and 3.4 works together to find a set of consistent association rules. Model OP T1 works with a predefined set of configurations and optimizes the current deviation with given association rules target. Model OP T 1Sub is used to find a new configuration so that Model OP T1 objective function value improves. Implementing the column generation approach in association rule verification problem is done in the following way: 1 Solve the OP T1 model with current columns of Aij matrix. In the first iteration, a feasible configuration can be used to initialize the A matrix. This iteration is used to get the dual variables which will be used in the new configuration generation model OP T 1Sub. 2 Get dual variable wi from Eq. 2 of the OP T1 Model 3 Set up a sub problem as per Section 3.4 4 Get new column (order as 0-1 vector [x] from solution of the sub problem discussed in section 3.4) 5 This generates a possible new configuration j with dual variable wi 6 If configuration j satisfies P wi xi 0 (pricing inequality) then i configuration j enters as jth column of Aij 7 Dual costs are re-computed and the process terminates when no more configurations satisfy the pricing inequality. 4
One of our goals is to provide a software system which can 1)
extract association rules from given configurations and is 2) able to use
new configuration rules (upgraded product) to validate attribute
association rules. Figure 3 shows the implementation flow of arriving
customer driven attribute associations for predicting future
configurations. We use Apriori algorithm through R-arules package to find a
list of interesting (by support and confidence threshold) association
among product attributes [
As a next step after computing attribute associations (support and confidence), we build the optimization model as per section 3 to compute configurations as per target input characteristics. Two optimization models are used: 1 2
Master model as per section 3.1 (OP T1) which models selection of configuration such that sum of absolute deviation from target association rules can be minimized.
Sub model as per section 3.4 which models all configuration rules as linear inequalities.
Both the optimization model receives input from each other in every iteration of column generation procedure described in section 3.5. Optimization models run iteratively until stopping criteria (no improvement to the current solution) is met. At any iteration of column generation procedure, sub model gives a single configuration which is used as new decision variable to the master problem. We have implemented both the optimization model using cplex 12.5. As a result of the optimization procedure, a configuration set is build adhering given association rule targets. In the next section, we will discuss our first computation result with developed models. 5
In this section, we discuss typical computational parameters and associated numbers with input data and decision variables. We have tested our methods and models mainly on automotive data. The historical configurations are analysed at specific granularity (productline/body style/market/engine type) to reflect current sales planning. Generally, about 500-1000 unique attributes are to be specified in a configuration set. However, not all attributes are available for customers choice as some of them are related to production. In our analysis, we have considered between 100 and 200 attributes which are available to customers. Three vehicle segments are used to test the methodology that has been developed. Table 4 shows various parameters of the data segments that we have selected. The number of orders is the number of prior configurations used to find the attribute associations (support and confidence). For this experiment, the maximum number of attributes in an association rule is limited to two i.e. association among two arbitrary attributes are computed.
Experiment # # of attributes Segment1 Segment2 Segment3
Starting from a set of configurations and attributes, we use additional parameters such as minimum support and minimum confidence to compute attribute association rules. In this experiment, our aim is to find association rules which are significant (e.g. above minimum support and confidence support). After applying data mining methods, we get a large number of attribute association rules which are then filtered as per their direct dependencies/conflict with configuration rules as explain in section 2.2. By doing so, we see a significant reduction in the number of association rules. These rules are now ready to be validated with respect to the upgraded product.
Now we apply optimization model discussed in section 3.1 to build a set of configurations so that association and configuration rules are met together. In most of the cases, not all computed association rules are applicable to the upgraded product. Therefore, it is important to use only consistent rules to predict the set of future configurations. We applied the optimization model discussed in section 3.1 to build such a configuration set.
An important use of the set of predicted future configurations is to find part demand estimates for future production. In order to see the influence of consistent customer buying behaviour in parts demand, we computed parts frequency associated with order sets, where 1) only consistent attribute associations are used to predict the order set and 2) all attribute associations available after pruning w.r.t. configuration rules are used to predict the order set. The above association rules are also supplemented with a few sales forecasts (at single attribute level) to include estimates of new attributes which are not present in past orders.
Order set built with inconsistent association rules
Order set built with consistent association rules ] % [ n i y c a r u c c a t s a c e r o f s t r a P 80 60 40 20 0
Segment1
Segment2
Segment3
Figure 5 shows the part forecast accuracy of the two scenarios discussed above. The order sets are compared with real customer orders to find the match with respect to estimated part number. About 10,000 part forecasts are compared and we used part demand matching parameter 10% i.e. if the estimated value of part demand is within 10% of actual demand then this forecast is considered good. With this measurement, we have compared two order set computed with consistent and non-consistent attribute association. In figure 5, for all the 3 cases we see significant improvement in forecast accuracy when consistent sets of input information are used. 6
Data mining techniques in manufacturing system are widely used
to provide detailed insights regarding processes and products, such
as customer segmentation, production control and quality controls
[
Another way of building reasoning between product attributes
from known configurations is through feature models [
In our work, we have formulated configuration problem as an optimization model to give an integrated solution within the column generation framework of validating set of association rules. Our model takes support and confidence value to attribute associations to build a set of configurations adhering given input targets. In case of conflicting association rules, the model that has been developed attempts to find the maximum number of association rules which can be satisfied after considering product configuration changes. 7
In this paper, we have discussed a framework for learning customer buying behaviour through data mining and optimization-based techniques. In mass customization, due to frequent changes in products, we are required to validate product attribute associations learnt from customer prior demand. The association rule mining technique when combined with the configuration problem gives the required framework for calculating consistent and feasible attribute associations. These associations among attributes can be used as inputs for predicting configurations for future production planning. The proposed framework uses data mining libraries from R to find association rules. The integrated framework with optimization models provides the ability to perform tests on many scenarios before using any association discovered from past data to future product planning.
One application of discovering attribute associations is to use them for predicting the set of future configurations. As per our initial computational results, such a configuration set results in considerable improvement in part demand forecasts. Currently, we only consider attribute associations which are frequent (e.g. above minimum support or confidence). In the next step, the association rule mining algorithm can be enhanced to look for other relations. Also, in current implementation we simply remove attribute association which are having the conflict with each other or with product configuration rules. As a next step, we will try to develop approaches which can readjust attribute association in case of conflicts. For example, we can have the same selection rate for attributes if they are selected together. Further computational tests are required to validate and improve our assumptions on attribute associations which can improve the selection of future configurations.