随着动态主机配置协议(DHCP)等机制的广泛应用,许多互联网服务提供商为其客户分配定期更改的动态IP地址,为用户流量的长期追溯带来诸多挑战。DNS访问记录反映了“人”对站点的访问行为,若将其放大到较大时间范围内,其中又蕴含了网络用户的访问意图与访问习惯。因此DNS访问记录在追溯用户行为方面处于有利地位,且它在现实中更易获得,便于我们进行存储以供长期分析。如果收集某个用户大量的DNS访问记录进行行为挖掘,发现这些行为的模式,就可满足用户识别、用户分析等应用需求。因此,我们需要寻找利用DNS流量进行用户行为追溯的可能性。本课题提出一种基于改进的半监督k-means机器学习算法进行用户行为追溯的方法,并设计了一种用户行为追溯系统。该系统可以基于采集的DNS流量数据,利用改进的半监督k-means方法对用户的行为模式进行挖掘分析,在用户IP地址不断变化的场景下完成用户识别,进而支持用户长期的DNS流量采集,从而在有限的数据场景下最大程度实现用户行为的追溯。本课题的主要工作包括两个方面:1)提出了一种利用改进的k-means算法进行用户行为追溯的方法,包括基于域名访问行为的特征向量构建方法,基于等簇划分的改进k-means算法,基于多初始化的最优结果选择算法三个方面。2)基于上述方法,设计并实现了一个基于改进的k-means算法追溯用户行为的系统。系统主要由服务器端、数据存储部分以及Web展示端组成。其中服务器端包括数据采集模块、数据处理模块、改进k-means模型算法模块。可以周期性采集用户的DNS流量,经过过滤处理、算法训练等步骤实现对不同用户各自的流量的划分。实验结果表明,改进的半监督k-means算法可以在少部分用户范围内表现出较高的准确度。