| With the development of large-scale integrated circuits and computer networks,vast amounts of data are stored in a wide variety of databases.These data often contain useful potential information.Data mining is a powerful tool to quickly acquire information and to effectively extract knowledge from massive data sets.As an important technology of data mining,clustering is used to find some potential groups in data according to a certain criterion.The data objects in these groups have higher similarity,they are also called clusters.As an unsupervised method for identifying potential patterns from data sets,cluster analysis has been widely used in many fields such as anomaly detection,data compression,computer vision,and artificial intelligence,and so on.Document clustering also plays an important role in cluster analysis.Currently,there are many methods for document clustering.K-means is a centroid-based partitioning method.Because it is simple to implement,easy to understand,and has low time complexity and is suitable for large-scale parallel computing,it has been applied in many practical applications and proved to be effective,and can get good clustering results.However,the traditional k-means algorithm has some limitations.For example,the random selection of the initial cluster centers affects the clustering results and is sensitive to isolated points.For limitations above,two improved algorithms are proposed in this paper:Sensitive to initial clustering centers:based on the principal of minimizing the sum of squared error to the most extent,present an optimized k-means method on selecting initial clustering centers.At the phase of initial selecting clustering centers,When Adding a clustering point each time,compute reduced sum of squared error of each point and select the point that can maximize the square of the reduced error.Using real datasets from UCI repository and compared with the results of other algorithms,the experimental results show the number of iteration is reduced on selecting initial clustering centers,so the time overhead in the process of clustering is reduced,as well as increasing F value and the quality of clustering is improved.Besides,artificial dataset demonstrates the method is much less sensitive to isolated points.K-means is sensitive to isolated points in the clustering stage:traditional outlier detection algorithms based on neighborhood usually require additional parameter input.In this paper,the k-means outlier filtering function is implemented by referring to normal distribution.The normal distribution has the following characteristics:The closer the independent variable is to the mean value,the more concentrated the data is distributed.Based on this feature,at the phase of k-means clustering,calculate the sum of distance to the other points from the same cluster.The globally isolated point is far from most of the data points,so distribution of distance sums of isolated points is different from the distribution of distance sums of other data points of the cluster.Simulation data results proves that this method can detect isolated points better.The minSSEKmeans to optimize initial clustering centers algorithm improves clustering results in all tested data sets from UCI repository,compared with traditional k-means method,F value increased about 8%.Besides,the simulation experimental results show that the algorithm avoid to select isolated points as initial clustering centers;On the one hand,the adaptive outlier detection algorithm ndfKmeans on the principal of normal distribution flexibly adjust clustering diameter according to the change of data points belonging to the cluster at the process of clustering,on the other hand,the weight factor of the isolated points is set up to measure the possibility of the outlier.The simulation data shows that the method can discover the isolated point adaptively and raise the clustering quality of the k-means.After then,the improved method is applied to document clustering.The Chinese text corpus which has been divided into 7 categories is from ICTCLAS project.Compared to traditional k-means,the clustering result shows the all clustering evaluation indicators are significantly improved(including precision indicator,recall indicator and f value),F value increased about 10%.After document clustering,get the clustering description according to the importance of lemma to the cluster. |
