知识卡片

普通读书笔记卡 · 6256.a

全体两两比较有平方级候选

理解等级:中级

对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(): # 注意不要改变原来的

    参考来源

    - 位置:《社交网站的数据挖掘与分析(原书第2版)》第3章《3.3 数据聚类速成》(spine79;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0068.html;u047-ch03-007)。 - 结论依据:原文在“n平方问题”附近的定义、例子或代码支撑本卡核心说明:对n个对象逐个与其余n−1个比较,会产生n(n−1)次有向比较;对称距离可省去重复对,但候选量仍是O(n²)。边界按已读前提解释;示例未执行。 - 原始内容:n平方问题,通常用O(n2)来表示这种问题;通俗地讲,你会称其为“n平方的大O”问题。对于很大的n值,O(n2)问题会很棘手,大多数情况下,很棘手意味着要想解决方案计算完毕,你要等“很长”时间。根据问题的性质和问题的限制,“很长”可能是几分钟,几年或者永世。 数据降维技术的探究超出了我们现在要讨论的范畴,但是知道一点即可:一个经典的数据降维技术涉及用一个函数 - 位置:《社交网站的数据挖掘与分析(原书第2版)》第3章《3.3.4 聚类算法》(spine79;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0068.html;u051-ch03-007)。 - 结论依据:100到10000个标题造成1万到1亿对比较,是输入增100倍、平方工作量增1万倍,不是指数复杂度。 - 原始内容:100000000次打分操作。这种操作从数学上来讲不会运行很好,并最终会遇到问题,即使是你用很多硬件来进行操作。 当遇到看起来是不可扩展的窘境时,你的最初反应可能是尽量缩小n值。但是大多数情况下随着输入数据的增加,你不可能将其减小很多而使你的解决方案可扩展,因为你的算法复杂度仍然是O(n2)。我们真正想要做的是设计一个复杂度是O(k×n)的算法,这里k是一个 - 位置:《社交网站的数据挖掘与分析(原书第2版)》第4章《4.4.3 寻找相似文档》(spine87;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0076.html;u066-ch03-007)。 - 结论依据:对所有文档存储距离还增加平方级结果矩阵,词表补齐和排序也各有成本。 - 原始内容:distances = {} for (title1, url1) in td_matrix.keys(): distances[(title1, url1)] = {} (min_dist, most_similar) = (1.0, ('', '')) for (title2, url2) in td_matrix.keys(): # 注意不要改变原来的