Parallel Decision Tree with Application to Water Quality Data Analysis

详细信息    查看全文

• 作者：Qing He (1) heq@ics.ict.ac.cn
  Zhi Dong (12) dongz@ics.ict.ac.cn
  Fuzhen Zhuang (1) zhuangfz@ics.ict.ac.cn
  Tianfeng Shang (12) shangtf@ics.ict.ac.cn
  Zhongzhi Shi (1) shizz@ics.ict.ac.cn
• 关键词：Data mining – ; Parallel decision tree – ; PID3 – ; Mapreduce
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7368
• 期：1
• 页码：628-637
• 全文大小：202.9 KB
• 参考文献：1. Shafer, J., Agrawal, R., Mehta, M.: SPRINT: A Scalable Parallel Classifier for Data Mining. In: Proceedings of the Twenty-Second VLDB Conference, pp. 544–555. Morgan Kaufmann, San Francisco
  2. Guo, Y., Grossman, R.: Parallel Formulations of Decision-Tree Classification Algorithms. Data Minging and Knowledge Discovery 3, 237–261 (1999)
  3. Bowyer, K.W., Chawla, N.V., Moore, I.E., Hall, L.O., Kegelmeyer, W.P.: A parallel decision tree builder for mining very large visualization datasets. In: IEEE System, Man, and Cybernetics Conference, pp. 1888–1893 (2000)
  4. Dean, J., Ghemawat, S.: MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM 51(1), 107–113 (2008)
  5. Zhao, W., Ma, H., He, Q.: Parallel K-Means Clustering Based on MapReduce. In: Jaatun, M.G., Zhao, G., Rong, C. (eds.) Cloud Computing. LNCS, vol. 5931, pp. 674–679. Springer, Heidelberg (2009)
  6. Ranger, C., Raghuraman, R., Penmetsa, A., Bradski, G., Kozyrakis, C.: Evaluating MapReduce for Multi-core and Multiprocessor Systems. In: Proc. of 13th Int. Symposium on High-Performance Computer Architecture (HPCA), Phoenix, AZ (2007)
  7. Lammel, R.: Google’s MapReduce Programming Model - Revisited. Science of Computer Programming 70, 1–30 (2008)
  8. Borthakur, D.: The Hadoop Distributed File System: Architecture and Design (2007)
  9. Hadoop: Open source implementation of MapReduce, http://lucene.apache.org/hadoop/
  10. Ghemawat, S., Gobioff, H., Leung, S.: The Google File System. In: Symposium on Operating Systems Principles, pp. 29–43 (2003)
  11. Safavian, S.R., Landgrebe, D.: A Survey of Decision Tree Classifier Methodology. IEEE Trans. on Systems, Man and Cybernetics 21(3), 660–674 (1991)
  12. Xu, X., Jager, J., Kriegel, H.P.: A Fast Parallel Clustering Algorithm for Large Spatial Databases. Data Mining and Knowledge Discovery 3, 263–290 (1999)
  13. He, Q., Wang, Q., Du, C.-Y., Ma, X.-D., Shi, Z.-Z.: A parallel Hyper-Surface Classifier for high dimensional data. Knowledge Acquisition and Modeling 3, 338–343 (2010)
• 作者单位：1. The Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, China2. Graduate University of Chinese Academy of Sciences, China
• ISSN：1611-3349

文摘

Decision tree is a popular classification technique in many applications, such as retail target marketing, fraud detection and design of telecommunication service plans. With the information exploration, the existing classification algorithms are not good enough to tackle large data set. In order to deal with the problem, many researchers try to design efficient parallel classification algorithms. Based on the current and powerful parallel programming framework — MapReduce, we propose a parallel ID3 classification algorithm(PID3 for short). We use water quality data monitoring the Changjiang River which contains 17 branches as experimental data. As the data are time series, we process the data to attribute data before using the decision tree. The experimental results demonstrate that the proposed algorithm can scale well and efficiently process large datasets on commodity hardware.