K-近邻、K-均值及其在文本分类中的应用

K-均值(K-means)算法聚类的结果依赖于距离度量的选取。传统的K-均值算法选择的相似性度量通常是欧几里德距离的倒数，这种距离通常涉及所有的特征。在距离公式中引入一些特征权参数后，其聚类结果将依赖于这些权值，从而可以通过调整这些权值来优化聚类效果。由于K-均值算法是迭代算法，很难直接确定其权值以优化聚类结果，因此提出了一种间接的学习权值算法以改进聚类结果。从数学意义上讲，这种权值学习相当于欧氏空间中对一组点进行了一个线性变换。 针对K值的学习，本文初步使用了遗传算法选择较优的K值，同时总结了一种聚类有效性函数，数值实验证实了其有效性，旨在指导应用于K-近邻分类中；然后还将“扩张能力”的概念引入K-近邻算法，根据训练集例子不同的覆盖能力，删除冗余样本，得到数量较小同时代表类别情况又比较完全的新的训练集，从而降低查找近邻复杂性。 基于以上的研究思想，本文提出了近邻算法在文本分类中的应用，对英文数据库Reuters-21578实现了分词以及分类的过程，并将特征权值的学习思想应用在文本分类中，同时对中文文本的分词做了初步分析与实验。