尋找目標類別的案例是資料探勘主要應用之一。例如，在直效行銷應用中，行銷人員為提高商品銷售回應率，需精準篩選目標客戶。在過去，我們常以決策樹,邏輯斯回歸,類神經網路等演算法建構回應模型，以作為直效行銷挑選目標客戶之依據。本研究提出利用關聯式分類對潛在客戶評分，來建構比這些傳統演算法更準確的分類系統。此外，為了避免分類系統針對過大潛在客戶範圍或回應率過低客戶群體進行評分，本研究也提出以聯集時序規則挑選最佳之潛在客戶範圍，建立顧客回應模型。
在關聯式分類方面，過去這個領域的研究主要著重在類別分類器開發，對於直效行銷應用所需之機率分類器較少探討。本研究提出以下三個演算法來建構機率分類器，以便利用關聯式分類提昇直效行銷之成效：
1.基於關聯規則的機率修剪法(probabilistic classification based on associations, PCBA)：基於關聯規則評分演算法(scoring Based on Associations, SBA) [45]是利用悲觀錯誤率修剪法(pessimistic error Pruning, PEP) [54]修剪規則，容易使得評分時因規則間之滿足案例高度重疊，造成錯估測試(新)案例正例之可能性。本研究提出PCBA修剪演算法，以調整SBA演算法解決上述問題。PCBA是修改自CBA使其能夠建構機率分類器，步驟如下：首先，該修剪法利用減少多數類別抽樣法(under-sampling)調高信賴度(confidence)以提升CBA正例規則之排名。再者，依各類別比例設定不同門檻值。最後，移除CBA以總錯誤率最低修剪規則之相關步驟。
2.基於關聯規則的機率分類器(Probabilistic Classification based on Association Rules, PCAR)：由於修正後SBA仍採用加權評分方式，不僅低估了高信賴度且超過最小支持度規則之重要性，也損失了關聯式分類易於解讀稀有事件之特性。因此，本研究再提出PCAR以解決此問題。此演算法是藉由修改CBA演算法之排序準則,規則修剪方法與評分方式而產生。CBA經由此修正將可被一般化到可以建構機率分類器，並精進關聯式分類預測稀有事件之效能。
3.基於貪婪法的關聯式分類法(Associative Classification base Greedy Method, ACGM)：PCAR最大限制在於需耗費相當多時間來找尋誤差抽樣比例之最佳解，本研究最後提出ACGM解決此問題。ACGM在修剪規則前不需像傳統演算法以排序準則對規則作排序，而是藉由重覆取出命中率最大之規則，並更新剩餘案例與剩餘規則之命中率方式完成規則修剪。
在聯集時序規則方面，過去研究幾乎都是以整個母體的客戶或者是依業務專家建議，選擇滿足某些屬性水準的客戶，作為回應模型的預測對象。但是，這樣的作法極有可能因選定的潛在客戶範圍過大，或者選到客戶群體回應率過低，導致預測模型精確度降低。因此，本研究提出一套結合聯集時序規則 (Union Sequential Patterns)與分類演算法的機制，以協助我們建立顧客回應模型。透過此機制，我們可以先利用聯集時序規則找出關聯強度較高的屬性水準作為潛在客戶範圍，然後再針對滿足該範圍客戶，利用支援向量機(support vector machines)與邏輯斯回歸(logistic regression)等分類演算法建立預測模式。如此，可以解決潛在客戶範圍設定之問題，同時也因縮小預測的客戶範圍,節省潛在客戶名單產生的時間。
我們也將本架構的演算法與現有廣為被接受的演算法加以比較，並且以UCI之基礎資料集及台灣某電信公司真實資料集進行一系列的實驗，來評估這些演算法的效率與性能。實驗結果顯示如下：
1.修正後SBA不僅優於C5.0與原始SBA，而且評分所需規則數也明顯變少。
2.PCAR對於所有案例其預測表現均優於先前關聯式分類演算法與C5.0，且在部分案例的預測表現甚至優於邏輯斯回歸與類神經網路。
3.ACGM之預測表現均優於PCAR與傳統分類演算法(C5.0,邏輯斯回歸與類神經網路)，且因此新演算法有提供規則過濾功能，使得規則修剪時間明顯比PCAR短。
4.經由聯集時序規則挑選之潛在客戶範圍所建立之預測模型的準確度，均顯著高於傳統以全部母體為客戶範圍所建立之預測模型的準確度。

In many data mining applications, the objective is to select data cases of a target class. For example, in direct marketing, marketers may want to focus on likely buyers of a particular product for promotion. In the past, we would use algorithms of decision trees, logistic regression and neural networks to construct a response model as the basis for targeting customers in direct marketing. This study proposes using associative classification to score potential customers when constructing a classification system that is much more accurate than the ones built with traditional algorithms. In addition, to have the classification system avoid scoring on an oversized scope of potential customers or on a low response customer base, this study also proposes to use the union sequential pattern to select the optimal scope of potential customers in building a customer response model.
In the aspect of associative classification, past studies in this field have focused on the development of class classifier, while the probability classifier needed in direct marketing was rarely touched upon. This study proposes three algorithms to construct the probability classifier so as to use associative classification to improve the direct marketing outcome. The three algorithms are:
1.Probabilistic Classification Based on Associations (PCBA)： SBA algorithm prunes rules by pessimistic error pruning (PEP) (Quinlan, 1992), and so many overlapping data cases that satisfy rules, raising the possibility of misevaluation in the scoring of a test set. This work attempts to solve the problem by adapting the scoring based on the associations (SBA) algorithm. The SBA algorithm is modified by coupling it with the pruning strategy of association rules in the PCBA algorithm, which is adjusted from the CBA for use in the structure of the probability classifier. PCBA is adjusted by increasing the confidence of under-sampling, setting different minimum supports (minsups) and minimum confidences (minconfs) for rules of different classes based on each type of distribution, and removing the pruning rules of the lowest error rate.
2.Probabilistic Classification based on Association Rules (PCAR)：Due to the adapting SBA still uses the weighted scoring method, this not only underestimates high confidence values and the importance of rules that exceed minsup, but also eliminates the ability of associative classification in order to interpret rare events easily. Consequently, this study proposes another new algorithm PCAR, aimed at solving the underlying problems. The algorithm is based on modifying the rule sorting index, the pruning method, and the scoring procedure in the CBA algorithm. CBA can be generalized so to construct a probability classifier and additionally, it can improve the efficiency of associative classification for predicting imbalanced data.
3.Associative Classification base Greedy Method (ACGM)：PCAR is limited mainly in that this algorithm must spend an excessive amount of time to obtain the optimum solution of an under-sampled ratio. Accordingly, this study proposes ACGM to solve the problem. The proposed method differs from conventional algorithms in that rather than pruning rules after sorting rules with sorting standards, ACGM prunes rules by selecting the rule with the largest hit rate and updating repetitively the remaining cases and hit rates of the remaining rules.
In regards to the union sequential pattern, previous studies largely adopt the approach that, as the subjects for response model predictions, the entire customer population is filtered through certain attribute values based on recommendations made from sales professionals. However, such methods may reduce response rates due to an oversized potential customer population, thus diminishing the accuracy of the prediction model. To resolve this problem, this work proposes a novel forecasting method that integrates the union sequential pattern with classification algorithms to facilitate the construction of customer response models. Based on the use of a union sequential pattern, the potential customer size is established by identifying attributes with a high level of association. The prediction model is then constructed using classification algorithms such as support vector machines and logistic regression. Consequently, the problem involving the setting of a range for potential customers can be solved, as well as the time spent on processing extended lists of customers during prediction.
We have also compared the algorithm of this framework with existing widely accepted algorithms, and used benchmark datasets and real-life application datasets of a telecom company to conduct a series of experiments to evaluate the efficiencies and performance of these algorithms. The experiment results show as follows:
1.Adapting SBA performs better than C5.0 and the original SBA do, and the number of rules required for scoring is significantly reduced.
2.PCAR outperforms the previous associative classification algorithm and C5.0 for all datasets. Also, in some datasets, the predictive performance exceeds that achieved by logistic regression and the use of a neural network.
3.ACGM algorithm performs better than PCAR and conventionally adopted classification algorithms, such as C5.0, logistic regression classification, and neural network classification. The proposed algorithm also spends less time in pruning rules than PCAR does owing to its rule-filtering feature.
4.The accuracy of the prediction model built with the potential customer scope selected with the union sequential pattern is clearly higher than that of the traditionally built models which take entire objects as the customer scope.

References
[1] R. Agrawal, T. Imielinski, and A. Swami, “Mining Association Rules between Sets of Items in Large Databases,” Proc. ACM SIGMOD Int"l Conf. Management of Data, pp. 207-216, 1993.
[2] R. Agrawal, and R. Srikant, “Fast Algorithms for Mining Association Rules,” Proc. 1994 Int'l Conf. Very Large Data Bases, pp. 487-499, 1994.
[3] R. Agrawal and R. Srikant, "Mining Sequential Patterns," Proceedings of the Eleventh International Conference on Data Engineering, pp. 3-14, 1995.
[4] J. Ahn, S. Han, and Y. Lee, "Customer Churn Analysis: Churn Determinants and Mediation Effects of Partial Defection in the Korean Mobile Telecommunications Service Industry," Telecommunications Policy, vol. 30, no.10-11, pp. 552-568, 2006.
[5] E. Baralis, S. Chiusano, and P. Garza, “A Lazy Approach to Associative Classification,” IEEE Trans. Knowledge and Data Eng., vol. 20, no. 2, pp. 156-171, 2008.
[6] R. Bayardo, R. Agrawal, and D. Gunopulos, “Constraint-Based Rule Mining in Large, Dense Databases,” Proceedings of IEEE International Conference on Data Engineering, pp. 188-197, 1999.
[7] C. Blake and C. Merz, “UCI Repository of Machine Learning Databases,” Univ. of California Irvine, http://www.ics.uci.edu/~mlearn/MLRepository.html, 1998.
[8] I. Bose, and X. Chen, "Quantitative Models for Direct Marketing: A Review from Systems Perspective," European Journal of Operational Research , vol. 195, no. 1, pp. 1-16, 2009.
[9] C. E. Brodley, and M. A. Friedl, “Identifying and Eliminating Mislabeled Training Instances,” Proceeding of Thirteenth National Conference on Artificial Intelligence, AAAI Press, 1996.
[10] J. R Bult, and T. J Wansbeek, ”Optimal Selection for Direct Mail,” Marketing Science, vol. 14, pp. 378-394, 1993.
[11] J. Burez, and D. Van den Poel, “Handling Class Imbalance in Customer Churn Prediction,” Expert Systems with Applications, vol. 36, no. 3, pp. 4626-4636, 2009.
[12] P. K. Chan, and S. J. Stolfo, “Toward Scalable Learning with Non-Uniform Class and Cost Distributions: A Case Study in Credit Card Fraud Detection,” Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, pp. 164-168, 2001.
[13] P. Chapman, J. Clinton, R. Kerber, T. Khabaza, T. Reinartz, C. Shearer, and R. Wirth, “CRISP-DM 1.0 Step-by-step Data Mining Guide,” SPSS Inc, 2000.
[14] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, “SMOTE: Synthetic Minority Over-Sampling Technique,” Journal of Artificial Intelligence Research vol. 16, pp. 321–357, 2002.
[15] C. Chen, A. Liaw, and L. Breiman, “Using Random Forests to Learn Imbalanced Data,” Technical Report 666, Statistics Department, University of California at Berkeley, 2004.
[16] T. C. Chen, and H. L. Tsao, "Using a Hybrid Meta-Evolutionary Rule Mining Approach as a Classification Response Model," Expert Systems with Applications, vol. 36, no. 2, pp. 1999-2007, 2009.
[17] F. Coenen, “LUCS-KDD DN Software,” Univ. of Liverpool, http://www.csc.liv.ac.uk/~frans/KDD/Software/LUCS_KDD_DN/, 2003.
[18] F. Coenen, G. Swinnen, K. Vanhoof, and G. Wets, “The Improvement of Response Modeling: Combining Rule-Induction and Case-Based Reasoning,” Expert Systems with Application, Vol. 18, no. 4, pp. 307-313, 2000.
[19] E. R. DeLong, D. M. DeLong, and D. L. Clarke-Pearson, “Comparing the Areas under Two or More Correlated Receiver Operating Characteristic Curves: A Nonparametric Approach,” Biometrics, vol. 44, no. 3, pp. 837–845, 1988.
[20] P. Domingos, “Knowledge Discovery Vie Multiple Methods,” IDA, Amsterdam: Elsevier, 1997.
[21] P. Domingos, “Multimodal Inductive Reasoning: Combining Rule-Based and Case-Based Learning,” Multimodal Reasoning, AAAI Press, 1998.
[22] G. Dong, X. Zhang, L. Wong, and J. Li, “CAEP: Classification by Aggregating Emerging Patterns,” Proc. Second Int’l Conf. Discovery Science, pp. 30–42, 1999.
[23] C. Drummond, and R.C. Holte, C4.5, “Class Imbalance, and Cost Sensitivity: Why Under-Sampling Beats Over-Sampling,” Workshop on Learning from Imbalanced Data Sets II, International Conference on Machine Learning, 2003.
[24] T. Fawcett, “An Introduction to ROC Analysis,” Pattern Recognition Letters, vol. 27, no. 8, pp. 861-874, 2006.
[25] C. Frothinger, "Results Oriented Direct Marketing," Bank Marketing, vol. 6, pp. 24-28, 1993.
[26] J. W. Grzymala-Busse, Z. L. Zheng, K. Goodwin, and W. J. Grzymala-Busse, “An Approach to Imbalanced Data Sets Based on Changing Rule Strength,” Proceedings of the AAAI Workshop, AAAI Press Technical Report WS-00-05, pp. 69-74, 2000.
[27] S. Gupta, D. Hanssens, B. Hardie, W. Kahn, V. Kumar, N. Lin, N. Ravishanker, and S. Sriram, “Modeling Customer Lifetime Value,” Journal of Service Research, vol. 9, no. 2, pp. 139–155, 2006.
[28] D. J. Hand, and R. J. Till, “A Simple Generalization of the Area Under the ROC Curve to Multiple Class Classification Problems,” Machine Learning, vol. 45, no. 2, pp. 171–186, 2001.
[29] D. Haughton, and S. Oulabi, ”Direct Marketing Modeling with CART and CHAID,” Journal of Direct Marketing, vol. 7, pp. 16-26, 1993.
[30] C. M. Heilman, F. Kaefer, and S. D. Ramenofsky, “Determining the Appropriate Amount of Data for Classifying Customers for Direct Marketing Purposes,” Journal of Interactive Marketing, vol. 17, no. 3, pp. 5–28, 2003.
[31] A. M. Hughes, “The Complete Database Marketer,” Chicago, Ill.: Irwin Professional, 1996.
[32] S. Y. Hung, D. C. Yen, and H. Y. Wang, "Applying Data Mining to Telecom Churn Management," Expert Systems with Applications, vol. 31, no. 3, pp. 515-524, 2006.
[33] D. Janssens, G. Wets, T. Brijs, and K. Vanhoof, “Adapting the CBA Algorithm by means of Intensity of Implication,” Information Sciences, vol. 173, no. 4, pp. 305-318, 2005.
[34] Y. Jiang, J. Shang, and Y. Liu, “Maximizing Customer Satisfaction through an Online Recommendation System: A Novel Associative Classification Model,” Decision Support Systems, vol. 48, no. 3, pp. 470-479, 2010.
[35] Y. Lan, D. Janssens, G. Chen, and G. Wets, “Improving Associative Classification by Incorporating Novel Interestingness Measures,” Expert Systems with Applications, vol. 31, no. 1, pp. 184-192, 2006.
[36] R.C.T .Lee, R.C. Chang, S.S. Tseng, and Y.T. Tsai, Introduction to the Design and Analysis of Algorithms : A Strategic Approach, McGraw-Hill, 2005.
[37] W. Li, J. Han, and J. Pei, “CMAR: Accurate and Efficient Classification Based on Multiple-Class Association Rules,” Proc. Int’l Conf. Data Mining, pp. 369-376, 2001.
[38] C. Ling, and C. Li, “Data Mining for Direct Marketing: Problems and Solutions,” Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-98), pp. 73–79, 1998.
[39] H. Y. Liu, J. Chen, and G. Chen, “Mining Insightful Classification Rules Directly and Efficiently,” Proceedings of the 1999 IEEE International Conference on Systems Man and Cybernetics, pp. 911–916, 1999.
[40] B. Liu, W. Hsu, and Y. Ma, “Integrating Classification and Association Rule Mining,” Proc. Fourth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining, pp. 80-86, 1998.
[41] D. Kim, H. Lee, and S. Cho, "Response Modeling with Support Vector Regression," Expert Systems with Applications, vol. 34, no. 2, pp. 1102-1108, 2008.
[42] Y. S. Kim, and W. N. Street, “An Intelligent System for Customer Targeting: A Data Mining Approach,” Decision Support Systems, vol. 37, no. 2, pp. 215–228, 2004.
[43] M. Kubat, R. C. Holte, and S. Matwin, “Machine Learning for the Detection of Oil Spills in Satellite Radar Images,” Machine Learning, vol. 30, no. 2, pp. 195-215, 1998.
[44] Y. Z. Liu, Y. C. Jiang, X. Liu, and S. L. Yang, “CSMC: A Combination Strategy for Multi-Class Classification Based on Multiple Association Rules,” Knowledge-Based Systems, vol. 21, no. 8, pp. 786-793, 2008.
[45] B. Liu, Y. Ma, C.K. Wong, and P.S. Yu, “Scoring the Data Using Association Rules,” Applied Intelligence, vol. 18, no. 2, pp. 119-135, 2003.
[46] S. Madeira, and J. M. Sousa, ”Comparison of Target Selection Methods in Direct Marketing,” Proceedings of 2nd European Symposium on Intelligent Technologies, 2002.
[47] H. Mamitsuka, "Selecting Features in Microarray Classification Using ROC Curves," Pattern Recognition, vol. 39, no. 12, pp. 2393-2404, 2006.
[48] G. Mccorkell, “Direct and Database Marketing,” London: Kogan Page Limited, 1997.
[49] E. L. Nash, “Database Marketing-the Ultimate Marketing Tool,” New York: McGraw-Hill, 1993.
[50] S. Neslin, S. Gupta, W. Kamakura, J. Lu, and C. Mason, “Detection Defection: Measuring and Understanding the Predictive Accuracy of Customer Churn Models,” Journal of Marketing Research, vol. 43, no. 2, pp. 204–211, 2006.
[51] M. R. Pearce, “Succeeding with Micro-Marketing,” Ivey Business Quarterly, pp.69-72, 1997.
[52] G. Piatetsky-Shapiro, and B. Masand, “Estimating Campaign Benefits and Modeling Lift,” Proc. Fifth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining, pp. 185-193, 1999.
[53] A. Prinzie, and D. Van den Poel, "Constrained Optimization of Data-Mining Problems to Improve Model Performance: A Direct-Marketing Application," Expert Systems with Applications, vol. 29, no. 3, pp. 630-640, 2005.
[54] J.R. Quinlan, C4.5: Programs for Machine Learning. San Mateo, Calif.: Morgan Kaufmann, 1993.
[55] H. Shin, and S. Cho, "Response Modeling with Support Vector Machines," Expert Systems with Applications, vol. 30, no. 4, pp. 746-760, 2006.
[56] H. W. Shin, and S. Y. Sohn, "Multi-attribute Scoring Method for Mobile Telecommunication Subscribers," Expert Systems with Applications, vol. 26, no. 3, pp. 363-368, 2004.
[57] E. H. Suh, K. C. Noh, and C. K. Suh, “Customer List Segmentation Using the Combined Response Model,” Expert Systems with Applications, vol. 17, no. 2, pp.89-97, 1999.
[58] F. Thabtah, P. Cowling, and S. Hammoud, “Improving Rule Sorting, Predictive Accuracy and Training Time in Associative Classification,” Expert Systems with Applications, vol. 31, no. 2, pp. 414-426, 2006.
[59] K. Wang, S. Zhou, and Y. He, “Growing Decision Tree on Support-Less Association Rules,” Proc. Sixth ACM SIGKDD Int’l Conf.Knowledge Discovery and Data Mining, pp. 265–269, 2000.
[60] C. P. Wei, and I. T. Chiu, "Turning Telecommunications Call Details to Churn Prediction: A Data Mining Approach," Expert Systems with Applications, vol. 23, no. 2, pp. 103-112, 2002.
[61] G.M. Weiss, “Mining with Rarity: A Unifying Framework,” ACM SIGKDD Explorations Newsletter, vol. 6, no. 1, pp. 7-19, 2004.
[62] Q. Yang, and X. Wu, “10 Challenging Problems in Data Mining Research,” Int'l J. Information Technology and Decision Making, vol. 5, no. 4, pp. 597-604, 2006.
[63] X. Yin, and J. Han, “CPAR: Classification Based on Predictive Association Rules,” Proc. 2003 SIAM Int’l Conf. Data Mining, pp. 331–335, 2003.
[64] Y. Yoon, and G.G. Lee, “Efficient Implementation of Associative Classifiers for Document Classification,” Information Processing & Management, vol. 43, no. 2, pp. 393-405, 2007.
[65] E. Yu, and S. Cho, "Constructing Response Model Using Ensemble Based on Feature Subset Selection," Expert Systems with Applications, vol. 30, no. 2, pp. 352-360, 2006.
[66] J. Zahavi, and N. Levin, ”Applying Neural Networks to Target Marketing,” Journal of Direct Marketing, vol. 11, pp. 2-22, 1997.