发布日期：2024-11-02 05:03 点击次数：151
标注(tagging)是现在广大酬酢网站的一个基本功能,用户在这些网站中不错使用自界说的标签形容各式信息资源(举例文本、图片和视频).诳骗用户孝敬的标签,酬酢网站提供了多种造访信息资源的机制,而标签云是其中的蹙迫一种,已被应用于Flickr、CiteULike、Delicious和豆瓣等网站中.在标签云中,一组具有代表性的标签以可视化的花样呈现给用户.借助于这组标签,用户不仅不错了解资源举座的信息nt 动漫,还不错通过点击其感兴味的标签造访与之相关联的个别资源.在标签云的创建经由中,从系数与资源相关联的标签中礼聘一组有代表性的标签是一个关节智商[1, 2, 3, 4],本文针对该标签礼聘问题进行议论.
标签云主要通过所包含的一组标签形容资源的信息,因而,为使标签云更富信息量,各样化标签礼聘根除相配必要.信息隐蔽进程与标签非相似性是现在标签礼聘方法引入各样性的两个主要角度[4],文件[1, 2, 3]隔离从单一角度提倡了些许标签礼聘方法,而概述议论信息隐蔽度与标签非相似性为标签礼聘各样化提供了新的想路,咱们在文件[4]中对这一想路进行了初步尝试,提倡一种新的标签礼聘方法.与只议论一种角度的方法比较,该方法在信息隐蔽度与标签非相似性方面王人发扬较好.在本文中,咱们仍沿用概述议论信息隐蔽度与标签非相似性的想路,议论不同的标签礼聘各样化方法,以进一步提升礼聘根除的各样化进程.
本文将标签礼聘各样化问题视作特定贪图函数在基数照应条目下的最大化问题,在该问题框架下,咱们提倡3种标签礼聘方法.本文采纳3种不同的计策来量化标签聚拢的信息隐蔽度与标签非相似性,据此界说了相应的贪图函数,并依据贪图函数的性质想象并收尾了最大化问题的类似求解算法,同期还分析了相应算法的类似比.诳骗CiteULike网站与Last.fm网站的标注数据集,咱们将所提倡的方法与已有方法进行了比较.实验根除标明:所提倡的方法在信息隐蔽度与标签非相似性方面王人发扬较好;与文件[4]中的方法比较发扬更好,进一步提升了标签礼聘根除的各样化进程.
本文第1节先容相关责任.第2节先容计议常识.第3节形容所提倡的3种方法.第4节给出在CiteULike的标注数据集与Last.fm的标注数据集上将所提倡方法与已有方法进行比较的实验根除.临了给出全文回想.
1 相关责任各样化问题在Web搜索[5, 6, 7, 8]、数据库[9, 10, 11]、文档纲领[12, 13, 14]、推选[15, 16, 17]等界限取得了泛泛议论.文件[18, 19, 20, 21, 22]对各样化的一般问题进行了议论.
现在已有的标签礼聘方法在不同进程上议论了各样化:
·最早的标签礼聘方法(以下简称POP)笔据标签所标注资源的总额(即流行度)礼聘标签.方法POP的礼聘根除通常包含许多相似标签,隐蔽的信息也不够全面;
·文件[1]中所提倡的标签礼聘方法(以下简称USE)以缩小礼聘根除中不同标签之间的资源重迭(相似性)为贪图,基于标签效力的办法礼聘标签;
·文件[3]中所提倡的标签礼聘方法之一(以下简称COV)以最大化礼聘根除所隐蔽的资源数为贪图,笔据相对于现时已礼聘标签所隐蔽的新资源的数量礼聘标签;
·文件[2]中提倡两种显式议论各样化的方法:一种方法(以下简称POP+DIS)是笔据标签流行度和与现时已礼聘标签的最短距离的凸组合礼聘标签,以使礼聘根除中的标签尽量互不相似;另一种方法(以下简称NOV)是笔据相对于现时已礼聘标签的新颖性礼聘标签.当方法NOV在最猛进程上强调新颖性时,其求得与方法COV调换的礼聘根除;
·咱们在文件[4]中所提倡的标签礼聘方法(以下简称COV+SUSE)以提升礼聘根除所隐蔽的资源数并缩小礼聘根除中不同标签之间的资源重迭为贪图,笔据相对于现时已礼聘标签所隐蔽的新资源的数量和所加多的标签效力的凸组合礼聘标签.
2 计议常识 2.1 酬酢标注系统议论者通常将酬酢标注系统(social tagging system)[23, 24]建模为三分超图G=(U$ cup $T$ cup $R,E),其中,U,T和R隔离为用户集、标签集和资源集且互不相交,而边集E$ subseteq $U×T×R.边(u,t,r)$ in $E默示用户u使用标签t标注资源r.
·对随心的t$ in $T,令R(t)={r$ in $R|$\exists $u(u$ in $U$ wedge $(u,t,r)$ in $E)},默示标签t所标注的一起资源的聚拢;
·对随心的r$ in $R,令T(r)={t$ in $T|$\exists $u(u$ in $U$ wedge $(u,t,r)$ in $E)},默示标注资源r的一起标签的聚拢.
2.2 次模函数及单调函数设X为有限聚拢.令
:2X→
.若对随心的A$ subseteq $B$ subset $X及随心的x$ in $X\B,(A$ cup ${x})-(A)≥(B$ cup ${x})-(B)建设,则称函数知足次模性(submodularity)[25],其中,称(A$ cup ${x})-(A)为给定聚拢A时x对于的边缘收益(marginal returns).次模函数具有边缘收益递减的性质.
易证次模函数知足如下性质:
引理1. 设X为有限聚拢,α1,α2,…,αn$ in $且αi≥0(0≤i≤n),1,2,…,n:2X→为次模函数.令:2X→,且对随心的A$ subseteq $X,界说(A)=$\sum\limits_{i = 1}^n {{\alpha _i} \cdot } $i(A),则亦然次模函数.
令
:2X→.若对随心的A$ subseteq $B$ subseteq $X,(A)≤(B)建设,则称函数知足单调性(monotonicity)[25].
设X为聚拢.令d:X×X→.若对随心的x,y$ in $X,d知足如下性质:
(1) d(x,y)≥0;
(2) d(x,y)=0当且仅当x=y;
(3) d(x,y)=d(y,x),
则称d为X上的距离函数(distance function)[26].若对随心的x,y,z$ in $X,距离函数d还知足d(x,z)≤d(x,y)+d(y,z),则称d为度量距离函数(metric distance function)[26].
3 提倡的方法界说1(标签礼聘各样化问题). 令G=(U$ cup $T$ cup $R,E)为酬酢标注系统,贪图函数
:2T→衡量T的子集的各样性.给定一个正整数k,标签礼聘各样化求解一个聚拢S,S$ subseteq $T,使得(S)最大,且|S|=k.
在该问题框架下,咱们提倡3种标签礼聘各样化方法.在每种方法中,采纳相应的、同期量化信息隐蔽度与标签非相似性的计策界说了贪图函数,并依据贪图函数的性质想象了类似求解算法,同期分析了类似算法的类似比.底下详备形容这3种方法.
3.1 方法COV-SIM 3.1.1 贪图函数界说议论到信息隐蔽度与标签非相似性可能相互打破,将本方法的贪图函数1:2T→界说为如下凸组合:
1(S)=λ×
1(S)+(1-λ)×
1(S).
其中,1:2T→是量化信息隐蔽度的子贪图函数;1:2T→是量化标签非相似性的子贪图函数;参数λ$ in $[0, 1],用于适度1与1的权重.底下详备先容函数1与1的界说.
(1) 在酬酢标注系统中,不错将每个资源看作一块信息,因此,一个标签聚拢中系数标签所标注的资源的总额是该标签集的信息隐蔽进程的一种量化.由于不同标签可能标注调换的资源,跟着一个标签聚拢中元素的增多,该标签荟萃系数标签所标注的资源的总额将会加多,然则加多的速率将会着落.可见,函数1应该知足单调次模性.使用文件[4]中的隐蔽函数行为1的界说,即:对随心的S$ subseteq $T:
1知足单调次模性[4].在1的界说中,正常根函数一方面用于保证1知足单调次模性,另一方面用于幸免1与1收支过多.
1(S)=$\sqrt {\left| {\bigcup\limits_{t \in S} {R\left( t \right)} } \right|} \cdot $.
(2) 因为标签的作用是标注资源,是以借助所标注的资源集来描述标签是比较当然的目的.这里,启程点将标签的相似性界说为其所标注的资源集的Jaccard相似度[27],即:对随心的ti,tj$ in $T有
${S_J}\left( {{t_i},{t_j}} \right) = \frac{{\left| {R\left( {{t_i}} \right) \cap R\left( {{t_j}} \right)} \right|}}{{\left| {R\left( {{t_i}} \right) \cup R\left( {{t_j}} \right)} \right|}} \cdot $
进一样子,咱们界说1如下:对随心的S$ subseteq $T:
1(S)=$ - \sum\limits_{{t_i},{t_j} \in S,{t_i} \ne {t_j}} {{s_J}\left( {{t_i},{t_j}} \right)} $.
默示礼聘标签时,使根除荟萃标签相似性的和尽量的小.
基于如上界说,贪图函数1知足如下性质:
命题1. 1瑕瑜单调次模函数.
解释:笔据界说,1(S)=$ - \sum\limits_{{t_i},{t_j} \in S,{t_i} \ne {t_j}} {{s_J}\left( {{t_i},{t_j}} \right)} $是次模函数.笔据文件[4]中的论断,1(S)=$\sqrt {\left| {\bigcup\limits_{t \in S} {R\left( t \right)} } \right|} \cdot $是单调次模函数.笔据引理1,1(S)=λ×1(S)+(1-λ)×1(S)(0/span>≤λ≤1)是次模函数.笔据界说,1(S)不是单调函数. □
因为以1为贪图函数的标签礼聘各样化问题包含了最大隐蔽问题(maximum coverage problem)[28],是以该标签礼聘各样化问题是NP-hard的.咱们采纳算法1类似求解该问题,该算法包含一种贪默算法1_1和一种局部搜索算法1_2.
·算法1_1从空集起徐徐构造一个包含k个标签的聚拢:在每个轮回中,该算法从剩余标签中礼聘给定现时根除集时对于1的边缘收益最大的标签,将其添加到根除荟萃,并连接下个轮回;
· 算法1_2启程点诳骗对于1的野神思策构造一个启动根除集,然后从这个启动根除集动手进行局部搜索,即:不拒却换现时根除集内、外的各一个标签以改良根除集的贪图函数值,直到莫得任何可实验的交换为止.在交换经由中,换出标签tout是从根除集内、按照对贪图函数值的孝敬从小到大的规则礼聘,换入标签tin是从根除集外礼聘的、与现时换出标签交换后使得贪图函数值最大的标签.
算法1是上述局部搜索算法和贪默算法的团结:启程点,以T和k为输入实验局部搜索算法1_2,求得包含k个标签的聚拢S1;然后,以T\S1和k为输入实验贪默算法1_1,求得包含k个标签的聚拢S2;临了,将S1与S2中贪图函数值较大的一个行为根除复返.
算法1.
输入:标签聚拢T,正整数k;
女同视频输出:S$ subseteq $T且|S|=k.
1: S1=Plocalsearch(T,k)
2: S2=Pgreedy(T\S1,k)
3: if 1(S1)≥1(S2) then S=S1 else S=S2 end if
4: return S
算法1_1. Pgreedy.
输入:标签聚拢T,正整数k;
输出:S$ subseteq $T且|S|=k.
1: S=Ø
2: while |S|<k do
3: t*=$\mathop {\arg \max }\limits_{t \in T\S} $(1(S$ \cup ${t})-(S))
4: S=S$ cup ${t*}
5: end while
6: return S
算法1_2. Plocalsearch.
输入:标签聚拢T,正整数k;
输出:S$ subseteq $T且|S|=k.
1: S=Ø
2: while |S|<k do
3: t*=$\mathop {\arg \max }\limits_{t \in T\S} $(1(S$ \cup ${t})-(S))
4: S=S$ cup ${t*}
5: end while
6: Tout=S;
7: while |Tout|>0 do
8: tout=$\mathop {\arg \max }\limits_{t \in _out} $(1(S\{t})
9: tin=$\mathop {\arg \max }\limits_{t \in T\S} $(1(S\{tout}$ \cup ${t})
10: if 1(S\{tout}$ cup ${tin})>1(S) then
11: S=S\{tout}$ cup ${tin}
12: Tout=S
13: else
14: Tout=Tout\{tout}
15: end if
16: end while
17: return S
定理1[29]. 设:2T→为非单调次模函数,对随心的S$ subseteq $T,王人有(S)≥0且(Ø)=0.若使用如下算法框架构造聚拢$\hat S$:
智商1:使用局部搜索算法求得S1,S1$ subseteq $T且|S1|=k:启动化S1,使其包含T中k个标签,当存在t1$ in $S1,t2$ in $T\S1使得(S1\{t1}$ cup ${t2})>(S1)时,S1=S1\{t1}$ cup ${t2};
智商2:使用贪默算法求得S2,S2$ subseteq $T\S1且|S2|=k:启动化S2为空集,从现时T\(S1$ cup $S2)中选出给定S2时对于的边缘收益最大的标签添加到S2中,直到|S2|=k为止;
智商3:取$\hat S$为S1与S2中贪图函数值较大者.则($\hat S$)≥$\frac{1}{4}$(S*),其中,(S*).
在本方法中,算法1是定理1中所述的算法框架的一个实例;笔据命题1,1瑕瑜单调次模函数;笔据界说, 1(Ø)=0;在给定的酬酢标注系统中,当λ取顺应的值,使得对随心的S$ subseteq $T,1(S)≥0竖随即,本方法具有如定理1所述的表面保证,即,算法1所生成的标签礼聘根除的贪图函数值至少是最优贪图函数值的0.25倍.在实验中咱们发现:在一个给定的酬酢标注系统中,大巨额λ的取值王人能使上述非负条目建设.
另外,在定理1所述的算法框架中,智商1的运行成矍铄定了通盘算法的运行成果;而一般来说,局部搜索算法在最坏情况下的运行时辰为指数级[30].为了提升智商1的运行成果,咱们实例化该智商时在算法1_2中采纳如下计策:
(1) 在启动化阶段,诳骗对于函数1的贪默算法构造启动根除集.1与方法COV的贪图函数只收支正常根函数,算法1_2中对于1的贪默算法与方法COV中的贪默算法求得调换的根除集,且该根除集在信息隐蔽度方面发扬较好[3].
(2) 在交换阶段,尽可能礼聘使贪图函数值改良较大的标签对进行交换.
基于上述计策,算法1_2所需进行的交换次数大大减少.在实验中咱们发现:在实质运行中,该交换次数与礼聘标签数k在吞并个量级.
3.2 方法COV+DIS 3.2.1 贪图函数界说将本方法的贪图函数2:2T→界说为如下凸组合:
2(S)=λ·1(S)+(1+λ)·$\sum\limits_{{t_i},{t_j} \in S} {{d_J}\left( {{t_i},{t_j}} \right)} $,
其中,
·dJ:TxT→是标签之间的距离函数,对随心的ti,tj$ in $T:${d_J}\left( {{t_i},{t_j}} \right) = 1 - \frac{{\left| {R\left( {{t_i}} \right) \cap R\left( {{t_j}} \right)} \right|}}{{\left| {R\left( {{t_i}} \right) \cup R\left( {{t_j}} \right)} \right|}}$
·参数λ$ in $[0, 1],用于适度1与$\sum\limits_{{t_i},{t_j} \in S} {{d_J}\left( {{t_i},{t_j}} \right)} $的权重.
在本方法中,咱们采纳与方法COV-SIM中调换的子贪图函数1量化信息隐蔽度,然则对于标签非相似性,咱们平直采纳标签聚拢中标签之间的距离之和量化[19, 20, 21].这与在方法COV-SIM中所采纳的子贪图函数1不同,后者使标签聚拢中标签相似性之和尽量地小.
以2为贪图函数的标签礼聘各样化问题雷同是NP-hard问题,咱们采纳算法2类似求解该问题.算法2是一个贪默算法,与算法1_1的不同之处在于:在每个轮回中,礼聘标签的顺序不是给定现时根除集时对于2的边缘收益,而是两部分的凸组合:一部分是给定现时根除集时对于1的边缘收益的$\frac{1}{2}$倍,另一部分是与现时已礼聘标签的距离的和.
算法2.
输入:标签聚拢T,正整数k;
输出:S$ subseteq $T且|S|=k.
1: S=Ø
2: while |S|<k do
3: t*=$\mathop {\arg \max }\limits_{t \in TS} \left( {\lambda \cdot \frac{1}{2}} \right.$(1(S$ \cup ${t})-1(S))+(1-λ)·$\sum\limits_{{t_i} \in S} {{d_J}\left( {t,{t_i}} \right)} $
4: S=S$ cup ${t*}
5: end while
6: return S
定理2[21]. 设:2T→界说如下:对随心的S$ subseteq $T,(S)=(S)+(1-λ)·$\sum\limits_{{t_i} \in S} {{d_J}\left( {t,{t_i}} \right)} $,其中,0≤λ≤1;而: 2T→为单调次模函数,且(Ø)=0,d:T×T→为度量距离函数.若使用如下贪默算法构造聚拢$\hat S$:
智商1:启动化$\hat S$为空集;
智商2:针对现时的$hat S$,礼聘一个标签t,$t \in T\\hat S$且使λ·$\frac{1}{2}$(($hat S$$ \cup ${t})-($hat S$))+(1-λ)·$\sum\limits_{{t_i} \in hat S} {{d_J}\left( {t,{t_i}} \right)} $大,并将t添加到$hat S$中;
智商3:重复实验智商2,直到|$hat S$|=k为止.则($hat S$)其中,${S^ * } \in \mathop {\arg \max }\limits_{S \subseteq T,\left| S \right| = k} $(S).
在本方法中,算法2是定理2中所述的贪默算法的一个实例.笔据文件[4]中的论断,1知足单调次模性且1(Ø)=0.笔据文件[31]中的论断,dJ是度量距离函数.综上,本方法具有如定理2所述的表面保证,即,算法2所生成的标签礼聘根除的贪图函数值至少是最优贪图函数值的0.5倍.
标签云通过所包含的标签为用户提供资源信息评释与资源空间导航的功能.本方法从标签给用户带来的效用的角度来界说贪图函数,其基本想想鉴戒于文件[12].
咱们启程点引入效用函数v:Rx2T→,其形容一个标签聚拢相对于一个资源的效用:对随心的S$ subseteq $T和随心的r$ in $R:
其中,λ$ in $(0,1].进一样子,咱们界说一个标签聚拢相对于通盘资源集的效用为该标签集相对于系数资源的效用之和:对于随心的S$ subseteq $T:
3(S)=$\sum\limits_{r \in R} {v\left( {r,S} \right)} $.
将函数3行为本方法的贪图函数.
贪图函数3合适咱们提升标签礼聘根除的资源隐蔽度并缩小礼聘根除中标签相似性的意图.
· 启程点,从效用函数的界说来看,若标签聚拢S中存在标签隐蔽资源r,则S对r的效用大于0;不然,S对r的效用为0.因而,依据3礼聘效用较大的标签聚拢时,咱们会比较倾向于礼聘隐蔽更多资源的标签聚拢;
· 其次,在效用函数的界说中,当资源r被标签聚拢S中的标签隐蔽时,S的效用是跟着r被隐蔽次数的加多而减少的.因而,依据3礼聘效用较大的标签聚拢时,咱们很当然地要使礼聘根除中的标签尽量隐蔽不同的资源集,这实质上就缩小了礼聘根除中标签的相似性;
· 临了,咱们在效用函数的界说中使用了参数λ,该参数用于权衡信息隐蔽度与标签非相似性:当λ变大时,信息隐蔽度的权重变大而标签非相似性的权重变小;当λ=1时,对随心标签聚拢S,函数3(S)计较的是S所隐蔽资源的数量,从而依据3礼聘标签时仅议论了礼聘根除的资源隐蔽度.
另外,贪图函数3在λ=1时知足如下性质:
命题2. 当λ=1时,3为单调次模函数.
解释:当λ=1时,对于随心的S$ subseteq $T和随心的r$ in $R:
$v\left( {r,S} \right) = \left\{ \begin{array}{l} 0,要是对随心的t \in S,r \notin R\left( t \right)\\ 1,要是\left| {\left\{ {t \in S:r \in R\left( t \right)} \right\}} \right| = x且x \ge 1 \end{array} \right.$此时,3(S)=$\sum\limits_{r \in R} {v\left( {r,S} \right) = \left| {\bigcup\limits_{t \in S} {R\left( t \right)} } \right|} $.笔据界说,3是单调次模函数. □
以3为贪图函数的标签礼聘各样化问题雷同是一个NP-hard问题,本方法使用算法3类似求解该问题.算法3为贪默算法,与算法1_1的区别在于贪图函数不同.
算法3.
输入:标签聚拢T,正整数k;
输出:S$ subseteq $T且|S|=k.
1: S=Ø
2: while |S|<k do
3: t*=$\mathop {\arg \max }\limits_{t \in TS} $(3(S$ \cup $)={t})-3(S))
4: S=S$ cup ${t*}
5: end while
6: return S
定理3[32]. 设:2T→为单调次模函数且(Ø)=0.若使用如下贪默算法构造聚拢$\hat S$:
启动化$hat S$为空集,从现时$T\\hat S$中选出给定$hat S$时对于的边缘收益最大的标签添加到$hat S$中,直到$\left| {\hat S} \right|$=k为止.则($\hat S$)≥(1-1/e)(S)其中,S*$ \in \mathop {\arg \max }\limits_{S \subseteq T,\left| S \right| = k} $(S).
在本方法中,算法3是定理3中所述的贪默算法的一个实例;笔据命题2,当λ=1时,3知足单调次模性且3(Ø)=0,是以此时本方法具有如定理3所述的表面保证;而当0<λ<1时,不行取得调换的论断.一般情形下,算法3不一定具有表面上的性能保证.
在从CiteULike网站()与Last.fm网站()抽取的标注数据集上咱们将本文所提倡的标签礼聘方法与已有方法进行了比较.
4.1 数据准备从CiteULike网站的通盘标注数据集()中抽取出一个子数据集用于实验.CiteULike网站的通盘标注数据集包括17 481 632个标注,每个标注由一个用户的id、一个标签、一个著述(article)的id和一些其他信息构成.该数据集一共包括761 674个不同标签,其中,software是流行度较高的一个标签.咱们将software看作东题标签[33],抽取出与software相关的子数据集:启程点抽取出software所标注的系数资源,然后抽取出系数与这些资源相关联的标注(包含software的标注以外),并将所抽取到的标注集行为与software相关的子数据集.为了使该数据集所包含的标签更有意旨,咱们将包含杂音标签(举例艳丽、停词)的标注删除,之后,该数据集的统计信息见表 1中第1行所示.
Table 1 Dataset statistics表 1 数据集的统计信息
咱们用于实验的Last.fm标注数据集是由明尼苏达大学(University of Minnesota)的GroupLens议论实验室()从Last.fm网站抽取并发布(-2011/)的,该数据集包括186 479个标注,每个标注由一个用户的id、一个标签、一个艺术家(artist)的id和一些时辰信息构成.该数据集的统计信息见表 1中第2行.
图 1形容了在CiteULike数据集与Last.fm数据荟萃标签对于标注资源数的漫衍.
Fig.1
Distribution of tags across the number of related resources
图 1
标签对于标注资源数的漫衍
如图 1所示:在这两个数据荟萃,大巨额标签所标注的资源的数量王人较小;何况在Last.fm数据荟萃,具有特定数量标签的资源的数量更小.
4.2 评价顺序在已有的评价标签礼聘根除的顺序中,隐蔽度与重迭度较好地反馈了信息隐蔽度与标签非相似性[4].本文使用隐蔽度与重迭度评价各个标签礼聘方法的根除的各样性.
标签礼聘根除S的隐蔽度衡量S中系数标签所隐蔽的资源占资源集R中一起资源的比例.在文件[2]中,将S的隐蔽度界说为
$coverage\left( S \right) = \frac{{\left| {\bigcup\limits_{t \in S} {R\left( t \right)} } \right|}}{{\left| R \right|}} \cdot $coverage(S)越大,S所隐蔽的信息越多.
标签礼聘根除S的重迭度衡量S中所包含的标签的冗余进程.在文件[1]中,将S的重迭度界说为
$overlap\left( S \right) = \frac{{\sum\limits_{{t_i},{t_j} \in S,{t_i} \ne {t_j}} {{s_J}\left( {{t_i},{t_j}} \right)} }}{{\left| S \right| \cdot \left( {\left| S \right| - 1} \right)/2}},$其中,${s_J}\left( {{t_i},{t_j}} \right) = \frac{{\left| {R\left( {{t_i}} \right) \cap R\left( {{t_j}} \right)} \right|}}{{\left| {R\left( {{t_i}} \right) \cup R\left( {{t_j}} \right)} \right|}} \cdot $overlap(S)越小,S所包含的标签越不相似.
4.3 实验根除咱们隔离收尾了在本文第3节所提倡的3种标签礼聘方法(COV-SIM,COV+DIS和GAIN)、在文件[4]中所提倡的方法COV+SUSE以及相关责任中先容的另外5种标签礼聘方法(POP,USE,COV,POP+DIS和NOV).咱们在第4.1节中所先容的CiteULike数据集与Last.fm数据集上比较这9种方法的礼聘根除的各样性.使用MySQL Server 5.0存储数据集,基于Java 1.6收尾各个标签礼聘方法并计较标签礼聘根除的隐蔽度与重迭度.在各个方法的收尾和实验中,令礼聘的标签数k=30.对于方法NOV,将一般情形下的函数γ()界说为
$\gamma \left( {{n_{r,S}}} \right) = \frac{{\left| {T\left( r \right)} \right| - {n_{r,S}}}}{{\left| {T\left( r \right)} \right|}}$,
其中,r$ in $R,S中包含现时已礼聘的标签,nr,s=|{t$ in $S:r$ in $R(t)}|(方法NOV的界说详见文件[2];当方法NOV在最猛进程上强调新颖性时,其礼聘根除与方法COV的礼聘根除调换,此处议论该方法的一般情形).
笔据第4.2节所先容的界说,计较方法POP,USE,COV和NOV的礼聘根除的隐蔽度与重迭度.令方法COV- SIM,COV+DIS,GAIN,POP+DIS和COV+SUSE中参数λ的值从0.05动手,以终止0.05加多到0.95(方法POP+DIS与方法COV+SUSE中,参数λ的界说见文件[2, 4]),并计较当λ取特定值时各个方法的礼聘根除的隐蔽度与重迭度.图 2、图 3隔离袒露了在CiteULike数据集与Last.fm数据集上这9种方法的礼聘根除的隐蔽度与重迭度随λ值的变化.
Fig.2
Coverage and overlap of nine approaches for increasing λ on the CiteULike dataset
图 2
CiteULike数据集上9种方法的隐蔽度与重迭度随λ值的变化
Fig.3
Coverage and overlap of nine approaches for increasing λ on the Last.fm dataset
图 3
Last.fm数据集上9种方法的隐蔽度与重迭度随λ值的变化
从图 2与图 3可见:
(1) 与已有的5种方法POP,USE,COV,POP+DIS和NOV比较,在CiteULike数据集与Last.fm数据集上,对于λ的许多取值,本文所提倡的3种方法在隐蔽度与重迭度方面王人发扬较好:
·如图 2(a)和图 3(a)所示:在CiteULike数据集与Last.fm数据集上,方法COV的礼聘根除的隐蔽度王人最大;当λ从0.05加多到0.95时,本文所提倡的3种方法的礼聘根除的隐蔽度王人在遏抑增长,且当λ增长到一定值之后,与已有的5种方法比较,这3种方法的礼聘根除的隐蔽度王人愈加接近于方法COV的礼聘根除的隐蔽度;
·如图 2(b)和图 3(b)所示:在CiteULike数据集与Last.fm数据集上,当λ从0.05加多到0.95时,与已有的4种方法POP,COV,POP+DIS和NOV比较,本文所提倡的3种方法的礼聘根除的重迭度王人恒久处于较低水平,只当λ增长到一定值之后才高于方法USE的礼聘根除的重迭度.
(2) 与咱们在文件[4]中所提倡的方法COV+SUSE比较,在CiteULike数据集与Last.fm数据集上,对于λ的许多取值,本文所提倡的3种方法在隐蔽度与重迭度方面王人发扬较好:
·在CiteULike数据集上,如图 2(a)、图 2(b)所示:对于绝大巨额的λ值,与方法COV+SUSE比较,本文所提倡的3种方法的礼聘根除王人具有更高的隐蔽度与更低的重迭度;
·在Last.fm数据集上,如图 3(a)所示:当λ从0.05加多到0.95时,率先方法COV+SUSE的礼聘根除的隐蔽度高于本文所提倡的3种方法的礼聘根除的隐蔽度,之后,本文所提倡的3种方法的礼聘根除的隐蔽度快速濒临于方法COV+SUSE的礼聘根除的隐蔽度,且当λ增长到一定值之后,这3种方法的礼聘根除的隐蔽度高于方法COV+SUSE的礼聘根除的隐蔽度.如图 3(b)所示:对于系数的λ值,本文所提倡的方法COV+DIS和方法GAIN的礼聘根除的重迭度王人远低于方法COV+SUSE的礼聘根除的重迭度,对于除了0.95之外的系数λ值,本文所提倡的方法COV-SIM的礼聘根除的重迭度王人远低于方法COV+SUSE的礼聘根除的重迭度.
(3) 本文所提倡的3种方法各有特质:
·COV-SIM在CiteULike数据集与Last.fm数据集上王人在隐蔽度方面发扬较好;
·COV+DIS在CiteULike数据集与Last.fm数据集上王人在重迭度方面发扬较好;
·GAIN在CiteULike数据集上在重迭度方面发扬较好,在Last.fm数据集上在隐蔽度方面发扬较好.
评释:在本文所提倡的3种标签礼聘方法中,参数λ用于权衡信息隐蔽度与标签非相似性,即:当λ变大时,信息隐蔽度的权重变大而标签非相似性的权重变小;相应地,在咱们的实验中,当λ从0.05加多到0.95时,标签礼聘根除的隐蔽度变大而重迭度变小.咱们不错为所提倡方法笃定参数λ的具体取值,使礼聘根除同期具有较好的隐蔽度与重迭度.图 4袒露了所提倡的3种方法在CiteULike数据集与Last.fm数据集上相对于λ的隐蔽度-重迭度权衡弧线,其中,弧线上的点隔离以λ取特定值时方法的礼聘根除的重迭度与隐蔽度为横坐标与纵坐标.从图 4可见,这3种方法在CiteULike数据集与Last.fm数据集上的隐蔽度-重迭度权衡弧线王人昭彰具有抨击部分.举例如图 4(a)中方法COV-SIM在CiteULike数据集上的隐蔽度-重迭度权衡弧线:当λ从0.05加多到0.25时,权衡弧线急剧飞腾,即,隐蔽度加多较快同期重迭度加多较慢;当λ从0.25加多到0.65时,权衡弧线变抨击,即,隐蔽度加多变慢同期重迭度加多变快;当λ从0.65加多到0.95时,权衡弧线趋于安闲,即,隐蔽度加多更慢同期重迭度加多更快.可见,当为这3种方法取其权衡弧线的抨击部分所对应的λ值时,所取得的礼聘根除的隐蔽度接近最大、重迭度接近最小.咱们一般不错通过两种花样笃定所提倡方法在特定数据集上的参数λ的具体取值:一是鉴戒文件[2, 4]中的作念法,平直取权衡弧线的抨击部分所对应的λ值中的一个,举例,为方法COV-SIM在CiteULike数据集上取λ=0.5;二是笔据用户反馈的偏好信息分析出权衡弧线的抨击部分所对应的λ值中的最优者.咱们将后者行为将来责任的一部分.
Fig.4
Coverage-Overlap tradeoff curves of our approaches for λ on the datasets of CiteULike and Last.fm
图 4
CiteULike数据集与Last.fm数据集上所提方法相对于λ的隐蔽度-重迭度权衡弧线
5 结 论
本文在最大化问题框架下提倡了3种标签礼聘各样化方法,以增强标签礼聘根除的信息隐蔽度与标签非相似性.在各个方法中,采纳不同的计策以量化标签聚拢的信息隐蔽度与标签非相似性,并界说了贪图函数.针对这些贪图函数,想象了类似算法以处分相应的最大化问题,并分析了类似算法的类似比.实验根除标明:与已有方法比较nt 动漫,本文所提倡的方法的礼聘根除具有较好的信息隐蔽度与标签非相似性.将来,咱们议论进行如下3方面责任:一是在更多的数据集上评估本文所提倡的方法;二是对标签礼聘根除的各样性的评价方法作深切议论;三是笔据用户反馈的偏好信息为所提倡方法的参数λ笃定较合适的取值.