知识卡片

普通读书笔记卡 · 6256.b

候选分桶需防止漏掉近邻

理解等级:中级

先用函数把可能相似的项放入桶,再在桶内做精细比较,可以减少不必要的两两计算。但只有近邻能被相应规则放到一起时才不会漏比较,桶过大也可能保留很高成本。原书将此放在降维旁栏讨论;这是候选缩减思路,不等于已实现特征空间投影或任何特定降维算法。

桶内全比较的总工作量是各桶大小平方之和。书中100万个对象均衡放到1000桶,每桶1000项,才得到约10亿次比较;若大多数项挤进少数桶,节省会减弱。随机分桶也可能分开相近对象,合并阶段不能凭空保证找回所有漏配。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      固定数目的桶内,这样在每个桶内的项彼此可以更充分地相互比较。数据降维通常既是艺术又是科学,并且那些应用降维方法成功获得竞争优势的机构经常把它当做产权信息或商业秘密。 聚类技术是任何数据挖掘者所必备工具的基本部分,因为从国防情报(defense intelligence)到银行部门的欺诈检测(fraud detection),再到景观美化的几乎任何工业的任何一

    • · 查看原书依据

      1000个桶中,每个桶中有1000个数据,聚类每个桶只需要10亿次操作。(1000个桶,每个桶进行1000×1000次操作)。10亿仍然是一个很大的数字,但是比1万亿小3个数量级,这也是一个巨大的进步(尽管在一些情况下,该进步还不够大)。 除了抽样和分桶的方法,文献中还有许多其他的方法,可以更好地降低问题的规模。例如,理论上你应该比较数据集中的每个数据,你所

    参考来源

    - 位置:《社交网站的数据挖掘与分析(原书第2版)》第3章《3.3 数据聚类速成》(spine79;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0068.html;u047-ch03-008)。 - 结论依据:原文在“固定数目的桶”附近的定义、例子或代码支撑本卡核心说明:先用函数把可能相似的项放入桶,再在桶内做精细比较,可以减少不必要的两两计算。边界按已读前提解释;示例未执行。 - 原始内容:固定数目的桶内,这样在每个桶内的项彼此可以更充分地相互比较。数据降维通常既是艺术又是科学,并且那些应用降维方法成功获得竞争优势的机构经常把它当做产权信息或商业秘密。 聚类技术是任何数据挖掘者所必备工具的基本部分,因为从国防情报(defense intelligence)到银行部门的欺诈检测(fraud detection),再到景观美化的几乎任何工业的任何一 - 位置:《社交网站的数据挖掘与分析(原书第2版)》第3章《3.3.4 聚类算法》(spine79;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0068.html;u051-ch03-008)。 - 结论依据:分桶成本还取决于桶的均衡程度,跨桶近邻需要额外处理。 - 原始内容:1000个桶中,每个桶中有1000个数据,聚类每个桶只需要10亿次操作。(1000个桶,每个桶进行1000×1000次操作)。10亿仍然是一个很大的数字,但是比1万亿小3个数量级,这也是一个巨大的进步(尽管在一些情况下,该进步还不够大)。 除了抽样和分桶的方法,文献中还有许多其他的方法,可以更好地降低问题的规模。例如,理论上你应该比较数据集中的每个数据,你所