5

我目前有一个 reddit 克隆类型的网站。我正在尝试根据我的用户以前喜欢的帖子推荐帖子。

似乎 K 最近邻或 k 均值是最好的方法。

我似乎无法理解如何实际实现这一点。我看过一些数学公式(例如 k 表示维基百科页面上的那个),但它们对我来说真的没有意义。

有人可以推荐一些伪代码,或者可以看的地方,这样我就可以更好地了解如何做到这一点?

4

5 回答 5

8

K-Nearest Neighbor(又名 KNN)是一种分类算法。

基本上,你需要一个包含 N 个项目的训练组并对它们进行分类。您如何对它们进行分类完全取决于您的数据,以及您认为该数据的重要分类特征是什么。在您的示例中,这可能是帖子的类别、发布项目的人、支持项目的人等。

一旦这个“训练”数据被分类,您就可以评估一个“未知”数据点。您可以通过在分类系统中定位最近的邻居来确定未知的“类别”。如果您通过 3 个最近邻确定分类,则可以将其称为 3-最近邻算法。

如何确定“最近邻”在很大程度上取决于您如何对数据进行分类。将数据绘制到 N 维空间中是很常见的,其中 N 表示您正在检查的不同分类特征的数量。

一个简单的例子:

假设您拥有可以在世界任何地方的任何陆地上的位置的经度/纬度坐标。让我们也假设您没有地图,但您确实有一个非常大的数据集,可以为您提供世界上许多不同城市的经度/纬度,并且您还知道这些城市位于哪个国家/地区。

如果我问你随机经度纬度点在哪个国家,你能算出来吗?你会怎么做才能弄清楚?

经度/纬度数据自然地落入 X、Y 图表中。所以,如果你在这张图上画出所有城市,然后是未知点,你将如何计算出未知的国家?您可能会开始围绕该点绘制圆圈,并逐渐变大,直到圆圈包含绘图上最近的 10 个城市。现在,您可以查看这 10 个城市的国家/地区。如果所有 10 个都在美国,那么您可以相当肯定地说您的未知点也在美国。但是如果只有6个城市在美国,另外4个在加拿大,你能说出你的未知点在哪里吗?您可能仍会猜测美国,但不确定性较低。

KNN 最困难的部分是弄清楚如何对数据进行分类,以便确定具有相似质量的“邻居”以及与这些邻居的距离。

于 2011-06-01T19:23:37.993 回答
2

您所描述的听起来像是推荐系统引擎,而不是像 k-means 这样的聚类算法,本质上是一种无监督的方法。我无法清楚地了解 reddit 的实际用途,但我通过谷歌搜索“recommender + reddit”发现了一些有趣的帖子,例如Reddit、Stumbleupon、Del.icio.us 和 Hacker News Algorithms Exposed!无论如何,可以使用k-NN算法(在十大数据挖掘算法中描述,在 Wikipedia 上有伪代码),或者其他技术,如协作过滤(例如,亚马逊使用),在这个很好的教程中描述。

于 2011-06-02T10:11:16.677 回答
1

k-Means 聚类最简单的形式是取平均值并将其他平均值保持在一个中心平均值附近。假设您有以下值

1,2,3,4,6,7,8,9,10,11,12,21,22,33,40

现在,如果我进行 k-means 聚类并记住 k-means 聚类将具有偏差(均值/平均)机制,该机制将值靠近中心或远离中心。我们得到以下信息。

cluster-1 
1,2,3,4,5,6,7,8

cluster-2
10,11,12

cluster-3
21,22

cluster-4
33

cluster-5
40

请记住,我只是组成了这些集群中心(集群 1-5)。所以接下来,当你进行聚类时,数字最终会围绕这些中心平均值(也称为 k 中心)中的任何一个。上面的数据是一维的。

当您对具有多维的大型数据集执行 kmeans 聚类时(多维数据是一个值数组,您将拥有数百万个相同维度的值),您将需要更大且可扩展的东西。您将首先平均一个数组,您将获得一个值,同样您将对其他数组重复相同的操作,然后执行 kmean 聚类。

在这里阅读我的一个问题

希望这可以帮助。

于 2011-06-01T19:08:15.883 回答
1

要进行 k-最近邻,您主要需要距离概念和找到 k 最近邻到您可以负担的点的方法(您可能不想逐个搜索所有数据点)。在http://www.cs.umd.edu/~mount/ANN/有一个近似最近邻的库。这是一个非常简单的分类算法——对一个新点 p 进行分类,找到它的 k 个最近邻,然后根据这 k 个邻居中最流行的类对 p 进行分类。

我想在您的情况下,您可以在确定最近的含义后立即向某人提供类似帖子的列表,然后监控点击率并尝试从中学习以预测哪些替代方案最受欢迎。

如果您有兴趣为您的目的找到一个特别好的学习算法,请查看http://www.cs.waikato.ac.nz/ml/weka/ - 它允许您尝试大量不同的算法,也可以自己编写插件。

于 2011-06-02T05:10:19.433 回答
0

这是 MINST 数据集的一个非常简单的 KNN 示例一旦您能够计算文档之间的距离,相同的算法就可以工作

http://shyamalapriya.github.io/digit-recognition-using-k-nearest-neighbors/

于 2014-09-25T02:28:17.093 回答