1. 基础知识

normalization概要

1.1. 1.

以基于机器学习来识别Android恶意程序为例,首先我们收集了一批应用程序的数据,例如其申明的权限、使用的api。

这组记录的集合称为一个“数据集”(data set),其中每条记录是关于一个事件或对象的描述,称为一个“示例”(instance)或“样本”(sample)。反映事件或对象在某方面的表现或性质的事项,例如权限、api,称为“属性”(attribute)或“特征”(feature);属性上的取值,例如申请了打电话的权限则该项属性为1(二值表示的话),称为“属性值”(attribute value)。属性张成的空间称为“属性空间”(attribute space)、“样本空间”(sample space)或“输入空间”。例如我们把“通话权限”“位置权限”“通讯录权限”作为三个坐标轴,则它们张成一个用于描述应用程序的三维空间,每个应用都可以在这个空间中找到自己的坐标位置。由于空间中的每个点对应一个坐标向量,因此我们也把示例称为一个“特征向量”。

一般地,令$D={x1,x_2,\dots,x_m}$表示包含$m$个示例的数据集,每个示例由$d$个属性描述,则每个示例$x_i=(x{i1};x{i2};\dots;x{id})$是$d$维样本空间$\mathcal X$中的一个向量,$xi\in \mathcal X$,其中$x{ij}$是$x_i$在第$j$个属性上的取值,$d$称为样本$x_i$的维数(dimensionality)。

如果希望能学得一个帮助判断是否是恶意程序的模型,就需要建立关于“预测”(prediction)的模型,我们需要获得训练样本的结果信息,例如“恶意程序”,称为“标记”(label);拥有了标记信息的示例,则称为“样例”(example)。一般的,用$(\mathbf x_i,y_i)$,其中$y_i\in \mathcal Y$是示例$\mathbf x_i$的标记,$\mathcal Y$是所有标记的集合,亦称“标记空间”(label space)或“输出空间”。

若我们预测的是离散值,例如“良性应用”“恶意应用”,此类学习任务称为“分类”(classification);若想要预测连续值,例如应用的威胁程度0.12、0.95,此类学习任务称为“回归”(regression)。对只涉及两个类别的“二分类”(binary classification)任务,通常称其中一个为“正类”(positive class),另一个为“反类”(negative class);涉及多个类别时,则称为“多分类”(multi-class classification)任务。一般的,预测任务是希望通过对训练集${(\mathbf x_1,y_1),(\mathbf x_2,y_2),\dots,(\mathbf x_m,y_m)}$进行学习,建立一个从输入空间$\mathcal X$到输出空间$\mathcal Y$的映射$f:\mathcal X \mapsto \mathcal Y$。 对于二分类任务,通常令$\mathcal Y={-1,+1}$或${0,1}$;对多分类任务,$|\mathcal Y|>2$;对回归任务,$\mathcal Y=\mathbb R$,$\mathbb R$为实数集。

我们还可以对应用程序做“聚类”(clustering),即将训练集中的应用程序分成若干组,每组称为一个"簇"(cluster);这些自动形成的簇可能对应一些潜在的概念划分,譬如应用自动分为“通讯类”“娱乐类”。这样的学习过程有助于我们了解数据内在的规律,能为更深入地分析数据建立基础,需说明的是,在聚类学习中,类似“通讯类”“娱乐类”这样的概念我们预先并不知道,而且学习过程中使用的训练样本通常不具标记信息。

在高维情形下易出现数据样本稀疏、距离计算困难等问题,被称为“维数灾难”(curse of dimensionality)。缓解维数灾难的一个重要途径就是降维,亦称“维数约简”,即通过某种数学变换将原始高维属性空间转变为一个低维“子空间”(subspace),在这个子空间中样本密度大幅提高,距离计算也变得更为容易。在很多时候,人们观测或收集到的数据样本虽是高维的,但与学习任务密切相关的也许仅是某个低维分布,即高维空间中的一个低维“嵌入”(embedding)(譬如前面提到的区分恶意应用和良性应用,有些权限或api特征并不起作用)。

(3)典型方法

监督:

  1. 决策树(decision tree)是一类常见的机器学习方法。顾名思义,决策树基于树结构来进行决策。一般的,一棵决策树包含一个根节点、若干个内部节点和若干个叶节点;叶节点对应于决策结果,其他每个结点则对应于一个属性测试;每个结点包含的样本集合根据属性测试的结果被划分到子结点中;根结点包含样本全集。
  2. 神经网络(neural networks)“神经网络是由具有适应性的简单单元组成的广泛并行互连的网络,它的组织能模拟生物神经系统对真实世界物体所作出的交互反应”。
  3. 支持向量机,分类学习最基本的想法就是基于训练集$\mathcal D$在样本空间中找到一个划分超平面,将不同类别的样本分开。而我们要找的划分超平面要是所产生的分类结果最鲁棒的,对未见示例泛化能力自强的。

无监督:

  1. k均值算法(k-means),把相似的观测向量分到一组,从而发现数据中的聚类结构。
  2. 流形学习(manifold learning)是一类借鉴了拓扑流形概念的降维方法。
  3. 主成分分析法(Principal Component Analysis,简称PCA)是最常用的一种降维方法。即对于正交属性空间中的样本点,用一个超平面对所有的样本进行恰当表达。这样的超平面具有两个性质:

  4. 最近重构性:样本点到这个超平面的距离都足够近;

  5. 最大可分性:样本点在这个超平面上的投影尽可能分开。

1.2. 3.

考虑正则化问题 定义正定核$K$诱导上的$H_k$的内积: 原问题变为:

采用的是再生核Hilbert空间中L2范数定义的正则化项,由表现定理,其解的形式: 求梯度,令之为$0$,可以获得

results matching ""

    No results matching ""