Fisher最优分割算法（附带MATLAB程序与java程序）

matlab程序如下：

function [LP,J]=lp(X)
%  LP对有序样品向量X进行最优分割
%  语法 LP=lp(X)
%  X─从小到大排列的有序数据向量
%  LP─分类损失函数值
%  J─最优分割点

n=length(X);
D=zeros(n,n);
LP=zeros(n,n-1);
J=zeros(n,n-1);
for i=1:n-1
    for j=2:n
        if(i<j)
            sx=0;
            d=0;
            for t=i:j
                sx=sx+X(t);
            end
            meanx=sx/(j-i+1);
            for k=i:j
                d=d+(X(k)-meanx).^2;
            end
            D(j,i)=d;
        end
    end
end
for k=2:n-1
    for p=3:n
        if(k<p)
            min=9999;
            minj=0;
            if(k==2)
                for j=2:p
                    temp=D(j-1,1)+D(p,j);
                    if(temp<min)
                        min=temp;
                        minj=j;
                    end
                end
            else
                for j=k:p
                    temp=LP(j-1,k-1)+D(p,j);
                    if(temp<min)
                        min=temp;
                        minj=j;
                    end
                end
            end
            LP(p,k)=min;
            J(p,k)=minj;
        end
    end
end
LP=LP(end,:);
J = unique([unique(J(:,2))',unique(J(end,:))]);

java程序如下：

 /**
     * fisher最优分割算法
     *
     * @param pair 样本对
     * @return 聚类结果
     */
    private static List<List<String>> fisher(Map<String, Double> pair) {
        //1、对样本序列排序
        List<Double> collect = pair.values().stream().sorted().collect(Collectors.toList());
        //2、fisher最优分割，获取最优分割点
        Set<Integer> fisher = fisher(collect);
        ArrayList<List<String>> category = new ArrayList<>();
        //3、拿到最优分割点，遍历拿到所有的聚类
        List<Integer> collect2 = new ArrayList<>(fisher);
        for (int i = 0; i < fisher.size() - 1; i++) {
            int finalI = collect2.get(i);
            Integer finalIL = collect2.get(i + 1);
            List<String> collect1;
            //最后一个分割点算进最后一个聚类
            if (i == fisher.size() - 2) {
                collect1 = pair.keySet().stream().filter(s -> pair.get(s) >= collect.get(finalI) && pair.get(s) <= collect.get(finalIL)).collect(Collectors.toList());
            } else {
                collect1 = pair.keySet().stream().filter(s -> pair.get(s) >= collect.get(finalI) && pair.get(s) < collect.get(finalIL)).collect(Collectors.toList());
            }
            category.add(collect1);
        }
        return category;
    }

    /**
     * fisher最优分割法
     *
     * @param values 有序样品向量
     * @return fisher最优分割点
     */
    private static Set<Integer> fisher(List<Double> values) {
        int size = values.size();
        double[][] D = new double[size][size];
        double[][] LP = new double[size][size - 1];
        int[][] J = new int[size][size - 1];
        for (int i = 0; i < size - 1; i++) {
            for (int j = 1; j < size; j++) {
                if (i < j) {
                    double sx = 0;
                    double d = 0;
                    for (int t = i; t <= j; t++) {
                        sx += values.get(t);
                    }
                    double meanx = sx / (j - i + 1);
                    for (int k = i; k <= j; k++) {
                        d += Math.pow((values.get(k) - meanx), 2);
                    }
                    D[j][i] = d;
                }
            }
        }
        for (int k = 1; k <= size - 2; k++) {
            for (int i = 2; i <= size - 1; i++) {
                if (k < i) {
                    double min = Double.MAX_VALUE;
                    int minJ = 0;
                    if (k == 1) {
                        for (int j = 1; j <= i; j++) {
                            double temp = D[j - 1][0] + D[i][j];
                            if (temp < min) {
                                min = temp;
                                minJ = j;
                            }
                        }
                    } else {
                        for (int j = k; j <= i; j++) {
                            double temp = LP[j - 1][k - 1] + D[i][j];
                            if (temp < min) {
                                min = temp;
                                minJ = j;
                            }
                        }
                    }
                    LP[i][k] = min;
                    J[i][k] = minJ;
                }
            }
        }
        TreeSet<Integer> splitPoint = new TreeSet<>();
        for (int[] ints : J) {
            splitPoint.add(ints[1]);
        }
        for (int i = 0; i < J[0].length; i++) {
            splitPoint.add(J[size - 1][i]);
        }
        return splitPoint;
    }

本文地址：https://blog.csdn.net/ibianma/article/details/109624316