Discovering interesting patterns through user's interactive feedback

ABSTRACT

In this paper, we study the problem of discovering interesting patterns through user's interactive feedback. We assume a set of candidate patterns (ie, frequent patterns) has already been mined. Our goal is to help a particular user effectively discover interesting patterns according to his specific interest. Without requiring a user to explicitly construct a prior knowledge to measure the interestingness of patterns, we learn the user's prior knowledge from his interactive feedback. We propose two models to represent a user's prior: the log linear model and biased belief model. The former is designed for item-set patterns, whereas the latter is also applicable to sequential and structural patterns. To learn these models, we present a two-stage approach, progressive shrinking and clustering, to select sample patterns for feedback. The experimental results on real and synthetic data sets demonstrate the effectiveness of our approach.

REFERENCES

• 1: R. Bayardo, B. Goethals, and M. Zaki. Fimi 2004 workshop. Proc. ICDM Workshop on Frequent Itemset Mining Implementations (FIMI), 2004.
• 2: Y. M. M. Bishop, S. E. Fienberg, and P. W. Holland. Discrete Multivariate Analysis. The MIT Press, 1975.
• 3: W. W. Cohen, R. R. Schapire, and Y. Singer. Learning to order things. Journal of Artificial Intelligence Research, 10:243--270, 1999.
• 4: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 5: Philip E. Gill , Walter Murray , Michael A. Saunders, SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization, SIAM Review, v.47 n.1, p.99-131, 2005 [doi>10.1137/S0036144504446096]
• 6: T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Comput. Sci., 38:293--306, 1985.
• 7: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 8: Szymon Jaroszewicz , Tobias Scheffer, Fast discovery of unexpected patterns in data, relative to a Bayesian network, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081887]
• 9: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 10: Xuehua Shen , ChengXiang Zhai, Active feedback in ad hoc information retrieval, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076047]
• 11: Avi Silberschatz , Alexander Tuzhilin, What Makes Patterns Interesting in Knowledge Discovery Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.970-974, December 1996 [doi>10.1109/69.553165]
• 12: Dong Xin , Jiawei Han , Xifeng Yan , Hong Cheng, Mining compressed frequent-pattern sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 13: Hwanjo Yu, SVM selective sampling for ranking with application to data retrieval, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081911]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
interactive feedback, pattern discovery