思想
最近邻法思想其实很简单：给出一大堆已经知道标签的图片。现在新来一张图片，新图片和所有的旧图片做比较，找出和旧图片中“最相似”的一张，输出这一张图片的标签作为预测值。
“最相近”怎么办？
一张图片需要抽取它的特征，只要所有特征都很相近，那么两幅图片就很相似。“当看到一只鸟走起来像鸭子、游泳起来像鸭子、叫起来也像鸭子，那么这只鸟就可以被称为鸭子”。虽然简单粗暴，但是很有效。如何定义相近呢？比如求欧式距离，比如距离的绝对值之类的都可以。
那么，这个特征怎么求呢？这个Toy里面使用灰度共生矩阵来求。求得灰度共生矩阵（因为简单啊），然后求灰度共生矩阵的5个二次统计量（能量，对比度，相关性，均匀度，熵）作为特征。在这里，灰度共生矩阵可以使用四个方向（0°，45°，90°，135°），每个方向都能求出来5个二次统计量，也就是一幅图片可以求得20个特征。作为Toy差不多够用了吧？
下面呢，就是如何定义“鸭子”了。公式如下，应该没有打错把？最起码我是这么理解的公式：
$$
F(X)=arc\min_{k}(\sum(X-X_{i}^{k})^{2})
$$
实现
主程序：参数调整，读入图片，分出训练集和测试集，驱动整个程序的运行。
clear all;
close all;
clc;
% 参数们
NumLevels=8;
Scale=0.5;
Verbose=0;
Dims=4;
% 读入所有图片，获取特征和其他辅助信息
[n_samples,n_classes,n_features,classes,label,data]=ReadImg(NumLevels,Dims);
% 其他一些基础的东西
half=int32(n_samples*Scale);
my_yes=[];
dt_yes=[];
% GoGoGo
for iter=1:1:10
% 随机排序
sel=randperm(n_samples);
% 分出训练集合和测试集合
TrainSet_data=data(sel(1:half),:);
TrainSet_label=label(sel(1:half),:);
TestSet_data=data(sel(half+1:n_samples),:);
TestSet_label=label(sel(half+1:n_samples),:);
% 开始做预测
my_yes(iter)=TestAll(TrainSet_label,TrainSet_data,TestSet_label,TestSet_data,Verbose);
% 拿决策树作对比
dt_yes(iter)=DTTestAll(TrainSet_label,TrainSet_data,TestSet_label,TestSet_data,Verbose);
% 输出看看
fprintf('Iter%d:t My:%ft DT:%fn',iter,my_yes(iter),dt_yes(iter));
end
% 统计结果
fprintf('My:t max:%f:t average:%ft min:%fn',max(my_yes),mean(my_yes),min(my_yes));
fprintf('DT:t max:%f:t average:%ft min:%fn',max(dt_yes),mean(dt_yes),min(dt_yes));
读入图片
这里给的数据集比较特殊：数据集有jpg和png两种类型的图片，每幅图片都是200*200的纹理。共有8个类别，每个类别有8张图片。比如第3个类别第6张图片，文件名为36.jpg。png是对jpg做过直方图均衡化的结果。这两种图片在这里我混用了，为了让基数更大一点。（这个数据集叫Brodatz）
function [ n_samples,n_classes,n_features,classes,label,data ] = ReadImg(NumLevels,Dims)
% 标签和特征
label=[];
data=[];
% 样本总数
total=0;
% 因为图片是有规律的，所以采取这样读取图片
for i=1:1:8
for j=1:1:8
for k=1:1:2
% 后缀名的判断
if k==1
aft='.jpg';
else
aft='.png';
end
total=total+1;
% 拼接文件名
filename=['data/',num2str(i),num2str(j),aft];
% 获得这个图片的特征
data(total,:)=ImgFeatureGen(filename,NumLevels,Dims);
% 获得这个图片的标签
label(total)=i;
end
end
end
% 标签转成列向量方便使用
label=reshape(label,[],1);
% 统计啦
n_samples=total;
classes=unique(label);
n_classes=length(classes);
n_features=size(data);
n_features=n_features(2);
end
对于每一张图片，转变成特征值
function [ feature ] = ImgInfoGen( f ,NumLevels,Dims)
feature=[];
% 读入图片，如果是彩色，则转化成灰度图片
IMG=imread(f);
if ndims(IMG)==3
IMG=rgb2gray(IMG);
end
% 总共有多少个特征
total=0;
% 几个方向
angle=[0,1;-1,1;-1,0;-1,-1];
for i=1:1:Dims
% 得到灰度共生矩阵
COMTX=graycomatrix(IMG,'Offset',angle(i,:),'NumLevels',NumLevels);
% 求二次统计量
MAT_ANS=graycoprops(COMTX);
% 转成行向量便于计算
MAT_ANS=struct2cell(MAT_ANS);
for j=1:1:length(MAT_ANS)
total=total+1;
feature(total)=cell2mat(MAT_ANS(j));
end
% 熵
% total=total+1;
% feature(total)=-sum(sum((COMTX+1).*log2(COMTX+1)));
end
end
测试的时候发现加上熵之后精度会下降。很奇怪。
熵哪里算错了？
$$
N=\sum_{i}\sum_{j}(i-j)^{2}p(i,j)
$$
另外我对灰度共生矩阵加上了1,防止log(0)得到NaN。
下面开始做预测吧！因为这个分类器不像决策树那样需要做训练，所以直接做预测就好了。
做预测的引导程序如下：
function [ yes_rate ] = TestAll( TrainSet_label,TrainSet_data,TestSet_label,TestSet_data,Verbose )
yes=0;
n_samples=length(TestSet_label);
for i=1:1:n_samples
% 获得预测值和预测分数
[prediction,score]=TestOne(TestSet_data(i,:),TrainSet_label,TrainSet_data);
if TestSet_label(i)==prediction
yes=yes+1;
end
% Verbose报告
if Verbose==1
fprintf('label:%d:tpredict:%dtscore:%fn',TestSet_label(i),prediction,score);
end
end
% 得到精度
yes_rate=yes/n_samples;
end
对于每一个样本，做预测的程序如下：
function [ prediction,bestScore ] = TestOne( test_data,train_label,train_data )
% 一些准备工作和统计工作
classes=unique(train_label);
n_classes=length(classes);
n_samples=length(train_label);
% 初始化工作
score=ones(n_classes,1);
score=score*413431390;
% 遍历训练集合中的每一个样本，得到此测试验本和每一个分类的最小距离
for i=1:1:n_samples
score(train_label(i))=min(score(train_label(i)),sum((train_data(i,:)-test_data).^2));
end
% 找出最小值，作为预测结果
[bestScore,prediction]=min(score);
end
其实整个算法核心就四句话：
for i=1:1:n_samples
score(train_label(i))=min( ...
score(train_label(i)), ...
pdist(train_data(i,:),test_data));
end
[bestScore,prediction]=min(score);
看出来了吧？
我还用了决策树作对比：
function [ yes_rate ] = DTTestAll(TrainSet_label,TrainSet_data,TestSet_label,TestSet_data,Verbose)
yes=0;
TREE=fitctree(TrainSet_data,TrainSet_label);
n_samples=length(TestSet_label);
for i=1:1:n_samples
prediction=predict(TREE,TestSet_data(i,:));
if TestSet_label(i)==prediction
yes=yes+1;
end
if Verbose==1
fprintf('label:%d:tpredict:%dn',TestSet_label(i),prediction);
end
end
yes_rate=yes/n_samples;
end
话说Matlab自带的决策树用的是什么算法？Sk-learn带的决策树用的是什么算法？
整体代码风格受到sk-learn的影响比较大。比如说参数传递和参数命名之类的。
下面结果是在某个Brodatz数据集上跑的效果。
结果
运行结果如下
Iter1: My:0.562500 DT:0.468750
Iter2: My:0.578125 DT:0.546875
Iter3: My:0.562500 DT:0.421875
Iter4: My:0.484375 DT:0.437500
Iter5: My:0.515625 DT:0.421875
Iter6: My:0.578125 DT:0.421875
Iter7: My:0.531250 DT:0.281250
Iter8: My:0.500000 DT:0.421875
Iter9: My:0.640625 DT:0.468750
Iter10: My:0.484375 DT:0.406250
My: max:0.640625: average:0.543750 min:0.484375
DT: max:0.546875: average:0.429688 min:0.281250
看来还是可以的。但加上熵之后，精度反而会下降：
Iter1: My:0.437500 DT:0.468750
Iter2: My:0.484375 DT:0.578125
Iter3: My:0.484375 DT:0.578125
Iter4: My:0.437500 DT:0.562500
Iter5: My:0.453125 DT:0.453125
Iter6: My:0.421875 DT:0.453125
Iter7: My:0.515625 DT:0.625000
Iter8: My:0.437500 DT:0.515625
Iter9: My:0.453125 DT:0.531250
Iter10: My:0.437500 DT:0.546875
My: max:0.515625: average:0.456250 min:0.421875
DT: max:0.625000: average:0.531250 min:0.453125
不知道是哪里有问题。
然后可以调整参数，例如加大训练集合、减少样本数之类、改变灰度共生矩阵量化精度之类的。在这里就不做对比了。反正就是，训练集合越大精度越好、特征数量增加可能导致精度减小。
最后附上一些很神奇的代码段：
十分解气啊！
收工开始复习考试。
参考文档
[1] 杨杰. 数字图像处理及Matlab实现. 北京：电子工业出版社
[2] 宋相法. 数字图像处理课堂PPT. 河南：河南大学
发表回复