辛 壮，万 良，李均涛

(1.贵州大学 计算机科学与技术学院，贵州 贵阳 550025;2.贵州财经大学 信息学院，贵州 贵阳 550025)

1 概 述

现阶段，计算机网络已经基本实现全球化，庞大的网络体系方便了信息的交流与传递，但是也给网络黑客提供了更多的便利。面对着越来越复杂的网络环境、灵活多变的网络攻击手段，如何快速、准确地识别网络异常行为，并减轻异常行为对网络环境的破坏具有非常重要的意义。对此，专家学者们将数据挖掘技术应用到检测技术中，依靠无监督、半监督的方式快速准确地识别异常、非异常行为，这也是当前的研究热点之一[1-2]。

K-means作为传统的聚类算法，能够对大量的数据进行快速聚类，较好地符合了网络异常行为检测的实时性要求。K-means算法能够对无标记的数据样本进行有效聚类，相比于有监督的方法能够大大减少标记时间并且降低数据开销。国内外不断有学者将聚类算法与分类算法相结合的半监督学习方式应用于异常行为检测，例如，Zhang等[3]分析了半监督学习方式对于聚类效果的影响，Erman等[4]将半监督学习方式应用到流量分类中，并且验证了半监督学习方式对于网络流量分类的有效性。

传统的K-means算法虽然简单有效，但需要事先确定k值，并且算法对于噪声敏感。为了克服K-means算法的不足，许多专家学者都曾试图从各个角度对K-means算法进行改进与优化。文献[5]提出了一种快速的最小生成树算法，该算法与K-means算法结合使用能够快速处理大规模数据集。……