CN102646097A - 一种聚类方法及装置 - Google Patents

Abstract

本发明公开了一种聚类方法及装置，其中，一种聚类方法包括：通过MinHash聚类模型为多个用户划分类别，存储所述MinHash聚类模型的哈希函数，以及存储所述多个用户的哈希值与所述类别的对应关系；通过所述MinHash聚类模型的哈希函数确定新用户的哈希值；根据所述哈希值与所述类别的对应关系，确定所述新用户的哈希值对应的类别。通过确定MinHash聚类模型的哈希函数以及哈希值与类别的对应关系，实现利用已有的MinHash聚类模型将新用户快速重聚类，不再需要重新生成聚类模型，提高对新用户的聚类效率。

Description

一种聚类方法及装置

技术领域

本发明涉及网络技术领域，尤其涉及一种聚类方法及装置。

背景技术

MinHash(Minwise Independent Permutation Hashing，一种符合交换独立条件的哈希)技术，把用户表示为元素的集合，基于MinHash的聚类方法可以估算两个集合之间的相似度，实现快速聚类的作用，进而提供用户推荐，如应用于近似网页检测方面，提供近似网页推荐。

但是，对于一个新集合而言，由于之前没有参与聚类，即新集合从属的聚类是未知的，MinHash的聚类方法无法直接确定新集合属于的类，只能重新生成聚类模型，得到新集合属于的类，才能进一步作推荐，导致新用户的聚类效率低，影响新用户的推荐效率。

发明内容

本发明实施例提供一种聚类方法及装置，其提高对新用户的聚类效率。

一种聚类方法，包括：

通过MinHash聚类模型为多个用户划分类别，存储所述MinHash聚类模型的哈希函数，以及存储所述多个用户的哈希值与所述类别的对应关系；

通过所述MinHash聚类模型的哈希函数确定新用户的哈希值；

根据所述哈希值与所述类别的对应关系，确定所述新用户的哈希值对应的类别。

一种聚类装置，包括：

划分单元，用于通过MinHash聚类模型为多个用户划分类别，存储所述MinHash聚类模型的哈希函数，以及存储所述多个用户的哈希值与所述类别的对应关系；

确定单元，用于通过所述MinHash聚类模型的哈希函数确定新用户的哈希值；

聚类单元，用于根据所述哈希值与所述类别的对应关系，确定所述新用户的哈希值对应的类别。

本发明实施例提供的聚类方法及装置，通过确定MinHash聚类模型的哈希函数以及哈希值与类别的对应关系，实现利用已有的MinHash聚类模型将新用户快速重聚类，不再需要重新生成聚类模型，提高对新用户的聚类效率。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域的普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他附图。

图1为本发明实施例提供的聚类方法的流程示意图。

图2为本发明实施例提供的聚类装置的构成示意图一。

图3为本发明实施例提供的聚类装置的构成示意图二。

图4为本发明实施例提供的聚类方法在一应用场景下的流程示意图。

具体实施方式

下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明的保护范围。

如图1所示，本发明实施例提供一种聚类方法，包括：

11、通过MinHash聚类模型为多个用户划分类别，存储MinHash聚类模型的哈希函数，以及存储多个用户的哈希值与类别的对应关系。

12、通过MinHash聚类模型的哈希函数确定新用户的哈希值。

13、根据哈希值与类别的对应关系，确定新用户的哈希值对应的类别。

由上述本发明提供的技术方案可以看出，通过确定MinHash聚类模型的哈希函数以及哈希值与类别的对应关系，实现利用已有的MinHash聚类模型将新用户快速重聚类，不再需要重新生成聚类模型，提高对新用户的聚类效率。

具体而言，本发明实施例提供一种聚类方法中，用户可以对应定义为多个关键字(或元素)构成的集合，如描述用户兴趣的关键字构成的集合A，如在音乐推荐中，关键字可以为用户收藏的歌曲，在新闻推荐中，关键字可以为用户浏览过的新闻的关键词，在电影推荐中，关键字可以为用户观看过的电影等等。

当用户的兴趣有了改变，集合的关键字增加或减少，则可以为该用户建立一个新的用户概况(profile)，把该用户当作新的用户。

可选的，MinHash聚类模型的哈希函数，可以包括：

一组哈希函数或者多组哈希函数，其中，每组哈希函数由多个不同的哈希函数构成。

示例性的，如q组不同的哈希函数，每组都有p个不同的哈希函数，对于每个集合，根据每组哈希函数生成一个速写(sketch)，该速写由p个哈希值构成，对于每一个集合，得到q个速写。

其中，MinHash聚类模型中哈希函数可以为随机哈希函数，不受限制。

具体而言，步骤11通过MinHash聚类模型为多个用户划分类别，存储MinHash聚类模型的哈希函数，以及存储多个用户的哈希值与类别的对应关系，可以包括：

确定并存储MinHash聚类模型的哈希函数。

通过MinHash聚类模型的哈希函数确定多个用户的哈希值。

将哈希值一致的用户划分为同一个类别。

存储哈希值与类别的对应关系。

其中，基于MinHash聚类模型的哈希函数是随机生成的，确定MinHash聚类模型的哈希函数后，可以存储MinHash聚类模型的哈希函数，以便后续处理新用户的时候，在已有的MinHash聚类模型里面找到这个新用户对应的类别。另外，存储MinHash聚类模型的哈希函数的步骤与通过MinHash聚类模型为多个用户划分类别的步骤之间没有限定先后顺序关系，即存储MinHash聚类模型的哈希函数的步骤可以在通过MinHash聚类模型为多个用户划分类别的步骤之前或之后。

示例性的，对于每个集合，根据每组哈希函数生成一个速写，该速写由p个哈希值构成，对于每一个集合，得到q个速写。如果给定两个集合，只要两个集合的q个速写中有一个速写是一样的，就把这两个集合聚在一起，划分成同一个类别。还可以根据划分的类别，确定类别与速写的对应关系，即哈希值与类别的对应关系。

而且，确定q组不同的哈希函数，并可以保存q组不同的哈希函数。

后续的，处理新用户的时候，进入步骤12通过MinHash聚类模型的哈希函数确定新用户的哈希值，进入步骤13根据哈希值与类别的对应关系，确定新用户的哈希值对应的类别，从而实现快速重聚类，不再需要重新生成聚类模型，提高对新用户的聚类效率，进而对新用户也能进行基于聚类的推荐。

步骤12通过MinHash聚类模型的哈希函数确定新用户的哈希值，可以包括：

通过MinHash聚类模型的哈希函数，并行确定一组新用户的哈希值。

步骤13根据哈希值与类别的对应关系，确定新用户的哈希值对应的类别，可以包括：

根据哈希值与类别的对应关系，并行确定一组新用户的哈希值对应的类别。

可见，并行确定一组新用户的哈希值，便于并行确定新用户的哈希值对应的类别，提高聚类效率。

由上述本发明提供的技术方案可以看出，MinHash聚类模型的聚类是可并行的，每个用户计算MinHash的时候相互独立，一旦哈希值计算出来之后，用户所属的类别也就确定了。对于新用户，计算MinHash也同样独立，不受其他已有用户的影响，对新用户的哈希值，只要保证哈希函数一样，对新用户按同样的方式生成一个速写，就能在已有的MinHash聚类模型里面找到这个新用户对应的类别。

本发明实施例聚类方法，还可以包括：

确定新用户的类别后，为新用户提供用户推荐。

其中，MinHash聚类模型的推荐可以参考下述示例得以理解。

示例性的，一个新用户u，找到这个用户所属于的类别c，计算用户与这个类别的相似度sim(u，c)，然后对于这个类别里面的每个元素ci，计算这个元素在类别里面出现的次数COUNT(ci)，那么元素ci推荐给用户的分数是sim(u，c)＊COUNT(ci)。对于类别c里面所有的元素，都会生成这样一个推荐分数，然后根据分数排序，最终推荐给用户。

由上述本发明提供的技术方案可以看出，通过确定MinHash聚类模型的哈希函数以及哈希值与类别的对应关系，实现利用已有的MinHash聚类模型将新用户快速重聚类，不再需要重新生成聚类模型，提高对新用户的聚类效率，进而提高了新用户的推荐效率。

基于MinHash聚类模型对新用户进行推荐，只需要生成p＊q个哈希函数，然后在聚类模型中找到对应的类别即可，最多只需q次文件操作(一般只有两到三次)，推荐速度较快。而且，基于MinHash聚类模型对新用户进行推荐，可以充分利用MinHash聚类模型的精度优势，推荐结果的精确度较高，避免基于条目的推荐只能根据单个条目去选择对应的推荐结果，而用户的历史条目是很多的，单个条目不能代表用户的兴趣，虽然推荐结果的合并能反映用户的整体兴趣，但是不能利用历史条目之间的关系，这样会导致推荐精度有所损失。

本发明实施例聚类方法，可以适用于所有用户，即只要用户的兴趣有了改变，则可以为该用户建立一个新的用户概况，把该用户当作新的用户，给出实时的推荐结果。

如图2所示，对应于上述本发明实施例提供的聚类方法，本发明实施例提供一种聚类装置，包括：

划分单元21，用于通过MinHash聚类模型为多个用户划分类别，存储MinHash聚类模型的哈希函数，以及存储多个用户的哈希值与类别的对应关系。

确定单元22，用于通过MinHash聚类模型的哈希函数确定新用户的哈希值。

聚类单元23，用于根据哈希值与类别的对应关系，确定新用户的哈希值对应的类别。

由上述本发明提供的技术方案可以看出，通过确定MinHash聚类模型的哈希函数以及哈希值与类别的对应关系，实现利用已有的MinHash聚类模型将新用户快速重聚类，不再需要重新生成聚类模型，提高对新用户的聚类效率。

具体而言，本发明实施例提供一种聚类装置，用户可以对应定义为多个关键字构成的集合，如集合A，新用户可以对应定义集合增加或减少关键字。

可选的，MinHash聚类模型的哈希函数，可以包括：

一组哈希函数或者多组哈希函数，其中，每组哈希函数由多个不同的哈希函数构成。

其中，MinHash聚类模型中哈希函数可以为随机哈希函数，不受限制。

示例性的，如q组不同的哈希函数，每组都有p个不同的哈希函数，对于每个集合，根据每组哈希函数生成一个速写，该速写由p个哈希值构成，对于每一个集合，得到q个速写。

如图3所示，划分单元21，可以包括：

第一存储子单元31，用于确定并存储MinHash聚类模型的哈希函数。

第一确定子单元32，用于通过MinHash聚类模型的哈希函数确定多个用户的哈希值。

划分子单元33，用于将哈希值一致的用户划分为同一个类别。

第二存储子单元34，用于存储哈希值与类别的对应关系。

可选的，可以一次处理一批新用户，则确定单元22，可以具体用于通过MinHash聚类模型的哈希函数，并行确定一组新用户的哈希值。

聚类单元23，可以具体用于根据哈希值与类别的对应关系，并行确定一组新用户的哈希值对应的类别。

本发明实施例聚类装置及其构成部分的作用，可以对应于上述本发明实施例提供的聚类方法的相关内容得以理解，在此不作赘述。

由上述本发明提供的技术方案可以看出，MinHash聚类模型的聚类是可并行的，每个用户计算MinHash的时候相互独立，一旦哈希值计算出来之后，用户所属的类别也就确定了。对于新用户，计算MinHash也同样独立，不受其他已有用户的影响，对新用户的哈希值，只要保证哈希函数一样，对新用户按同样的方式生成一个速写，就能在已有的MinHash聚类模型里面找到这个新用户对应的类别。

本发明实施例聚类装置，还可以包括：

推荐单元，用于确定新用户的类别后，为新用户提供用户推荐。

其中，MinHash聚类模型的推荐可以参考下述示例得以理解。

示例性的，一个新用户u，找到这个用户所属于的类别c，计算用户与这个类别的相似度sim(u，c)，然后对于这个类别里面的每个元素ci，计算这个元素在类别里面出现的次数COUNT(ci)，那么元素ci推荐给用户的分数是sim(u，c)＊COUNT(ci)。对于类别c里面所有的元素，都会生成这样一个推荐分数，然后根据分数排序，最终推荐给用户。

由上述本发明提供的技术方案可以看出，通过确定MinHash聚类模型的哈希函数以及哈希值与类别的对应关系，实现利用已有的MinHash聚类模型将新用户快速重聚类，不再需要重新生成聚类模型，提高对新用户的聚类效率，进而提高了新用户的推荐效率。

基于MinHash聚类模型对新用户进行推荐，只需要生成p＊q个哈希函数，然后在聚类模型中找到对应的类别即可，最多只需q次文件操作(一般只有两到三次)，推荐速度较快。而且，基于MinHash聚类模型对新用户进行推荐，可以充分利用MinHash聚类模型的精度优势，推荐结果的精确度较高，避免基于条目的推荐只能根据单个条目去选择对应的推荐结果，而用户的历史条目很多，单个条目不能代表用户的兴趣，虽然推荐结果的合并能反映用户的整体兴趣，但是不能利用历史条目之间的关系，导致推荐精度有所损失。

下面将结合具体应用场景对本发明实施例聚类方法作进一步地详细描述。

首先，说明MinHash聚类模型原理：

定义V表示元素的全集，那么随机哈希函数就可以表示成f：V→R，R是实数集。如果Xa和Xb是全集中任意两个不同的元素，那么哈希函数必须满足两个条件，f(Xa)≠f(Xb)和P(f(Xa)＜f(Xb))＝0.5，P(·)表示概率，这两个条件的意思是，任意两个不同的元素的哈希值不能相等，并且任意一个元素的哈希值小于另一个元素的哈希值的概率是0.5，即不同元素的哈希值的大小关系必须是随机的。

在这样的哈希函数的基础上，如果A是全集V上的子集，定义MinHash为：

$h(f,A)=\underset{X\∈A}{\min }f\left(X\right)---\left(1\right)$

对于同样的哈希函数，集合A和B的哈希值的相同的概率是：

$P(h(f,A)=h(f,B))=\frac{|A\∩B|}{|A\∪B|}---\left(2\right)$

式(2)右边表示集合A和集合B的相似度，即集合A和B的哈希值相同的概率等于集合A和B的相似度。

应用MinHash聚类比较直接，如果集合A和集合B的哈希值一样，那么就把集合A和B聚到同一个类，类的标号就用它们相同的哈希值h标识。集合A和集合B聚合子一起的概率为它们的相似度。

为了提高聚类的精确度，通常可以取p个不同的哈希函数，要求同一个类别里面的集合的哈希值都要相等，但是容易导致聚类的召回率快速降低。

为了提高召回率，通常是取q组不同的哈希函数，每组都有p个不同的哈希函数，对于每个集合A，根据每组哈希函数生成一个速写，该速写由p个哈希值构成(速写中多个哈希值之间可以用逗号隔开)。对于每一个集合A，得到q个速写。给定两个集合，只要有一个速写是一样的，就把这两个集合聚在一起。这样增加了聚在一起的概率，能有效地提高聚类的召回率，但也同时降低了类间相似度，也就降低了聚类的精确度。

再说明MinHash聚类模型的推荐原理：

给定一个用户u，找到这个用户所属于的类别c，计算用户与这个类的相似度sim(u，c)，然后对于这个类里面的每个元素ci，计算这个元素在类里面出现的次数COUNT(ci)，那么元素ci推荐给用户的分数是sim(u，c)＊COUNT(ci)。对于类别c所有的元素，都会生成这样一个推荐分数，然后根据分数排序，最终推荐给用户。

在一个用户可以属于多个类别的情况下，处理也是类似的，具体过程如下：首先对每个类别做如上所述的处理，然后把类别里面的所有元素合在一起，并对相同元素的分数累加，最终得到一个长的推荐列表，排序之后推荐给用户。

如图4所示，MinHash聚类模型的哈希函数，如(f1，f2，…，fp)，图4终只示意出一组哈希函数。MinHash聚类模型的类别，如类1(h11，h21，…，hp1)，类2(h12，h22，…，hp2)，类3(h13，h23，…，hp3)，其中，(h11，h21，…，hp1)为速写。

本发明实施例聚类方法，包括：

41、通过MinHash聚类模型的哈希函数确定新用户的哈希值。

通过MinHash聚类模型，如(f1，f2，…，fp)确定新用户u_new的速写(h1_new，h2_new，…，hp_new)。

42、根据哈希值与类别的对应关系，确定新用户的哈希值对应的类别。

确定新用户u_new的速写(h1_new，h2_new，…，hp_new)对应的类别，如类3(h13，h23，…，hp3)。

43、为新用户提供用户推荐。

根据新用户unew的类3(h13，h23，…，hp3)得到推荐结果，进行用户推荐。

由上述本发明提供的技术方案可以看出，MinHash聚类模型的聚类是可并行的，每个用户计算MinHash的时候相互独立，一旦哈希值计算出来之后，用户所属的类别也就确定了。对于新用户，计算MinHash也同样独立，不受其他已有用户的影响，对新用户的哈希值，只要保证哈希函数一样，对新用户按同样的方式生成一个速写，就能在已有的MinHash聚类模型里面找到这个新用户对应的类别。

在本申请所提供的几个实施例中，应该理解到，所揭露的系统，装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明披露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求书的保护范围为准。

Claims (10)

1.一种聚类方法，其特征在于，包括：

通过MinHash聚类模型为多个用户划分类别，存储所述MinHash聚类模型的哈希函数，以及存储所述多个用户的哈希值与所述类别的对应关系；

通过所述MinHash聚类模型的哈希函数确定新用户的哈希值；

根据所述哈希值与所述类别的对应关系，确定所述新用户的哈希值对应的类别。

2.根据权利要求1所述的聚类方法，其特征在于，所述MinHash聚类模型的哈希函数为随机哈希函数。

3.根据权利要求1所述的聚类方法，其特征在于，所述MinHash聚类模型的哈希函数，包括：

一组哈希函数或者多组哈希函数，其中，每组哈希函数由多个不同的哈希函数构成。

4.根据权利要求1所述的聚类方法，其特征在于，所述通过MinHash聚类模型为多个用户划分类别，存储所述MinHash聚类模型的哈希函数，以及存储所述多个用户的哈希值与所述类别的对应关系，包括：

确定并存储所述MinHash聚类模型的哈希函数；

通过所述MinHash聚类模型的哈希函数确定所述多个用户的哈希值；

将所述哈希值一致的用户划分为同一个类别；

存储所述哈希值与所述类别的对应关系。

5.根据权利要求1所述的聚类方法，其特征在于，所述通过所述MinHash聚类模型的哈希函数确定新用户的哈希值，包括：

通过所述MinHash聚类模型的哈希函数，并行确定一组新用户的哈希值。

6.一种聚类装置，其特征在于，包括：

划分单元，用于通过MinHash聚类模型为多个用户划分类别，存储所述MinHash聚类模型的哈希函数，以及存储所述多个用户的哈希值与所述类别的对应关系；

确定单元，用于通过所述MinHash聚类模型的哈希函数确定新用户的哈希值；

聚类单元，用于根据所述哈希值与所述类别的对应关系，确定所述新用户的哈希值对应的类别。

7.根据权利要求6所述的聚类装置，其特征在于，所述MinHash聚类模型的哈希函数为随机哈希函数。

8.根据权利要求6所述的聚类装置，其特征在于，所述MinHash聚类模型的哈希函数，包括：

一组哈希函数或者多组哈希函数，其中，每组哈希函数由多个不同的哈希函数构成。

9.根据权利要求6所述的聚类装置，其特征在于，所述划分单元，包括：

第一存储子单元，用于确定并存储所述MinHash聚类模型的哈希函数；

第一确定子单元，用于通过所述MinHash聚类模型的哈希函数确定所述多个用户的哈希值；

划分子单元，用于将所述哈希值一致的所述用户划分为同一个类别；

第二存储子单元，用于存储所述哈希值与所述类别的对应关系。

10.根据权利要求6所述的聚类装置，其特征在于，所述聚类单元，具体用于通过所述MinHash聚类模型的哈希函数，并行确定一组新用户的哈希值。

Images