Y Jiang et al. / Decision Support Systems 48(2010)470-479 Need- rating data composed of customers'needs, preferences, personal profile and ratings about the Mine need-rating rules and retain useful 2Organize all rules into a set of classification Imulti-class information xperts, with conflicting rules being in one expert 3 Prune redund 4 Calculate the weights of evidence bodies using Measure the importance of need-rating rules K nthe neural network approach 5 Find the necessary classification experts for the potential customer's ratings 6 Apply the integrated strategy to predict ratings of the potential customers General phases The proposed algorithm Fig. 2. The proposed rating classification framework. In data table L customers are described by customer characteristics, Ri consists of all the need-rating rules which have the same pre- preferences, and ratings for the product. For example, a middle-aged condition but different ratings. That is, it includes all the multi-class customer who prefers a laptop with average central processing unit(CPU) information associated with Pim. For convenience, we rewrite Ri as: peed, good battery life, and rates the laptop Inspiron a good R:P→E, where product can be described as follows: (Age= Midle A' cPU= Average'A'Battery =Good,)A 'Rating Good. P=Pum: E-G, 1. on/ 1 )V-vI(Gum, con/um)V-VI(GLIRAI, COn/ 1R )v(B, conte) The rule mining algorithm first scans the data table once to mine confum is the confidence degree of Pim=CLm, which is larger than the need-rating rules involving one attribute in rule preconditions. It then minimal confidence threshold, and e is the frame of discernment recursively combines the need-rating rules generated to extract rules defined in the evidence theory. The confi e is the belief degree assigned involving more attributes. The support and confidence degrees forrul to catchall(default) terms since they cannot be classified to any spe- are calculated simultaneously. Any rules with support and confidence cific ratings by rules in R. degrees larger than the threshold are saved as need-rating rules For example,P1→c;P1→c2andP1→c3 are three conflicting rules with the same precondition. Their confidence degrees are 49%, 43%, and 8% confi e=1-2 confi.m respectively. If the minimal confidence threshold is 40%, then rules P1→C1andP1→c2 would be retained, whereas p1→c3 is pruned. After a comprehensive set of rules are mined, the redundant ones In evidence theory, evidence bodies are given by experts and are deleted. The proposed prune process eliminates redundancy to consist of hypothesis-probability pairs. For example, the evidence ensure that succinct need-rating rules are derived, and all necessary body may look like: (Good, 0.6), (Average, 0.3).(poor, 0.1). In the multi-class information is preserved experts opinion, the probability of receiving a good evaluation is 60% an average evaluation is 30%, and a poor evaluation is 10%. Recall that 3.2. 1. Derivation of classification experts confim can be treated as a belief degree given by expert R to a hypo- Let r be the set of need-rating rules discovered from data table l: thesized rating Cum, based on observed attribute values in P. Therefore, Ei is regarded as the evidence body provided by classification expert R R={P1→C1,-,Pa→ca-,PR→c1 The set of need-rating rules is transformed into a set of classi fication experts, R=[RI.Rm. R.. Rr), which satisfy the following where R is the number of rules in R Precondition Pa consists of the constraints attribute-values in data table l, and result ca is the corresponding rating. For any subset R of the rule setR, Ri= r R1={B1→C1,-,Pm→Cm,P1→c1} (2) RnR =p, for any i and j, i*j. where Ril is the number of rules in R Pim-Cum is the mth rule in R. R is a classification expert in the rating classification problem if the fol- The set of evidence bodies corresponding to R is denoted as E lowing constraints are satisfied E…,E…,E1……ErJ. To this point, we have transformed all the need rating rules into T independent classification experts. However, not all (1)P1=-=Pm=-PR classification experts are necessary for the recommendation system; For any other rules(Pa→cd)∈R,P≠Pm some are redundant. In the next subsection, we develop pruning i≠-≠Cm≠-≠CR methods to remove the redundant classification experts.In data table I, customers are described by customer characteristics, preferences, and ratings for the product. For example, a middle-aged customer who prefers a laptop with average central processing unit (CPU) speed, good battery life, and rates the laptop Inspiron 1525 as a good product can be described as follows: ð 0 Age = Middle0 ∧ 0 CPU = Average0 ∧ 0 Battery = Good0 Þ ∧ 0 Rating = Good0 : The rule mining algorithm first scans the data table once to mine need-rating rules involving one attribute in rule preconditions. It then recursively combines the need-rating rules generated to extract rules involving more attributes. The support and confidence degrees for rules are calculated simultaneously. Any rules with support and confidence degrees larger than the threshold are saved as need-rating rules. For example, P1→c1, P1→c2, and P1→c3 are three conflicting rules with the same precondition. Their confidence degrees are 49%, 43%, and 8%, respectively. If the minimal confidence threshold is 40%, then rules P1→c1 and P1→c2 would be retained, whereas P1→c3 is pruned. After a comprehensive set of rules are mined, the redundant ones are deleted. The proposed prune process eliminates redundancy to ensure that succinct need-rating rules are derived, and all necessary multi-class information is preserved. 3.2.1. Derivation of classification experts Let R be the set of need-rating rules discovered from data table I: R = fP1→c1; ⋯; Pd→cd; ⋯; Pj Rj→cj Rj g where |R| is the number of rules in R. Precondition Pd consists of the attribute-values in data table I, and result cd is the corresponding rating. For any subset Ri of the rule set R, Ri = fPi;1→ci;1; ⋯; Pi;m→ci;m; ⋯; Pi; j Ri j→ci; j Ri j g where |Ri| is the number of rules in Ri, Pi,m→ci,m is the mth rule in Ri. Ri is a classification expert in the rating classification problem if the fol￾lowing constraints are satisfied: (1) Pi,1=⋯=Pi,m=⋯Pi,|Ri | (2) For any other rules (Pd→cd)∉Ri, Pd≠Pi,m (3) ci,1≠⋯≠ci,m≠⋯≠ci,|Ri |. Ri consists of all the need-rating rules which have the same pre￾condition but different ratings. That is, it includes all the multi-class information associated with Pi,m. For convenience, we rewrite Ri as: Ri: Pi→Ei, where Pi = Pi;m; Ei = ðci;1; confi;1Þ∨⋯∨ðci;m; confi;mÞ∨⋯∨ðci; jRi j ; confi; j Ri j Þ∨ðΘ; confi;Θ Þ confi,m is the confidence degree of Pi,m→ci,m, which is larger than the minimal confidence threshold, and Θ is the frame of discernment defined in the evidence theory. The confi,Θ is the belief degree assigned to catchall (default) terms since they cannot be classified to any spe￾cific ratings by rules in Ri: confi;Θ = 1− ∑ jRi j m= 1 confi;m In evidence theory, evidence bodies are given by experts and consist of hypothesis–probability pairs. For example, the evidence body may look like: {(Good, 0.6), (Average, 0.3), (poor, 0.1)}. In the expert's opinion, the probability of receiving a good evaluation is 60%, an average evaluation is 30%, and a poor evaluation is 10%. Recall that confi,m can be treated as a belief degree given by expert Ri to a hypo￾thesized rating ci,m, based on observed attribute values in Pi. Therefore, Ei is regarded as the evidence body provided by classification expert Ri. The set of need-rating rules is transformed into a set of classi- fication experts, R={R1,…,Ri,…, Rj,…, RT}, which satisfy the following constraints: (1) ∪ T i= 1 Ri = R (2) Ri∩Rj = φ, for any i and j, i≠j. The set of evidence bodies corresponding to R is denoted as E= {E1,…,Ei,…, Ej,…, ET}. To this point, we have transformed all the need￾rating rules into T independent classification experts. However, not all classification experts are necessary for the recommendation system; some are redundant. In the next subsection, we develop pruning methods to remove the redundant classification experts. Fig. 2. The proposed rating classification framework. Y. Jiang et al. / Decision Support Systems 48 (2010) 470–479 473