用WEKA进行数据挖掘，第3部分 最近邻和服务器端库

简介

在这个 “用 WEKA 进行数据挖掘” 系列之前的两篇文章中，我介绍了数据 挖掘的概念。如果您还未曾阅读过 用 WEKA 进行数据挖掘，第 1 部分：简介和 回归 和 用 WEKA 进行数据挖掘，第 2 部分：分类和群集，那么请先阅读这两 个部分，因为二者涵盖了一些在继续之前必须了解的关键概念。而且更重要的是 ，在这两个部分中我谈及了数据挖掘中常用的三种技术，它们可以将难以理解的 无用数据转变为有意义的规则和趋势。第一种技术是回归，用来基于其他的示例 数据预测一个数值输出（比如房屋价值）。第二种技术是分类（即分类树或决策 树），用来创建一个实际的分支树来预测某个未知数据点的输出值。（在我们的 例子中，我们预测的是对 BMW 促销活动的反应。）我介绍的第三种技术是群集 ，可用它来创建数据组（群集）并从中识别出趋势和其他规则（在我们的例子中 ，即 BMW 的销售）。三者的相似点在于它们都能将数据转换成有用信息，但它 们各自的实现方法以及使用的数据各不相同，而这正是数据挖掘最为重要的一点 ：正确的模型必须用于正确的数据。

本文将讨论四种常用的数据挖掘技术中的最后一种：最近邻。您将看到它更 像是分类与群集的组合，并为我们消灭数据误导的使命提供了另一种有用的武器 。

在我们之前的文章中，我们将 WEKA 用作一种独立的应用程序。那么它在实 际中能多有用呢？很显然，它并不完美。由于 WEKA 是一种基于 Java 的应用程 序，它有一个可被用在我们自己的服务器端代码中的 Java 库。对于大多数人而 言，这可能是最为常见的用法，因为您可以编写代码来不断地分析您的数据并动 态地做出调整，而不必依赖他人提取数据、将其转换成 WEKA 格式，然后再在 WEKA Explorer 内运行它。

最近邻

最近邻（也即 Collaborative Filtering 或 Instance-based Learning）是 一种非常有用的数据挖掘技术，可用来用输出值已知的以前的数据实例来预测一 个新数据实例的未知输出值。从目前的这种描述看来，最近邻非常类似于回归和 分类。那么它与这二者究竟有何不同呢？首先，回归只能用于数值输出，这是它 与最近邻的最直接的一个不同点。分类，如我们在前一篇文章的例子中看到的， 使用每个数据实例 来创建树，我们需要遍历此树才能找到答案。而这一点对于 某些数据而言会是一个很严重的问题。举个例子，亚马逊这样的公司常常使用 “购买了 X 的顾客还购买了 Y" 特性，如果亚马逊拟创建一个分类树，那么它 将需要多少分支和节点？它的产品多达数十万。这个树将有多巨大呀？如此巨大 的一个树能有多精确呢？即便是单个分支，您都将会惊讶地发现它只有三个产品 。亚马逊的页面通常会有 12 种产品推荐给您。对于这类数据，分类树是一种极 不适合的数据挖掘模型。

而最近邻则可以非常有效地解决所有这些问题，尤其是在上述亚马逊的例子 中遇到的这些问题。它不会受限于数量。它的伸缩性对于 20 个顾客的数据库与 对于 2000 万个顾客的数据库没有什么差异，并且您可以定义您想要得到的结果 数。看起来是一个很棒的技术！它的确很棒 — 并且可能对于那些正在阅读本文 的电子商务店铺的店主最为有用。

让我们先来探究一下最近邻背后的数学理论，以便能更好地理解这个过程并 了解此技术的某些限制。

最近邻背后的数学理论

最近邻技术背后的数学理论非常类似于群集技术所涉及到的数学理论。对于 一个未知的数据点，这个未知数据点与每个已知数据点之间的距离需要被计算出 来。如果用电子数据表计算此距离将会非常繁琐，而一个高性能的计算机则可以 立即完成这些计算。最容易也是最为常见的一种距离计算方式是 “Normalized Euclidian Distance”。它看起来复杂，实则不然。让我们通过一个例子来弄清 楚第 5 个顾客有可能会购买什么产品？

清单 1. 最近邻的数学理论

Customer　　　Age　　　Income　　　Purchased　Product
1　　　　　　45　　　　46k　　　　Book
2　　　　　　39　　　　100k　　　TV
3　　　　　　35　　　　38k　　　　DVD
4　　　　　　69　　　　150k　　　Car　Cover
5　　　　　　58　　　　51k　　　　???

Step　2:　Calculate　the　Score
Customer　　　Score　　　Purchased　Product
1　　　　　　.385　　　　　Book
2　　　　　　.710　　　　　TV
3　　　　　　.686　　　　　DVD
4　　　　　　.941　　　　　Car　Cover
5　　　　　　0.0　　　　　???

如果使用最近邻算法回答我们上面遇到的 “第 5 个顾客最有可能购买什么 产品” 这一问题，答案将是一本书。这是因为第 5 个顾客与第 1 个顾客之间 的距离要比第 5 个顾客与其他任何顾客之间的距离都短（实际上是短很多）。 基于这个模型，可以得出这样的结论：由最像第 5 个顾客的顾客可以预测出第 5 个顾客的行为。

不过，最近邻的好处远不止于此。最近邻算法可被扩展成不仅仅限于一个最 近匹配，而是可以包括任意数量的最近匹配。可将这些最近匹配称为是 “N-最 近邻”（比如 3-最近邻）。回到上述的例子，如果我们想要知道第 5 个顾客最 有可能购买的产品，那么这次的结论是书和 DVD。而对于上述的亚马逊的例子， 如果想要知道某个顾客最有可能购买的 12 个产品，就可以运行一个 12-最近邻 算法（但亚马逊实际运行的算法要远比一个简单的 12-最近邻算法复杂）。

并且，此算法不只限于预测顾客购买哪个产品。它还可被用来预测一个 Yes/No 的输出值。考虑上述例子，如果我们将最后一列改为（从顾客 1 到顾客 4）“Yes,No,Yes,No,”，那么用 1-最近邻模型可以预测第 5 个顾客会说 “Yes”，如果用一个 2-最近邻算法也会得到预测结果 “Yes”（顾客 1 和 3 均说 “Yes”），若用 3-最近邻模型仍会得到 “Yes”（顾客 1 和 3 说 “Yes”，顾客 2 说 “No”，所以它们的平均值是 “Yes”）。

我们考虑的最后一个问题是 “我们应该在我们的模型中使用多少邻？” 啊 哈 — 并不是每件事都这么简单。为了确定所需邻的最佳数量，需要进行试验。 并且，如果要预测值为 0 和 1 的列的输出，很显然需要选择奇数个邻，以便打 破平局。