基于K_means聚类算法的校园网用户行为分析研究

1、第 31卷第 6期 2010年 6月 微 计 算 机 应 用 M I CROCOMP UTER APP L I CATI O NS Vol 131No 16Jun 12010基于 K -m ean s 聚类算法的校园网用户行为分析研究3丁 青 1 周留根 2 朱爱兵 1 张义东 1(1南京农业大学工学院网络中心 南京 210031 2南京农业大学研究生院 南京 摘要 :利用数据挖掘相关技术 , 针对后台计费服务器的数据库 , -分析 , 提出了几个校园网用户行为分析的模型 。 , 满足校园网用户个性化需求 方面提供理论依据 。数据挖掘 s Research of Custo m er Beha

2、v i or Ana lysis I n Cam pus NetworkBa sed on K -m ean s C luster i n g A lgor ith mD ING Q ing 1, Z HOU L iugen 2, ZHU A ibing 1, Z HANG Yidong 1(1Net Center, College of Engineering, Nanjing Agricultural University, Nanjing , 210031, China,2Graduate School, Nanjing Agricultural University, Nanjing

3、, 210095, China Abstract:The paper p resents s ome models f or cust omer behavi or analysis of ca mpus net w ork based on data m ining technol ogy, which is constructed by clustering analysis of backgr ound charging server database with behavi or characteristic of high -school cust omers based on K

4、-means algorith m 1The model can p r ovide good theoretical support for net w ork ad m inistrat ors t o design effective manage 2ment strategy t o meet individual require ments of high -school cust omers 1Keywords:data -m ining, cust omer behavi or, clustering algorith m, K -means用户行为主要是指用户在使用网络资源时所

5、呈现出来的规律 , 可以用某些特征量的统计特征或特征量的关联关系定量或定性的表示 1。 而校园网用户行为的使用情况 、 行为特征更有其独特之处 。如今 , 通过相关数据挖掘技术来分析校园网的用户行为 , 合理分配带宽 , 提高用户使用网络的效率己成为校园网络管 理的一个重要课题 2。目前国内的很多高校在校园网的运营管理上 , 都会使用一些应用服务器 , 主要用于认证计费 、 入侵检 测 、 流量监控等方面 。 在提供服务的同时 , 也产生了大量的日志数据存储于后台数据库中 。在这些数据中 , 不仅包含着整个校园网内部用户的使用状况 , 也记录了网络运行的全部信息 。 如果能对这些数据进行科学

6、有效分析 , 并对分析结果加以合理利用 , 将会对整个网络管理起到很大的推进作用 。我院从 2006年开始基于认证上网 , 现有的认证计费服务器的后台数据库提供了相当丰富的数据资源 。 以此为基础 , 运用数据挖掘技术 , 以校园网用户的上网数据为对象进行聚类分析用户上网的行为特征 , 有效 的概括出若干个用户上网行为模型 , 从而全面的描述全院校园网的用户使用及网络运行状况 。这对于全面 了解校园网用户的行为特征和校园网络的使用状况 、 及时调整网络带宽分布 、 改善校园网络性能和应用效 本文于 2010-03-18收到 , 2010-05-18收到修改稿 。3基金简介 :江苏省农机局科研启

7、动基金 (GXS06016 。 6期 丁 青 等 :基于 K -means 聚类算法的校园网用户行为分析研究 率等都具有重要作用 。1 聚类分析的理论基础聚类 (Clustering 是数据挖掘中一种重要的挖掘方法 , 它是将物理或抽象对象进行分组并将相似对象归为一类的过程 3。 聚类分析将物理的或抽象的对象分为几个群体 , 在每个群体内部 , 对象之间具有较高的相似性 , 而在群体之间相似性则比较低 。聚类算法大体可以划分为以下几类 :划分方法 、 层次方法 、 基于密 度的方法 、 基于网格的方法和基于模型的方法 。 在各种方法里面都有其各自具有代表性的算法 。在本文所 做的工作中 , 采

8、用了分裂法当中的 K -means 算法 。K -means 算法属于聚类方法中的一种划分方法 , , 适合处理大文 档集 。 K -means 算法将一组物理的或抽象的对象 , 构成一组 。 , 而不同聚类中的对象相 似度较小 。111 K -m ean s 该算法形式可以描述为 :已知 d 维空间 R d , 在 R d 中定义一个评价函数 E:p:PC R +, 给每个聚类一个量化的评价 , 输入 R d 中的对象集合 C 和一个整数 k, 要求输出 C 的一个划分 :C 1, C 2, C k , 这个划分使得评价函数 E 最小化 。 不同的评价函数将产生不同的聚类结果 , 一般我们采

9、用均方差作为评价函数 , 定义 如下 :【 6】E = k i =1 PEC i |p -m i |2上式中 , E 为数据库中所有对象的平方误差的综合 , p 为 R d空间的点 , 表示给定的数据对象 , m i 为簇 C i 的平均值 (p 和 m i 都是多维的 , |p -m i |2表示数据对象与聚类中心之间的距离 。此评价函数使所获得的 k 个聚类具有以下特点 :各聚类之间本身尽可能紧凑 , 而各聚类之间尽可能 分开 。112 K -m ean s 算法过程K -means 算法主要有三个过程组成 :首先是选取初始的聚类中心 , 其次是样本点分类 , 最后是聚类中 心的调整 ,

10、其中后两个过程迭代交替进行 。 下面是 k -means 算法的流程描述 :输入 :簇的数目 k 和包含 n 个对象的数据库 。输出 :k 个簇 , 使平方误差准则最小 。方法 :Step1 任意选择 k 个对象作为初始的簇中心 ;Step2 对于所剩下其它对象 , 则根据它们与这些聚类中心的相似度 (距离 , 分别将它们分配给与其最 相似的聚类 ;Step3 重新计算每个 (有变化 聚类的均值 , 根据新的每个聚类对象的均值 , 计算每个对象与这些新聚 类中心对象的距离 , 并根据最小距离开始收敛为止 ;Step4 循环第 3步 until 不再发生变化 。如图 1所示 , 当 k =3时

11、, 即需要将数据对象 C 聚类为 3个簇 , 根据以上算法描述 , 任意选择 3个对象作 为 3个初始簇中心 , 簇中心在图中用“ +” 来标注 。根据与簇中心的距离 , 每个对象被分配给最近的一个 簇 , 这样的分布形成了虚线所描绘的图形 。面对大规模数据集 , 该算法是相对可扩展的 , 并且具有较高的效率 。算法复杂度为 O (NK t , 其中 , N 为 数据集中样本的数目 , K 为期望得到的簇的数目 , t 为迭代的次数 。 57 微 计 算 机 应 用 2010 年 图 1 基于 K -ME ANS 算法聚类过程 2 数据准备211 理解数据, 日常的用户日志数据主要存于登录记录

12、数据库中 U ser_log 表中 , , 它的主要结构如表 1所示 :表 1 User_log表结构字 段名 称 类 型 长 度 备 注 TRAN I D流水号 I nt ACCOUNT账号 STR I N G 50校园网用户账号 LOG ON_TIM E登录时间 DATE LOG OUT_TIM E注销时间 DATE USED_TIM E使用时长 (M I N LONG I P_ADDRESSI P 地址 STR I N G 15F LOW _DOWN使用流量 (MB Double 小数点后三位 CHARGE收费 (RMB Double 小数点后两位 USERNAME 用户名称String

13、 20 要研究校园网用户的上网行为 , 就必须先建立一个能反映用户特征的多维数据特征项 , 用户日志数据 表中提供的 23个字段成为分析校园网用户行为的基础 , 在仔细考察各项参数后 , 确定用户行为特征项为 tranid 、 Logon_tim e 、 Logout_ti m e 、 U sed_ti m e 、 Fl ow_up、 I p _address,分别为流水号 , 用户登陆时间 , 注销时间 , 使 用时长 , 上行流量 , I P 地址 6项数据 。以提取单月的日志数据为例 , 由于用户登录日志中主要记录的是每一次登录时的用户行为数据 , 也就 是说同一用户对应着多条登录记录

14、。 所以要实现对全校园网用户的整体分析 , 必须按照登录上来的 I P 地址 进行聚合统计 。 同时要实现对某用户月使用流量的分析 , 必须提取他的 Fl ow_up(使用流量 字段 , 并进行累 加 ; 而对在线时长的分析主要是提取 U sed_tim e (每次在线时长 字段 , 并将该用户一个月内所有使用时长累 加起来并除以该月天数 。 由于以上的数据分析工作都是根据关键字 I P 地址进行提取 , 所以原日志内用户每 一次登录的登录时间和注销时间便失去意义 。接下来我们主要是利用使用时长和月均流量对用户行为进 行聚类分析 , 看是否能产生具有代表性的用户行为模式 。212 利用 SQL

15、 2005的 ET L 工具对用户数据进行处理我们依然从日志数据库中抽取一个月的数据 , 以 2009年 6月为例 , 该月用户登录日志达 215681条数 。 根据生成数据的要求 , 我们只需要三个字段 , I P_ADDRESS (I P 地址 、 USED_HOUR(每天在线时长 、 F LOW _67 6期 丁 青 等 :基于 K -means 聚类算法的校园网用户行为分析研究 S UM (流量和 。 213 利用数据流处理数据过程我们设计了如图 2的一个数据流 , 并通过 S QLSever 2005的 SSI S 工具生成了聚类分析所需要的数据 , 形 成了聚类的初始输入文件 ,

16、命中的记录数为 3381行 , 也就说明在 6月份活跃的 I P 数达到了 3381条 , I P 地址 作为该聚类文件唯一性的关键字段。 图 2 数据流过程通过 ET L 工具我们将符合以上条件的用户行为数据进行抽取 4, 最终获得训练用户样本数据 3381条 , 准备做样本的模型的建立 。 3 调整算法参数由于 K -means 算法是属于硬聚类 , k 果 5。 在 S , 关键参数 :311 C luster i n g_M ethod 参数该参数指出使用哪一个算法来决定聚类的成员 , 根据我们所选的算法选择 3。(1 可伸缩的 E M 算法(2 普通的 (不可伸缩的 E M 算法(3

17、 可伸缩的 K -means 算法(4 普通的 (不可伸缩的 K -means 算法312 C luster_Count 参数该参数是指 K -means 算法中的 k 值 , 它指出聚类算法要找出多少个聚类 , 如果将这个参数的值设为 0, 则聚类算法将会在数据中启发式地猜测合适的聚类个数 。经过对比和调整我们最终选择 k =3, 这样的分类最为独立 。4 生成并理解聚类模型 聚类非常适合于按属性的分数提取数据并且把数据进行分组 。 因为每一个聚类不能被看作是相互独立的 , 所以理解最后得到的分组可能比较困难 , 聚类只有与所 有其他聚类联系起来才可以理解 。 而在 S QL Server

18、Analysis Server 提供了一个查看器 , 该查看器有 4个以选 项卡形式出现的聚类视图 , 分别是分类剖面图视图 、 分类关系图视图 、 分类特征视图和分类对比视图 。通过 这几个视图我们可以对聚类结果有比较好的理解 。(1 分类关系图视图该图直观的显示分类之间的强弱连接 , 可以看到三个分类之间连接强度各异 , 较强连接的分类中参数 之间确实有很多相似之处 , 这里最强的两个连接是分类 1与分类 2。(2 剖面图和特征图通过这两种图我们可以根据输入的参数了解所得到每个分类的基本信息 。通过这两种图我们可以根 据输入的参数了解所得到每个分类的基本信息 。 从图 3可以看出三种分类各

19、占据不同范围的区间 , 直观地 可以看出分类 1的各项字段的值范围较小 , 而分类 2处于中间 , 分类 3则数值范围较大 。77 微 计 算 机 应 用 2010 年图 3(3, 我们可以将 分类 1和分类 2做一下对比 。图 4 强连接分类之间的对比可以看出这两个聚类中最具差异性的就是 Fl ow Su m 与 U sed Hour 参数 , 分类 1的 Fl ow Su m 参数更多倾 向于 (0, 9 区间 , 而分类 2则数值更大 , 处于 (9, 571 区间 ; 分类 1的 U sed Hour 参数倾向于 (0, 416 区间 , 而 分类 2则处于 (416, 23 区间 。

20、411 聚类结果通过这样的比较 , 我们得出在我院校园网中用户行为主要有三种表现形式 :第一种行为模型 :计 1876条 , 占到总体的 5515%, 每天上网时段通常会持续 300分钟以内 , 这一类用户 的月均使用流量约为 010G 以内 。第二类用户行为模型 :计 1470条 , 占总体的 4315%, 每天上网时段通常在 10-20个小时以内 , 这类用户 的网络使用流量约为 8G -100G 以内 。第三类用户行为模型 :计 35条 , 占总体的 1%, 每天上网时段通常超过 20个小时 , 这类用户使用流量约 为 100G 以上 。可以看出第一第二类用户无论是相似度或是关联度都非常

21、强 , 第三类用户则与其他类距离较远 。得出 这样的结果 , 非常有利于网络管理者制定相关的流量计费策略以使网络带宽得到最高效率的利用 。412 聚类结果分析我们的校园网用户账号分类主要分成学生用户和教工用户 , 通过聚类算法我们得出校园网的三种用户 行为模型 , 为了进一步探究各类模型的用户组成 , 我们利用数据钻取功能读取出每类用户具体数据 。由于 我院学生的 I P 地址利用 NAT 技术进行了地址转换 , 这类用户都是使用了 172116/12专用地址段的地址 。 87 6期 丁 等 : 基于 K - means聚类算法的校园网用户行为分析研究 青 79 而教工用户的 IP地址则从属于

22、 21118711 /21 这个地址块 ,所以根据 IP 地址我们就可以抽取出相应的数据 集 ,见表 2。 表 2 三种分类中学生和教工数据的占用比例情况 百分比 分类 2 1224 246 分 类 学生 教工 合计 分类 1 1525 351 百分比 分类 3 0 百分比 1876 从表中我们可以看出分类 1 和分类 2 中学生用户占了大多数 ,在分类 3 中 ,则全由教工用户组成 。同时 通过统计 ,分类 2 中学生和教工用户每天使用时长相似 ,但月使用流量非常迥异 ,学生的月使用流量基本在 8 - 11G。而对应的教工用户月使用流量普遍在 10G以上 ,最多的用户达到 97G。如果对分类

23、 2 再次进行聚 类 ,应该会发现更多的用户模型 。 教工用户账号中还分成办公区账号 、 电子阅览室账号 、 南苑家属区账号 ,而实际上办公区网段中除了各 系部和机关办公室 ,还包含部分研究生实验室 。我们在对各个分类中教工用户进行再次分类统计 , 看占用 比例情况如何 。 表 3 三种分类中教工各种用户占用比例情况 百分比 23% 47% 30% 教工分类 分类 1 81 南苑家属区 办公区 165 105 351 电子阅览室 总计 在表 3 中 ,可以看出各类用户绝大多数还是分属于分类 1 和分类 2 ,只不过占有比例略有不同 , 而在分 类 3 中 ,有家属区和办公区用户组成 。电子阅览

24、室由于只有白天工作时间开放 , 不能达到每天在线时长 20 小时以上 ,则不属于第三类用户模型 。 而分类 3 中命中的用户主要还是办公区的实验室用户和少量的家属区用户 ,这两种用户在线时间过长 , 月使用网络流量过多 ,说明该用户对网络有上瘾倾向 ,要引起关注 ,对其制定相对严格的上网行为管理策略 。 综上所述 ,从聚类实验的结果我们可以看出 ,同类之间的距离较小 ,而不同类之间的距离较大 ,符合“ 聚 类” 的最终目标 ,而这样的知识发现就使得网络管理者可以对不同类的用户制定不同的网络应用策略 ,使得 带宽能到最为合理有效的利用 。 5 结束语 将 K - means聚类算法应用于校园网用户行为分析是一种新的尝试 ,它的聚类结果可以给网络管理人 员对用户的行为有所了解从而考虑制定相应的网络策略 。 K - m eans算法的优点是对属性类型没有局限性 , 6 而且通过簇内主要点的位置来确定选择中心点 ,对孤立点的敏感性小 。不过 K - m eans算法存在一个缺 陷 ,就是用户必须事先指定聚类 k 的个数 ,如果聚类个数定义不准确将会使聚类结果不合理 。 本文中所使用的南京农业大学工学院认证计费系统后台数据库目前已经大面积的推广 ,记录涉及全院 用户 。因此下一步的工作是进一步细化 ,对数据进行更多时间维度的分析 ,以此对用户数据全面进行统计 , 制定更加