[發明專利]用于將用戶分配到集群的方法和系統

有效

• 申請號: 201210016687.9
• 申請日: 2006-08-15
• 公開（公告）號: CN102682059A
• 公開（公告）日: 2012-09-19
• 發明（設計）人: 馬尤爾·達塔爾;阿舒托什·加爾格
• 申請（專利權）人: 谷歌公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中原信達知識產權代理有限責任公司 11219
• 代理人: 周亞榮;安翔

本申請是國際申請日為2006年8月15日、國際申請號為PCT/US2006/031868的PCT國際申請的、進入中國國家階段的國家申請號為200680038100.7、題為“基于集的相似性的可擴展用戶聚類”的專利申請的分案申請。

技術領域

本發明涉及數字數據處理，并且尤其涉及將計算機應用或系統的用戶分組為集群(cluster)。

背景技術

將用戶分組為集群的操作是出于多種目的。為了實現用戶的個性化，例如一種眾所周知的技術，即協同過濾(collaborative?filtering)，涉及將用戶進行聚類(clustering)并把在用戶集群中的其它用戶已經表達過興趣的項目推薦給用戶。一般可以認為用戶以多種方式表達對項目的興趣，例如，通過點擊項目、購買項目、或將項目添加到購物車。推薦可采用多種方式，例如以部分搜索結果的形式呈現給用戶，以用戶可能想要閱讀的新聞故事的形式進行展現，對用戶可能想要購買的項目進行確定等等。

一種實現用戶聚類的方法是先定義兩個用戶之間的距離度量(distance?measure)，然后使用眾所周知的諸如k-均值或分層合并聚類(HAC)的聚類算法將用戶進行聚類。然而，這些技術有缺點。例如，HAC的運行時間為O(n²)，對于數以億計的n值是難以實現的；而k-均值算法需要代表數據點的均值，當數據點是集的時候，這是不可行的。

發明內容

在特定實施方式中，本發明可提供可擴展的用戶聚類，其中每個用戶都以代表取自全體項目之中的項目的元素集的形式來表示。

例如，當給定用戶可以通過與計算機系統進行交互而選擇的全體項目時，每個用戶可以通過不同的行為(例如點擊項目，購買項目，將項目添加到購物列表、查看項目等)來表達它們對項目的各個子集的興趣。本發明的特定實施方式以此種方式將用戶進行聚類(即將用戶分配到集群)，也就是在相同集群之中的用戶可能在它們各自的項目子集之間具有高度的重疊。

一方面，符合本發明實施方式的計算機程序產品可使得數據處理裝置為多個用戶之中的每一個用戶獲得各自的興趣集，每個興趣集表示在其中各個用戶已通過與數據處理系統進行交互而表達了興趣的項目；對多個用戶之中的每一個用戶，確定各個興趣集的k個散列值(hash?value)，其中第i個散列值是在對應的第i個散列函數之下的各個興趣集之中的最小值，其中i是在1和k之間的整數，并且其中k是大于或等于1的整數；并且將多個用戶之中的每一個用戶分配到為各個用戶所建立的各個k個集群中的每一個集群，第i個集群由第i個散列值所代表，其中將多個用戶之中的每一個用戶分配到k個集群的完成不考慮任何其它用戶到k個集群的分配。

有利的實施方式可包括一個或多個下述特征。本產品可使得數據處理裝置將表達用戶興趣的行為記錄在日志中；并且使用該日志為多個用戶生成興趣集。

本產品可使得數據處理裝置為多個用戶之中的第一個用戶獲得已改變的興趣集；使用已改變的興趣集為第一用戶確定k個散列值；并且將第一用戶僅分配到由使用已改變的興趣集所確定的k個散列值所代表的各個k個集群之中的每一個集群，而不改變任何其它多個用戶到集群的分配。

在另一個方面，符合本發明實施方式的計算機程序產品可使得數據處理裝置為用戶獲得興趣集，興趣集代表在其中用戶已經通過與數據處理系統進行交互而表達了興趣的項目；確定興趣集的k個散列值，其中第i個散列值是在對應的第i個散列函數之下的興趣集之中的最小值，其中i是在1和k之間的整數，并且其中k是大于或等于1的整數；并且將用戶分配到k個集群中的每一個集群，第i個集群由第i個散列值所代表。

有益的實施方式可包括一個或多個下述特征。興趣集有m個元素；第i個散列值是單向散列函數的m個應用的最小值，每一個m應用將第i個種子值和興趣集之中的m個元素的各個元素進行散列。產品可使得數據處理裝置來使用k個用戶集群來為用戶完成協同過濾。

另一方面，符合本發明實施例的系統包括：由多個用戶使用數據處理系統所選擇的項目的日志；用于使用指紋函數和項目的日志來將多個用戶的每一個用戶分配到k個集群的裝置，其中k是大于或等于1的整數；并且基于第一用戶到一個或多個k個集群的分配，可運行協同過濾計算機程序應用來將信息提供給多個用戶的第一用戶。

有益的實施方式可以包括一個或多個下述特征。信息包括推薦、預計、或排名之中的至少一種。