聚类分析要求较高聚类质量和快速响应能力,各行业数据仓库中的大量、高维数据对算法的效率提出了更大的挑战.CURE算法能够提供高质量聚类结果但不满足联机聚类要求.结合数据仓库数据不定期批量、增量更新的特点,提出了一种新的增量式CURE聚类算法--InCURE,利用对象的互连性和近似度,保持原算法的动态聚类特性的同时大大缩短聚类时间.5维、20维、50维的大量数据实际测试表明无论低维还是高维数据,InCURE都比CURE具有更高的效率,适合数据仓库环境下的增量式聚类分析.
Data warehouse is a challenging field of application for data mining tasks such as clustering. Clustering online requires good result and fast-response ability at the same time. The CURE algorithm can get high-quality clusters but efficiency is relatively low. In this paper, a novel incremental CURE algorithm-InCURE is proposed, after investigating CURE and updates mode of data warehouse. CURE keeps nicely the dynamic clustering characteristic of the original algorithm, while shortens the clustering time consumedly by using the historical clustering results and dealing with added items separately. Performance evaluation of InCURE based on multidimensional data demonstrates that it is well applicable for incremental clustering in data warehouse.
[1] 曲昭伟, 郑岩, 吕廷杰, QU Zhao-wei, ZHENG Yan, LU Ting-jie. 基于聚类实现客户行为分析 [J]. 东北师大学报（自然科学版） 2006.doi:10.3321/j.issn:1000-1832.2006.02.005
[2] HAN Jianwei, KAMBR M. Data Mining Concepts and Techniques [M]. 北京:高等教育出版社 2001.
[3] HAN E H, KARYPIS G, UMARV K. Hypergraph based clustering in high-dimensional data sets:A summary of results [J]. IEEE Computer Society Technical Committee on Data Engineering 1998, 21(01).
[4] BERCHTHOLD A, KEIM D, KRIEGEL H-P. The X-Tree:An index structure for high-dimensional data [A]. Bombay, India 1996.
[5] BECKMANN N, KRIEGEL H-P, SCHNEIDER R. The R-tree:An efficient and robust access method for points and Rectangles [A]. Atlantic City 1990.
[6] Bouguettaya A.. On-line clustering [J]. IEEE Transactions on Knowledge and Data Engineering 1996, 2(2).
[7] KAUFAN L, ROUSSEEUW P J. Finding groups in data:an introduction to cluster analysis [M]. New York:John Wiley and Sons, Inc 1990.
[8] ZHANG T, RAMAKRISHNAN R, LIVNY M. An efficient data clustering method for very large databases [A]. Montreal, Canada 1996.
[9] GUHA S, RASTOGI R, SHIM K. Cure:An efficient clustering algorithm for large database [A]. Seattle, Washington 1998.
[10] ESTER M, KRIEGEL HP, SANDER J. A density based algorithm for discovering clusters in large spatial databases with noise [A]. Portland, Oregon, USA 1996.
[11] ANKERST M, BREUING M M, KRIEGEL HP. OPTICS:Ordering points to identify the clustering structure [A]. Philadelphia, PA, USA 1999.
[12] KARYPIS G, HAN E-H, KUMAR V. A hierarchical clustering algorithm using dynamic modeling [J]. IEEE Transaction on Computer 1999, 5(03).
[13] ESTER M, KRIEGEL H P, SANDER J. Incremental clustering for mining in a data warehouse environment [M]. New York 1998.
[14] KRIEGEL HP, GOTLIBOVICH I. Incremental OPTICS:Efficient computation of updates in a hierarchical cluster ordering [J]. Lecture Notes in Computer Science 2003, 2737.
[15] ESTER M, WITTMAN R. Incremental generalization for mining in a data warehousing environment [A]. Valencia, Spain 1998.
