臺灣博碩士論文加值系統

目前許多領域都會運用群體排序資料做不同的應用，例如：群體決策、機器學習、網路搜尋技術…等。這些應用都希望能在已知的群體排序資料中找出一個最有共識的結果，因此，群體排序問題儼然成為一項重要的議題。過去的研究多半試圖利用不同的演算法以產生一個單一的排序結果，並以此做為所謂的群體共識。然而，這類研究縱使遇到群體之間的資料充滿衝突或是共識性很低時，仍然會產生一個排序結果，這樣的方式其實是很不適當的，會誤導決策者一個錯誤的方向。因此，本文提出『最大共識』的觀念，希望能透過我們所提出的演算法，不但可以找出群體間『最大共識』的資料之外，還能指出群體資料衝突之處，這樣才真的可以幫助決策者做進一步的協調與溝通以尋求最後的共識。因此，本文針對使用者提供資訊的完成程度，區分成兩種不同類型的來源資料，一是完整排序資料，另一則是允許使用者提供多個部分排序資料，以此分別提出不同的演算法。另一方面也提出方法找出個人化的排序資料以運用在推薦系統上。這些方法經由一連串的實驗過程(包含人工資料與真實資料)，證明本文所提出的方法不論在效率與效果方面都有不錯的表現。

In the last decade, the problem of getting a consensus group ranking from users’ ranking data has received increased attention due to its widespread applications. Previous research solved this problem by consolidating the opinions of all users, thereby obtaining an ordering list of all items that represent the achieved consensus. The weakness of this approach, however, is that it always produces a ranking list of all items, regardless of how many conflicts exist among users. This work rejects the forced agreement of all items. Instead, we define a new concept, maximum consensus sequences, which are the longest ranking lists of items that agree with the majority and disagree only with the minority. Based on this concept, we use two kinds of input data, individual’s total ranking and individual’s partial rankings, to develop algorithms to discover maximum consensus sequences and also to identify conflict items that need further negotiation. Besides, we propose another algorithm to achieve personalized rankling list which can be used in recommender system. Extensive experiments are carried out using synthetic data sets, and the results indicate that the proposed methods are computationally efficient.

ABSTRACT I
中文摘要 II
誌謝 III
CONTENTS IV
LIST OF FIGURES VI
LIST OF TABLES VIII
CHAPTER 1　INTRODUCTION 1
1.1 MOTIVATION 1
1.2 ORGANIZATION OF THIS DISSERTATION 4
CHAPTER 2　RELATED WORKS 6
2.1. GROUP RANKING PROBLEM 6
2.1.1 Total ranking approach 7
2.1.2 Partial ranking approach 8
2.2. SEQUENTIAL PATTERN MINING 8
2.3. PERSONALIZED RANKING LIST 9
CHAPTER 3　MINING MAXIMUM CONSENSUS SEQUENCES FROM INDIVIDUAL''S TOTAL RANKING 11
3.1 RESEARCH PROBLEM 11
3.2 METHODOLOGY 16
3.2.1 The MCS Algorithm 16
3.2.2 The MCS-2 Algorithm 22
3.3 EXPERIMENTS 28
3.3.1 The first experiment 28
3.3.1.1 Synthetic data generation 28
3.3.1.2 Run time comparisons and pattern comparisons 29
3.3.1.3 Scalability 34
3.3.2 Real case analyses 35
3.3.2.1. Data collection 35
3.3.2.2. Mining results 36
3.4 DISCUSSION 38
3.4.1 Discovered sequences 39
3.4.2 Decision process demonstration 40
3.5 SUMMARY 42
CHAPTER 4　MINING MAXIMUM CONSENSUS SEQUENCES FROM INDIVIDUAL''S PARTIAL RANKING 43
4.1 MOTIVATION 43
4.2 RESEARCH PROBLEM 44
4.3. METHODOLOGY 50
4.3.1. The MCSP algorithm 50
4.3.2. Candidates generation and counting supports 54
4.4. SIMULATION RESULTS 58
4.4.1 Synthetic data generation 58
4.4.2 Run time comparisons and pattern comparisons 59
4.4.2.1 Effect of the maximum conflict support 60
4.4.2.2 Effect of the minimum comply support 61
4.4.2.3 Effect of the number of patterns discovered 63
4.4.3 Scalability 65
4.5. SUMMARY 66
CHAPTER 5　 PERSONALIZED RANKING LIST MINING 68
5.1 MOTIVATION 68
5.2 PROBLEM DESCRIPTION 70
5.3 METHODOLOGY 73
5.4 SIMULATION EVALUATION 82
5.4.1. Data collection 82
5.4.2. Simulation design 82
5.4.3. Simulation results 83
5.4.3.1. Effect of the missing rate 83
5.4.3.2. Effect of the number of similar users 84
5.4.3.3. Effect of the number of users in the database 86
5.5 SUMMARY 87
CHAPTER 6　CONCLUSIONS AND FUTURE WORKS 89
REFERENCES 91

[1]G.Adomavicius, A. Tuzhilin, Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions, IEEE Transactions on Knowledge and Data Engineering 17(6) (2005) 734-749.
[2]S. Antonie, A. P. D.Silva, Stochastic judgments in the AHP: The measurement of rank reversal probabilities, Decision Sciences 28(3) (1997) 655.
[3]J. Bartholdi, C. A. Tovey, M. A. Trick, Voting schemes for which it can be difficult to tell who won the election, Social Choice and Welfare 6(2) (1989)157-165.
[4]M. Balabanovic, and Y. Shoham, Fab: Content-based, collaborative recommendation, Communications of the ACM 40(3) (1997) 66-72.
[5]M. M. S. Beg, N. Ahmad, Soft computing techniques for rank aggregation on the World Wide Web, World Wide Web-Internet and Web Information Systems 6(1) (2003) 5-22.
[6]K. Bogart, Preference structures I: Distances between transitive preference relations, Journal of Math Sociology 3 (1973) 49-67.
[7]K. Bogart, Preference Structures II: Distances Between Asymmetric Relations, SIAM Journal of Applied Math 29(2) (1975) 254-265.
[8]J.C. Borda, Memoire sur les elections au scrutin, Histoire de l Academie Royale de Science, 1981, Paris.
[9]J. S. Breese, D. Heckerman, C. Kadi . Empirical analysis of predictive algorithms for collaborative filtering. In: Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, Madison, 1998, 43-52.
[10]W. Cohen, Learning to order things, The journal of artificial intelligence research, 10 (1999)243.
[11]W. D. Cook, Distance-based and ad hoc consensus models in ordinal preference ranking. European Journal of Operational Research 172(2) (2006) 369-385.
[12]W. D. Cook, B. Golany, M. Kress, M. Penn, T. Raviv, Optimal Allocation of Proposals to Reviewers to Facilitate Effective Ranking, Management Science 51(4) (2005) 655-661.
[13]W. D. Cook, B. Golany, M. Kress, M. Penn, T. Raviv, Creating a Consensus Ranking of Proposals from Reviewer''s Partial Ordinal Rankings. Computers & OR 34(4) (2007) 954-965.
[14]W. D. Cook, M. Kress, M. Seiford, L. M., An Axiomatic Approach to Distance on Partial Orders, Revue Automatique, Informatique et Recherche Operationnelle 20(2) (1986) 115-122.
[15]W. D. Cook, M. Kress, L., Seiford, Information and Preference in Partial Orders: A Bimatrix Representation, Psychometrika 51(2) (1986) 197-207.
[16]W. D. Cook, M., Kress, L., Seiford, A general framework for distance-based consensus in ordinal ranking models, European Journal of Operational Research 96 (1996)392-397.
[17]R. Fagin, R.Kumar, D.Sivakumar, Efficient similarity search and classification via rank aggregation. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, San Diego, California: ACM, pp. 301-312, 2003..
[18]B.Golden, The Analytic Hierarchy Process: Applications and Studies. New York NY: Springer, 1989.
[19]J. Gonzalez-Pachon, C. Romero, Aggregation of partial ordinal rankings: an interval goal programming approach. Computers and Operations Research 28(8) (2001) 827-834.
[20]S. Greco, V. Mousseau, R. Slowinski, Ordinal regression revisited: multiple criteria ranking with a set of additive value functions, European Journal of Operational Research (2007), doi:10.1016/j.ejor.2007.08.013.
[21]J. L. Herlocker, , J. A. Konstan, et al., Evaluating collaborative filtering recommender systems, ACM Transactions on Information Systems, 22(1):(2004)5-53.
[22]D. S. Hochbaum, A. Levin, Methodologies and algorithms for group-rankings decision, Management Science 52(9) (2006) 1394-1408.
[23]T. Hofmann, Latent semantic models for collaborative filtering. ACM Transactions on Information Systems, 22(1) (2004),89-115.
[24]T. Kamishima, Nantonac collaborative filtering: Recommendation based on order responses, In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, Washington, DC, USA, 2003, pp. 583–588.
[25]J. G. Kemeny, L. J. Snell, Preference Ranking: An Axiomatic Approach, In: Proceedings of Mathematical Models in the Social Science (1962) 9–23.
[26]M. Kendall, Rank Correlation Methods, third ed., Hafner, New York, 1955.
[27]H. S. Lewis, T. W. Butler, An interactive framework for multi-person, multiobjective decisions, Decision Sciences 24(1) (1993).
[28]G. Linden, B. Smith, J. York, Amazon.com recommendation Item-to-item collaborative filtering, IEEE Internet Computing, 7(1), (2003)76-80.
[29]P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom ,J. Riedl, GroupLens: An open architecture for collaborative filtering of netnews.In: Proceedings of ACM Conference on Computer-Supported Cooperative Work, 1994,175-186.
[30]F. D. Robert, H. F. Ernest, Group decision support with the analytic hierarchy process. Decision Support System 8(2) (1992) 99-124.
[31]T. L. Saaty, Rank Generation, Preservation, and Reversal in the Analytic Hierarchy Decision Process, Decision Sciences 18(2) (1987) 157.
[32]S.Saint, J. R.Lawson, Rules for Reaching Consensus: A Modern Approach to Decision Making, Pfeiffer & Company (1994).
[33]B.Sarwar, G. Karypis, J. Konstan, J. Riedl, Item-based collaborative filtering recommendation algorithms, In: Proceedings of the 10th international conference on World Wide Web, 2001, 285-295.
[34]R. Srikant, R. Agrawal, Mining sequential patterns: Generalizations and performance improvements. In: Proceedings of the Fifth Int''l Conference on Extending Database Technology (EDBT). Avignon, France, (1996).
[35]O. S. Vaidya, S.Kumar, Analytic hierarchy process: An overview of applications. European Journal of Operational Research 169(1) (2006) 1-29.