传统编程遇上机器学习会擦出怎样的火花？
在这篇文章中，我们将开发一个使用树状数据结构和协同过滤的自动完成组件来为用户选择最佳的图书标题提供建议。值得注意的是，算法、数据结构和机器学习都在朝着最终的解决方案一起工作，完整的代码和工作应用程序与结果一起提供。
问题公式化
我们想要从高层次角度来构建一个自动完成的字段，所以当我们键入一些字符时，它建议从这些图书的标题开始。
从GUI的角度来看，需要的是一个TextField或者ComboBox，它显示了一些像findTitlesThatStartWith（chars [] ch）这样的服务提供的选项列表。幸运的是，在Swing（也是JavaScript或jQuery）中已经有了现有的GUI组件。对于这篇文章，构建GUI自动完成组件并不是关注的焦点，尽管构建它们可能是一个很大的挑战。
另一方面，实现findTitlesThatStartWith（chars [] ch）则更具吸引力，因为它提供了一个机会，可以从数据的角度优化向客户提供的内容。从特定字符开始可能会有一个长列表，所以我们只能返回有限数量的标题，这个短名单中包含的内容尽可能多地从用户的角度来理解。
这有一些选项：
按照一些标准（字母顺序）对列表进行排序，然后只返回前10位（或任何有意义的数字）
计算用户获得标题的次数，只显示前10个最高的标题
显示最受用户欢迎的10大标题
根据当前的用户偏好显示最感兴趣的前10名
一旦我们在高层次上表明什么样的服务将返回，就是时候研究如何在相当大的标题集合中搜索标题。
同样，这也有各种各样的选择：
我们搜索所有的列表/数组和每个标题，我们看看ut是否从这些字符开始：
如果N代表列表的大小，k是单词的长度，我们需要θ（N * k）时间来搜索。插入新标题需要一定的时间（θ（1）），虽然有添加新电影，但情况相当少。
由于这是一个搜索问题，HashTable可能是一个选项，因为它的访问和插入速度非常快（θ（1））。不幸的是，HashTables只能查找整个单词匹配，而不是匹配前缀（即以......开始的标题）。
同样，我们可以考虑一个平衡良好的二叉树。因为它给了我们θ（log（N），即所有标题的大小乘以搜索和插入的复杂度。同样，二叉树没有帮助，因为它们找不到前缀匹配而是精准匹配。
幸运的是，现有的数据结构已经准备好用于查找前缀匹配。关于这个数据结构的好处是，只要稍作修改，它就会给你提供搜索时间复杂度θ（k），其中k是前缀的长度。是的，有一个小问题：你可能需要更多的存储空间。
尝试
在本节中，我们将探讨试图如何在标题（单词）列表中搜索前缀匹配。一旦你理解了单词的插入方式，就相当容易理解：
接下来让我们看看如何搜索以“te”开头的标题：
你可能在想，没有那么快！事实上，复杂度是θ（k + M），其中k是前缀的长度，M是建议列表或最后一个节点匹配下的子树的大小（直接子节点保存在HashTable中，因此需要经常查找字符匹配）。 无论如何，我们需要遍历子树来收集建议的单词/标题 - 如果列出的结果很多，则会显著减慢算法的速度。
当然，它比θ（k * N）好，其中k是前缀的长度，N是所有列表的大小。但是，我们能做得更好吗？ 那么，我们可以稍微增加节点来存储更多的信息，而不仅仅是字符，如下所示：
由于该节点已经具有子树包含的单词列表，所以该修改可以极大地帮助避免在最后一个匹配节点下的所有子树。下面看看现在搜索的结果：
最终变更
在算法准备好实施之前，还有一个小诀窍要做。标题通常是句子而不是一个单词。如果我们只搜索标题的开头部分，这将不是很有用，例如，很多标题以“这”开头。因此，如果用户搜索以其中一个词开头的标题，很可能会搜索不出来。
解决方案很简单！我们只是将每个单词分别插入到树中，并将标题的所有句子保存到节点建议列表中。现在，不再只提供单词建议，而是有一个句子列表。这样，我们可以搜索中间的单词，同时能够提出所有的标题句子。
推荐系统
我们只有极少数的建议，所以涉及到向用户在提出什么样的建议时，我认为最好的选择是展示与用户兴趣更贴近或更接近的东西。这促成推荐系统的形成。
推荐系统根据用户偏好和数据趋势提出建议信息。这些系统的主要优点是可以自动学习，更多地了解用户的喜好。基本上，更多的用户与系统交互的越多（即喜欢或点击特定的书籍或电影），系统将提出更多更好的建议（即更接近用户的兴趣）。
数据
感谢这个来源提供了足够的数据来构建一个有意义的算法。数据集相当大，约有271.000本书、110万的收视率和279,000用户。
应用
应用程序可以在没有任何Java知识的情况下下载和执行（尽管Java必须安装在你的计算机上，我们可以通过简单地执行RUN类来运行应用程序，或者如果你不想使用IDE打开它，只需运行mvn exec：java。
你可以通过对某些书籍进行评分来试用（请注意，如果书籍未先评分，则不会提出建议），然后在该字段中搜索自动填充建议。随意游玩（50个功能不需要太多时间来训练），并注意算法如何根据你的喜好进行调整。对于50种类型，给出预测评级的建议以及算法的误差（均方误差）将不会超过30秒。你还可以将评级数据的规模增加到1,149,000，但请注意培训过程的速度需要放缓。
该应用程序使用Swing作为GUI和Spark MLib构建协作过滤算法。运行后，屏幕显示如下：
