第一题
第二题
第三题
第四题
第六题
第七题
第八题
第九题
第十题

第一题

试编程实现Relief算法，并考察其在西瓜数据集3.0上的效果。

解：

%{
Relief算法实现西瓜数据集的分类,西瓜数据集：第1列是密度，第2列是含糖率，第3列是瓜
的属性（1为好瓜，-1为坏瓜）
%}
%密度为连续型，这里的西瓜数据集在0-1之间，不需要规范化
load dataset.mat
data = watermelon;
delta_matrix = nearHit_Miss(data);
for i = 1:size(data,1)
    delta = -delta_matrix(i,1)+delta_matrix(i,2);
    delta_result(i) = delta;
end
delta_result = sum(delta_result);

function matrix = nearHit_Miss(X)
%猜中近邻
cmp = 1;%因为已经规范化到[0,1]，所以最大为1
for i = 1:size(X,1)
    for j = 1:size(X,1)
        if i ~= j
            if X(i,3) == X(j,3)
                cmp = min(abs(X(i,2)-X(j,2)),cmp);
            end
        end
    end
    hit_matrix(i) = cmp;
end
%猜错近邻
cmp = 1;
 for i = 1:size(X,1)
    for j = 1:size(X,1)
        if i ~= j
            if X(i,3) ~= X(j,3)
                cmp = min(abs(X(i,2)-X(j,2)),cmp);
            end
        end
    end
    miss_matrix(i) = cmp;
 end
matrix = [hit_matrix' miss_matrix'];
end

这单独计算一个属性的结果，Relief算法的更新权重怎么选择？在这里，最后直接使用的权重的相加。

第二题

试写出Relief-F的算法描述。
解：
相比Relief增加了多分类的样本所占的比例，很奇怪为什么相同的分类不需要乘上对应的比例。

------------------------------------------------
输入：
    数据集D；
过程：
将数据集连续属性参数用Min-max归一化
计算数据集各样本分类的概率p
计算数据集各样本两两距离dist
for x in D
    根据dist找出各分类离x最近的样本集合xmin
    for xm in xmin
        if(x分类与xm相同)
            for i=1:k
                θ_i=θ_i-diff(x_i,xm_i)^2
            end for
        else
            for i=1:k
                θ_i=θ_i+p_i*diff(x_i,xm_i)^2
            end for         
        end if
    end for
end for
输出：
各属性相关统计量θ
------------------------------------------------

第三题

Relief算法是分别考察每个属性的重要性。试设计一个能考虑每一对属性重要性改进的算法。
解：
由于过滤式的算法都是很老的算法了，并没有去想太多。
一个简单的方法，将单一属性的相关统计量计算出来后，两两相加得到每对属性的相关统计量。不过这样并没有什么用，所有属性还是认为互不相关。

第四题

试为LVW设计一个改进算法，即便有运行时间限制，该算法也一定能给出解。
解：
LVW结束循环的条件是连续T次随即出来的特征都比当前最优特征集合差。当T和特征集合A很大时，LVW需要的迭代时间很长。
如果有运行时间限制，可以再给一个结束条件，设最多迭代次数t，当总迭代次数达到t的时候，结束迭代并返回当前最优的特征集合。t的值根据限定的时间来估计。

第六题

试析岭回归与支持向量机的联系。
解：
相同点：

目标函数中都有参数项项。

不同点：

岭回归中的是作为罚项，防止过拟合和病态矩阵的产生，而支持向量机中是优化目标。
岭回归主要优化目标是累积平方误差。而线性支持向量机不以平方误差作为参考，而是将误差作为约束，来保证样本必须被求出的直线分隔，即，所以要求样本线性可分。
第七题
试述直接求解L范数正则化会遇到的困难。
解：
由于L范数不连续，非凸，无法用解析法很好的表示，只能通过遍历来寻求最优解，这导致L范数的最优化为题是个NP难问题。
第八题
试给出求解L范数最小化问题中的闭式解(11.14)的详细推到过程
解：

第九题
试述字典学习与压缩感知对稀疏性利用的异同。
解：
字典学习通过学习出的字典使属性适度稀疏，使得文本数据在字频上线性可分，从而提升如SVM获得更好的性能。
压缩感知则是希望原始信号本身虽然不稀疏，但是他内部是高度相关的，这样可以通过使得是一个稀疏的向量。此时通过采样信号来还原时可以得到足够接近的结果，从而更好的还原原始信号。
第十题
一般字典学习：。
假设字典学习具有分组结构，即同一个分组内的变量同为非0或者同为0.

输入：分组属性输出：参数属性，要学习的字典参数学习：对于每个求出其中其中是组成的向量字典学习：求出其中