基于变宽直方图的无线传感器网络异常数据检测算法

基于变宽直方图的无线传感器网络异常数据检测算法 1 1 2姜旭宝 ,李光耀 ,连 朔 ( )1. 同济大学 计算机科学与技术系 ,上海 201804; 2. 西安交通大学 计算机科学与技术系 ,西安 710049 ()08 jxb@ tongji. edu. cn ()摘 要 :数据的准确性是衡量无线传感器网络 W SN 性能的重要指标 ,异常数据检测是无线传感器网路面临的 关键问题和主要挑战 。提出了一种基于变宽直方图的异常数据检测算法 ,通过数据聚合的方式将网络中的动态感知 数据聚合成变宽的直方图来准确检测出异常数据 ,同时避免不必要的数据传输 。对算法的性能进行了理论 ,并 基于真实大规模无线传感器网络系统数据进行了实验评估 ,结果表明算法具有很高的准确率 ,并有效降低了网络通 信开销 。 关键词 :无线传感器网络 ;异常检测 ;直方图 中图分类号 : TP311. 13 文献标志码 : A O u tl ier de tec t ion a lgor ithm ba sed on va r ia b le2w id th h istogram for w ire le ss sen sor n e t work 1 1 2J IAN G Xu2bao, L I Guang2yao, L IAN Shuo (1. D epa rtm en t of Com pu ter S cience and Technology, Tong ji U n iversity, S hangha i 201804, Ch ina; )2. D epa rtm en t of Com pu ter S cience and Technology, X iπan J iaotong U n iversity, X iπan S haanx i 710049, C h ina A b stra c t: The accu racy of sen so r da ta is a c ritica l index to eva lua te the p e rfo rm ance of W ire le ss Sen so r N e two rk ()W SN . O u tlie r de tec tion is a c ruc ia l bu t cha llenging issue fo r W SN. In th is p ap e r, an ou tlie r de tec tion app roach ba sed on va riab le2w id th h istogram wa s p ropo sed. The dynam ic sen so r da ta we re aggrega ted in to va riab le2w id th h istogram s, wh ich avo ided unnece ssa ry da ta tran sm ission s wh ile de tec ting ou tlie rs. The theo re tica l ana lysis and eva lua tion on rea l W SN da ta se t show tha t th is app roach ha s h igh de tec tion accu racy, and the co st is effec tive ly reduced. () Key word s: W ire le ss Sen so r N e two rk W SN ; ou tlie r de tec tion; h istogram 提出过很多种方法 ,这些方法可以分为基于统计学的方法 、基 0 引言 于最近 邻 居 的 方 法 、基 于 分 簇 的 方 法 和 基 于 聚 类 的 方 法 ()[ 5 ] [ 6 ]无线传感器网络 W ire le ss Sen so r N e two rk, W SN 是由大 等 。 Pap ad im itriou等人 提出了一种基于多粒度偏差因子 量细小的传感器节点组成的多跳自组织网络系统 ,其目的是 () 的 LOC ILoca l Co rre la tion In tegra l算法 ,能够检测出基于密度探测感知 、采集和处理外界环境中的各种数据信息 ,并发送给 [ 7 ]的异常数据 ,具有较高的检测率 。 J anak iram 等人 考虑到了 [ 1 ] 观察者 ,在环境监测 、灾难预警等领域能 够发挥很大的作 同一节点的不同属性之间具有相关性 ,提出了利用贝叶斯信 [ 2 ]用 。 GreenO rb s是用于森林生态监测的长 期大规模无线传 任网络来检测无线传感器网络中的异常数据的方法 。 [ 3 ] 感器网络系统 , 其应用包括森 林郁闭度测量 、森林火灾风 [ 8 ]Sheng等人 提出了基于等宽直方图的异常数据检测算 险评估等 。精准的林业测量和林业研究对数据的准确性和可 法 ,通过收集直方图信息 ,利用一定的判断规则过滤掉正常数 靠性的要求非常高 ,但是由于传感器节点资源有限 、处理能力 据 ,再进行多次查询的方式来获得无线传感器网络中的全局 非常弱 ,而且长期部署于外部世 界 ,容易受 到环境因素 的 干 异常数据 。与传统的集中式查询方法需要收集网络中的全部 扰 ,无线传感器网络很容易出现各种故障 ,收集到一些错误数 数据相比 ,该方法给网络带来的通信开销较低 。 据 。这些错误的数据不仅增加了网络的通信开销 ,浪费了有 基于等宽直方图的方法虽然对网络造成的开销较低 ,但 限的能量 ,而且还会使观察者产生错误的判断 ,严重降低了无 它忽略了直方图的相邻高频区间具有相同特性 ,造成了不必 线传感器网络的系统性能 。异常数据检测有助于发现那些不 要的冗余数据传输 。本文提出了一种基于变宽直方图的全局 可靠的数据 ,是无限传感器网络的一项重要研究内容 。 异常数据检测方法 ,在收集直方图的过程中动态合并满足一 在无线传感器网络中 ,如果一个节点的测量数据明显背 [ 4 ] 定条件的相邻区间 ,进一步减少数据传输 ,降低了通信开销 。离于该点的正常值 ,则称该数据为异常数据 。异常数据分 为局部和全局异常数据 ,局部异常数据是指那些与其邻居节 点的数据存在很大不同的数据 ,而全局异常数据是指那些与1 背景知识 网络中的全部其他数据存在较大差别的数据 。 针对无线传 1. 1 问题描述 感器网络中的异常数据检测问题 ,目前已经 在统计学中 , 异常数据有很多不同的定义 , 本文采用基于 [ 9 ] 距离的定义 , 即两个数据之间的 差值的绝对值 。假设网络 收稿日期 : 2010 - 09 - 06; 修回日期 : 2010 - 11 - 10。 ( ) ( ) 作者简介 :姜旭宝 1987 - ,男 ,安徽池州人 ,硕士研究生 ,主要研究方向 :计算机仿真 ; 李光耀 1965 - ,男 ,安徽安庆人 ,研究员 ,博士生 ( ) 导师 ,主要研究方向 :计算机仿真 ; 连朔 1982 - ,男 ,河南安阳人 ,博士研究生 ,主要研究方向 :普适计算 、无线传感器网络 。 695 第 3期姜旭宝等 :基于变宽直方图的无线传感器网络异常数据检测算法 ( ) } , | p- p| 表示 p和 p中的数据集合为 P: { p, p, , p,间 i内的数目 , f i, j表示节点 n在区间 i中的数据摘要信 i j i j1 2 i j ( ) ( ) 息 。如果 n是叶子节点 , f i, j= g i, j。如果 n是非叶子节 jjp, 将 P中其余的数据按与 p距离递增之间的距离 。对于数据 i i ( ) ( ) ( ) ( ) 点 , 那么有 f i, j= g i, j+ fi, j, 其中 fi, j是 nc c j ?的顺序排列成 P ′: { p′, p′, , p′,- p| ?} , 即满足 | p′ 1 2 k i 1( ) 的子节点在区间 i中的数据摘要信息 。如果 f i, j> k, 为了 | p′- p| ? ?| p′- p| ? 。 2 i k i ( ) 降低通信开销 , 设 f i, j= k + 1。 ( 定义 1 对于数据 p, 设 p是距离p第 k 近的邻居 K k ) N ea re st N e ighbou r, K2NN , 则 p和 p之间的距离 | p- p | 称 k k 合并过程当节点汇总完其所有的子节点的数据摘要 ( ) 为 D k, p。, 如 果 发 现 存 在 两 个 相 邻 的 区 间 i 和 i + 1, 满 足信息后 ( ) 定义 2 对于数据 p, 如果 D k, p? d, 那么称 p是一个( ) ( ) f i, j> k且 f i + 1, j> k, 那么就将这两个区间合并为一 ( ) O d, k 型异常数据 , 其中 k和 d是给定的参数 。 本文假设( ) 个新的区间 i′, 并设置新的区间的数据摘要 f i′, j= k + 1。 在由 n 个节点组成的无线传感器网络中 , 路由 如果非叶子节点在汇总其子节点信息时 , 发现存在已经 协议是一棵有向汇聚树 , 所有的节点通过路由树定期向 Sink合并过的区间 , 那么它将采用合并过的区间分布 , 重新更新直 节点发送感知数据 。为计算方便 , 所有的数据将转换成整数 ,方图信息 。这一步的算法用伪代码描述如下 。 对于一定的参数 k和 d, 要求算法能够查找出所有满足定义的w = d; ( ) O d, k 型异常数据 。fo r each node j and bucket i if j is a leaf node 1. 2 直方图查询方法 [10 ] ( ) ( )f i, j= g i, j 直方图是一种统计报告图 ,是一种重要的数据查询工具 。 else 其构造过程如下 :对于数据分布 S,将其划分成 n个不相交的子集 ( ) ( ) ( )f i, j= g i, j+ fi, j?c ( ) A。在平面?A i = 1, 2, , n, 使得其满足 S = A? A? n i 1 2 end if 直角坐标系中 ,直方图的横轴表示每一个子集的取值范围 , 纵轴 ( ) ( ) if exists f i, j> k and f i + 1, j> k 表示数据位于该子集内的频数 。 将直方图表示方法应用到无 m e rge bucket i, i + 1 to a bucke t i′ ( ) 线传感器网络中 ,有助于分 f i′, j= k + 1 end if 析网络的数据分布 。大部分正常数据将集中在直方图的若干 end fo r 区间内 ,而异常数据则落入到一些低频的区间 。同时 ,在网络 2. 3 判断数据状态中采集直方图信息而不是节点的原始读数 ,由此带来的通信 在收集完变宽直方图后 ,将根据直方图的区间分布状况 开销将大大降低 。 来判断网络中的读数的状态 :正常或异常 。 等宽直方图的各个区间的宽度相等 ,本文根据直方图中 对于区间 i, 如果宽度 w = d, 本文分两种情况来考虑 。 i 满足一定条件的相邻高频区间为正常数据这一特性 ,将其合 ( ) 第 1种情况 如果区间 i的频数 f i> k, 那么对于区间 i中并成一个区间 ,从而形成了动态可变宽的直方图 ,这将有助于 的任一数据 p, p的 K2NN邻居 p一定同样落在区间 i内 , 那 k 进一步减少通信开销 ,将重点关注在那些低频的异常数据区 ( ) 么 D k, p= | p - p| < w = d, p不是异常数据 , 该区间内的 k i ( )( ) 间 。图 1中 a和 b分别为等宽直方图和变宽直方图 ,其中数据都是正常的 。 ( )( ) 图 1 b是将图 1 a中的相邻高频区间合并而来 。( ) ( ( ) 第 2种情况如果 f i? k, 那么考虑 Sum f= f i - ) ( ) ( ) 1 + f i+ f i + 1 , 即 将 区 间 i向 左 右 各 延 伸 1 个 区 间 , ( ) ( ) Sum f表示这 3个区间的频数的总和 。如果 Sum f? k, 那 么对于区间 i内的任一数据 p, p的 K2NN邻居一定位于这 3个 ( ) 区间以外 , 设在区间 j内 , 则有 | j - i | ? 2, 因此 D k, p? ( ) ( ) w = d, p是一个 O d, k型的异常数据 。如果 Sum f> k, 那 i 么 p的 K2NN 邻居位于这 3个区间内 , 则暂时无法判断数据 p 图 1 两种直方图查询方法 的状态 , 称之为潜在异常数据 。 如果 w > d, 即该区间的宽度比初始的宽度要大 , 表明该 i 2 算法介绍 区间是在收集直方图的过程中合并了多个区间而形成的 , 这 2. 1 获取数据集取值范围 ( ) ( ) 个区间的频数 f i都满足 f i> k, 该区间内的数据都是正 常的 。为了构建无线传感器网络中数据分布的直方图 , 需要知 对于异常和潜在异常的区间 , Sink节点将向网络中发出 道数据集的取值范围 。Sink节点向网络中发出广播查询 , 以获 得所有节点的读数中的最小值 V和最大值 V。 广播查询 ,每个节点将自己的读数中所有位于这些区间的读 m in m ax 2. 2 收集动态可变宽直方图数回传到 Sink节点处 。 在这一步中 , 本文设定直方图的初始宽度 w = d。每个节 2. 4 判定潜在异常数据状态 点在收到 Sink的查询请求后 , 首先确认自己的历史数据是位 对于那些潜在异常数据 , 需要在网络中重新验证其是否 于直方图的哪一个区间 , 然后所有叶子节点向其父节点发送 ( ) 属于 O d, k型的异常数据 。考虑到如果数据 p是异常的 , 那 i 它的直方图信息 。当非叶子节点收到它所有的子节点的直方 ) ( 么 D k, p? d, 则与 p的距离在 d以内的数据个数一定小于 i i 图信息后 , 需要进行汇总和合并两个过程 。 k, 所以对于每一个潜在异常数据 , 只需在网络中查询与其距 汇总过程( ) 设 g i, j表示节点 n的读数中所有位于区 ( ) 离在 d以内的读数的个数 f′i。j 696 计算机应用第 31卷 按照第 2章所介绍的算法 ,在 V isua l Stud io 2008 环境下采用Sink节点 将 向 网 络 中 广 播 所 有 的 潜 在 异 常 数 据 P: po C#设计实现了程序 , 根据不同的参数 k和 d, 输出符合条件的 ′, p′,{ p} 。每个节点 n在收到广播后检 查自己的历史数 1 2 j ( ) O d, k 型异常数据 。表 1是实验的参数信息 , 其中温度数值 ( ) 据 , 计算与数据 p′距离在 d以内的读数的个数 f′i, j。非叶 i 均按乘以 100处理 。 子节点 n将向其孩子节点广播潜在异常数据 P和附加信息j po 为了验证该算法的有效性 ,本文将实验结 果与文献 [ 6 ] λλλ( ) λλ: {,,} , 如果 f′i, j> k, 则设 = 1; 反之 = 0。 1 2 i i 中提出的 LOC I算法结果进行比较 , 得出本文算法 的检测正 λ= 1表示 p是正常数据而不用继续在下游节点中查询 , 因 i 确率 。检测正确率是指被正确判定为异常数据的个数与总的 i λ( ) 此每个节点将只需计算那些其父节点 = 0的 f′i。最后每异常数据个数之比 。设采用本文算法得出的异常数据集合为 i O , 采用 LOC I算法得出的异常数据集合为 L , 则检测正确率 r ( ) ( ) } 。个节点向上游依次传递并汇总信息 { f′1 , f′2, 的计算公式为 : ( ) ( ) 最终在 Sink节点处 , 对于 f′i, 如果 f′i> k, 那么相应 ( ) 的读数 p就是一个正常读数 ; 如果 f′i? k, 那么 p就是一个 i i 异常读数 。 r = / O ? L L 表 1 实验参数信息 3 性能分析与实验评估 参数 数值 参数 数值 3. 1 性能分析 79 988 数据总个数 d 100 ,300异常检测会给网络带来一定的通信开销 ,本文假定开销 数据的最大值 58 988 k 50 ,500只与传输的数据大小有关 ,下面将分析基于变宽直方图的检 数据的最小值 1 252 — —测方法给网络造成的通信开销 。 本文以算法所产生的数据传输大小来估算通信开销 。传在 2. 1节中 , 每个节点需将其读数的最大值和最小值向 统的集中式查询方法需要预先知道网络中的全部数据 , 由此 上游传递 , 设 V和 V分别代表节点 n及其所有孩子节 m ax+ j m in + j j 造成的相应的通信开销也非常大 。本文分别计算了 文献 [ 8 ] 点的读数的最大值和最小值 , S 为所有节点的集合 , 此处的开 销为 : 中的基于等宽直方图的方法和本文提出的基于变宽直方图的 方法所造成的通信开销的大小 , 结果均以集中式查询方法为 ()C os t = lb V〃V1m ax+ j m in + j ? n ?S j基础 , 并对比两种方法的通信开销差异 。 在 2. 2节中 , 为了收集变宽直方图 , Sink节点将向网络中 3. 2. 2 实验结果传递一些必要的参数 : k、d、V和 V, 同时 , 每个节点将自己 m in m ax 通过设定不同的参数 k和 d, 可以观察检测出的异常数据 ( ) 的直方图摘要信息 f i, j回传到 Sink节点 。N 表示网络中非 n l结果和这两个参数之间的相关性 。实验结果显示 , 当 k 增大时 , ) (叶子节点的个数 , b = V- V/ d, 表示直方图初始的区 m ax m in 异常数据的个数随之增加 ; 当 d 增大时 , 异常数据的个数随之间个数 , 此处的开销为 : 减少 ,如图 2所示 。通过与 LOC I算法对比发现 , 利用本文提出 b ( ) ( )C os t= N 〃 lb k 〃d 〃V〃V+ f i, j的算法能够检测出绝大多数的异常数据 , 具有较高的检测正确 2 n l m in m ax ?? n ?S i = 1 j率 , 而且不同的参数 k和 d,最终的检测正确率也不同 ,如图 3所 在 2. 3节中 , Sink节点向网络中广播直方图的区间状态( ) 示 。O d, k型异常数据与两个参数 d和 k之间的关系很大 , 选 信息 , 收集所有位于异常和潜 在异常区间的具体读数 。D is tp i 表示读数 p距离 Sink节点的路径长度 , P表示所有异常和 择合适的参数 ,将有助于用户发掘正确的异常数据 。i o +po 潜在异常数据的集合 , 这一步的开销为 : C os t= N 〃b + D is t〃lb p3 n l p i? i p ?P o +poi 在 2. 4节中 , Sink节点将向网络中广播所有潜在异常节 点的读数 , 同时节点将向 Sink发送用于判断异常数据的相关 信息 。P表示潜在异常数据的集合 , | P| 表示集合中数据 po po 的个数 , 此处的开销为 : P po ( )+ f′i, j C os t= N 〃 p+P4 n l i ? ??po ) ( p ?P n ?S i =1po ij 图 2 异常数据个数与 k、d 之间的关系 因此 ,整个算法对网络所造成的开销即为上述开销的总 和 。 3. 2 实验评估 3. 2. 1 实验设置 [ 2 ] 本文所用到的实验数据来自于 GreenO rb s无线传感器 网络原型系统 ,该系统部署于某植物园中 ,范围约为 120 m × 80 m ,共有 105个节点 ,节点之间通过多跳广播定期将感知到 的温度 、光照等信息传回 Sink 节点 。本文选择 2009 年 5 月 19日的温度数据 ,共有近 8 万条记录 ,绝大 多数温度处于正 ( ) 常范围内 19 ?C,36 ?C,也存在一些明显错误的数据 。本文图 3 本文算法的检测正确率 697 第 3期姜旭宝等 :基于变宽直方图的无线传感器网络异常数据检测算法 [ 2 ] GreenO rb s R e sea rch Group. GreenO rb s [ EB /OL ]. [ 2010 - 08 - 同时 ,实验结果显示 ,本文提出的基于变宽直方图的方法 12 ]. h ttp: / /www. greeno rb s. o rg. 对网络 造 成 的 通 信 开 销 非 常 小 , 不 到 集 中 式 查 询 方 法 的MO LU FEN G, H E YUAN , L IU YUNHAO , et a l. Canop y c lo su re [ 3 ] 10 % ,如图 4所示 。相比文献 [ 8 ]中的方法 ,基于变宽直方图 e stim a te s w ith GreenO rb s: Su stainab le sen sing in the fo re st [ C ] / / 的方法进一步降低了通信开销 , 而随着 k 的变大 , 该方法所 P roceed ings of the 7 th ACM Confe rence on Em bedded N e two rked 带来的通信开销也进一步变大 。 Sen so r System s. Ca lifo rn ia: ACM P ress, 2009: 99 - 112. CHANDOLA V , BAN ERJEE A , KUMAR V. A nom a ly de tection: A [ 4 ] () su rvey [ J ]. ACM Comp u ting Su rveys, 2009 , 41 3 : 1 - 58. ZHAN G YAN G, M ERA TN IA N , HAV IN GA P. O u tlie r de tec tion [ 5 ] techn iques fo r w irele ss sen so r ne two rk s: A su rvey [ J ]. IEEE Com 2 () m un ica tion s Su rveys and Tu to ria ls, 2010 , 12 2 : 159 - 170. PA PAD MI ITR IOU S, K ITA GAWA H , G IBBON S P B , et a l. LO 2 [ 6 ] C I: Fast ou tlie r de tec tion u sing the loca l co rre la tion in tegral [ C ] / / P roceed ings of the 19 th In te rna tiona l Confe rence on D a ta Enginee r2 ing. B anga lo re: IEEE, 2003: 315 - 326. JAN K IRAM D , R EDD Y V A , KUMAR A V U P. O u tlier de tec tion [ 7 ] 图 4 两种方法通信开销对比 in w irele ss sen so r ne two rk s u sing B aye sian be lief ne two rk s [ C ] / / P roceed ings of the 1 st In te rna tiona l Confe rence on Comm un ica tion 4 结语 System Softwa re and M idd lewa re. D e lh i: IEEE, 2006: 1 - 6. SH EN G BO , L I QUN , MAO W E IZH EN , et a l. O u tlie r de tec tion in [ 8 ] 本文提出了一种基于变宽直方图的无线传感器网络异常 sen so r ne two rk s [ C ] / / P roceed ings of the 8 th In te rna tional Sympo si2 数据检测算法 ,适用于检测出基于距离的定义的全局异常数 um on Mob ile A d Hoc N e two rk ing and Comp u ting. Q uebec: ACM , 据 。该方法的一个显著特点是通过收集无线传感器网络中数 2007: 219 - 228. 据流分布的直方图信息 ,并且动态合并直方图区间改变原区 KNORR E M , N G R T. A lgo rithm s fo r m in ing d istance2based ou tli2 [ 9 ] 间的宽度 ,进一步减少数据的传输量 ,节省了通信开销 。实验 e rs in la rge data se ts [ C ] / / P roceed ings of the 24 th In te rna tiona l 结果表明算法具有较高的检测正确率 ,给网络带来的通信开 Confe rence on V e ry L a rge D a ta B a se s. San F ranc isco: ACM , 1998: 销非常小 。 392 - 403. ( ) 2 [ 10 ] IOANN ID IS Y. The h isto ry of h istogram s ab ridged [ C ] / / P ro 参考文献 : ceed ings of the 29 th In te rna tiona l Confe rence on V e ry L a rge D a ta [ 1 ] 孙利民 ,李建中 ,陈渝 ,等. 无线传感器网络 [M ]. 北京 : 清华大学 B a ses. B e rlin: ACM , 2003: 19 - 30. 出版社 , 2005. ()上接第 682页 [ 2 ] 杨丹 ,曹俊. 基于 W eb 2. 0 的社会性标签推荐系统 [ J ]. 重庆工学 无法识别这些冗余标签时 ,就低估了推荐系统的质量 。针对传 () 院学报 , 2008 , 22 7 : 51 - 55.统 K2M eans聚类的模糊标签和冗余标签抽取不准确 ,导致处理 V IG J , EN S, R IEDL J. Tagsp lana tion s: Exp la in ing recomm enda2 [ 3 ] 标签模糊和标签冗余效果不理想的问题 ,本文提出使用核 K2 tion s u sing tags [ C ] / / IU Iπ09: P roceed ings of the 13 th In te rna tiona l M eans聚类方法识别模糊标签和冗余标签 ,该算法的聚类效果 Confe rence on In te lligen t U ser In te rfaces. N ew Yo rk: ACM P ress, 更好 ,在抽取模糊标签和冗余标签的准确度上有较大的改进 。 2009: 47 - 56. 在模糊标签的抽取上 ,减少了因资源的错误分类而导致与其相 GEMM ELL J , RAM EZAN I M , SCH MIOL ER T. A fa st effec tive [4 ] 关标签的模糊度被高估的情况 ;在冗余标签的抽取上 ,获得了 m u lti2channe led tag recomm ende r [ C ] / / Eu rop ean Confe rence on 冗余度更高的标签类 ,找到了更准确的冗余标签 。 M ach ine L ea rn ing and P rinc ip les and P rac tice of Know ledge D iscov2 e ry in D a taba se s. B led, Sloven ia: [ s. n. ] , 2009: 35 - 42. ZHAN G N IN G, ZHAN G YUAN , TAN G J IE. A tag recomm enda tion [ 5 ] system ba sed on con ten ts [ C ] / / Eu rop ean Confe rence on M ach ine L ea rn ing and P rinc ip le s and P rac tice of Know ledge D iscove ry in D a2 taba se s. B led, Sloven ia: [ s. n. ] , 2009: 19 - 25. [ 6 ] ZHANG YUAN , ZHANG N ING, TANG J IE. A collaborative filtering tag recommendation system based on graph [C ] / / European Conference on Machine Learning and Princip les and Practice of Know ledge D iscov2 ery in Databases. B led, Slovenia: [ s. n. ], 2009: 152 - 158. GEMM ELL J , RAM EZAN I M , SCH IMOL ER T, et a l. The imp ac t [ 7 ] of am b igu ity and redundancy on tag recomm endation in fo lk sonom ie s [ C ] / / P roceed ings of the 2009 ACM Confe rence on R ecomm ende r System s. N ew Yo rk: ACM P re ss, 2009: 23 - 25. 图 3 标签冗余度对比 [ 8 ] 孔锐 ,张国宣 ,施泽生 , 等. 基于核的 K2均值聚类 [ J ]. 计算机工 () 程 , 2004 , 33 11 : 12 - 14.参考文献 : 张莉 , 周 伟达 , 焦 李成. 核 聚类算 法 [ J ]. 计 算 机 学 报 , 2002 , 25 [ 9 ] [ 1 ] L IPCZA K M. Tag recomm endation fo r fo lk sonom ie s o rien ted toward s () 6 : 557 - 590. ind ividual u se rs [ C ] / / Eu rop ean Conference on M ach ine L earn ing [ 10 ] 姜园 ,张朝阳 ,仇佩亮 ,等. 用于数据挖掘的聚类算法 [ J ]. 电子与 and P rinc ip les and P rac tice of Know ledge D iscove ry in D a taba se s. () A n twe rp , B e lgium: [ s. n. ] , 2008: 84 - 89. 信息学报 , 2005 , 27 4 : 655 - 662.