K-means算法是一种重要的聚类算法，在网络信息处理领域有着广泛的应用。由于K-means算法终止于一个局部最优状态，所以初始类中心点的选择会在很大程度上影响其聚类效果。本文提出了一种K-means算法的改进算法，首先探测数据集中的相对密集区域，再利用这些密集区域生成初始类中心点。该方法能够很好地排除类边缘点和噪声点的影响，并且能够适应数据集中各个实际类别密度分布不平衡的情况，最终获得较好的聚类效果。

K-means is an important clustering algorithm. It is widely used in Internet information processing technologies. Because the procedure terminates at a local optimum, K-means is sensitive to initial starting condition. An improved algorithm is proposed, which searches for the relative density parts of the database and then generates initial points based on them. The method can achieve higher clustering accuracies by well excluding the effects of edge points and outliers, as well as adapt to databases which have very skewed density distributions.