ComputeColStats UDF中 近似算法的介绍(续)

简介:

在前一篇文章的最后提到,对于准确率的提升是后续需要做的事情之一。接下来看看对于提升准确率,还有哪些事情可以做。

一,回顾

首先回顾下前一篇文章最后得到的结果,如下:
b01
执行时间先忽略,只看准确率。对于上面8个字段,有些在sample为25(采样比例1/25)的情况下还是相当准确的,比如odps_task_type,start_time;而有些则存在一定差距,比如project_name,fuxi_ceil_mem等;还有些存在比较大的差距,比如odps_inst_id,fuxi_avg_cpu。同样的采样算法,同样的估计算法,对于不同的数据会得到截然不同的结果。这种差异相信决大部分来自于数据本身。
下面就从数据本身来看下到底差异是如何出现的。

二,数据差异

不同的字段存储的数据不同,不同数据可能会存在唯一值上的差异。比如说对于主键,比如说对于纬度直,两者肯定在DistinctValue的分布上肯定是完全不同的。

1,如果该字段为主键,那么RowCount(X轴)和DistinctValue(Y轴)关系类似下图:

b02
这是一条斜率为1的直线。
对于这种情况,目前的算法肯定可以非常准确的估算出DistinctValue值。

2,如果该字段为纬度值(唯一值非常少),那么RowCount(X轴)和DistinctValue(Y轴)关系类似下图:

b03
随着RowCount的增加,DistinctValue也在增加,但到了某个点后DistinctValue基本保持不变。

3,如果该字段为一般字段,随着RowCount的增加而DistinctValue也缓慢增加,类似下图:

b04

三,数据差异导致的DistinctValue的计算误差?

上面一部分列举了三种可能的RowCount和DistinctValue关系。第一种类型是比较简单的,也能很准确的估算出DistinctValue值。而对于第二种和第三种则要困难的多,从测试的结果来看是这样的。
我们采样的前提是,采样算法能保证采样是随机的,每条数据被访问的几率是相同的。但实际上这样的前提是不存在的。这也是目前对第三种的估算也可能存在较大差异的原因。因为按道理来说,其实第三种我们也应该能很好的预估才对。目前的采样算法并不是随机的,数据本身分布对采样的结果影响极大。为了性能和实现起来简单,目前采样的算法是隔n条取1条的方式实现的,并不是真正意义上的随机采样。
针对同一次估算过程,我尝试过不同的拟合回归算法,结果并没有特别的不同,问题并不是在算法上,而是在数据本身上。下面通过对存在较大误差的fuxi_avg_cpu来看下,不同的采样比例下的RowCount和DistinctValue关系的差异。
b05
b06
b07
b08
上面几张图对下对比,能看得出来在不同的采样比例下图形的状态会有很大的变化。差异这么大的话想要比较准确的预估显然是不太现实的。

四,总结

目前看来DistinctValue估算的差异大部分原因是因为采样,想要提高准确率增加采样比例就可以了。而具体回归的算法,则没那么重要了。

目录
相关文章
|
1月前
|
机器学习/深度学习 算法 Oracle
ICLR 2024:近似最优的最大损失函数量子优化算法
【2月更文挑战第27天】ICLR 2024:近似最优的最大损失函数量子优化算法
29 3
ICLR 2024:近似最优的最大损失函数量子优化算法
|
3月前
|
缓存 算法 NoSQL
Redis 为何使用近似 LRU 算法淘汰数据,而不是真实 LRU?
Redis 为何使用近似 LRU 算法淘汰数据,而不是真实 LRU?
29 0
|
4月前
|
机器学习/深度学习 开发框架 .NET
【Python强化学习】马尔可夫决策过程与蒙特卡洛近似算法讲解(图文解释)
【Python强化学习】马尔可夫决策过程与蒙特卡洛近似算法讲解(图文解释)
43 0
|
11月前
|
分布式计算 算法 大数据
白话Elasticsearch45-深入聚合数据分析之易并行聚合算法,三角选择原则,近似聚合算法
白话Elasticsearch45-深入聚合数据分析之易并行聚合算法,三角选择原则,近似聚合算法
68 0
|
11月前
|
存储 JSON 分布式计算
「PostgreSQL高级特性」PostgreSQL 数据库的近似算法
「PostgreSQL高级特性」PostgreSQL 数据库的近似算法
|
算法 Python
MCMC、蒙特卡洛近似和Metropolis算法简介
MCMC、蒙特卡洛近似和Metropolis算法简介
315 0
MCMC、蒙特卡洛近似和Metropolis算法简介
|
算法
《算法技术手册》一1.3.4 近似算法
本节书摘来华章计算机《算法技术手册》一书中的第1章 ,第1.3.4节, George T.Heineman Gary Pollice Stanley Selkow 著 杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1133 0
|
人工智能 算法 大数据
《中国人工智能学会通讯》——12.7 序列模式挖掘近似算法
本节书摘来自CCAI《中国人工智能学会通讯》一书中的第12章,第12.7节, 更多章节内容可以访问云栖社区“CCAI”公众号查看。
1257 0
|
算法 BI JavaScript
近似算法---首次适宜法
该算法实现非常简单,思路大概是这样子的:      定义若干个空箱子,假设箱子的体积有多大,然后把一些货物存在这些箱子里,当第一个箱子存满后,接着存放第二个箱子,直到货物存完为止,我们来看看这个程序: #include #include #include int FirstFit(in...
873 0

热门文章

最新文章