数据收集和数据存储技术的快速进步使得各组织机构可以积累海量数据。然而，提取有用的信息已经成为巨大的挑战。通常，由于数据量太大，无法使用传统的数据分析工具和技术处理它们。有时，即使数据集相对较小，由于数据本身的非传统特点，也不能使用传统的方法处理。在另外一些情况下，需要回答的问题不能使用已有的数据分析技术来解决。这样，就需要开发新的方法。
数据挖掘是一种技术，它将传统的数据分析方法与处理大量数据的复杂算法相结合。数据挖掘为探查和分析新的数据类型以及用新方法分析旧有数据类型提供了令人振奋的机会。本章，我们概述数据挖掘，并列举本书所涵盖的关键主题。我们从介绍需要新的数据分析技术的一些著名应用开始。
商务 借助POS（销售点）数据收集技术[条码扫描器、射频识别（RFID）和智能卡技术]，零售商可以在其商店的收银台收集顾客购物的最新数据。零售商可以利用这些信息，加上电子商务网站的日志、电购中心的顾客服务记录等其他的重要商务数据，更好地理解顾客的需求，做出更明智的商务决策。
数据挖掘技术可以用来支持广泛的商务智能应用，如顾客分析、定向营销、工作流管理、商店分布和欺诈检测等。数据挖掘还能帮助零售商回答一些重要的商务问题，如“谁是最有价值的顾客？”“什么产品可以交叉销售或提升销售？”“公司明年的收入前景如何？”这些问题催生了一种新的数据分析技术——关联分析（见第6、7章）。
医学、科学与工程 医学、科学与工程技术界的研究者正在快速积累大量数据，这些数据对获得有价值的新发现至关重要。例如，为了更深入地理解地球的气候系统，NASA已经部署了一系列的地球轨道卫星，不停地收集地表、海洋和大气的全球观测数据。然而，由于这些数据的规模和时空特性，传统的方法常常不适合分析这些数据集。数据挖掘开发的技术可以帮助地球科学家回答如下问题：“干旱和飓风等生态系统扰动的频度和强度与全球变暖之间有何联系？”“海洋表面温度对地表降水量和温度有何影响？”“如何准确地预测一个地区的生长季节的开始和结束？”
再举一个例子，分子生物学研究者希望利用当前收集的大量基因组数据，更好地理解基因的结构和功能。过去，传统方法只允许科学家在一个实验中每次研究少量基因。微阵列技术的最新突破已经能让科学家在多种情况下，比较数以千计的基因的特性。这种比较有助于确定每个基因的作用，或许可以查出导致特定疾病的基因。然而，由于数据的噪声和高维性，需要新的数据分析方法。除分析基因序列数据外，数据挖掘还能用来处理生物学的其他难题，如蛋白质结构预测、多序列校准、生物化学路径建模和种系发生学。
1.1 什么是数据挖掘
数据挖掘是在大型数据存储库中，自动地发现有用信息的过程。数据挖掘技术用来探查大型数据库，发现先前未知的有用模式。数据挖掘还具有预测未来观测结果的能力，例如，预测一位新的顾客是否会在一家百货公司消费100美元以上。
并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系统查找个别的记录，或通过因特网的搜索引擎查找特定的Web页面，则是信息检索（information retrieval）领域的任务。虽然这些任务是重要的，可能涉及使用复杂的算法和数据结构，但是它们主要依赖传统的计算机科学技术和数据的明显特征来创建索引结构，从而有效地组织和检索信息。尽管如此，数据挖掘技术也已用来增强信息检索系统的能力。
数据挖掘与知识发现
数据挖掘是数据库中知识发现（knowledge discovery in database, KDD）不可缺少的一部分，而KDD是将未加工的数据转换为有用信息的整个过程，输入数据可以以各种形式存储（平展文件、电子数据表或关系表），并且可以驻留在集中的数据存储库中，或分布在多个站点上。数据预处理（preprocessing）的目的是将未加工的输入数据转换成适合分析的形式。数据预处理涉及的步骤包括融合来自多个数据源的数据，清洗数据以消除噪声和重复的观测值，选择与当前数据挖掘任务相关的记录和特征。由于收集和存储数据的方式可能有许多种，数据预处理可能是整个知识发现过程中最费力、最耗时的步骤。
“结束循环（closing the loop）”通常指将数据挖掘结果集成到决策支持系统的过程。例如，在商务应用中，数据挖掘的结果所揭示的规律可以与商务活动管理工具集成，使得可以进行和测试有效的商品促销活动。这样的集成需要后处理（postprocessing）步骤，确保只将那些有效的和有用的结果集成到决策支持系统中。后处理的一个例子是可视化（见第3章），它使得数据分析者可以从各种不同的视角探查数据和数据挖掘结果。在后处理阶段，还能使用统计度量或假设检验，删除虚假的数据挖掘结果。
引发数据挖掘的挑战
正如前面所提到的，当面临新的数据集提出的挑战时，传统的数据分析技术常常遇到实际困难。下面是一些特定的挑战，它们引发了对数据挖掘的研究。
可伸缩 由于数据产生和收集技术的进步，数吉字节、数太字节甚至数拍字节的数据集越来越普遍。如果数据挖掘算法要处理这些海量数据集，则算法必须是可伸缩（scalable）。许多数据挖掘算法使用特殊的搜索策略处理指数性搜索问题。可伸缩可能还需要实现新的数据结构，以有效的方式访问个别记录。例如，当要处理的数据不能放进内存时，可能需要非内存算法。使用抽样技术或开发并行和分布算法也可以提高可伸缩程度。
高维性 现在，常常遇到具有数以百计或数以千计属性的数据集，而不是数十年前常见的只具有少量属性的数据集。在生物信息学领域，微阵列技术的进步已经产生了涉及数千特征的基因表达数据。具有时间或空间分量的数据集也趋向于具有很高的维度。例如，考虑包含不同地区的温度测量的数据集。如果温度在一个相当长的时间周期内重复地测量，则维度（特征数）的增长正比于测量的次数。为低维数据开发的传统的数据分析技术通常不能很好地处理这样的高维数据。此外，对于某些数据分析算法，随着维度（特征数）的增加，计算复杂性迅速增加。
异种数据和复杂数据 通常，传统的数据分析方法只处理包含相同类型属性的数据集，或者是连续的，或者是分类的。随着数据挖掘在商务、科学、医学和其他领域的作用越来越大，越来越需要能够处理异种属性的技术。近年来，已经出现了更复杂的数据对象。这些非传统的数据类型的例子包括含有半结构化文本和超链接的Web页面集、具有序列和三维结构的DNA数据、包含地球表面不同位置上的时间序列测量值（温度、气压等）的气象数据。为挖掘这种复杂对象而开发的技术应当考虑数据中的联系，如时间和空间的自相关性、图的连通性、半结构化文本和XML文档中元素之间的父子联系。
数据的所有权与分布 有时，需要分析的数据并非存放在一个站点，或归属一个单位，而是地理上分布在属于多个机构的资源中。这就需要开发分布式数据挖掘技术。分布式数据挖掘算法面临的主要挑战包括：(1) 如何降低执行分布式计算所需的通信量？(2) 如何有效地统一从多个资源得到的数据挖掘结果？(3) 如何处理数据安全性问题？
非传统的分析 传统的统计方法基于一种假设—检验模式。换句话说，提出一种假设，设计实验来收集数据，然后针对假设分析数据。但是，这一过程劳力费神。当前的数据分析任务常常需要产生和评估数以千计的假设，因此希望自动地产生和评估假设导致了一些数据挖掘技术的开发。此外，数据挖掘所分析的数据集通常不是精心设计的实验的结果，并且它们通常代表数据的时机性样本（opportunistic sample），而不是随机样本（random sample）。而且，这些数据集常常涉及非传统的数据类型和数据分布。
数据挖掘已有许多教科书。引论性教科书包括Dunham[10]、Han和Kamber[21]、Hand等[23]以及Roiger和Geatz[36]。更侧重于商务应用的数据挖掘书籍包括Berry和Linoff[2]、Pyle[34]和Parr Rud[33]。侧重统计学习的书籍包括Cherkassky和Mulier[6]和Hastie等[24]。侧重机器学习或模式识别的一些书包括Duda等[9]、Kantardzic[25]，Mitchell[31]、Webb[41]以及Witten和Frank[42]。还有一些更专业的书：Chakrabarti[4]（Web挖掘）、Fayyad等[13]（数据挖掘早期文献汇编）、Fayyad等[11]（可视化）、Grossman等[18]（科学与工程技术）、Kargupta和Chan[26]（分布式数据挖掘）、Wang等[40]（生物信息学）以及Zaki和Ho[44]（并行数据挖掘）。
有许多与数据挖掘相关的会议。致力于该领域研究的一些主要会议包括ACM SIGKDD知识发现与数据挖掘国际会议（KDD）、IEEE数据挖掘国际会议（ICDM）、SIAM数据挖掘国际会议（SDM）、欧洲数据库中知识发现的原理与实践会议（PKDD）和亚太知识发现与数据挖掘会议（PAKDD）。数据挖掘的文章也可以在其他主要会议上找到，如ACM SIGMOD/PODS会议、超大型数据库国际会议（VLDB）、信息与知识管理会议（CIKM）和数据工程国际会议（ICDE）、机器学习国际会议（ICML）以及人工智能全国学术会议（AAAI）。
数据挖掘方面的期刊包括《IEEE知识与数据工程汇刊》（IEEE Transactions on Knowledge and Data Engineering）、《数据挖掘与知识发现》（Data Mining and Knowledge Discovery）、《知识与信息系统》（Knowledge and Information Systems）、《智能数据分析》（Intelligent Data Analysis）、《信息系统》（Information Systems）和《智能信息系统杂志》（Journal of Intelligent Information Systems）。
有大量数据挖掘的一般性文章界定该领域及其与其他领域（特别是与统计学）之间的联系。Fayyad等[12]介绍数据挖掘，以及如何将它与整个知识发现过程协调。Chen等[5]从数据库角度阐释数据挖掘。Ramakrishnan和Grama[35]给出数据挖掘的一般讨论，并提出若干观点。与Friedman[14]一样，Hand[22]讨论数据挖掘如何有别于统计学。Lambert[29]考察统计学在大型数据集上的应用，并对数据挖掘与统计学各自的角色提出一些评论。Glymour等[16]考虑统计学可能为数据挖掘提供的教训。Smyth等[38]讨论诸如数据流、图形和文本等新的数据类型和应用如何推动数据挖掘演变。新出现的数据挖掘应用也被Han等[20]考虑，而Smyth[37]介绍数据挖掘研究所面临的一些挑战。Wu等[43]讨论如何将数据挖掘研究进展转化成实际工具。数据挖掘标准是Grossman等的文章[17]的主题。Bradley[3]讨论如何将数据挖掘算法扩展到大型数据集。
随着数据挖掘新的应用的出现，数据挖掘面临新的挑战。例如，近年来人们对数据挖掘破坏隐私问题的关注逐步上升，在电子商务和卫生保健领域的应用尤其如此。这样，人们对开发保护用户隐私的数据挖掘算法的兴趣逐步上升。为挖掘加密数据或随机数据而开发的技术称作保护隐私的数据挖掘。该领域的一些一般文献包括Agrawal和Srikant的文章[1]，Clifton等[7]和Kargupta等[27]。Vassilios等[39]提供一个综述。
近年来，我们看到快速产生连续的数据流的应用逐渐增加。数据流应用的例子包括网络通信流、多媒体流和股票价格。挖掘数据流时，必须考虑一些因素，如可用内存有限、需要联机分析、数据随时间而变等。流数据挖掘已经成为数据挖掘的一个重要领域。有关参考文献有Domingos和Hulten[8]（分类）、Giannella等[15]（关联分析）、Guha等[19]（聚类）、Kifer等[28]（变化检测）、Papadimitriou等[32]（时间序列）以及Law等[30]（维归约）。
[1] R. Agrawal and R. Srikant. Privacy-preserving data mining. In Proc. of 2000 ACMSIGMOD Intl. Conf. on Management of Data, pages 439–450, Dallas, Texas, 2000. ACM Press.
[2] M. J. A. Berry and G. Linoff. Data Mining Techniques: For Marketing, Sales, and Customer Relationship Management. Wiley Computer Publishing, 2nd edition, 2004.
[3] P. S. Bradley, J. Gehrke, R. Ramakrishnan, and R. Srikant. Scaling mining algorithms to large databases. Communications of the ACM, 45(8):38–43, 2002.
[4] S. Chakrabarti. Mining the Web: Discovering Knowledge from Hypertext Data. Morgan Kaufmann, San Francisco, CA, 2003.
[5] M.-S. Chen, J. Han, and P. S. Yu. Data Mining: An Overview from a Database Perspective. IEEE Transactions on Knowledge abd Data Engineering, 8(6):866–883,1996.
[6] V. Cherkassky and F. Mulier. Learning from Data: Concepts, Theory, and Methods. Wiley Interscience, 1998.
[7] C. Clifton, M. Kantarcioglu, and J. Vaidya. Defining privacy for data mining. In National Science Foundation Workshop on Next Generation Data Mining, pages 126–133, Baltimore, MD, November 2002.
[8] P. Domingos and G. Hulten. Mining high-speed data streams. In Proc. of the 6th Intl. Conf. on Knowledge Discovery and Data Mining, pages 71–80, Boston, Massachusetts, 2000. ACM Press.
[9] R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification. John Wiley & Sons, Inc., New York, 2nd edition, 2001.
[10] M. H. Dunham. Data Mining: Introductory and Advanced Topics. Prentice Hall, 2002.
[11] U. M. Fayyad, G. G. Grinstein, and A. Wierse, editors. Information Visualization in Data Mining and Knowledge Discovery. Morgan Kaufmann Publishers, San Francisco, CA, September 2001.
[12] U. M. Fayyad, G. Piatetsky-Shapiro, and P. Smyth. From Data Mining to Knowledge Discovery: An Overview. In Advances in Knowledge Discovery and Data Mining, pages1–34. AAAI Press, 1996.
[13] U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, editors. Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996.
[14] J. H. Friedman. Data Mining and Statistics: What’s the Connection? Unpublished. www- stat.stanford. edu/～jhf/ftp/dm-stat.ps, 1997.
[15] C. Giannella, J. Han, J. Pei, X. Yan, and P. S. Yu. Mining Frequent Patterns in Data Streams at Multiple Time Granularities. In H. Kargupta, A. Joshi, K. Sivakumar, and Y. Yesha, editors, Next Generation Data Mining, pages 191–212. AAAI/MIT, 2003.
[16] C. Glymour, D. Madigan, D. Pregibon, and P. Smyth. Statistical Themes and Lessons for Data Mining. Data Mining and Knowledge Discovery, 1(1):11–28, 1997.
[17] R. L. Grossman, M. F. Hornick, and G. Meyer. Data mining standards initiatives. Communications of the ACM, 45(8):59–61, 2002.
[18] R. L. Grossman, C. Kamath, P. Kegelmeyer, V. Kumar, and R. Namburu, editors. Data Mining for Scientific and Engineering Applications. Kluwer Academic Publishers, 2001.
[19] S. Guha, A. Meyerson, N. Mishra, R. Motwani, and L. O’Callaghan. Clustering Data Streams: Theory and Practice. IEEE Transactions on Knowledge and Data Engineering, 15(3):515–528, May/June 2003.
[20] J. Han, R. B. Altman, V. Kumar, H. Mannila, and D. Pregibon. Emerging scientific applications in data mining. Communications of the ACM, 45(8):54–58, 2002.
[21] J. Han and M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, San Francisco, 2001.
[22] D. J. Hand. Data Mining: Statistics and More? The American Statistician, 52(2):112–118, 1998.
[23] D. J. Hand, H. Mannila, and P. Smyth. Principles of Data Mining. MIT Press, 2001.
[24] T. Hastie, R. Tibshirani, and J. H. Friedman. The Elements of Statistical Learning:Data Mining, Inference, Prediction. Springer, New York, 2001.
[25] M. Kantardzic. Data Mining: Concepts, Models, Methods, and Algorithms. Wiley-IEEE Press, Piscataway, NJ, 2003.
[26] H. Kargupta and P. K. Chan, editors. Advances in Distributed and Parallel Knowledge Discovery. AAAI Press, September 2002.
[27] H. Kargupta, S. Datta, Q. Wang, and K. Sivakumar. On the Privacy Preserving Properties of Random Data Perturbation Techniques. In Proc. of the 2003 IEEE Intl. Conf. on Data Mining, pages 99–106, Melbourne, Florida, December 2003. IEEE Computer Society.
[28] D. Kifer, S. Ben-David, and J. Gehrke. Detecting Change in Data Streams. In Proc. of the 30th VLDB Conf., pages 180–191, Toronto, Canada, 2004. Morgan Kaufmann.
[29] D. Lambert. What Use is Statistics for Massive Data? In ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pages 54–62, 2000.
[30] M. H. C. Law, N. Zhang, and A. K. Jain. Nonlinear Manifold Learning for Data Streams. In Proc. of the SIAM Intl. Conf. on Data Mining, Lake Buena Vista, Florida, April 2004. SIAM.
[31] T. Mitchell. Machine Learning. McGraw-Hill, Boston, MA, 1997.
[32] S. Papadimitriou, A. Brockwell, and C. Faloutsos. Adaptive, unsupervised stream mining. VLDB Journal, 13(3):222–239, 2004.
[33] O. Parr Rud. Data Mining Cookbook: Modeling Data for Marketing, Risk and Customer Relationship Management. John Wiley & Sons, New York, NY, 2001.
[34] D. Pyle. Business Modeling and Data Mining. Morgan Kaufmann, San Francisco, CA, 2003.
[35] N. Ramakrishnan and A. Grama. Data Mining: From Serendipity to Science—Guest Editors’ Introduction. IEEE Computer, 32(8):34–37, 1999.
[36] R. Roiger and M. Geatz. Data Mining: A Tutorial Based Primer. Addison-Wesley, 2002.
[37] P. Smyth. Breaking out of the Black-Box: Research Challenges in Data Mining. In Proc. of the 2001 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2001.
[38] P. Smyth, D. Pregibon, and C. Faloutsos. Data-driven evolution of data mining algorithms. Communications of the ACM, 45(8):33–37, 2002.
[39] V. S. Verykios, E. Bertino, I. N. Fovino, L. P. Provenza, Y. Saygin, and Y. Theodoridis. State-of-the-art in privacy preserving data mining. SIGMOD Record, 33(1):50–57, 2004.
[40] J. T. L. Wang, M. J. Zaki, H. Toivonen, and D. E. Shasha, editors. Data Mining in Bioinformatics. Springer, September 2004.
[41] A. R. Webb. Statistical Pattern Recognition. John Wiley & Sons, 2nd edition, 2002.
[42] I. H. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations. Morgan Kaufmann, 1999.
[43] X.Wu, P. S. Yu, and G. Piatetsky-Shapiro. Data Mining: How Research Meets Practical Development? Knowledge and Information Systems, 5(2):248–261, 2003.
[44] M. J. Zaki and C.-T. Ho, editors. Large-Scale Parallel Data Mining. Springer, September 2002.