H-K算法介绍与MATLAB实现

不去幼儿园

发布于 2024-12-03 12:57:33

3040

本篇文章是博主在人工智能等领域学习时，用于个人学习、研究或者欣赏使用，并基于博主对人工智能等领域的一些理解而记录的学习摘录和笔记，若有不当和侵权之处，指出后将会立即改正，还望谅解。文章分类在AI学习笔记： AI学习笔记（12）---《H-K算法介绍与MATLAB实现》

H-K算法介绍与MATLAB实现

1. 前言

理解并掌握 H-K 算法的基本原理，并针对 H-K算法实现需要掌握的前置知识进行练习实现。

掌握 H-K 算法的求解步骤，并编程实现一个使用 H-K 算法求解分类模型的例子。

2.相关知识

2.1H-K 算法分类模型

H-K 算法与单层感知器算法具有一定的相似性，都属于线性分类的几何分类方法，即要求输入的样本集本身是线性可分的。但不同的是，H-K 算法对于线性不可分的样本集可以进行判别，这一点是单层感知器所不具备的。

H-K 算法的出发点是以均方误差为准则函数而建立起来的。H-K 算法的分类模型与单层感知器一样，引入权值向量 w∈Rn 来作为分类模型， H-K 算法学习的过程就是求解 w∈Rn，如果样本集 x∈X 线性可分为两个集合X+,X−，那么应该存在一个权值向量 w 使得

其中，我们将 y 称为线性可分类的标签值。

2.2样本的规范化

我们将标签值 y 值为负的样本称为负样本，如果我们对样本集进行这样的操作：

那么分类问题可以写为如下形式：

wx′>0

此时，由x′构成的经过以上处理过的样本集称为规范化的样本向量。此时，分类问题变成了求解不等式 wx′>0 的问题。

2.3最小二乘准则函数

求解不等式 wx′>0 的问题可以进一步转化为 wx′=b(b>0) 的问题，同时对所有的样本进行联立，得到方程组 wX=B ,其中向量 B 的每个分量 bi>0。针对这样一个有多个可能解的方程组，我们可以求它的最小二乘解。即使得

取极小值（上式即为 H-K 算法的最小二乘准则函数）。此时可以使用梯度下降法或者伪逆法进行求解。为了下一关更好的介绍 H-K 算法，这里你需要了解伪逆的求法。

2.4伪逆

伪逆（pseudo inverse）是对于矩阵逆的一种推广，满足一定性质的矩阵都可以成为矩阵A的伪逆。伪逆具有存在且唯一的良好性质，可以用于解决最小二乘和最小范数问题。矩阵 X 的伪逆计算方式如下：

3.H-K 算法原理

通过对分类问题的一步步抽象，H-K 算法求解分类问题变成了一个线性方程组求解的问题，即：

其中 w 是要求解的参数，X 是所有样本规范化之后得到矩阵，B是所有分量大于 0 的向量。

如果对于任意 B 这个方程组都无解，那么说明样本集线性不可分。

以上线性方程式可以通过最小二乘变成一个优化问题，即找到 w 使得

尽可能的小。用 J 对 w 求偏导，

其中，X#=(XTX)−1XT是 X的伪逆。

因此，求 w 就相当于求满足前述条件的 B。

H-K 算法步骤

H-K 算法步骤也就是通过迭代一步一步的逼近出理想的 B。

步骤 1：随机初始化 B ，其每个分量均为正值；
步骤 2：计算 w=X#B;
步骤 3：计算 e=Xw−b；
步骤 4：根据 e的取值情况作进一步处理：
- 若分量全部大于等于 0，算法结束，求解完成；
- 若分量有正有负，则跳到步骤 5 继续迭代；
- 若分量全部小于 0，停止迭代，样本线性不可分。
步骤 5：完成更新计算

并跳转到步骤 2; 其中 ∣e∣ 是向量的模运算，即二范数。

4.编程实现

4.1伪逆的计算MATLAB代码

function [result] = step1_mission(samples, labels)
    for i = 1:length(labels) % 遍历每一个标签
        if labels(i) < 0 % 如果标签小于0
            samples(i,:) = -samples(i,:); % 对应样本取反
        end
    end
    result = inv(samples.' * samples) * samples.'; % 计算伪逆矩阵
end

4.2 H-K 算法求解MATLAB代码

function [w, b, flag] = step2_mission(samples, labels)
    samples_X = diag(labels) * samples; % 将样本矩阵与标签对角矩阵相乘，生成样本变换矩阵 samples_X
    X = pinv(samples_X); % 计算样本变换矩阵的伪逆矩阵 X
    [~, num] = size(labels); % 获取标签的数量，即样本数量 num
    b = ones(num, 1); % 初始化长度为 num 的全 1 向量 b
    while(1 == 1) % 无限循环，直到满足终止条件
        w = X * b; % 计算权重向量 w
        e = samples_X * w - b; % 计算误差向量 e
        flagt = 0; % 初始化正误差计数器
        flagf = 0; % 初始化负误差计数器
        for i = 1:num % 遍历每一个样本
            if (e(i) > -0.01) % 若误差大于 -0.01，正误差计数器加一
                flagt = flagt + 1;
            end
            if (e(i) < -0.01) % 若误差小于 -0.01，负误差计数器加一
                flagf = flagf + 1;
            end
        end
        if (flagt == 0) % 若没有正误差，设置标志为 -1 并跳出循环
            flag = -1;
            break
        end
        if (flagf == 0) % 若没有负误差，设置标志为 1 并跳出循环
            flag = 1;
            break
        end
        b = b + 0.1 * (e + norm(e)); % 更新向量 b，步长为 0.1
    end
end

4.3 测试输入

MATLAB终端输入下面指令

测试step1_mission(samples, labels)

samples = [-7.82 -4.58 -3.97; -6.68 3.16 2.71; 4.36 -2.91 2.09; 6.72 0.88 2.80; -8.64 3.06 3.50; -6.87 0.57 -5.45; 4.47 -2.62 5.76; 6.73 -2.01 4.18; -7.71 2.34 -6.33; -6.91 -0.49 -5.68; 6.18 2.81 5.82; 6.72 -0.93 -4.04; -6.25 -0.26 0.56; -6.94 -1.22 1.13; 8.09 0.20 2.25; 6.81 0.17 -4.15; -5.19 4.24 4.04; -6.38 -1.74 1.43; 4.08 1.30 5.33; 6.27 0.93 -2.78];
labels = [-1.0000    1.0000    1.0000    1.0000   -1.0000   -1.0000    1.0000    1.0000   -1.0000   -1.0000    1.0000    1.0000   -1.0000   -1.0000    1.0000    1.0000    1.0000   -1.0000    1.0000    1.0000];

s1 = samples(1:6,1:end);
l1 = labels(1:6);

s2 = samples(1:10,1:end);
l2 = labels(1:10);

s3 = samples(10:end,1:end);
l3 = labels(10:end);

s4 = samples;
l4 = labels;

disp('task1');
r1 = step1_mission(s1, l1)

disp('task2');
r1 = step1_mission(s2, l2)

disp('task3');
r1 = step1_mission(s3, l3)

disp('task4');
r1 = step1_mission(s4, l4)

测试step2_mission(samples, labels)

samples = [-7.82 -4.58 -3.97; -6.68 3.16 2.71; 4.36 -2.91 2.09; 6.72 0.88 2.80; -8.64 3.06 3.50; -6.87 0.57 -5.45; 4.47 -2.62 5.76; 6.73 -2.01 4.18; -7.71 2.34 -6.33; -6.91 -0.49 -5.68; 6.18 2.81 5.82; 6.72 -0.93 -4.04; -6.25 -0.26 0.56; -6.94 -1.22 1.13; 8.09 0.20 2.25; 6.81 0.17 -4.15; -5.19 4.24 4.04; -6.38 -1.74 1.43; 4.08 1.30 5.33; 6.27 0.93 -2.78];
labels = [-1.0000    1.0000    1.0000    1.0000   -1.0000   -1.0000    1.0000    1.0000   -1.0000   -1.0000    1.0000    1.0000   -1.0000   -1.0000    1.0000    1.0000    1.0000   -1.0000    1.0000    1.0000];

w1 = [1.0 1.0 1.0];
w2 = [-1.0 1.0 -1.0];
w3 = [-1.0 0.0 2.0];
w4 = [1.0 1.0 -1.0];

b1 = 1.0;
b2 = 2.0;
b3 = 3.0;
b4 = 4.0;

eta1 = 0.1;
eta2 = 0.2;
eta3 = 0.3;
eta4 = 0.5;

s1 = samples(5:15,1:end);
l1 = labels(5:15);

s2 = samples(1:10,1:end);
l2 = labels(1:10);

s3 = samples(10:end,1:end);
l3 = labels(10:end);

disp('task1');
[w,b,f] = step2_mission(s1, l1)

disp('task2');
[w,b,f] = step2_mission(s2, l2)

disp('task3');
[w,b,f] = step2_mission(s3, l3)