| With the rapid growth of web-based applications, mining personalized preferencesfor promotion becomes a hot topic. In this thesis, we focus on two problems related touser preferences: understanding user preferences and utilizing user preferences. In understanding user preferences, we propose two sub-problems when we considertemporal user preferences. The first sub-problem is called a?ttribute-based s?ubsequence m?atching (ASM) : given a query sequence and a set of sequences, considering the attributesof elements, we want to find all the sequences which are matched by this querysequence. We propose an efficient algorithm for problem ASM by applying the ChineseRemainder Theorem. The second sub-problem is to find all the attribute-basedfrequent subsequences. We adapt an existing efficient algorithm for this second sub-problemto show that we can use the algorithm developed for the first sub-problem.Experimental results show that frequent subsequences reflect user preferences, and ouralgorithms are scalable in large datasets. This work can stimulate a lot of existing datamining problems which are fundamentally based on subsequence matching. In utilizing user preferences, we identify and tackle three sub-problems, findingtop-k profitable products, finding top-k popular products, and finding K-dominatingcompetitive price. The former two sub-problems are about designing new products, while the latter one is about pricing new products. In finding top-k profitable products, we consider generalized user preferences, derivedfrom the skyline concept. We propose a dynamic programming approach whichcan find the optimal solution when there are two attributes to be considered. We showthat this problem is NP-hard when there are more than two attributes. Two greedy algorithmsare proposed and one of them has theoretical bounds. We also consider thisproblem on dynamic datasets and propose update algorithms for different update operations.We extend this problem by considering another form of customer preferences,namely tolerant customer preferences in finding top-k popular products. We prove thatthis problem is NP-hard and propose a 0.63-approximate algorithm for this problem.Extensive experiments show the effectiveness and efficiency of our approaches on bothsynthetic and real datasets. In finding K-dominating competitive price in which we consider generalized userpreferences only, we propose an efficient algorithm. We utilize spatial properties forpruning to speed up our algorithm. An extensive performance study using both syntheticand real datasets is reported to verify its effectiveness and efficiency. We alsoprovide a real case study to show how our algorithm works in reality. |
