下六个月下午 程序员 考试试题-案例分析-答案与解析试题一（共 15 分）【阐明】两个包具有限个元素的非空集合 A、B 的相似度定义为|A∩B|/|A∪B|，即它们的交集大小(元素个数)与并集大小之比
如下的流程图计算两个非空整数集合(以数组表达)的交集和并集，并计算其相似度
已知整数组 A[1:m]和 B[1:n]分别存储了集合 A 和 B 的元素(每个集合中包含的元素各不相似)，其交集寄存于数组 C[1:s]，并集寄存于数组 D[1:t]，集合 A 和 B 的相似度寄存于SIM
例如，假设 A={1,2,3,4},B={1,4,5,6},则 C={1,4},D={1,2,3,4,5,6},A 与 B 的相似度SIM=1/3
阅读以上阐明和流程图，弥补流程图中的空缺(1)〜(5)，将解答填入答题纸的对应栏内
【参照答案】(1)、s (2)、t (3)、C[s] (4)、D[t] (5)、s/t【答案解析】首先我们来理解两个有限集合的相似度的含义
两个包具有限个元素的非空集合 A、B的相似度定义为它们的交集大小(元素个数)与并集大小之比
假如两集合完全相等，则相似度必然为 1(100%);假如两集合完全不一样(没有公共元素)，则相似度必然为 0;假如集合A 中有二分之一元素就是集合 B 的所有元素，而另二分之一元素不属于集合 B，则这两个集合的相似度为 0
5(50%)
因此，这个定义符合人们的常理性认识
在大数据应用中，常常要将诸多有限集进行分类
例如，每天均有大量的新闻稿
为了以便顾客检索，需要将新闻稿分类
用什么原则来分类呢
每一篇新闻稿可以用其中所有的关键词来表征
这些关键词的集合称为这篇新闻稿的特征向量
两篇新闻稿与否属于同一类，依赖于它们的关键词集合与否具有较高的相似度(公共关键词个数除以总关键词个数)
搜索引擎可以将相似度超过一定水平的新闻稿作为同一类
