To buy or not to buy: mining airfare data to minimize ticket purchase price

ABSTRACT

As product prices become increasingly available on the World Wide Web, consumers attempt to understand how corporations vary these prices over time. However, corporations change prices based on proprietary algorithms and hidden variables (e.g., the number of unsold seats on a flight). Is it possible to develop data mining techniques that will enable consumers to predict price changes under these conditions?This paper reports on a pilot study in the domain of airline ticket prices where we recorded over 12,000 price observations over a 41 day period. When trained on this data, Hamlet --- our multi-strategy data mining algorithm --- generated a predictive model that saved 341 simulated passengers $198,074 by advising them when to buy and when to postpone ticket purchases. Remarkably, a clairvoyant algorithm with complete knowledge of future prices could save at most $320,572 in our simulation, thus HAMLET's savings were 61.8% of optimal. The algorithm's savings of $198,074 represents an average savings of 23.8% for the 341 passengers for whom savings are possible. Overall, HAMLET saved 4.4% of the ticket price averaged over the entire set of 4,488 simulated passengers. Our pilot study suggests that mining of price data available over the web has the potential to save consumers substantial sums of money per annum.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: José Luis Ambite , Greg Barish , Craig A. Knoblock , Maria Muslea , Jean Oh , Steven Minton, Getting from here to there: interactive planning and agent execution for optimizing travel, Eighteenth national conference on Artificial intelligence, p.862-869, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 3: G. Barish and C. A. Knoblock. An efficient and expressive language for information gathering on the web. In Proceedings of the AIPS-2002 Workshop on Is there life after operator sequencing? - Exploring real world planning, pages 5--12, Tolouse, France, 2002.
• 4: Donald J. Berndt , James Clifford, Finding patterns in time series: a dynamic programming approach, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 5: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 6: Hans Chalupsky , Yolanda Gil , Craig A. Knoblock , Kristina Lerman , Jean Oh , David V. Pynadath , Thomas A. Russ , Milind Tambe, Electric Elves: Applying Agent Technology to Support Human Organizations, Proceedings of the Thirteenth Conference on Innovative Applications of Artificial Intelligence Conference, p.51-58, August 07-09, 2001
• 7: C. Chatfield. The Analysis of Time Series: An Introduction. Chapman and Hall, London, UK, 1989.
• 8: W. W. Cohen. Fast effective rule induction. In A. Prieditis and S. Russell, editors, Proc. of the 12th International Conference on Machine Learning, pages 115--123, Tahoe City, CA, July 9--12, 1995. Morgan Kaufmann.
• 9: F. Diebold. Elements of Forecasting. South-Western College Publishing, 2nd edition, 2000.
• 10: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 11: Robert B. Doorenbos , Oren Etzioni , Daniel S. Weld, A scalable comparison-shopping agent for the World-Wide Web, Proceedings of the first international conference on Autonomous agents, p.39-48, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267666]
• 12: Y. Freund and R. E. Schapire. Experiments with a new boosting algorithm. In Proceedings of the Thirteenth International Conference on Machine Learning, pages 148--156, Bari, Italy, 1996. Morgan Kaufmann.
• 13: C. W. J. Granger. Forecasting in Business and Economics. Harcourt Brace, second edition, 1989.
• 14: J. C. Hull. Options, Futures, and Other Derivatives. Prentice Hall College Div, 5th edition, 2002.
• 15: Craig A. Knoblock , Kristina Lerman , Steven Minton , Ion Muslea, Accurately and reliably extracting data from the Web: a machine learning approach, Intelligent exploration of the web, Physica-Verlag GmbH, Heidelberg, Germany, 2003
• 16: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 17: D. Lucking-Reiley, D. Bryan, N. Prasad, and D. Reeves. Pennies from ebay: The determinants of price in online auctions. Technical report, University of Arizona, 2000.
• 18: Sridhar Mahadevan, Average reward reinforcement learning: foundations, algorithms, and empirical results, Machine Learning, v.22 n.1-3, p.159-195, Jan./Feb./March 1996 [doi>10.1007/BF00114727]
• 19: S. McCartney. Airlines Rely on Technology To Manipuate Fare Structure. Wall Street Journal, November 3 1997.
• 20: J. Moody and M. Saffell. Reinforcement learning for trading systems and portfolios. In KDD, pages 279--283, 1998.
• 21: J. Moody and M. Saffell. Minimizing downside risk via stochastic dynamic programming. In Y. S. Abu-Mostafa, B. LeBaron, A. W. Lo, and A. S. Weigend, editors, Computational Finance 1999, Cambridge, MA, 2000. MIT Press.
• 22: J. Moody and M. Saffell. Learning to trade via direct reinforcement. In IEEE Transactions on Neural Networks, Vol. 12, No. 4, 2001.
• 23: John F. Roddick , Myra Spiliopoulou, A bibliography of temporal, spatial and spatio-temporal data mining research, ACM SIGKDD Explorations Newsletter, v.1 n.1, p.34-38, June 1999 [doi>10.1145/846170.846173]
• 24: H. S. Shah, N. R. Joshi, A. Sureka, and P. R. Wurman. Mining for bidding strategies on ebay. In Lecture Notes in Artificial Intelligence. Springer-Verlag, 2003.
• 25: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 26: K. M. Ting and I. H. Witten. Issues in stacked generalization. Journal of Artificial Intelligence Research, 10:271--289, 1999.
• 27: M. P. Wellman, D. M. Reeves, K. M. Lochner, and Y. Vorobeychik. Price prediction in a trading agent competition. Technical report, University of Michigan, 2002.
• 28: David H. Wolpert, Stacked generalization, Neural Networks, v.5 n.2, p.241-259, 1992 [doi>10.1016/S0893-6080(05)80023-1]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Keywords:
Internet, Web mining, airline price prediction, price mining