《网络标签聚类方法和系统的制作方法》由会员分享,可在线阅读,更多相关《网络标签聚类方法和系统的制作方法(10页珍藏版)》请在金锄头文库上搜索。
1、网络标签聚类方法和系统的制作方法专利名称:网络标签聚类方法和系统的制作方法技术领域:本发明涉及互联网领域,尤其涉及一种网络标签聚类方法和系统。背景技术:随着互联网的发展,网络资源越来越丰富。互联网上的网络资源可以包括:网络上的视频、音乐、图片文件,或者话题、课件等文件;网络标签(Tag)是用户根据自己的需要、理解和偏好,对网络资源进行标注得到的,用于描述网络资源的主题、类型、功能等多种特征。网络标签具有揭示资源的隐含内容或信息、分类的作用,并在此基础上实现网络资源聚合、协同与推荐等功能。通过对网络标签的向量化,得到网络标签向量;现有网络标签向量是由用户数据、网络资源和网络标签三维属性来表征的,
2、现有网络标签向量中每一个元素表示每个用户数据与每个网络资源与网络标签三者之间的总关联度。在对网络标签向量化后,可以针对向量化后网络标签进行聚类算法的计算,实现对网络标签的聚类;对网络标签聚类后,有助于挖掘出范围更广、程度更深的与网络标签相关的网络资源,可以提高以网络标签来搜索、推荐网络资源等互联网应用的效率。所谓对向量化后的网络标签的聚类,就是对于由多个网络标签向量所构成的网络标签向量集,使用某种算法将该网络标签向量集划分成若干网络标签向量子集,使得聚在同一网络标签向量子集中的网络标签向量之间的相似度较高;这样,通过对网络标签向量的聚类,也就实现了网络标签向量所对应的网络标签的聚类;即同一网络
3、标签向量子集中的网络标签向量所对应的网络标签之间具有较高的相似度。通常,将网络标签向量子集定义为一个簇;对簇中的全部网络标签向量求平均后得到一个平均向量,将该簇内与该平均向量距离最小的网络标签向量定义为该簇的质心;计算簇内任意两个网络标签向量之间的距离,将计算出的最大距离定义为该簇的直径;网络标签向量之间的距离与网络标签向量之间的相似度互为倒数关系。常用的网络标签向量聚类算法有层次聚类算法和k-means (k均值)聚类算法等,由于层次聚类算法在网络标签向量数目较大时,计算复杂而耗时较长,因此对于大数目的网络标签向量,一般采用k-means聚类算法。如图1所示,对网络标签向量集的k-means
4、聚类算法的具体步骤如下:SlOl:进行初始化,令迭代次数j=l。具体的,在对网络标签向量集进行k-means聚类之前,先进行初始化:设定网络标签向量集中的簇的数目(即簇数目),和用于判断k-means聚类过程中迭代步骤是否结束的准则函数阈值;从网络标签向量集中随机选择与设定的簇数目相同数目的网络标签向量,分别作为各簇的初始质心,即第I次迭代过程中的各簇的质心。S102:根据第j次迭代过程中的各簇的质心,进行第j次迭代过程中的一次聚类,从而确定第j次迭代过程中的网络标签向量集的各簇所包含的网络标签向量。具体的,根据各簇的第j次迭代过程中的各簇的质心,进行第j次迭代过程中的一次聚类过程为:针对网络
5、标签向量集中每个非质心的网络标签向量,分别计算该非质心的网络标签向量与各簇的第j次迭代过程中的质心之间的距离;确定出与该非质心的网络标签向量之间的距离最小的质心;将该非质心的网络标签向量聚类到(即划分到)确定出的质心所在的簇中;由此,确定出第j次迭代过程中的网络标签向量集的各簇所包含的网络标签向量。其中,非质心的网络标签向量具体指的是,网络标签向量集中除第j次迭代过程中的各簇的质心之外的其它网络标签向量。S103:根据第j次迭代过程中的网络标签向量集的各簇所包含的网络标签向量,计算第j次迭代过程中的准则函数值。具体地,在确定第j次迭代过程中的网络标签向量集的各簇所包含的网络标签向量后,针对第j
6、次迭代过程中的网络标签向量集中的每个簇,确定该簇的距离评估值:k-means聚类算法的准则函数一般 采用平方误差准则函数(squared-error crkterkon)进行距离评估值的计算,具体可以用如下公式I来表示:F= Pec|P-m|2 (公式 I)公式I中,簇C为网络标签向量集中的任一个簇,F为第j次迭代过程中簇C的距离评估值,P表示簇C中的任一个非质心网络标签向量,m表示簇C的质心,p-m表示P与m的差值,即P到m之间的距离。将第j次迭代过程中的各簇的距离评估值进行累加,得到第j次迭代过程中的准则函数值。S104:将第j次迭代过程中的准则函数值与设定的准则函数阈值进行比较;若第j次
7、迭代过程中的准则函数值大于准则函数阈值,则执行步骤S105;否则,结束迭代,执行步骤 S106。S105:计算各簇的新质心,分别作为第j+次迭代过程中的各簇的质心后,令j=j+l,跳转到步骤S102。具体的,对于步骤S102中第j次迭代过程中的一次聚类后得到的网络标签向量集的各簇,针对每簇,计算该簇中全部网络标签向量的平均向量,选择该簇中与计算出的平均向量距离最小的网络标签向量作为该簇的新质心,即第j+次迭代过程中的该簇的质心。在确定出第j+次迭代过程中的各簇的质心后,令j=j+l,跳转到步骤S102。S106:将第j次迭代过程中的一次聚类后得到的网络标签向量集的各簇,作为此次k-means聚
8、类所得到的最终的聚类结果,结束此次k-means聚类过程。具体的,将第j次迭代过程中的一次聚类后得到的网络标签向量集的各簇,亦即将第j次迭代过程中确定的网络标签向量集的各簇所包含的网络标签向量,作为此次k-means聚类所得到的最终的聚类结果,并结束此次k-means聚类过程。事实上,上述的每一次迭代过程,完成了对网络标签向量集的一次聚类;其中后一次迭代过程的准则函数值会小于前一次迭代过程的准则函数值,即后一次对网络标签集的聚类精度要高于或等于前一次的聚类精度。多次迭代过程,实际上是对网络标签向量集的多次聚类,且聚类精度是逐次提高的,当聚类精度恒定时,完成本次k-means聚类。然而,本发明的
9、发明人发现,现有的网络标签聚类方法即使采用多次迭代的聚类算法,达到聚类精度恒定时,其精度仍然不高。其原因有两个:其一,在对网络标签向量集运用聚类算法时,簇数目是固定的;如果设定的簇数目过多,则互相之间距离较小(相似度较大)的网络标签向量也有可能被聚类到不同的簇中,造成簇间精度降低和簇冗余;如果设定的簇数目过少,则互相之间距离较大(相似度较小)的网络标签向量也有可能被聚类到同一个簇中,造成簇内精度降低。总之,不合适的簇数目,会造成聚类结果的精度降低。另一个原因则是,由于在对网络标签向量集运用聚类算法前,每个簇的初始质心为随机选取,如果个别的,如介词、助词等组成的无意义的网络标签向量化后的网络标签
10、向量、不常用词汇组成的网络标签向量化后的网络标签向量等噪声性质的网络标签向量被选取为初始质心,则导致初始质心所在的簇将没有聚类的意义或者簇内聚类精度降低,总体上降低了聚类的精度。综上所述,现有技术的网络标签聚类方法所得到的聚类结果精度低,有必要提供一种聚类结果精度更高的网络标签聚类方法。发明内容针对上述现有技术存在的缺陷,本发明提供了一种网络标签聚类方法和系统,用以提高聚类结果的精度。本发明的技术方案公开了一种网络标签聚类方法,包括:计算网络标签向量集中各网络标签向量的模值,并根据模值大小对所述网络标签向量集中的网络标签向量进行排序;其中,所述网络标签向量是对网络标签进行向量化后得到的:对于一
11、个网络标签,其网络标签向量是由该网络标签与各网络资源的关联度作为向量元素构成的;根据排序结果,选取数目与簇数目相一致的、所述网络标签向量集中排序在前的网络标签向量,分别作为所述网络标签向量集中各簇的初始质心;所述簇数目为所述网络标签向量集中待聚类 的簇的数目;根据所述簇数目,以及确定的各簇的初始质心,对所述网络标签向量集运用聚类算法得到所述网络标签向量集中聚类后的各簇。其中,所述簇数目为预先设定的;或者所述簇数目根据如下方法确定:对于一组参考簇数目,分别针对其中每个参考簇数目,根据该参考簇数目,以及所述网络标签向量集中各参考簇的初始质心,对所述网络标签向量集进行参考性聚类,将得到的参考性聚类后
12、的各参考簇作为对应于该参考簇数目的参考性聚类结果;根据该参考簇数目的参考性聚类结果,计算每个参考簇的直径;将计算出的直径中的最大值作为对应于该参考簇数目的参考簇最大直径;根据对各参考簇数目的排序结果,针对两两相邻的参考簇数目,计算出该相邻的参考簇数目所对应的参考簇最大直径之间的差值,将计算出的差值作为对应于该相邻的参考簇数目的直径差值;将计算出的差值与设定的差值阈值进行比较,找出小于所述差值阈值的最大差值;根据找出的差值所对应的两个相邻的参考簇数目,确定出所述簇数目。其中,所述一组参考簇数目为预先设定的一组数目;或者所述一组参考簇数目是根据所述网络标签向量集中的网络标签向量个数确定的:对I 的
13、自然数,从中间隔选取设定个数的数字作为所述一组参考簇数目,或者从中以指数间隔或等值间隔选取数字作为所述一组参考簇数目;其中,为所述网络标签向量集中的网络标签向量个数。较优的,所述根据找出的差值所对应的两个相邻的参考簇数目,确定出所述簇数目,具体包括:以找出的差值所对应的两个相邻的参考簇数目中的较大的参考簇数目作为上限参考簇数目;以找出的差值所对应的两个相邻的参考簇数目中的较小的参考簇数目作为下限参考簇数目;选取所述上限参考簇数目和所述下限参考簇数目之间的数目作为所述簇数目。较优的,所述选取所述上限参考簇数目和所述下限参考簇数目之间的数目作为所述簇数目,具体包括:将位于所述上限参考簇数目和所述下
14、限参考簇数目之间的自然数作为待选簇数目集合中的元素,构成所述待选簇数目集合;判断所述待选簇数目集合中的元素个数是否小于设定的元素数目阈值;若小于,则从所述待选簇数目集合中任选一个数目作为所述簇数目;否则:将所述一组参考簇数目作为第I次迭代过程中的一组参考簇数目,所述待选簇数目集合作为第I次迭代过程中的待选簇数目集合后,对所述待选簇数目集合进行以下方法的迭代:将从第i次迭代过程中的待选簇数目集合中选取的一组参考簇数目,作为第i+1次迭代过程中的一组参考簇数目;针对第i+次迭代过程中的一组参考簇数目,确定第i+1次迭代过程中的待选簇数目集合;若判断第i+次迭代过程中的待选簇数目集合中的元素个数小于
15、所述元素数目阈值,则结束迭代,从最后一次迭代过程中的待选簇数目集合中任选一个数目作为所述簇数目;否则,进行下次迭代;其中,I为自然数。较优的,所述根据该参考簇数目,以及所述网络标签向量集中各参考簇的初始质心,对所述网络标签向量集进行参考性聚类,具体包括:针对所述网络标签向量集中每个非初始质心的网络标签向量,分别计算该非初始质心的网络标签向量与各簇的初始质心之间的距离;确定出与该非初始质心的网络标签向量之间的距离最小的初始质心;将该非初始质心的网络标签向量聚类到确定出的初始质心所在的簇中;以及所述聚类算法具体为k均值聚类算法。本发明的技术方案还公开了一种网络标签聚类方法,包括:对于一组参考簇数目
16、,分别针对其中每个参考簇数目,根据该参考簇数目,以及网络标签向量集中各参考簇的初始质心,对所述网络标签向量集进行参考性聚类,将得到的参考性聚类后的各参考簇作为对应于该参考簇数目的参考性聚类结果;根据该参考簇数目的参考性聚类结果,计算每个参考簇的直径;将计算出的直径中的最大值作为对应于该参考族数目的参考族最大直径;根据对各参考簇数目的排序结果,针对两两相邻的参考簇数目,计算出该相邻的参考簇数目所对应的参考簇最大直径之间的差值,将计算出的差值作为对应于该相邻的参考簇数目的直径差值;将计算出的差值与设定的差值阈值进行比较,找出小于所述差值阈值的最大差值;根据找出的差值所对应的两个相邻的参考簇数目,确定出簇数目;根据确定出的簇数目,以及数目与所述簇数目相应的、所述网络标签向量集中各簇的初始质心,对所述网络标签向量集运用聚类算法得到所述网络标签向量集中聚类后的各簇;其中,所述网络标签向量是对网络标签进行向量化后得到的:对于一个网络标签,其网络标签向量是由该网络标签与各网络资源的关联度作为向量元素构成的。其中,所述网络标签向量集中各簇的初始质心是从