CN104915388A - 一种基于谱聚类和众包技术的图书标签推荐方法 - Google Patents

Abstract

本发明公开了一种基于谱聚类和众包技术的图书标签推荐方法，该方法应用于数字图书馆系统，通过使用用户的检索点击日志构建Laplacian矩阵，并利用谱聚类对检索词进行聚类，之后通过使用众包技术，对聚类的结果进行持续的优化，最后将优化的结果应用于推荐系统中。本发明将用户的检索词作为标签，通过谱聚类和众包技术的结合提升检索词聚类的准确度，从而提高系统在标签推荐方面的准确性。

Description

一种基于谱聚类和众包技术的图书标签推荐方法

技术领域

本发明属于基于谱聚类和众包技术的图书标签推荐技术，涉及一种基于谱聚类和众包技术的图书标签推荐方法。

背景技术

随着互联网信息的不断增多，信息呈现爆炸式增长，对信息合理高效的归类成为信息有效利用的关键。传统的归类方法主要通过人工的方式进行，而在海量信息的前提下，此种信息归类的方式已经难以为继，因而逐渐出现了以标签为核心的新型信息归类方式，并已经成为互联网应用的关键。在数字图书馆系统当中，标签主要来自图书信息，同时在用户使用系统的过程中，用户的检索词、图书标引信息也可以作为一种标签加入到系统当中，并以标签为纽带拉近用户与图书的关系，提升用户发现图书的效率。

同时，对于海量数据的应用，推荐系统得到越来越多的关注。用户获取信息的方式由全网式信息检索到领域知识的垂直检索，再到当前的推荐系统，信息的获取速度不断的加快，针对不同用户的信息个性化不断提高，推荐系统在系统可用性方面的贡献日益显著。聚类算法是数据挖掘的关键方法，在推荐系统中聚类算法用来实现对物品、用户的聚类，并通过算法的迭代运行来优化聚类的效果。

发明内容

本发明的目的在于针对现有推荐系统对检索词利用的不足，提供一种用于数字图书馆上基于谱聚类和众包技术的图书标签推荐方法。

本发明的目的是通过以下技术方案来实现的：一种基于谱聚类和众包技术的图书标签推荐方法，包括以下步骤：

(1)从日志收集系统或者Web日志中筛选出用户的检索数据和检索点击数据；

(2)利用用户的检索数据和检索点击数据，构建检索词-图书矩阵，根据检索词-图书矩阵得到检索词-检索词的Laplacian矩阵；

(3)使用谱聚类对Laplacian矩阵进行聚类操作，得到检索词的聚类结果；

(4)利用众包技术对步骤3所得到的聚类结果进行持续的优化；

(5)将用户过去的检索记录与步骤4优化后的聚类结果进行映射，利用映射后的聚类结构作为标签推荐给用户。

进一步地，所述步骤2具体为：从用户的检索数据中得到所有用户的检索词集合Q＝{q₁,q₂,…,q_n}，其中n为检索词的总数，q为独立检索词；从用户的检索点击数据中得到检索词点击的图书集合B＝{b₁,b₂,…,b_m}，其中m为点击图书的总数，b为独立的图书；根据所有用户的检索词集合Q和检索词点击的图书集合B得到检索词-图书矩阵M，对于检索词-图书矩阵M的每一项，定义如下：

其中I_ij为第i个检索词和第j本书的对应关系；针对每一本图书，如果有多个检索词均对这本书存在点击行为，那么这些检索词之间存在联系，根据检索词之间的联系构建检索词-检索词矩阵D，对于检索词-检索词矩阵D的每一项，如果两个检索词之间存在联系则为1，否则为0；通过把检索词-检索词矩阵D的每一列元素相加得到的值置于对角线上，其它位置设为0，从而构成新的矩阵W；Laplacian矩阵L通过公式L＝D-W求出。

进一步地，所述步骤3具体为：对于谱聚类算法，选定的目标函数RatioCut为：

$\mathrm{RatioCut}(A_i,...,A_k)=\frac{1}{2}\underset{i=1}{\overset{k}{\mathrm{\Σ}}}\frac{W(A_i,\stackrel{\‾}{A_i})}{\left|A_i\right|}=\underset{i=1}{\overset{k}{\mathrm{\Σ}}}\frac{\mathrm{cut}(A_i,\stackrel{\‾}{A_i})}{\left|A_i\right|}$

其中k为聚类的个数，A_i表示第i个聚类结果，|A_i|表示第i个聚类结果中的检索词数量，表示除去A_i之外的其它聚类结果集合，表示第i个聚类结果与其他聚类结果的权重之和，的计算公式为其中W(a,b)为聚类结果a与聚类结果b的权重；根据Laplacian矩阵L的性质推出最小化目标函数RatioCut等价于最小化Laplacian矩阵，从而使用SVD矩阵分解的方法实现对Laplacian矩阵的降维，使用K-mean聚类算法完成对降维后的Laplacian矩阵的聚类操作。

进一步地，所述步骤4具体为：将步骤3得到的检索词的聚类结果中检索词对应的用户作为众包的选定用户，通过发送邮件的方式将聚类的结果发送给选定用户，选定用户的反馈定义为：

其中，Query表示一个检索词，正反馈表示用户认为该检索词符合所在聚类结果的主题，负反馈表示用户认为该检索词不符合聚类结果的主题，零反馈表示该检索词难以判断是否符合主题；根据选定用户对一个聚类结果的反馈信息，对该聚类结果进行以下三种不同方式的处理：

(a)选定用户的反馈信息表明该聚类可以很好的表明某一个主题，其具体体现在两个方面：一方面是负反馈结果少于正反馈结果，另一方面是用户的反馈信息不存在彼此矛盾的情况；在这种情况下，删除聚类结果中的负反馈，保留正反馈和零反馈的检索词；

(b)选定用户的反馈信息混乱，难以表明该聚类效果的优劣，其具体表现为多名用户对相同检索词的反馈信息不同甚至相反；该种情况下，意味着当前选定用户的反馈信息尚不足以对该聚类进行判断，因而需要引入新的用户，重新众包任务分发操作；

(c)选定用户的反馈信息表明该聚类不具有明确的主题，具体表现为在选定用户的反馈中超过50％的检索词的反馈信息不同或相反；在这种情况下，直接将该聚类结果删除。

本发明的有益效果是：该方法利用谱聚类对用户的检索词信息进行聚类，并使用众包技术对聚类的结果持续的优化，最终实现利用检索词提高图书标签推荐的效果。本发明在聚类结果的基础上，提出了通过使用众包技术来实现对聚类结果进行优化的目的，通过收集多个用户对聚类结果的反馈信息来判断并优化聚类的结果，并将聚类的结果应用到推荐系统当中。

附图说明

图1是本发明基于谱聚类和众包技术的图书标签推荐方法的流程图。

具体实施方式

下面结合附图对本发明作进一步详细说明。

如图1所示，本发明一种基于谱聚类和众包技术的图书标签推荐方法，包括以下步骤：

(1)从日志收集系统或者Web日志中筛选出用户的检索数据和检索点击数据；

(2)利用用户的检索数据和检索点击数据，构建检索词-图书矩阵，根据检索词-图书矩阵得到检索词-检索词的Laplacian矩阵；具体为：从用户的检索数据中得到所有用户的检索词集合Q＝{q₁,q₂,...,q_n}，其中n为检索词的总数，q为独立检索词；从用户的检索点击数据中得到检索词点击的图书集合B＝{b₁,b₂,...,b_m}，其中m为点击图书的总数，b为独立的图书；根据所有用户的检索词集合Q和检索词点击的图书集合B得到检索词-图书矩阵M，对于检索词-图书矩阵M的每一项，定义如下：

其中I_ij为第i个检索词和第j本书的对应关系；针对每一本图书，如果有多个检索词均对这本书存在点击行为，那么这些检索词之间存在联系，根据检索词之间的联系构建检索词-检索词矩阵D，对于检索词-检索词矩阵D的每一项，如果两个检索词之间存在联系则为1，否则为0；通过把检索词-检索词矩阵D的每一列元素相加得到的值置于对角线上，其它位置设为0，从而构成新的矩阵W；Laplacian矩阵L通过公式L＝D-W求出。

(3)使用谱聚类对Laplacian矩阵进行聚类操作，得到检索词的聚类结果；具体为：对于谱聚类算法，选定的目标函数RatioCut为：

$\mathrm{RatioCut}(A_i,...,A_k)=\frac{1}{2}\underset{i=1}{\overset{k}{\mathrm{\Σ}}}\frac{W(A_i,\stackrel{\‾}{A_i})}{\left|A_i\right|}=\underset{i=1}{\overset{k}{\mathrm{\Σ}}}\frac{\mathrm{cut}(A_i,\stackrel{\‾}{A_i})}{\left|A_i\right|}$

其中k为聚类的个数，A_i表示第i个聚类结果，|A_i|表示第i个聚类结果中的检索词数量，表示除去A_i之外的其它聚类结果集合，表示第i个聚类结果与其他聚类结果的权重之和，的计算公式为其中W(a,b)为聚类结果a与聚类结果b的权重；根据Laplacian矩阵L的性质推出最小化目标函数RatioCut等价于最小化Laplacian矩阵，从而使用SVD矩阵分解的方法实现对Laplacian矩阵的降维，使用K-mean聚类算法完成对降维后的Laplacian矩阵的聚类操作。

(4)利用众包技术对步骤3所得到的聚类结果进行持续的优化；具体为：将步骤3得到的检索词的聚类结果中检索词对应的用户作为众包的选定用户，通过发送邮件的方式将聚类的结果发送给选定用户，选定用户的反馈定义为：

其中，Query表示一个检索词，正反馈表示用户认为该检索词符合所在聚类结果的主题，负反馈表示用户认为该检索词不符合聚类结果的主题，零反馈表示该检索词难以判断是否符合主题；根据选定用户对一个聚类结果的反馈信息，对该聚类结果进行以下三种不同方式的处理：

(a)选定用户的反馈信息表明该聚类可以很好的表明某一个主题，其具体体现在两个方面：一方面是负反馈结果少于正反馈结果，另一方面是用户的反馈信息不存在彼此矛盾的情况；在这种情况下，删除聚类结果中的负反馈，保留正反馈和零反馈的检索词；

(b)选定用户的反馈信息混乱，难以表明该聚类效果的优劣，其具体表现为多名用户对相同检索词的反馈信息不同甚至相反；该种情况下，意味着当前选定用户的反馈信息尚不足以对该聚类进行判断，因而需要引入新的用户，重新众包任务分发操作；

(c)选定用户的反馈信息表明该聚类不具有明确的主题，具体表现为在选定用户的反馈中超过50％的检索词的反馈信息不同或相反；在这种情况下，直接将该聚类结果删除。

(5)将用户过去的检索记录与步骤4优化后的聚类结果进行映射，利用映射后的聚类结构作为标签推荐给用户。

Claims (4)

1.一种基于谱聚类和众包技术的图书标签推荐方法，其特征在于，包括以下步骤：

(1)从日志收集系统或者Web日志中筛选出用户的检索数据和检索点击数据；

(2)利用用户的检索数据和检索点击数据，构建检索词-图书矩阵，根据检索词-图书矩阵得到检索词-检索词的Laplacian矩阵；

(3)使用谱聚类对Laplacian矩阵进行聚类操作，得到检索词的聚类结果；

(4)利用众包技术对步骤3所得到的聚类结果进行持续的优化；

(5)将用户过去的检索记录与步骤4优化后的聚类结果进行映射，利用映射后的聚类结构作为标签推荐给用户。

2.根据权利要求1所述一种基于谱聚类和众包技术的图书标签推荐方法，其特征在于，所述步骤2具体为：从用户的检索数据中得到所有用户的检索词集合Q＝{q₁,q₂,…,q_n}，其中n为检索词的总数，q为独立检索词；从用户的检索点击数据中得到检索词点击的图书集合B＝{b₁,b₂,…,b_m}，其中m为点击图书的总数，b为独立的图书；根据所有用户的检索词集合Q和检索词点击的图书集合B得到检索词-图书矩阵M，对于检索词-图书矩阵M的每一项，定义如下：

其中I_ij为第i个检索词和第j本书的对应关系；针对每一本图书，如果有多个检索词均对这本书存在点击行为，那么这些检索词之间存在联系，根据检索词之间的联系构建检索词-检索词矩阵D，对于检索词-检索词矩阵D的每一项，如果两个检索词之间存在联系则为1，否则为0；通过把检索词-检索词矩阵D的每一列元素相加得到的值置于对角线上，其它位置设为0，从而构成新的矩阵W；Laplacian矩阵L通过公式L＝D-W求出。

3.根据权利要求1所述一种基于谱聚类和众包技术的图书标签推荐方法，其特征在于，所述步骤3具体为：对于谱聚类算法，选定的目标函数RatioCut为：

$\mathrm{RatioCut}(A_i,...,A_k)=\frac{1}{2}\underset{i=1}{\overset{k}{\mathrm{\Σ}}}\frac{W(A_i,\stackrel{\‾}{A_i})}{\left|A_i\right|}=\underset{i=1}{\overset{k}{\mathrm{\Σ}}}\frac{\mathrm{cut}(A_i,\stackrel{\‾}{A_i})}{\left|A_i\right|}$

其中k为聚类的个数，A_i表示第i个聚类结果，|A_i|表示第i个聚类结果中的检索词数量，表示除去A_i之外的其它聚类结果集合，表示第i个聚类结果与其他聚类结果的权重之和，的计算公式为其中W(a,b)为聚类结果a与聚类结果b的权重；根据Laplacian矩阵L的性质推出最小化目标函数RatioCut等价于最小化Laplacian矩阵，从而使用SVD矩阵分解的方法实现对Laplacian矩阵的降维，使用K-mean聚类算法完成对降维后的Laplacian矩阵的聚类操作。

4.根据权利要求1所述一种基于谱聚类和众包技术的图书标签推荐方法，其特征在于，所述步骤4具体为：将步骤3得到的检索词的聚类结果中检索词对应的用户作为众包的选定用户，通过发送邮件的方式将聚类的结果发送给选定用户，选定用户的反馈定义为：

其中，Query表示一个检索词，正反馈表示用户认为该检索词符合所在聚类结果的主题，负反馈表示用户认为该检索词不符合聚类结果的主题，零反馈表示该检索词难以判断是否符合主题；根据选定用户对一个聚类结果的反馈信息，对该聚类结果进行以下三种不同方式的处理：

(a)选定用户的反馈信息表明该聚类可以很好的表明某一个主题，其具体体现在两个方面：一方面是负反馈结果少于正反馈结果，另一方面是用户的反馈信息不存在彼此矛盾的情况；在这种情况下，删除聚类结果中的负反馈，保留正反馈和零反馈的检索词；

(b)选定用户的反馈信息混乱，难以表明该聚类效果的优劣，其具体表现为多名用户对相同检索词的反馈信息不同甚至相反；该种情况下，意味着当前选定用户的反馈信息尚不足以对该聚类进行判断，因而需要引入新的用户，重新众包任务分发操作；

(c)选定用户的反馈信息表明该聚类不具有明确的主题，具体表现为在选定用户的反馈中超过50％的检索词的反馈信息不同或相反；在这种情况下，直接将该聚类结果删除。