Fisher准则一维聚类

在做FAQ系统时，用户输入一个查询之后，返回若干个打好分数的文档。对于这些文档，有些是应该输出的，有些是不应该输出的。那么应该在什么地方截断呢？

这个问题其实是一个聚类问题，在一维空间中把若干个点聚成两类。

聚类就有标准：类内距离尽量小、类间距离尽量大。

由此想到Fisher准则。

那么给定一个浮点数组，寻找这个浮点数组的fisher点，应该如何实现呢？

fisher准则目标函数为fisher=(s1+s2)/(m1-m2)^2。

可以用O（n）复杂度实现。

但是有没有更快速的方法呢？

从左往右扫描，如果fisher准则函数是一个类似二次函数的形状，那么就可以利用“三分法”求极值的策略将复杂度降为O（logN）。其实是不可能的，因为O（n）的方法优势在于快速计算目标函数fisher，如果使用三分法就无法O（1）复杂度计算目标函数fisher，而是O（n）的复杂度计算目标函数。这样其实复杂度反而提高了。所以这个问题到这里就可以停止了。但是“fisher曲线”到底是不是类似二次函数的呢？

为了验证是否满足“类似二次函数”的特性，我随机出一堆数字，求fisher曲线。

实验结果：并不满足“类似二次函数”，但是大概率地满足此条件。

本实验一共测试了10000组长度在3~1000之间的数组。

下面的0，1，2...表示曲线斜率方向变化次数，右面数字表示出现次数。

可以发现，那些 不满足“类似二次函数”的图像看上去也都近似“V”形。

0: 7668

1: 1732

2: 416

3: 129

4: 34

5: 17

6: 3

7: 1

实验代码如下：

import numpy as np

import tqdm

def getfisher(a):

    s = np.sum(a)

    ss = np.sum(a * a)

    now_s = 0

    now_ss = 0

    ret = []

    for i in range(len(a) - 1):

        now_s += a[i]

        now_ss += a[i] ** 2

        l_s = now_s / (i + 1)

        l_ss = now_ss / (i + 1)

        r_s = (s - now_s) / (len(a) - 1 - i)

        r_ss = (ss - now_ss) / (len(a) - 1 - i)

        fisher = (l_ss + r_ss) / (l_s - r_s) ** 2

        ret.append(fisher)

    return ret

def checkright(a):

    dir = 0

    cnt = 0

    for i in range(1, len(a)):

        if dir != np.sign(a[i] - a[i - 1]) and dir != 0 and np.abs(a[i]-a[i-1])>1e-2:

            cnt += 1

        dir = np.sign(a[i] - a[i - 1])

    return cnt

def main():

    c = dict()

    for i in tqdm.tqdm(range(10000)):

        x = np.sort(np.random.rand(np.random.randint(3, 1000)))

        f = getfisher(x)

        # plt.plot(x[:-1], f)

        cnt = checkright(f)

        if cnt not in c:

            c[cnt] = 0

        c[cnt] += 1

        # plt.show()

    print(c)

if __name__ == '__main__':

    main()