威尔逊区间及Golang的实现

比眉伴天荒 2022-01-14 08:45 152阅读 0赞

对于投票排名，如何给出排名。一种常见的错误算法是：\[得分 = 赞成票 - 反对票假定有两个项目，项目A是60张赞成票，40张反对票，项目B是550张赞成票，450张反对票。请问，谁应该排在前面？按照上面的公式，B会排在前面，因为它的得分（550 - 450 = 100）高于A（60 - 40 = 20）。但是实际上，B的好评率只有55%（550 / 1000），而A为60%（60 / 100），所以正确的结果应该是A排在前面。\[Urban Dictionary就是这种错误算法的实例。另一种常见的错误算法是得分 = 赞成票 / 总票数如果"总票数"很大，这种算法其实是对的。问题出在如果"总票数"很少，这时就会出错。假定A有2张赞成票、0张反对票，B有100张赞成票、1张反对票。这种算法会使得A排在B前面。这显然错误。Amazon就是这种错误算法的实例。

我们先做如下设定：  
（1）每个用户的投票都是独立事件。  
（2）用户只有两个选择，要么投赞成票，要么投反对票。  
（3）如果投票总人数为n，其中赞成票为k，那么赞成票的比例p就等于k/n。如果你熟悉统计学，可能已经看出来了，这是一种统计分布，叫做"二项分布"（binomial distribution）。我们的思路是，p越大，就代表这个项目的好评比例越高，越应该排在前面。  
但是，p的可信性，取决于有多少人投票，如果样本太小，p就不可信。好在我们已经知道，p是"二项分布"中某个事件的发生概率，因此我们可以计算出p的置信区间。  
所谓"置信区间"，就是说，以某个概率而言，p会落在的那个区间。**95%置信区间，意味着如果你用同样的步骤，去选样本，计算置信区间，那么100次这样的独立过程，有95%的概率你计算出来的区间会包含真实参数值，即大概会有95个置信区间会包含真值。**

这样一来，排名算法就比较清晰了：第一步，计算每个项目的"好评率"（即赞成票的比例）。第二步，计算每个"好评率"的置信区间（以95%的概率）。第三步，根据置信区间的下限值，进行排名。这个值越大，排名就越高。这样做的原理是，置信区间的宽窄与样本的数量有关。比如，A有8张赞成票，2张反对票；B有80张赞成票，20张反对票。这两个项目的赞成票比例都是80%，但是B的置信区间（假定\[75%, 85%\]）会比A的置信区间（假定\[70%, 90%\]）窄得多，因此B的置信区间的下限值（75%）会比A（70%）大，所以B应该排在A前面。

置信区间的实质，就是进行可信度的修正，弥补样本量过小的影响。如果样本多，就说明比较可信，不需要很大的修正，所以置信区间会比较窄，下限值会比较大；如果样本少，就说明不一定可信，必须进行较大的修正，所以置信区间会比较宽，下限值会比较小。二项分布的置信区间有多种计算公式，最常见的是"正态区间"（Normal approximation interval），教科书里几乎都是这种方法。但是，它只适用于样本较多的情况（np > 5 且 n(1 − p) > 5），对于小样本，它的准确性很差。1927年，美国数学家 Edwin Bidwell Wilson提出了一个修正公式，被称为"威尔逊区间"，很好地解决了小样本的准确性问题。

## 下面给出Golang的Wilson区间代码 ##

分位数表（局部）：

P	0.000	0.001	0.002	0.003	0.004	0.005	0.006	0.007	0.008	0.009
    0.50	0.0000	0.0025	0.0050	0.0075	0.0100	0.0125	0.0150	0.0175	0.0201	0.0226
    0.51	0.0251	0.0276	0.0301	0.0326	0.0351	0.0376	0.0401	0.0426	0.0451	0.0476
    0.52	0.0502	0.0527	0.0552	0.0577	0.0602	0.0627	0.0652	0.0677	0.0702	0.0728
    0.53	0.0753	0.0778	0.0803	0.0828	0.0853	0.0878	0.0904	0.0929	0.0954	0.0979

代码：

package predict
    
    import (
    	"fmt"
    	"math"
    	"strconv"
    	"strings"
    	"util"
    )
    
    const (
    	uvinf    = 0x7FF0000000000000 //正无穷大
    	uvneginf = 0xFFF0000000000000 //负无穷大
    )
    
    //计算威尔逊区间
    func ConfidenceInterval2(n int64, k int, alpha float64, arr *[]float64) (float64, float64) {
    	z, _ := GetQuantile(1-0.5*alpha, arr)
    	p := float64(k) / float64(n)
    	s := (1 - p) * p
    
    	left := p + z*z/(2*float64(n))
    	right := z * math.Sqrt(s/float64(n)+z*z/(4*float64(n)*float64(n)))
    	factor := 1 / (1 + z*z/float64(n))
    	return factor * (left - right), factor * (left + right)
    }
    
    //加载分位数表
    func LoadQuantile() (*[]float64, error) {
    	var features []float64
    	content, err := util.ReadFile("./src/predict/Quantile.txt")
    	if err != nil {
    		fmt.Print(err)
    	}
    	for _, line := range strings.Split(string(content), "\n") {
    		if !strings.Contains(line, "P") {
    			lineNew := strings.Split(line, "\t")
    			i := 0
    			lineNew = append(lineNew[:i], lineNew[i+1:]...)
    			for _, value := range lineNew {
    				fValue, err := strconv.ParseFloat(strings.ReplaceAll(value, "\r", ""), 64)
    				if err == nil {
    					features = append(features, fValue)
    				} else {
    					fmt.Printf("eValue:%s,%s", value, err)
    				}
    			}
    		}
    	}
    	return &features, err
    }
    
    //查分位数表
    func GetQuantile(p float64, arr *[]float64) (float64, error) {
    	if p < 0 || p > 1 {
    		return 0, fmt.Errorf("p value error")
    	}
    	switch {
    	case p == 0:
    		return uvneginf, nil
    	case p == 1:
    		return uvinf, nil
    	case p >= 0.5:
    		return (*arr)[int64(p*1000-500)], nil
    	case p < 0.5:
    		return -(*arr)[-int64(p*1000 - 500)], nil
    	}
    	return 0, fmt.Errorf("p value error")
    }