升級缺乏競爭力產品之最大化潛在客戶數

Upgrading Uncompetitive Products to Maximize the Number of Potential Customers

蕭鈺翰(Yu-Han Hsiao)

指導教授 ： 陳良弼

國立清華大學/電機資訊學院/資訊工程學系/碩士(2013年)

https://doi.org/10.6843/NTHU.2013.00048

摘要

近年來已經有很多解決天際線問題的方法被提出。從市場的觀點來看，支配的概念有助於選擇具競爭力的產品。廠商可能會想要在一筆有限的預算下更新一些不具競爭力的產品，並獲得最多的潛在客戶數。在這篇論文中我們嘗試解決一個新的問題在於這些不具競爭力的產品之中更新他們成為不被現存產品所支配並得到最大的潛在客戶數。給了兩組資料集A和P以及一個有限的預算M，而A中為不具競爭力的產品集合，P中為具有競爭力的產品集合；我們將從P中挑選出一些產品能夠更新成為不被A中產品所支配的產品並且更新後的產品能得到最大的潛在客戶數。我們提出了近似的演算法建置在一個能夠群集相似的點有趣的資料結構以及能夠排除更新花費較大的產品上。我們在實驗部分做三組不同分布的造資料集以及一組實際資料集。實驗結果顯示近似的方法能夠比基本的算法更有效率且在也有不錯的精確度。

關鍵字

天際線 ； 支配 ； 最大化 ； 潛在客戶 ； 更新

並列摘要

Recently, many approaches on solving the skyline problems have been proposed. From the perspective of marketing, the domination concept is conducive to choose the competitive products. A product provider may want to know which uncompetitive products can be upgraded to gain much more potential customers under a limited budget. In this paper, we make the first attempt to address a new problem on upgrading uncompetitive products to maximize the number of potential customers, which returns a set of products that are not dominated by any existing products and maximize the number of potential customers. Given two data sets A and P, the former represents a set of competitive products while the latter represents a set of uncompetitive products waiting for being upgraded, and a limited budget of M, we return some products in P that are upgraded to avoid being dominated by any products in A under the condition of M and these products can maximize the number of potential customers. We propose an approximate algorithm based on an interesting index structure to group together the similar products and prune the other products that may cost too much. A series of experiments on a real dataset and three synthetic datasets are performed. The experiment results show that the approximate method is more efficient than a basic method and also has a good accurate rate.

並列關鍵字

skyline ； dominate ； maximize ； potential customer ； upgrade

參考文獻

[DS07] Evangelos Dellis, Bernhard Seeger: Efficient Computation of Reverse Skyline Queries. In: VLDB 2007, pp.291- 302.

[BKS01] Börzsönyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: ICDE 2001, pp.421- 430.

[CCA09] P. Cortez, A. Cerdeira, F. Almeida, T. Matos, and J. Reis. Modeling wine preferences by data mining from physicochemical properties. In: DSS 2009, pp.547- 553.

[CGG03] Chomicki, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with presorting. In: ICDE 2003, pp.717- 816.

[HC12] Hua Lu, Christian S. Jensen: Upgrading Uncompetitive Products Economically. In: ICDE 2012, pp.977- 988.