投影寻踪模型在文本聚类算法中的应用研究
|
摘要
快速、高效的文本聚类算法有助于从大量非结构化的文本源中发现和挖掘其所蕴含的巨大潜在知识。文本数据以向量空间模型表示成特征向量，往往呈现出高维特征。
利用投影寻踪模型实现文本特征降维，把高维文本特征投影到二维或三维的可视化空间当中，不仅可以表现出文本的结构特征，还可以大大简化文本聚类算法的计算复杂性，提高算法效率和精度。利用投影寻踪模型对文本特征向量进行降维的过程中，关键是最优投影方向的搜索。
本文提出两种改进的基于遗传算法的投影寻踪文本聚类算法，结合遗传算法来确定最优投影方向，将高维文本特征向量投影到二维和三维空间上，实现文本特征降维，使得文本的结构特征在可视的空间中凸现出来，从而能够直观地观察文本集的结构分布情况，直观地确定文本类数目。实验表明，这种方法可以得到较好的聚类结果。
The efficient and high quality Text Clustering Algorithms would help to discover and mine the huge latent valued knowledge from a great deal of unstructured text sources. Vector Space Model is usually used to express text feature with high dimensional characteristic.
Applying the Projection Pursuit Model in text feature dimension reduction to project high dimensional feature vector into visualization space with two or three dimension. It not only can express text structure features, but also reduce computation complexity, improve efficiency and precision of the text clustering algorithms. The key in this process is to find the global optimal projecting directions.
This paper proposed two kinds of improved genetic algorithm based projection pursuit text clustering algorithm, which uses accelerating immune genetic algorithm to determine optimal projection direction and project the high-dimensional text feature vectors into two or three dimensional space. It can merge text structure features in a visualization space, and determine the text cluster number intuitionisticly. Experiments demonstrate this algorithm can get better clusting result.
利用投影寻踪模型实现文本特征降维，把高维文本特征投影到二维或三维的可视化空间当中，不仅可以表现出文本的结构特征，还可以大大简化文本聚类算法的计算复杂性，提高算法效率和精度。利用投影寻踪模型对文本特征向量进行降维的过程中，关键是最优投影方向的搜索。
本文提出两种改进的基于遗传算法的投影寻踪文本聚类算法，结合遗传算法来确定最优投影方向，将高维文本特征向量投影到二维和三维空间上，实现文本特征降维，使得文本的结构特征在可视的空间中凸现出来，从而能够直观地观察文本集的结构分布情况，直观地确定文本类数目。实验表明，这种方法可以得到较好的聚类结果。
The efficient and high quality Text Clustering Algorithms would help to discover and mine the huge latent valued knowledge from a great deal of unstructured text sources. Vector Space Model is usually used to express text feature with high dimensional characteristic.
Applying the Projection Pursuit Model in text feature dimension reduction to project high dimensional feature vector into visualization space with two or three dimension. It not only can express text structure features, but also reduce computation complexity, improve efficiency and precision of the text clustering algorithms. The key in this process is to find the global optimal projecting directions.
This paper proposed two kinds of improved genetic algorithm based projection pursuit text clustering algorithm, which uses accelerating immune genetic algorithm to determine optimal projection direction and project the high-dimensional text feature vectors into two or three dimensional space. It can merge text structure features in a visualization space, and determine the text cluster number intuitionisticly. Experiments demonstrate this algorithm can get better clusting result.
引文
[1] E H, Karypis G Centroid-based Document Classification: Analysis& Experimental Results[A]. Technical Report 002017. Computer Science[R]. University of Minnesota, 2000.
[2] HearstMa, Pedersen J. Reexamining the Cluster Hypothesis: Scatter/Gather on Retrieval Results[C]. Proc. of the 19th Annual Int Acm /Sigir Conf. Zurich, 1996. 76284.
[3] Cutting D, et al Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections [C]. Proc. of the 15th Annual Int Acm /Sigir Conf. Copenhagen, 1992. 3182329.
[4] Rocchio J J. Document Retrieval Systems Optimization and Evaluation[D]. Harvard University, Cambridge, Ma, 1996.
[5] RFeldman, HHirsh. Finding Associations in Collectionds of Text[M]. Machine Learning and Data Mining: Methods and Applications, John Wiley Sons, 1998. 223-240.
[6] Switer P. Numerical Classification. In Geostatistics. New York:Plenum Press, 1970.
[7] Wang Ke, Liu Huiqing. Schema Discovery from SemiStructured Data[C]. Proc. of the 3 rd Int Conf. on Knowledge Discovery and Data Mining, New Port Beach, 1997.
[8] Feldman R, Dagan I. Knowledge Discovery in Textual Databases(KDT) [C]. Montreal: Proc. of the 1 st Int Conf. on Knowledge Discovery, 1995. 112-117.
[9] Wuthrich B, Permunetilleke D, Leung S, et al. Daily Prediction of Major Stock Indices from Textual WWW Data[C]. New York: Procof the 4 th Int Conf. on Knowledge Discovery, 1998.
[10] D H Zhu, A LPorter. Automated Extraction and Visualization of Information [J]. Technological Intelligence and Forecasting, Techno21ogical Forecasting & Social Change, 2002, (69): 495-506.
[11] Fodor I. K. A Survey of Dimension Reduction Techniques [R/EB/OL]. LLNL technical report, June 2002, UCRL-ID-148494. URL: http://www.llnl.gov/CASC/sapphire/pubs.html.
[12] Friedman J.H.,Tukey J.W.A Projection Pursuit Algorithm for Exploratory Data Analysis[J]. IEEE rrans. Computer, 1974,23(9): 881-890.
[13] M. Mizuta. Dimension Reduction Methods [R/EB/OL]. URL:http://www.case.hu-berlin.de/Publikationen/papers/papersKatalog/15_mm.pdf.T.Hastie,R. Tibshir
[14] J. Friedman. The Elemants of Statistical Learning: Data Mining, Inference, and Prediction[M]. Springer-Verlag. 2001.
[15] Fisher R A. The use of multiple measurements in taxonomic problem. Ann Eugene Lond, 1937, (9): 179.
[16] CHEN Ming—shan, HAN Jia—wei, PHILP S YU. Datamining: An overview from a database perceptive[J]. IEEE Transactions on Knowledge and Data Engineering, 1996, 8(6): 866-882.
[17] Maechler M, Mertin D, Schimert J. Projection pursuit learning networks for regression. Proc 2 Int IEEE Conf Tools Artif Intell, 1990.
[18] ESTER M, KRIEGEL P—H, SANDER J, et al. A densiTybased algorithm for discovering clusters in large spatial databases with noise[A]. Second International Conference on Knowledge Discovery and Data Mining[C]. Portland: OR, AAAI Press, 1996, 226-231.
[19] 高飞．关联规则挖掘算法研究[D]．西安：西安电子科技大学，2001．
[20] 陈莉．数据库中的知识发现[J]．西北大学学报(自然科学版)，1999，29(1)：5-7．
[21] 朱明．数据挖掘[M]．合肥：中国科学技术大学出版社，20HD2．
[22] 王小平，曹立明．遗传算法——理论、应用与软件实现[M]．西安交通大学出版社，2002．
[23] 王顺久，张欣莉，丁晶等．投影寻踪聚类模型及其应用[J]．长江科学院院报，2002，19(6)：53-55．
[24] 胥桂仙．文本挖掘中的特征表示及聚类方法[D]．长春：吉林工学院计算机科学与工程学院，21302．[25]
[25] 郝占钢．基于遗传算法和k-medoids算法的聚类新算法．现代图书情报技术，2006年第5期．
[26] 龙昊 冯剑琳．R-means：以关联规则为簇中心的文本聚类计算机科学 2005Vol．32No．9．
[27] 唐春生 金以慧．基于聚类特性的大规模文本聚类算法研究 计算机科学 2002Voi．29N～2．
[28] 李向军，徐国华．一种文本聚类算法西北大学学报(自然科学版)2005年4月，第35卷第2期．
[29] 时念云．改进遗传算法在模糊文本聚类中的应用研究科学技术与工程．第5卷第24期．2005年12月．
[30] 高坚，基于C一均值和免疫遗传算法的聚类分析，计算机工程2003；29(12)，65—66
[31] 钱晓东，王正欧．基于SOM网络的随机映射文本降维方法．计算机应用，2004，24(5)：56—59．
[32] 丛爽．神经网络、模糊系统及其在运动控制中的应用[M]．合肥：中国科学技术大学出版社，2001．
[33] 刘源．信息处理用现代汉语分词规范及自动分词方法[M]北京：清华大学出版社，1994．36237．
[34] 蒋澄，马范援，蒋思杰．中英文WWW搜索引擎的信息处理[J]．计算机工程，1999，25(4)：37238．
[35] 杨斌，孟志青．一种文本分类数据挖掘的技术[J]．湘潭大学自然科学学报，2001，23(4)：34237．
[36] 董振东，董强．知网[C]．北京：计算语言学文集，1999．
[37] 吴立德等著．大规模中文文本处理[M]．上海：上海复旦大学出版社，1997．
[38] 徐建锁，王正欧．基于LSI和自组织神经网络的高效文本聚类方法．天津大学学报．第37卷 第11期．2004年11月．
[39] 一种基于小生境遗传算法的中文文本聚类新方法 计算机工程 2006年3月第32卷 第6期
[40] 景丽萍．用于文本挖掘的特征选择方法TFIDF及其改进．广西师范大学学报．2003年3月．第21卷 第一期．
[41] 张小瑜．基于主成分分析和聚类分析的员工满意度研究方法中国人力资源调研网．
[42] 高茂庭，王正欧．基于LSA的RPCL文本聚类算法．计算机工程与应用，2006．42(23)：138-140．
[43] 周水庚，关佶红，胡运发．隐含语义索引及其在中文文本处理中的应用研 究[J]．小型微型计算机系统，2001；22(2)：239～243
[44] 付强 赵小勇著．投影寻踪模型原理及其运用．科学出版社。
[45] Gao Mao-ting, Wang Zheng-ou. A New Algorithm for Text Clustering based on Projection Pursuit. The sixth International Conference on Machine Learning and Cy-bernetics, Hongkong: IEEE, 2007.8.
[46] 杨力行．1998年长江三峡年最大洪峰的投影寻踪长期预报与验证．新疆农业大学学报，1998，21(4)：312～315．
[47] 史久恩．投影寻踪方法及其在气象中的应用．气象学研究——统计气候学，气象出版社，1992．
[48] 李祚泳．用投影寻踪回归进行大气颗粒的污染源解析．中国环境学，1999，19(3)．
[49] 张剑飞．数据挖掘中基于模型的聚类分析方法研究．克山师专学报．2004年第三期．
[2] HearstMa, Pedersen J. Reexamining the Cluster Hypothesis: Scatter/Gather on Retrieval Results[C]. Proc. of the 19th Annual Int Acm /Sigir Conf. Zurich, 1996. 76284.
[3] Cutting D, et al Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections [C]. Proc. of the 15th Annual Int Acm /Sigir Conf. Copenhagen, 1992. 3182329.
[4] Rocchio J J. Document Retrieval Systems Optimization and Evaluation[D]. Harvard University, Cambridge, Ma, 1996.
[5] RFeldman, HHirsh. Finding Associations in Collectionds of Text[M]. Machine Learning and Data Mining: Methods and Applications, John Wiley Sons, 1998. 223-240.
[6] Switer P. Numerical Classification. In Geostatistics. New York:Plenum Press, 1970.
[7] Wang Ke, Liu Huiqing. Schema Discovery from SemiStructured Data[C]. Proc. of the 3 rd Int Conf. on Knowledge Discovery and Data Mining, New Port Beach, 1997.
[8] Feldman R, Dagan I. Knowledge Discovery in Textual Databases(KDT) [C]. Montreal: Proc. of the 1 st Int Conf. on Knowledge Discovery, 1995. 112-117.
[9] Wuthrich B, Permunetilleke D, Leung S, et al. Daily Prediction of Major Stock Indices from Textual WWW Data[C]. New York: Procof the 4 th Int Conf. on Knowledge Discovery, 1998.
[10] D H Zhu, A LPorter. Automated Extraction and Visualization of Information [J]. Technological Intelligence and Forecasting, Techno21ogical Forecasting & Social Change, 2002, (69): 495-506.
[11] Fodor I. K. A Survey of Dimension Reduction Techniques [R/EB/OL]. LLNL technical report, June 2002, UCRL-ID-148494. URL: http://www.llnl.gov/CASC/sapphire/pubs.html.
[12] Friedman J.H.,Tukey J.W.A Projection Pursuit Algorithm for Exploratory Data Analysis[J]. IEEE rrans. Computer, 1974,23(9): 881-890.
[13] M. Mizuta. Dimension Reduction Methods [R/EB/OL]. URL:http://www.case.hu-berlin.de/Publikationen/papers/papersKatalog/15_mm.pdf.T.Hastie,R. Tibshir
[14] J. Friedman. The Elemants of Statistical Learning: Data Mining, Inference, and Prediction[M]. Springer-Verlag. 2001.
[15] Fisher R A. The use of multiple measurements in taxonomic problem. Ann Eugene Lond, 1937, (9): 179.
[16] CHEN Ming—shan, HAN Jia—wei, PHILP S YU. Datamining: An overview from a database perceptive[J]. IEEE Transactions on Knowledge and Data Engineering, 1996, 8(6): 866-882.
[17] Maechler M, Mertin D, Schimert J. Projection pursuit learning networks for regression. Proc 2 Int IEEE Conf Tools Artif Intell, 1990.
[18] ESTER M, KRIEGEL P—H, SANDER J, et al. A densiTybased algorithm for discovering clusters in large spatial databases with noise[A]. Second International Conference on Knowledge Discovery and Data Mining[C]. Portland: OR, AAAI Press, 1996, 226-231.
[19] 高飞．关联规则挖掘算法研究[D]．西安：西安电子科技大学，2001．
[20] 陈莉．数据库中的知识发现[J]．西北大学学报(自然科学版)，1999，29(1)：5-7．
[21] 朱明．数据挖掘[M]．合肥：中国科学技术大学出版社，20HD2．
[22] 王小平，曹立明．遗传算法——理论、应用与软件实现[M]．西安交通大学出版社，2002．
[23] 王顺久，张欣莉，丁晶等．投影寻踪聚类模型及其应用[J]．长江科学院院报，2002，19(6)：53-55．
[24] 胥桂仙．文本挖掘中的特征表示及聚类方法[D]．长春：吉林工学院计算机科学与工程学院，21302．[25]
[25] 郝占钢．基于遗传算法和k-medoids算法的聚类新算法．现代图书情报技术，2006年第5期．
[26] 龙昊 冯剑琳．R-means：以关联规则为簇中心的文本聚类计算机科学 2005Vol．32No．9．
[27] 唐春生 金以慧．基于聚类特性的大规模文本聚类算法研究 计算机科学 2002Voi．29N～2．
[28] 李向军，徐国华．一种文本聚类算法西北大学学报(自然科学版)2005年4月，第35卷第2期．
[29] 时念云．改进遗传算法在模糊文本聚类中的应用研究科学技术与工程．第5卷第24期．2005年12月．
[30] 高坚，基于C一均值和免疫遗传算法的聚类分析，计算机工程2003；29(12)，65—66
[31] 钱晓东，王正欧．基于SOM网络的随机映射文本降维方法．计算机应用，2004，24(5)：56—59．
[32] 丛爽．神经网络、模糊系统及其在运动控制中的应用[M]．合肥：中国科学技术大学出版社，2001．
[33] 刘源．信息处理用现代汉语分词规范及自动分词方法[M]北京：清华大学出版社，1994．36237．
[34] 蒋澄，马范援，蒋思杰．中英文WWW搜索引擎的信息处理[J]．计算机工程，1999，25(4)：37238．
[35] 杨斌，孟志青．一种文本分类数据挖掘的技术[J]．湘潭大学自然科学学报，2001，23(4)：34237．
[36] 董振东，董强．知网[C]．北京：计算语言学文集，1999．
[37] 吴立德等著．大规模中文文本处理[M]．上海：上海复旦大学出版社，1997．
[38] 徐建锁，王正欧．基于LSI和自组织神经网络的高效文本聚类方法．天津大学学报．第37卷 第11期．2004年11月．
[39] 一种基于小生境遗传算法的中文文本聚类新方法 计算机工程 2006年3月第32卷 第6期
[40] 景丽萍．用于文本挖掘的特征选择方法TFIDF及其改进．广西师范大学学报．2003年3月．第21卷 第一期．
[41] 张小瑜．基于主成分分析和聚类分析的员工满意度研究方法中国人力资源调研网．
[42] 高茂庭，王正欧．基于LSA的RPCL文本聚类算法．计算机工程与应用，2006．42(23)：138-140．
[43] 周水庚，关佶红，胡运发．隐含语义索引及其在中文文本处理中的应用研 究[J]．小型微型计算机系统，2001；22(2)：239～243
[44] 付强 赵小勇著．投影寻踪模型原理及其运用．科学出版社。
[45] Gao Mao-ting, Wang Zheng-ou. A New Algorithm for Text Clustering based on Projection Pursuit. The sixth International Conference on Machine Learning and Cy-bernetics, Hongkong: IEEE, 2007.8.
[46] 杨力行．1998年长江三峡年最大洪峰的投影寻踪长期预报与验证．新疆农业大学学报，1998，21(4)：312～315．
[47] 史久恩．投影寻踪方法及其在气象中的应用．气象学研究——统计气候学，气象出版社，1992．
[48] 李祚泳．用投影寻踪回归进行大气颗粒的污染源解析．中国环境学，1999，19(3)．
[49] 张剑飞．数据挖掘中基于模型的聚类分析方法研究．克山师专学报．2004年第三期．
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |