知识卡片
全体两两比较有平方级候选
对n个对象逐个与其余n−1个比较,会产生n(n−1)次有向比较;对称距离可省去重复对,但候选量仍是O(n²)。这是比较次数随规模的增长量级,不是以秒为单位的运行时间,每次距离计算成本还需另算;也不是所有聚类算法都必须采用完整两两比较。
本节叙述把n²增长写成“指数倍增加”,需区分:n²属于多项式中的平方增长。100个标题的1万次与1万个标题的1亿次比较对应同一平方规律;对称性只节省常数比例,不改变该量级。
文档相似度示例还为每对文档复制权重字典、补词并排序,同时保存全部距离;比较次数之外还包含每对特征处理和矩阵存储成本。索引、候选缩减与稀疏表示需按问题选择,不能仅换成向量就认作可扩展实现。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 3 处
- · 查看原书依据
n平方问题,通常用O(n2)来表示这种问题;通俗地讲,你会称其为“n平方的大O”问题。对于很大的n值,O(n2)问题会很棘手,大多数情况下,很棘手意味着要想解决方案计算完毕,你要等“很长”时间。根据问题的性质和问题的限制,“很长”可能是几分钟,几年或者永世。 数据降维技术的探究超出了我们现在要讨论的范畴,但是知道一点即可:一个经典的数据降维技术涉及用一个函数
- · 查看原书依据
100000000次打分操作。这种操作从数学上来讲不会运行很好,并最终会遇到问题,即使是你用很多硬件来进行操作。 当遇到看起来是不可扩展的窘境时,你的最初反应可能是尽量缩小n值。但是大多数情况下随着输入数据的增加,你不可能将其减小很多而使你的解决方案可扩展,因为你的算法复杂度仍然是O(n2)。我们真正想要做的是设计一个复杂度是O(k×n)的算法,这里k是一个
- · 查看原书依据
distances = {} for (title1, url1) in td_matrix.keys(): distances[(title1, url1)] = {} (min_dist, most_similar) = (1.0, ('', '')) for (title2, url2) in td_matrix.keys(): # 注意不要改变原来的