A Genetic Algorithm Approach for Group Recommender System Based on Partial Rankings

2.1 Group Recommender Systems

GRSs make suggestions for a group. It considers the preferences of each individual member of a group into account and provides an optimal single recommendation. “In order to generate effective recommendations for a group, the system must satisfy, as much as possible, the individual preferences of the group’s members” [9; 21].

GRSs approaches can be classified into two broad categories [1; 4]. The first one merges the profiles of multiple users and constructs a single preference model for the group, and the other one makes the group recommendation instead of the individual’s recommendations. The RA is a prominent method for developing multiple strategies for GRS [5; 19].

2.2 Rank Aggregation

There are two well-established ranking methods, namely, KtD and SFD. Fagin et al. has proposed various metrics for comparing PR-suggested algorithms for computing few topmost items of a near-optimal aggregation of multiple different PRs [8; 10; 11; 12].

2.3 Partial Ranking without Ties

Following Dwork et al. [10] and Fagin et al. [12], we encounter PRs where there are some items unranked by a set of users, and such lists that rank only some of the items by a set of users are called partial list. There are many situations where a full listis not convenient or even cannot be possible. A special case of partial lists is the following. If σ is a set of rank order for a full list which includes all results, another set is called τ which is a partial list which is some subset of σ. τ is only a subset of σ, and each ranked item list above all unranked items is called top n list, where n is the size of the list. In order to deal with PRs, modified SFD is used [8; 11].

2.4 Partial Ranking with Ties

Let us consider the problem of RA of PRWT, that is, where items have the same preference for a user can be tied. Following Brancotte et al. [8], a bucket order on n is represented by a set of buckets B₁ to B_m that forms a disjointed partition of n such that x has transitive binary relation with y if there are i, j with i < j such that x ∈ B_i and y ∈ B_j. A ranking with ties on n is defined as r = [B₁…, B_m], where r[x] = i if x ∈ B_i. Although the classical formulation of the KtD allows comparing rankings with ties, in this case, it is not a distance anymore. Moreover, ties are actually ignored, and no disagreement can be considered for items which do not have ties. Thus, independent of the input, the ranking with the fewest disagreements is the ranking where all elements are tied in a unique bucket. To avoid reducing such a useless solution, algorithms based on KtD have to restrain themselves to produce permutations [11; 12].

With reference to only one ranking, a set of items which are either counter or tied would be counted as one disagreement. KtD is equivalent to sorting the elements and can be done, with adaptations, when considering ranking with ties [8; 11]. An optimal consensus ranking of a set of rankings with ties R ⊆ Rn under the generalized Kemeny RA with ties is a ranking such that

A consensus ranking denotes a not certainly optimal solution of the problem. When a solution is optimal, it is explicitly denoted as an optimal solution of a problem [6; 14].

2.5 Bucket Order (Spearman Foot Rule Distance Measure)

A bucket order is a linear order intuitively, with ties where every bucket is of size 1. Since the foot rule optimal aggregation is an optimal distance measure, the technique is called Kemeny optimal aggregation. The computations of optimal aggregation using foot rule for the partial list is an NP-hard problem of computing distance between one partial list and full list example of bucket order show in Figure 1.

Figure 1:

Bucket Order Representation.

2.6 Genetic Algorithm

A population of chromosomes is processed in a GA approach where a possible solution to an optimization problem is shown by chromosomes, and the solution quality is measured using a fitness function. Chromosomes with minimum distance fitness value are selected, and offspring are produced using genetic operators, crossover, and mutation [19; 20]. A new population is formed by replacing individuals with low fitness in the current populations by the newly generated good individuals.

That will be acceptable stopping criterion, such as for termination of GA when a maximum number of generations proceed or a desired level of fitness is reached will be a suitable stopping criterion. GA is the suitable technique to produce near-optimal solution for Kemeny optimal aggregation [7; 18]. Main steps of GA are summarized below:

1. Create a population of random individuals in which each individual represents a possible solution to the problem at hand.

2. Evaluate each individual’s fitness – its ability to solve the specified problem.

3. Select individual population members to be parents.

4. Produce offspring by recombining parent material via crossover and mutation and add them to the population.

5. Evaluate the offspring’s fitness.

6. Repeat steps iii–v until a solution with the desired fitness goal is obtained.

2.7 The Effectiveness of a Ranked List of Recommendation

Normalized discounted cumulative gain (nDCG) is used to evaluate the effectiveness of a ranked list of recommendations [4]. Computation of nDCG requires full ratings, and updating of nDCG for partial ratings is utilized in our work.

For example, if I = {1, 3, 5, 9, 2, 7, 6, 4, 8} is a recommendations list of rank for group and user u test set is {1, 4, 9, 2, 3}, then nDCG is computed on the ranked list {1, 3, 9, 2, 4}.

3.1 Scheme 1

Assuming that a group of n users do not give their preferences for all m items, not all items are present in the list; the rating matrix m*n is generated in which the ith row represents the rating of u_i for i₁, to i_n.

Here, to solve the problem of GRS, generate a group of 15 items for aggregating m chromosomes that tries to satisfy different sets of users optimally.

In view of the limited access of GRS data sets, we have done a test to conduct our experiments on a randomly generated data set that closely relates the characteristics of the information available on the internet sources like MovieLens and GoupLens data sets. Schematic representation of our proposed Scheme 1 is show in Figure 2.

Figure 2:

The Schematic Representation of Our Proposed GRS-GA-PRWOT.

Details of the proposed GRS-GA-PRWOT based on PRWOT are given below:

3.1.2 Fitness Function for PRWOT (Sum-SFD)

Given a partial list τ and a full list σ, the SFD is explained in Table 2 (Example of sum-SFD)

(1) G(σ,τ)=∑i∈τ|σ(i)/σ−τ(i)/|τ||σ=4,1,2,9,7,8,3,5,6,10

Table 2:

Example of Fitness Function (Sum-SFD).

Ranking											SFD
R1	5	–	3	–	–	6	7	–	10	–	3.9
R2	3	–	4	8	–	7	2	–	–	9	1.9
R3	–	8	–	10	–	7	6	–	1	2	4.2
R4	5	–	10	–	–	8	–	3	–	1	4.1
R5	–	–	7	–	8	5	–	2	9	–	3.6
	Total distance (sum-SFD)										17.7

Figure 3:

Representation of Chromosomes.

Our proposed GRS finally recommends the list of items that is the permutation of best chromosome permutation with the minimum SFD.

Encoding

A chromosome for a group of users is simply the permutation of items, i.e. (i₈, i₇, ……………. i₃) which is encoded as (8, 7, ………. 3) representation of chromosomes is shown in Figure 3.

Offspring Generation. The following genetic sequencing operators are employed to generate offspring [18; 20].

Uniform Order-Based Crossover. Explained in Figure 4

Figure 4:

Uniform Order-Based Crossover.

Scramble Sublist Mutation show in Figure 5

Figure 5:

Show Scramble Sublist Mutation.

Selection Criteria. In order to avoid the possibility of crossover or mutation destroying best individuals, elitist approach is used, where top chromosomes are preserved from one generation to the next generation.

3.2 Scheme 2

Here, for solving the problem of GRS is to generate a group of 15 items for aggregating m chromosome that tries to satisfy different sets of users optimally. Movie lens datasets used for Scheme 2.

Details of the proposed GRS-GA-PRWT based on partial rating with ties are given below. Schematic representation of our proposed Scheme 2 is show in Figure 6.

Figure 6:

The Schematic Representation of Our Proposed GRS-GA-PRWT.

3.2.2 Fitness Function for PRWT (Sum-KtD)

Based on these three cases, define k(p), the KtD with penalty parameter p, sum-KTD with bucket order explained in Table 3 as follows:

(2) k(p)(σ,τ)=∑{i,j}∈𝒫k¯i,j(p)(σ,τ).σ=2,4,3,1,5,4,3,5,4,1

Table 3:

Example of Fitness Function (Sum-KtD with Bucket Order).

Ranking											KtD
R1	5	–	3	–	–	4	2	–	5	–	3.5
R2	3	–	4	2	–	5	2	–	–	1	4.5
R3	–	5	–	2	–	1	3	–	1	2	7
R4	5	–	1	–	–	4	–	3	–	1	6.5
R5	–	–	2	–	3	5	–	2	4	–	5.5
	Total distance (sum-KtD)										27

Crossover and Mutation

Here, we have to apply crossover and mutation in full ranking with ties.

Single-Point Crossover

One crossover point is selected randomly; the ranking is copied till this point from the first parent, then the second parent is scanned, and in the offspring it is added. Explained in Figure 7.

Figure 7:

Example of Single-Point Crossover.

Order-Changing Mutation. In this mutation operator two numbers are selected randomly and exchanged with randomly generated numbers between 1 and 10. Explained in Figure 8.

Figure 8:

Example of Order Changing Mutation.

Stopping Criteria for Genetic Algorithm. If there is no improvement in the fitness value after 20 consecutive generations, then evolution process terminates [16].

The Effectiveness of a Ranked List of Recommendations

Let p1, …, pk be a recommended list of items produced by proposed GRSs model. Let u be a user and the actual rating is r_upi for the item pi of the user u ranked in position i, i.e., σ_u(pi) = i. The definitions of nDCG, ideal discounted cumulative gain (IDCG) and discounted cumulative gain (DCG) at rank k are given below:

(3) DCGku=rup1+∑i=2krupilog2(i)

(4) nDCGku=DCGkuIDCGku

where for user u the maximum possible gain value which is IDCG will be the same as DCG that is obtained with the optimal re-order of the k items in p1, …, pk.

4.1 Data Set

For our experiments, we have used both the synthetic data set and real-world MovieLens data set. We have performed experiments for Scheme 1 using synthetic data sets because the type of data required for this Scheme is not publicly available, whereas for Scheme 2 MovieLens data set is used, which contains 12,832 ratings provided by 1043 users for 1682 movies; we generated list of users who have rated at least 12 movies, which provide five random splits (S), S-1, S-2, S-3, S-4, and S-5, where for each split, 20 users were randomly selected as active users. The data sets consist of users’ profiles and their preferences about movies.

Scheme 1: Partial Ranking without Ties (PRWOT).

In order to measure the performance of proposed GRS-GA-PRWOT Scheme with different baseline GRS techniques, our experiments had groups of different sizes (G5, G10, G15, and G20). The evaluation is based on the sum of Spearman foot rule distance (sum-SFD); the smaller the Sum-SFD, the better the proposed model.

Experiment 1. Here sum-SFD is computed for four different group sizes (G5, G10, G15, and G20) across generations. The results shown in Figure 9 clearly indicate that for all the groups of different sizes, GA converges to the near-optimal solution after 500 generations.

Figure 9:

For Different Group Size Variation of Sum-SFD across Generations.

Experiment 2. In this experiment, the proposed GRS-GA-PRWOT is compared with the baseline techniques. The results depicted in Figure 10 clearly demonstrate that our Scheme GRS-GA-PRWOT outperforms several RA techniques given in the chart.

Figure 10:

The Effectiveness of Proposed GRS-GA-PRWOT for Different Group Sizes Compared with Several Techniques.

Experiment 3. Here, the effectiveness of the group recommendation by our proposed Scheme GRS-GA-PRWOT is compared with baseline techniques based on mean nDCG with varying group sizes. Results are shown in Figure 11.

Figure 11:

The Effectiveness of Group Recommendation with Rank Aggregation Techniques.

Scheme 2: Partial Ranking with Ties (PRWT).

In order to measure the performance of proposed GRS-GA-PRWT Scheme with different baseline GRS techniques, we conducted experiments with groups of different sizes (G10, G20, G30, G40, and G50) users and 20 items. The evaluation is based on the Kemeny optimal aggregation with bucket order (sum-KtD); the smaller sum-KtD shows that this technique outperforms several stats of art techniques.

Experiment 1. Here sum-SFD is computed for four different sizes of the group (G10, G20, G30, G40, and G50) across generations. The results shown in Figure 12 clearly indicate that for all the groups of different sizes, GA converges to the near-optimal solution after 500 generations.

Figure 12:

For Different Group Sizes Variation of Sum-KtD across Generations.

Experiment 2. In this experiment, the proposed GRS-GA-PRWT is compared with the baseline techniques. The results depicted in Figure 13 clearly demonstrate that our Scheme GRS-GA-PRWT outperforms Least misery, Most pleasure, Borda count, and Copeland rule.

Figure 13:

The Effectiveness of Proposed GRS-GA-PRWT Compared to Baseline Techniques Based on Different Group Sizes.

Experiment 3. Here, the effectiveness of the group recommendation by our proposed Scheme GRS-GA-PRWT is compared with baseline techniques based on mean nDCG with varying group sizes. Results are shown in Figure 14.

Figure 14:

The Effectiveness of Proposed GRS-GA-PRWT Compared to Baseline Techniques Based on Mean nDCG for Different Group Sizes.