| In the era of big data,as the rapid development of the Internet,online document information increase rapidly.The Web is the most main database,and the text is holds the lion's share of the information carrier in the Web.So how to extract the information users really require from vast amounts of Web text information,has become a hot topic today.And so automatic text classification technology as one of the most fundamental and important information processing methods,has aroused wide attentions and become an advanced research hot.K Nearest Neighbor algorithm(KNN)has be applied ever since because of its clear concept,good robustness,high accuracy and recall rate.And at the same time it has been proved to be one of the best text categorization methods under the vector space model(VSM).However,as a lazy algorithm,it also has some disadvantages:first,if the training sample set is too large,KNN algorithm's cost on calculation would be too large,and its efficiency would decrease obviously;Second,under the uneven distribution of training sample set,class imbalance would appear easily,and make classification accuracy fallen.As to the problems of KNN algorithm mentioned above,this paper proposes two goals:one is reducing the computing cost under large scale of training samples;the other is improving the classification accuracy under imbalance samples.First,as to the problem that the training sample set is too large,an improved KNN algorithm,based on K-Means clustering(KCKNN)is proposed.KCKNN does clustering in each category and chooses the samples in the clusters whose cluster center vectors have higher similarities with the test sample as samples in the new training samples set.Improved algorithm can choose the most representative training samples in each category for different test samples,so as to achieve the aim of cutting the training sample set,and obviously reduce the time on classification with guaranteeing the classification accuracy.The experiment results show that,the improved algorithm can obviously cut down the computing cost while keeping the good classification accuracy.Second,for the problem that training sample set's uneven distribution raises class imbalance,the paper puts forward another improved KNN algorithm(IWKNN),which use a new weighting decision based on the average distance of category and the sample quantity of category.The average distance of category refers to average distance between samples in the category;the sample quantity of category can reflect the category's probability of being selected.Refining the weight decision of KNN algorithm according the two points above,can efficiently avoid class imbalance and improve the classification accuracy.The experiment results show that,the improved algorithm can obviously improve the classification accuracy when the sample set is imbalanced.In the end,we make a conclusion and indicate the following study issues on KNN algorithm applying in automatic text classification. |
