Linear and Quadratic Discriminant Function implemented by Python(2021/10/5更新)

Github: https://github.com/asd123pwj/pattern-recognition

发现标题中文占比极低,当机立断毅然决然果断的改成了全英文。

2021/10/5更新:为实现代码区块渲染,更新为Markdown格式。

写在前面

  • 本篇代码基于上一篇文章LDA与QDA分类数据的简单应用实现的。
  • 之前是使用sklearn库,直接调用QDA与LDA函数,对四个数据集进行分类的。
  • 本篇文章不再调用sklearn库,直接使用python内置的numpy与math库实现。
  • QDF与QDA似乎一样的,公式一样,我根据QDF公式写的分类器,效果与sklearn的QDA也极其相似。
  • 因此LDF与LDA也应该是一样的,但我写的时候,LDF分类器的效果会比LDA库有所差别,不知是否是我对公式的理解错误导致的,这点后续会说明。
  • 即,本篇文章的QDF大致是没问题的,但LDF可能有参数错误,仅供参考,后续可能会根据这个点对本文修改。
    • 注:我老师说我对LDF最后一项的理解没问题,所以应该是正确的。

相关公式

/

/

  • 公式解释及示例参考:《模式识别导论》-齐敏、李大健、郝重阳编著-P92

高斯分类原理

  • 如果认为一个事件的可能性分布属于正态分布,就可以根据这个事件的结果,来得出其发生的可能性。
    • 在高斯分类器中,体现为,认为类的特征属于正态分布。
  • 那么给出一个特征,就可以求出其属于这个类的可能性。
    • 同样的,如果有多个类的正态分布函数,那么就能得出这个特征,属于各类的可能性,我们认为可能性最高的,就是特征对应的类。
    • 当要求多个特征的类,就需要求出多维正态分布的公式,并根据公式来计算特征属于不同类的可能性。
    • 即,当实现分类器的时候,只需要将其方差与期望参数求出,就可以得到每个类对应的高斯公式。
    • 这样,将不同特征代入高斯公式,就能求出不同概率,再取可能性最大的类,就是这个特征组的类别。
  • QDF对高斯公式进行了简化,LDF又在QDF的基础上进一步简化。

数据集

Dataset#class#feature#train#test
Letter2616160004000
Opt-digits106438231797
Statlog-Satimage63644352000
Vowel1110528462

QDF/LDF与QDA/LDA对比

  • 可以看出,QDF的效果与QDA效果相似。

    • 注:optdigits数据集生成的协方差矩阵不可逆,导致QDF与LDF公式不适用。
    • 对此,sklearn发出了警告,而本文的QDF与LDF使用伪逆解决了这个问题。
    • 此外,矩阵不可逆还表示该矩阵的行列式为0,不能对其求对数,因此QDF公式的最后一项,用了LDF公式的最后一项,因此该数据集的QDF实际上是LDF实现的。
  • 对于letter数据集,本文实现的LDF分类器比LDA分类器效果好,但对于vowel数据集,稍显劣势。

  • 但在处理效率上,我写的和sklearn库差的不是一星半点。

  • 本文提到的QDF、LDF全称为Quadratic Discriminant Function、Linear Discriminant Function。

  • 本文提到的QDA、LDA全称为Quadratic Discriminant Analysis、Linear Discriminant Analysis。

  • QDF与LDF表示根据QDF、LDF公式代码写出来的分类器。

  • QDA与LDA表示sklearn库提供的分类器。

/本文实现的QDF/LDF分类器效果
/sklearn提供的QDA/LDA效果

结果分析与效率改进方向

  • 从输出可以看出,LDF与QDF在letter、optdigits、sat三个数据集中表现较好,而在vowel中表现较差。
    • 观察了vowel数据集,vowel是语音信息数据集,提供了10个特征,且附带了性别与说话人。
    • 但在训练时,只使用了10个特征,并没有将性别考虑进去。
    • 因此,可能是因为不同性别的语音信息有不同,且不同说话人的语音信息也不同,导致特征不是正态分布,进而导致高斯分类器效果不佳。
  • 效率改进方向:
    • 代码中使用了不少了列表,以及列表嵌套多类型列表,导致效率极低。
    • 且在测试时访问的列表是不会变化的,因此应该转成元组。
    • 将列表转成元组,并将高维列表拆开来后,应该能大大加快效率。

难点及解决

  • 公式的理解:
    • 线性代数已经快忘光了,因此公式很难看懂,在讨论未果后,决定翻书。
      • 在《模式识别导论》的第92页上找到了公式及例题。
      • 并根据公式介绍及例题,推测了一下每项的含义,并利用python实现了出来。
    • 在对QDF公式的实现时,与QDA的效果类似,但LDF与LDA有所不同。
      • 可能是因为LDF最后一项的理解错误,我的代码将P(wi)解释成wi类在训练集发生的概率。
  • 实现公式:
    • 基于面向过程的思想来实现公式,但分成多个函数后,函数间的参数传递比较麻烦。
    • 主要因为开始的时候是直接将每项实现,但给的数据集实际上并不能直接传给函数。
    • 因此设计了几个列表和字典作为桥梁,这里列出两个最重要的:
      • sort_features{}:
        • 键是类,值是按行保存特征的特征列表。
        • 根据训练集的特征列表与类列表得出。
        • 以类作为键,值为所有该类元素特征列表的列表。
        • 因为后面使用的协方差与期望,传入参数是以特征数为行,以元素数为列,因此又对字典的键进行了转置。
        • 返回该字典。
      • param_list[]:
        • [0]保存类,[1]保存特征列表的协方差矩阵,[2]保存特征列表的期望,[3]保存键是类,值是出现概率的字典。
        • 这样,在对公式求解的时候,可以基于该列表获得不同类对应的参数。
  • 数据集不合适:
    • 本次使用的optdigits数据集,其训练集生成的协方差矩阵是不可逆的,且行列式为0。
    • 对此,在求协方差矩阵的逆时,改用了伪逆。
    • 在因协方差矩阵行列式为0,而无法求其对数时,使用该类在训练集中出现概率的对数来代替。
      • 即,在QDF分类器不适用的情况下,使用了LDF分类器来处理它。
      • 本来是直接将该参数置0的,但后来觉得改用概率会更好,不过两者效果在optdigits数据集上效果一致。

代码

import numpy as np
import math

#   对letter数据集分类
def get_list_letter(char, features, path):
    with open(path, 'r') as letter_train:
        content_letter_train = letter_train.readlines()
    for line in content_letter_train:
        temp = line.split(',')
        temp[-1] = list(temp[-1])[0]
        char.append(temp[0])
        features.append((temp[1::]))

#   对optdigits数据集分类
def get_list_optdigits(dig, features, path):
    with open(path, 'r') as dig_train:
        content_dig_train = dig_train.readlines()
    for line in content_dig_train:
        temp = line.split(',')
        temp[-1] = list(temp[-1])[0]
        dig.append(temp[-1])
        features.append((temp[0:len(temp)-1:]))

#   对sat数据集分类
def get_list_sat(sat, features, path):
    with open(path, 'r') as sat_train:
        content_sat_train = sat_train.readlines()
    for line in content_sat_train:
        temp = line.split(' ')
        temp[-1] = list(temp[-1])[0]
        sat.append(temp[-1])
        features.append((temp[0:len(temp)-1:]))

#   对vowel数据集分类
def get_list_vowel(vowel, features, path):
    with open(path, 'r') as vowel_train:
        content_vowel_train = vowel_train.readlines()
    for line in content_vowel_train:
        temp = line.split()
        temp[-1] = list(temp[-1])[0]
        vowel.append(temp[-1])
        features.append((temp[3:len(temp)-1:]))

#   列表字符串元素转浮点型
def convert_float(str_list):
    for row in range(0, len(str_list)):
        for col in range(0, len(str_list[row])):
            str_list[row][col] = float(str_list[row][col])

#   列表字符串元素转整型
def convert_int(str_list):
    for row in range(0, len(str_list)):
        for col in range(0, len(str_list[row])):
            str_list[row][col] = int(str_list[row][col])

#   求期望
def get_expectation(features):
    expectation = [0] * len(features)
    for row in range(0, len(features)):
        for col in range(0, len(features[0])):
            expectation[row] += features[row][col]
    for pos in range(0, len(expectation)):
        expectation[pos] = expectation[pos] / len(features[0])
    return expectation

#   train_features_sort_by_class_with_same_feature:
#       将训练集的特征列表,按类保存成字典,即,键是类,值是特征列表的列表
#   sort_features{}: { class, features_list[] }, 保存每个类对应的特征列表的列表,字典
#   class: 类
#   features_list[]: [ feature_list[] ], 保存所有特征列表,每个元素均是列表
#   注意,这里字典里保存的不再是特征列表的列表,而是特征的列表,即原本按类来排序的特征列表的列表,被转置了。
#       这样方便后续的求协方差。
def train_features_sort_by_class_with_same_feature(train_features, train_class):
    sort_features = {}
    for pos in range(0, len(train_class)):
        if train_class[pos] not in sort_features:
            sort_features[train_class[pos]] = []
        sort_features[train_class[pos]].append(train_features[pos])
    for clas in sort_features:
        sort_features[clas] = np.array(sort_features[clas]).T
    return sort_features

#   get_param: 根据训练集特征与类,得到对应QDF的参数列表
#   param_list[] : [ class[], cov[][][], expectation[][] ], 保存class对应的协方差矩阵cov与期望expectation
#   class: 类别
#   cov[][]: 由训练集特征得到的协方差矩阵
#   expectation[]: 特征期望
def get_param(sort_features, train_class):
    param_list = [[], [], []]
    for clas in sort_features:
        param_list[0].append(clas)
        param_list[1].append(np.cov(sort_features[clas]))
        param_list[2].append(np.array(get_expectation(sort_features[clas])))
    param_list.append(get_char_probability(train_class))
    return param_list

#   得到训练集中各类出现的可能性,返回可能性字典,键是类,值是可能性
def get_char_probability(train_class):
    char_probability = {}
    for chr in train_class:
        if chr not in char_probability:
            char_probability[chr] = 0
        char_probability[chr] += 1
    for chr in char_probability:
        char_probability[chr] = char_probability[chr] / len(train_class)
    return char_probability

#   以method方法预测test_features可能的类别,返回其类别
def predict(test_features, param_list, method):
    max_probability = 0
    max_char = ''
    for pos in range(0, len(param_list[0])):
        clas = param_list[0][pos]
        cov = param_list[1][pos]
        expectation = param_list[2][pos]
        cov_det = np.linalg.det(cov)

        ele1 = test_features - expectation
        if cov_det == 0:
            # 协方差矩阵不可逆,使用伪逆
            ele2 = np.linalg.pinv(cov)
            cov_reversible = False
        else:
            # 协方差矩阵可逆
            ele2 = np.linalg.inv(cov)
            cov_reversible = True
        ele3 = ele1.T
        if method == 'QDF':
            if cov_reversible:
                ele4 = - math.log(cov_det)
            else:
                ele4 = math.log(param_list[3][clas]) * 2
        elif method == 'LDF':
            ele4 = math.log(param_list[3][clas]) * 2

        probability = np.matmul(ele1, ele2)
        probability = np.matmul(probability, ele3)
        probability = - probability + ele4
        if probability > max_probability or max_char == '':
            max_probability = probability
            max_char = clas
    return max_char

#   使用method方法对训练集进行训练,并测试测试集,返回每个测试特征可能的类别
def train_and_predict(train_features, train_class, test_features, method):
    predict_class = []
    sort_features = train_features_sort_by_class_with_same_feature(train_features, train_class)
    param = get_param(sort_features, train_class)
    for pos in range(0, len(test_features)):
        predict_class.append(predict(test_features[pos], param, method))
    return predict_class

#   分析方法精确度,返回精确度
def analysis_accuracy(judge_result, test_char):
    sum = 0
    right_num = 0
    for pos in range(0, len(judge_result)):
        sum += 1
        if judge_result[pos] == test_char[pos]:
            right_num += 1
    return right_num / sum

#   letter数据集初始化
letter_train_path = './dataset/letter.train'
letter_train_class = []
letter_train_features = []
letter_test_path = './dataset/letter.test'
letter_test_class = []
letter_test_features = []
get_list_letter(letter_train_class, letter_train_features, letter_train_path)
get_list_letter(letter_test_class, letter_test_features, letter_test_path)
convert_int(letter_train_features)
convert_int(letter_test_features)
#   letter数据集训练及测试
letter_LDF_predict = train_and_predict(letter_train_features, letter_train_class, letter_test_features, 'LDF')
letter_LDF_accuracy = analysis_accuracy(letter_LDF_predict, letter_test_class)
print('使用LDF对letter的', len(letter_train_features), '份数据学习后,对',
      len(letter_test_features), '份测试数据分类的准确率为:', letter_LDF_accuracy)
letter_QDF_predict = train_and_predict(letter_train_features, letter_train_class, letter_test_features, 'QDF')
letter_QDF_accuracy = analysis_accuracy(letter_QDF_predict, letter_test_class)
print('使用QDF对letter的', len(letter_train_features), '份数据学习后,对',
      len(letter_test_features), '份测试数据分类的准确率为:', letter_QDF_accuracy)

#   optdigits数据集初始化
optdigits_train_path = './dataset/optdigits.train'
optdigits_train_class = []
optdigits_train_features = []
optdigits_test_path = './dataset/optdigits.test'
optdigits_test_class = []
optdigits_test_features = []
get_list_optdigits(optdigits_train_class, optdigits_train_features, optdigits_train_path)
convert_int(optdigits_train_features)
get_list_optdigits(optdigits_test_class, optdigits_test_features, optdigits_test_path)
convert_int(optdigits_test_features)
#   optdigits数据集训练及测试
optdigits_LDF_predict = train_and_predict(optdigits_train_features, optdigits_train_class, optdigits_test_features, 'LDF')
optdigits_LDF_accuracy = analysis_accuracy(optdigits_LDF_predict, optdigits_test_class)
print('使用LDF对optdigits的', len(optdigits_train_features), '份数据学习后,对',
      len(optdigits_test_features), '份测试数据分类的准确率为:', optdigits_LDF_accuracy)
optdigits_QDF_predict = train_and_predict(optdigits_train_features, optdigits_train_class, optdigits_test_features, 'QDF')
optdigits_QDF_accuracy = analysis_accuracy(optdigits_QDF_predict, optdigits_test_class)
print('使用QDF对optdigits的', len(optdigits_train_features), '份数据学习后,对',
      len(optdigits_test_features), '份测试数据分类的准确率为:', optdigits_QDF_accuracy)

#   sat数据集初始化
sat_train_path = './dataset/sat.train'
sat_train_class = []
sat_train_features = []
sat_test_path = './dataset/sat.test'
sat_test_class = []
sat_test_features = []
get_list_sat(sat_train_class, sat_train_features, sat_train_path)
convert_int(sat_train_features)
get_list_sat(sat_test_class, sat_test_features, sat_test_path)
convert_int(sat_test_features)
#   sat数据集训练及测试
sat_LDF_predict = train_and_predict(sat_train_features, sat_train_class, sat_test_features, 'LDF')
sat_LDF_accuracy = analysis_accuracy(sat_LDF_predict, sat_test_class)
print('使用LDF对sat的', len(sat_train_features), '份数据学习后,对',
      len(sat_test_features), '份测试数据分类的准确率为:', sat_LDF_accuracy)
sat_QDF_predict = train_and_predict(sat_train_features, sat_train_class, sat_test_features, 'QDF')
sat_QDF_accuracy = analysis_accuracy(sat_QDF_predict, sat_test_class)
print('使用QDF对sat的', len(sat_train_features), '份数据学习后,对',
      len(sat_test_features), '份测试数据分类的准确率为:', sat_QDF_accuracy)

#   vowel数据集初始化
vowel_train_path = './dataset/vowel.train'
vowel_train_class = []
vowel_train_features = []
vowel_test_path = './dataset/vowel.test'
vowel_test_class = []
vowel_test_features = []
get_list_vowel(vowel_train_class, vowel_train_features, vowel_train_path)
convert_float(vowel_train_features)
get_list_vowel(vowel_test_class, vowel_test_features, vowel_test_path)
convert_float(vowel_test_features)
#   vowel数据集训练及测试
vowel_LDF_predict = train_and_predict(vowel_train_features, vowel_train_class, vowel_test_features, 'LDF')
vowel_LDF_accuracy = analysis_accuracy(vowel_LDF_predict, vowel_test_class)
print('使用LDF对vowel的', len(vowel_train_features), '份数据学习后,对',
      len(vowel_test_features), '份测试数据分类的准确率为:', vowel_LDF_accuracy)
vowel_QDF_predict = train_and_predict(vowel_train_features, vowel_train_class, vowel_test_features, 'QDF')
vowel_QDF_accuracy = analysis_accuracy(vowel_QDF_predict, vowel_test_class)
print('使用QDF对vowel的', len(vowel_train_features), '份数据学习后,对',
      len(vowel_test_features), '份测试数据分类的准确率为:', vowel_QDF_accuracy)

You may also like...

1 Response

  1. MWHLS MWHLS说道:

    高斯分类原理
    如果认为一个事件的可能性分布属于正态分布,就可以根据这个事件的结果,来得出发生其可能性。
    在高斯分类器中,体现为,认为类的特征属于正态分布。
    那么给出一个特征,就可以求出其属于这个类的可能性。
    同样的,如果有多个类的正态分布函数,那么就能得出这个特征,属于各类的可能性,我们认为可能性最高的,就是特征对应的类。
    当要求多个特征的类,就需要求出多维正态分布的公式,并根据公式来计算特征属于不同类的可能性。
    即,当实现分类器的时候,只需要将其方差与期望参数求出,就可以得到每个类对应的高斯公式。
    这样,将不同特征代入高斯公式,就能求出不同概率,再取可能性最大的类,就是这个特征组的类别。
    QDF对高斯公式进行了简化,LDF又在QDF的基础上进一步简化。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注