Feature models have become one of the most widely used formalism for representing the variability among the products of a product line. The design of a feature model from a set of existing products can help stakeholders communicate on the commonalities and differences between the products, facilitate the adoption of mass customization strategies, or support the definition of the solution space of a product configurator (i.e. the sets of products that will be and will not be offered to the targeted customers). As the manual construction of feature models proves to be a time-consuming and error prone task, researchers have proposed various approaches for automatically deriving feature models from available product data. Existing reverse engineering techniques mostly rely on data mining algorithms that search for frequently occurring patterns between the features of the available product configurations. However, when the number of features is too large, the sparsity among the configurations can reduce the quality of the extracted model. In this paper, we discuss motivations for the development of dimensionality reduction techniques for product lines in order to support the extraction of feature models in the case of high-dimensional product spaces. We use a real world dataset to illustrate the problems arising with high dimensionality and present four research questions to address them.
Feature Models (FMs) have been first introduced for representing
the commonalities among the software systems of a software
product line [
Defining an FM over a set of existing configurations can bring
valuable support in the adoption of mass customization strategies.
Tseng and Jiao [
An FM is a concise representation of the solution space of a
product line. It can be used to engineer mass customization systems, such
as configurators [
For these reason researchers have provided significant
contributions in the development of techniques for automating the extraction
of FMs from sets of existing products specifications (or
configurations) - e.g. see [
In this paper, we discuss the pitfalls related to the extraction of FMs from product configuration data. In particular, we highlight the limitation of applying logical approaches to high dimensional data (i.e. when the product space is defined by a very large number of features). When the number of features grows, logical methods require an increasing number of available configurations to maintain statistical significance. This means that while automatic support is desirable to help practitioners manage high dimensional product space, an FM extraction process that solely relies on logical techniques does not cope well with high dimensionality. We argue that, even when a large volume of configuration data is available, one cannot consistently assume that a logical pattern extracted from the data should be used to define the boundaries of the configuration space. It follows that while it is desirable to support practitioners with logical techniques, an FM extraction process should also consider available product domain knowledge. In the following sections, we highlight the need for formal methods that operate on both logical techniques and background domain knowledge.
The remainder of the paper is organised as follows. Section 2 describes feature modeling and prior work related to the synthesis of FMs. Section 3 illustrates the curse of dimensionality in the context of the FM synthesis problem with a real world example. In section 4 we elaborate a research plan with four research questions. 2
An FM is an explicit representation of the underlying variability among the products of a product line. It defines the set of features that compose the products and how these features can be combined into products. An FM can be represented as a tree in which nodes are features and edges between the features represent hierarchical relationships (see Figure 1). In the tree hierarchy, each parent-child decomposition constrains the valid combinations of features that can be found in product configurations. The FM in Figure 1 shows a XOR-decomposition for the feature Screen into the features High definition and Basic (i.e. the two child features form a XORgroup), which specifies that exactly one of the two child features has to be included in each configuration. Other usual decomposition types are OR-groups and Mutex-groups, which respectively define that when the parent feature is selected, all features, or at most one feature, must be included. As shown in Figure 1, filled circles and full circles represent mandatory and optional child features respectively. It is also possible to define cross-tree constraints such as the implies relationship in Figure 1.
An FM is attributed if there are typed attributes associated to its features. Figure 1 shows an attribute size of type integer under the feature Screen. Such FMs are referred hereafter as Attributed Feature Models (AFM).
The semantics of an FM f m, noted [[f m]], is commonly defined
as the sets of products (i.e. the sets of sets of features) that satisfy the
constraints specified by f m [
size : int implies
X
X X
X
The FM synthesis problem consists in the extraction of an FM from
an existing set of products. The synthesis can be decomposed into
two steps. First, a logical formula over the inclusion of features in
products is mined from the set of configurations. Then, an FM is
extracted from the logical formula [
The initial set of configurations can be represented as a configuration matrix, which presents the features that are included in the existing configurations, as well as the values for the feature attributes. Table 2 shows a possible initial configuration matrix from which the FM in Figure 1 could be synthesised.
There are multiple examples of prior work related to the
synthesis of FMs from a logical formula, or from sets of formally defined
configurations [
X X
X X X
X
of FMs is the elicitation of the FM hierarchy. She et al. [
Other works address the extraction of FMs from less structured
artefacts such as textual product descriptions [
In [
A machine learning algorithm suffers from the effects of the socalled curse of dimensionality when it does not scale well with highdimensional data. For example, performance issues can arise when the complexity of the algorithm is exponential in the number of dimensions of the dataset. High dimensionality can also impact the quality of results when some dimensions of the dataset are not relevant to the problem to be solved, and thus feed an algorithm with distracting information. Data are referred to as being high-dimensional when they are embedded into an high-dimensional space. In the context of the FM synthesis problem, the data are formed by the existing product configurations. Consequently, data dimensionality is defined by the number of features, the number of attributes, and the size of the domains for the values of these attributes. 3.1
We now list the variability structures that are commonly mined from configuration matrices by existing FM synthesis approaches.
Binary implications: Binary implications indicate dependencies between the feature or attribute values in the configuration matrix. Hierarchy: A tree hierarchy is built from the binary implications between the features. Conceptually, the hierarchy of an FM organizes the features into different levels of increasing detail. It also defines that the selection of a child feature in a configuration always implies the selection of its parent feature.
Mandatory features: Once the hierarchy has been found, for any binary implication from a parent feature to one of its child, the child has to be made mandatory.
Feature groups: OR-groups, XOR-groups and Mutex-groups represent how sibling features can be combined together in product configurations.
Cross-tree constraints: In addition to the constraints represented in the feature hierarchy, cross-tree constraints such as requires or excludes relationships are mined.
In order to illustrate the curse of dimensionality in the context of
the FM synthesis problem, we have applied an AFM synthesis
algorithm to a real world dataset extracted from the Best Buy product
catalog. Best Buy is an American retailer that provides consumer
electronics, and publishes its products data on the web through an API
3. We built configuration matrices for the Best Buy data by merging
extracted sets of products that have at least 75% of features and
attributes in common. A description of the AFM synthesis algorithm
is out of the scope of this paper and can be found in [
We have considered 242 extracted configuration matrices. Table 3 shows statistics about these matrices. The number of Configurations is the number of products in the matrix while the number of Variables is the number of columns (corresponding to features or attributes). Domain size is the number of distinct values in a column. The properties of the configuration matrices are quite representative of high dimensional product spaces. The number of products is low w.r.t. to the total number of distinct cell values. In our dataset, there is almost the same number of variables (columns) as configurations; and in average there are more than 5 values per variable. The application of the AFM synthesis algorithm to this dataset brings to light the need for further research efforts as summarised below.
Configurations Variables (columns)
Domain size
Firstly, the Best Buy configuration matrices contain empty cells. The average proportion of empty cells in the matrices is 14.4%, and in the worst case, the proportion is 25.0% The problem with empty cells is that they do not have a clearly defined semantics in terms of variability. One might consider that an empty cells translates the absence of the corresponding feature in the configuration. However it is unsure whether the feature is really excluded, or if its value is simply unknown. This uncertainty is important because different interpretations of empty cells could lead to different synthesised FMs.
Another concern is the ability to distinguish features from attributes among the columns of the matrix. As for the empty cells, different heuristics for this task could result in very different synthesised FMs. Furthermore, each attribute should be associated to the appropriate parent feature, and automating the association resolution becomes harder as the number of features and attributes grows.
One possible direction for addressing the interpretation of empty cells and the distinction between features and attributes is to rely on the specification of domain knowledge by users. This strategy would require the design of user interactions that prevent users from being overwhelmed with huge volume of variability information, notwithstanding the large number of features and attributes in the dataset.
Another important concern is related to constraints. The number
of constraints synthesised from the Best Buy matrices average 237
3 http://developer.bestbuy.com/
with a maximum of 8906. Such large numbers of constraints put
into question the validity of the extracted constraints - that is whether
these are legitimate configuration constraints w.r.t. to restrictions in
the product line domain. When the data is sparse, it can be hard to
evaluate whether the configurations just happened to exhibit the
constraint. Moreover, when the number of constraints is high, many
different FMs that fit the data equally well can be derived from them.
A purely statistical synthesis approach is thus limited as it cannot
be used to assess the quality of the candidate FMs. Therefore, it
would be useful to automatically reduce the number of irrelevant
constraints, or help users assess them. Several approaches can be
considered to determine a readable subset of relevant constraints to
present to users, e.g. prioritization, or minimisation [
Our example does not illustrate the synthesis of PFMs. While the constraints mined for crisp FMs have a confidence of 100% (i.e. they cannot be violated by any product), the constraints mined for PFMs have a confidence above a predefined threshold lower than 100%. PFMs can be useful to model variability trends among the products. Similar to the synthesis of FMs, a high dimensional matrix can lead to the computation of a very large number of constraints with a confidence above the predefined threshold, and thus make the elicitation of the PFM structure arduous. 3.2
In machine learning, the term dimensionality reduction denotes the
process of reducing the number of attributes to be considered in the
data for a particular task [
In feature selection, a subset of the original data attributes is
selected (see [
Feature extraction consists in defining a projection from the high-dimensional space of the data to a space of lower dimension. Let us consider a product line featuring the features length, width and depth. One could define a mathematical function over the values of these three features to replace them with a new attribute size, thus reducing the number of dimensions by mapping three features to a single one. The intended benefit is to reduce the cognitive effort when configuring since (1) less configuration variables are presented to users; (2) the configuration variables abstract details that are typically technical, making the promise of raising the level of abstraction for domain analysts or end-users of the engineered configurator. 4
We aim at addressing dimensionality reduction in the synthesis of FMs in future research. To this end, we state four research questions: RQ1: How should empty cells in configuration matrices be interpreted during the FM synthesis? An empty cell can either represent the absence of a feature (resp. attribute) or translate a lack of knowledge for the value of a feature (resp. attribute). Acknowledging different semantics for empty cells can lead to different synthesis results. It would be interesting to investigate the use of complementary data, such as product descriptions or user knowledge, to set these missing values.
RQ2: How to use background-knowledge in the construction of FMs? Current synthesis approaches commonly use only data for constructing FMs. However, when a configuration matrix is highly dimensional, it is possible to find many different FMs that fit the data equally well. Some researchers in the machine learning community have already considered that constructing models only from observed data is a bad practice, which has been referred to as data fishing. In order to select the right FM, we believe that practical synthesis procedures should be guided by existing knowledge about the application domain of the targeted FM (i.e. background knowledge). More specifically, background knowledge could be particularly useful for (1) differentiating the columns of a configuration matrix into features and attributes, and (2) selecting the tree hierarchy among the features of the FM.
RQ3: How to reduce dimensionality by modeling product qualities? Configuration matrices represent products as sets of features, which refer to a large number of technical specifications (e.g. size, weight, battery life). However, customers usually communicate and reason about the products in terms of different abstractions we call product qualities (e.g. ease-of-use, portability, ergonomics). An interesting research direction is the design of formal methods for augmenting configuration matrices with product qualities. Projections of qualities onto the technical features could help define a new configuration space of lower dimensionality. RQ4: How to assess the quality of extracted FMs? One usually wants to elicit an FM with a set of specific tasks to solve in mind, which means that the quality of the FM should be assessed on the basis of the degree of support it provides w.r.t. these tasks. For instance, if an FM is extracted from a set of products with the aim of providing an overview of the underlying variability (domain analysis task), then the readability and the learnability of the FM are relevant quality criteria. In the case of the synthesis of an FM to model a solution space, the conformance of the FM to the existing products should be evaluated. A framework is thus required to identify the evaluation criteria of extracted FMs. 5
In this paper, we discussed the problems arising during the automatic synthesis of feature models from high-dimensional configuration matrices. We first framed concepts well-studied in the machine learning community, such as the curse of dimensionality and dimensionality reduction, in the context of the feature model synthesis problem. Using a real world dataset extracted from the Best Buy website, we then highlighted the steps in an attributed feature model synthesis process that require further investigations (e.g., when computing constraints). We stated research questions related to the application of FM synthesis algorithms to high dimensional configuration matrices.
The motivation for enabling domain experts to apply dimensionality reduction on configuration matrices is to synthesize variability information that is relevant w.r.t. to the intention of practitioners, and to produce more useful, readable resulting feature models. 22