Towards an enhanced user’s preferences integration into ranking process using dominance approach

Many computer applications recognize user preferences as essential. Xiaoye Miao [14] considers them in a multidimensional space including language and preference operators, where a set of preference builders are assigned to categorical and numerical domains. Elsewhere are presented statistical models for user preferences, where the frequency of an item depends on the user preference and item accessibility. The user preference is modelable as an algebraic function to approximate the statistical value of the item’s features and the user profile. In [10], preference samples provided by the user are used to establish the order of tuples in the database. These samples are classified into two classes: Superior and Inferior samples; they contain information about relevant and irrelevant samples, respectively. In [7], the authors suggest “ProfMiner algorithm” to discover user profile on the basis of preferences and wishes which are user-provided. ProfMiner algorithm operates on a database containing contextual preference rules. This algorithm determines a threshold ‘k’ to select the contextual preference rules, describing the user profile and the member of these rules depends on ‘k’. However ProfMiner algorithm relies only on two measures: support and confidence which not be sufficient to preserve all the relevant information. Worth noting that the contextual preference rules is determined and extracted by “CPrefMinerAlgorithm”. The latter is a qualitative approach based on Baysian Network preference rules. The main strength of this approach that it produces a compact model of ordered preferences and products accurate result as well. In [24], the authors propose processing contextual logs of mobile device users to find out context-aware preferences.

In the same framework, PrefMinerAlgorithm [13] proposes a new solution to mine user’s preferences for intelligent mobile device notification management. PrefMiner Algorithm has the ability to determine automatically rules that reflect user’s preferences by studying notifications collected in advance in databases. In [22], the authors present an algorithm based on clustering and filtering user preferences, it is adapted to the different habits of users, and it partitions users into three groups according to their different habits and preferences: optimistic, pessimistic, and neutral. This grouping or clustering is based on new similarity measures to solve the shortcoming of previous or classical methods. In addition, some people used to resort to query rewriting or merely query enhancement [2] which consists of integrating into the user query some elements from the user profile. This technique is well used in Information Retrieval domain [8] and this is very recent in database domain.

Between business activity and Datamining lies a relationship of reflexion, i.e., the complexity of datamining is only a reflexion of that of business activity. A huge amount of business-related information is stored in big databases with thousands if not millions of pieces of information. Datamining is the fields, where these databases are exploited to get interesting and valuable information for the benefit of business management. Therefore, different techniques are devised to analyze databases to get this objective. Ranwar [12] is one of these techniques which uses interestingness measures to sort and rank ARs; Acdr [11] as an algorithm which relies on rule-dissimilarity criterion to get rid of redundant rules and sort dissimilar rules. These dissimilar rules are ranked from top to bottom according to their priority and frequency degrees. In [17], the algorithm uses interesting measures and clustering techniques to chase out redundancy and to keep rules which satisfy predefined criteria. Skyrules Algorithm [4] proposes a statistical dominance-based algorithm which distinguishes dominant from non-dominant rules; the algorithm keeps the former and discards the latter with complete reliance on skyline operator. This techniques is only an extended exploitation of the technique proposed in [19] which is based on the notion of dominance to generate dominant patterns and reject dominated ones with regard to skyline operators [20]. In [1], authors are interested in modeling and automating the mining process of relevant ARs. They use Electre Tri as a Multi-Criteria Analysis approach. Recently, the authors focus on combining by Multi-Criteria Decision Analysis and multiobjective evolutionary algorithms to select the most preferred solution from the generated set [5, 6]. In [3], the authors introduce the hash algorithm to push speediness and efficiency of ARM process with the aim of providing a faster mining.

The common objective of the techniques described above is to minimize the number of rules to be generated. We reasonably notice that there is a causative relationship between the number of generated rules and the number of criteria or interestingness measures imposed on the databases: the higher the latter, the lesser the former.

Unlike the approaches described above, our contribution presents a method which allows for the user preference as a further restriction of the mining operation so as to optimize the ARs cardinality.

Figure 1 shows a visual representation of the mining process of MDP\(_\mathrm{REF}\) rules. Notice that it consists of three main operations the last of which is the concern of MDP\(_\mathrm{REF}\) rules algorithm.

MDP\(_{\mathrm \mathrm{REF}}\) is short for most dominant and preferential rules; it is threshold-free and it does not discard any measure, so more objective and contributes to solve the dimensionality more than other approaches without losing information [15].

For an algorithm to be effective, it has to be iterative without consuming much time. Iterativeness is necessary for accurate and reliable results. MDP\(_{\mathrm {REF}}\) Algorithm processes rules iteratively and integrates a multithreading system for a concurrent processing which makes it faster and time-saving. The more tasks it performs, the less time it needs to finish the processing, and therefore, being iterative does not necessarily mean being time consuming. In our case, the fourth task is basically important, since it results in determining three groups of rules:MDP\(_{\mathrm {REF}}\) Algorithm focuses on SER and processes all SER-Rules, to mine those which cover the user’s preferences provided in advance by the user: tasks 6, 7, and 8.

The seventh task allows discarding preferentially redundant and/or overlapping rules. The performance of task 7 implies the performance of task 8. MDP\(_{\mathrm {REF}}\) Algorithm tasks do not include learning user preferences; these were provided prior to processing—the fact which means that these do not have any influence on the processing time of MDP\(_{\mathrm {REF}}\) Algorithm.

Table 3 shows a set of ARs on which MDP\(_{\mathrm {REF}}\) Algorithm is applied and the obtained results are these two rules: ar \(_{10}\) and ar \(_{05}\) the most dominant and preferential rules (MDP\(_{\mathrm {REF}}\) rules).

To evaluate experimentally the MDP\(_{\mathrm {REF}}\) Algorithm’s efficiency, the MDP\(_{\mathrm {REF}}\) Algorithm is further applied on a data set of mobile phones proposed to the customers, which includes a wide range of mobile brands launched in the Moroccan national market.

The characteristics of these mobile phones and there attributes are specified in Tables 4 and 5. The AR-set involved contains 25,000 rules corresponding to a set of some distinct mobile phones, described by a set of 326 transactions, representing a set of 128 distinct items. These 25,000 rules (which may not be big data) processed by MDP\(_{\mathrm {REF}}\) Algorithm and the result is the generation of 14,268 rules representing only \(\approx \)57% of the original number.

As the other algorithms are based on thresholding, we are obliged to accept their optimal threshold only for reasons of comparison.

Table 6 describes the behavior of MDP\(_{\mathrm {REF}}\) algorithm in comparison with others concerning the number of generated association rules. We notice the following:Table 6 allows us to predict that with a confidence level of 95%, MDP\(_{\mathrm {REF}}\) will select an average of 14,268 ± (4275) rules.

Given that the user’s preferences are provided prior to processing as well as a number of rules he prefers to get back. This number is noted “u”. On the basis of MDP\(_{\mathrm {REF}}\) performance, our algorithm “Rank-Sort-MDP\(_{\mathrm {REF}}\)” processes the set of ARs (AR-set) and partitions it into subsets (\(E_i\))i \(\in \) {0,...n}, to sort them and to return their ranks. Then, it checks for the ARs taking into consideration the priority of MDP\(_{\mathrm {REF}}\) rules, and stores the ARs in \(E_i\), and these Association Rules members of Ei are intra-ranked from left to right. The original “AR-Set” is the sum total or union of subsets (\(E_i\)) which can be mathematically expressed aswhere “u” represents the size of rules that the user wishes to get back. This size can be expressed with the following algebraic formula:The “u-rules” set is the union of E\(_{i}\) subsets, such that \(i\le n\), and E\(_{i}\) is prior to E\(_{j}\) when \(i\le j\), the idea is that each time Rank-Sort-MDP\(_{\mathrm {REF}}\) iterates, MDP\(_{\mathrm {REF}}\) also iterates and the outcome is a subset E\(_{i}\).

Rank-Sort-MDP\(_{\mathrm {REF}}\) algorithm was coded OOP language programming and all tests were performed on a computer with the following specification: 1.73 GHz Intel processor with Windows 7 operating system and 2 GB as memory Capacity.

The Rank-Sort-MDP\(_{\mathrm {REF}}\) algorithm processes by stage, for instance:

At stage 1 (k = 0 + 1) (Line 6), the Rank-Sort-MDP\(_{\mathrm {REF}}\) algorithm call for MDP\(_{\mathrm {REF}}\) algorithm to select the first subset association rules (E\(_{1)}\) (Line 7) from the all Association Rules belonging to R \(\ne \) Ø (Line 5) in our case, see Table 3, where R is the “14-Rules set”. The AR\(_{10}\), AR\(_{05}\) are the two first association rules selected at this stage and ranged in the E\(_{1}\) that is considered as a first subset: {AR\(_{10}\), AR\(_{05}\)}\(\in \) E\(_{1}\).

At stage 2 (k = 1 + 1), the Rank-Sort-MDP\(_{\mathrm {REF}}\) algorithm call for MDP\(_{\mathrm {REF}}\) algorithm to select the second subset of association rules (E\(_{2}\) = {AR\(_{02}\), AR\(_{08}\)}) the E\(_{2}\) succeeds the E\(_{1}\), it is less good according to their members and ranked after the E\(_{1}\).

Recursively, at each stage k + 1, the proposed algorithm call for the MDP\(_{\mathrm {REF}}\) algorithm to select the new association rules succeeding those selected and ranked at the stage k. Then, the Association Rules set goes back before the one generated at the (k + 1)th stage. Consequently, all predecessor association rules are better classified and sorted than any association rules which belong to the successors set. Furthermore, the MDP\(_{\mathrm {REF}}\) rules ranked at the same stage in moving order of their degree similarity and the covered user preferences. Finally, the Rank-Sort-MDP\(_{\mathrm {REF}}\) algorithm can be considered as a sound algorithm.

When the Association Rules set R becomes empty and as the Rank-Sort-MDP\(_{\mathrm {REF}}\) terminates processing all association rules which are ranked and classified. This means that the Rank-Sort-MDP\(_{\mathrm {REF}}\) algorithm is complete.

We finally come to the conclusion that the Rank-Sort-MDP\(_{\mathrm {REF}}\) algorithm is sound and complete.

To show the performance of Rank-Sort-MDP\(_{\mathrm {REF}}\) algorithm, we applied it on the AR-set (in our case “14-Rule Set”), as shown in Table 3. It processed the said set and the result is the division into 7 subsets {E\(_{1}\)... E\(_{7}\)}, as summarized in Table 7.

The subset E\(_{1}\) which contains two rules ar \(_{10, }\) ar \(_{05}\) is generated in the first iteration of Rank-Sort-MDP\(_{\mathrm {REF}}\) algorithm. Worth noticing is that ar \(_{10, }\) ar \(_{05}\) are themselves the rules generated by MDP\(_{\mathrm {REF}}\) algorithm. Therefore, we reasonably conclude that the first generated subset E\(_{1}\) by Rank-Sort-MDP\(_{\mathrm {REF}}\) is also the result generated by MDP\(_{\mathrm {REF}}\) applied on the entire AR-set (14-Rule Set).

E\(_{2}\) is the Rank-Sort-MDP\(_{\mathrm {REF}}\) extracted subset in the second iteration which concerns the database “AR-set\(\backslash \)E\(_{1}\)”. The member rules {ar \(_{02, }\) ar \(_{08}\)} belonging to E\(_{2}\) are the most dominant and preferential rules in “AR-set\(\backslash \)E\(_{1}\)”.

At the end of the seventh and final iterations of Rank-Sort-MDP\(_{\mathrm {REF}}\), we get E\(_{7}\).

The result we get after the seven iterations is seven subsets in which rules are ranked from top to bottom. Therefore, all the 14 rules are ordered.

By now, we are ready to respond to the user’s order. Whatever “u” may be seeing Table 8.

This section proposes to compare the proposed algorithm with related algorithms having the same goals: ranking and sorting the association rules.

The first related algorithm is Rank Rules that suggested by [4]’s authors to rank the association rules basing on the Skyline operator and founding on SkyRules algorithm’s performances which is called at each iteration to determine the undominated association rules. The second one is the Rule Rank-CBA [21] which is evolved by Genetic Network Programming, where the directed graphs are used as genes population to compute the fitness function allowing to rank and to sort the members of thr data set. The third one is the Hybrid-RuleRank [16] that couples the Genetic Algorithms and a probabilistic and meta-heuristic method searching to optimize and approximate global solution, this meta-heuristic method known as: Simulated Annealing (SA). Worth recalling that RuleRank-CBA combines arithmetically the historical interesting measure, support, and confidence to create a set of functions to optimize its fitness function and achieve the target objectives. Like RuleRank-CBA, the Hybrid-RuleRank algorithm sorts and ranks the association rules according to the support and confidence measures.

In addition, the execution time and accuracy indicators are utilized as tools to measure the Rank-Sort-MDP\(_{\mathrm {REF}}\)’s performances and to accomplish this comparison.

To analyze, to study, and to interpret the execution time’s behavior of the proposed algorithm, as the input data size increases. We have arbitrarily taken from the AR-set (the mobile-phone database) some samples the different size on which we applied Rank-Sort-MDP\(_{\mathrm {REF}}\). Both Figs. 2 and 3 illustrate the evolution of runtime (the execution time indicator) when changing the size of the sample and when varying also the measure cardinality.

From Fig. 2, we notice that the execution time indicator is linearly increasing with respect to the sample sizes whatever the measure cardinality; all indicators are increasing regardless of the measure cardinality. Likewise, the trend of the execution time indicator is lower, because Rank-Sort-MDP\(_{\mathrm {REF}}\) calls MDP\(_\mathrm{REF}\) which is coded in threads approach; that is, in the event that we take each particular indicator alone, we notice that the trend is lower. This postulate may be extend to a Big-Database (more than 25000 association rules), since the Rank-Sort-MDP\(_\mathrm{REF}\) is an algorithm permitting to sort and to rank all given association rules with the straightforward time complexity basing on MDP\(_{\mathrm {REF}}\) algorithm approach. Rank-Sort-MDP\(_{\mathrm {REF}}\) relies on the output of MDP\(_{\mathrm {REF}}\) algorithm which is successfully tested, and evaluated, and applied on different databases bigger than actual one. The MDP\(_{\mathrm {REF}}\) algorithm’s results were the best performances that transmitted to Rank-Sort-MDP\(_{\mathrm {REF}}\), in terms of accuracy; precision and execution time [for further information, see our previous work in the 15th reference]. While Fig. 3 depicts that when varying the measure (cardinality or nature), the average execution time indicator may decrease and/or increase. This movement depends on the size of MDP\(_{\mathrm {REF}}\) rules set selected in the first iteration, since these selected rules are correlated with the employed and utilized measures.

We remark that the average execution time indicator decreases until a given measure cardinality (may be an optimal measure cardinality). Then, it increases. Hence, we intend to study the property of interesting measures belonging to measures sets.

Table 9 summarizes some statistical indicators: accuracy and the execution time, concerning the three different databases (Mobile phone, Iris, Flare) on which the four related approaches are applied. In this subsection, we compare, in terms of the execution time and accuracy indicator, the proposed approach known as: “Rank-Sort-MDP\(_{\mathrm {REF}}\) algorithm with “Rank Rules” [4] and “RuleRank-CBA” [21] and the Hybrid-RuleRank [16]. To evaluate the proposed approach’s performance and efficiency, we execute the aforementioned algorithms on other databases having different sizes and attributes (Mobile phone, Iris, Flare) which their characteristics are described in Table 10. To validate the obtained results and conduct a reliable comparison, the k-fold cross-validation technique is used, since it processes repeatedly each data set k-times. For getting accuracy, the compared algorithms are tested multiple times by running the k-fold cross validation technique on each data set, worth noting that the data set elements are rearranged and re-stratified before each round, and then, we keep the computed average accuracy of the multiple tests for each data set, (in our case: k = 10).

On the one hand, Rank-Sort-MDP\(_{\mathrm {REF}}\) outperforms Rank Rules in terms of accuracy (88.09 vs 87.69%). However, in terms of execution time, the proposed algorithm is much longer than Rank Rules (9.18 vs 3.93 s), because the Rank Rules algorithm does not process reasonably the statistically equivalent rules—SER, the Rank Rules algorithm may rank two SER in different levels. Hence, it is probably having the wrong ranking of an SER-set.

On the other hand, Rank-Sort-MDP\(_{\mathrm {REF}}\) is faster than RuleRank-CBA algorithm (9.18 vs 42.07 s) and it is, also, faster than the Hybrid-RuleRank (9.18 vs 42.10 s), since there are many redundant and repeated functions estimated and created in RuleRank-CBA. Meanwhile, in terms of accuracy, Rank-Sort-MDP\(_{\mathrm {REF}}\) and RuleRank-CBA have approximately the same performance (88.09 vs 88.78 %). Finally, the Rank-Sort-MDP\(_{\mathrm {REF}}\)’s performances compared to those of the Hybrid-RuleRank algorithm show that the last algorithm “Hybrid-RuleRank” surpasses the proposed one “Rank-Sort-MDP\(_{\mathrm {REF}}\)” in terms of accuracy (89.54 vs 88.09).

Table 10 summarizes the characteristics of the data sets: database is the database appellation, # Items is the item count in the data set, # AR is the association rules count, and # Transaction is the transaction count in the data set and Avg. MDP\(_{\mathrm {REF}}\) correspond to the average count of the association rules selected by the MDP\(_{\mathrm {REF}}\) algorithm from each data set.