E[x]=0 (4)
令w表示m维单位向量,x在ω上投影。该投影被定义为向量x和ω的内积,表示为:
主元分析的目的就是寻找一个权值向量w,使得表达式的值最大化:
即使得式(7)值最大化的w是矩阵的最大特征值所对应的特征向量。
鉴于主元分析的优点,这里引入主元分析技术给数据集降维,然后用降维后的数据构建网络,提高学习贝叶斯网络结构算法的效率、简化网络结构。构造贝叶斯网络的算法步骤如下:
(1)用普瑞姆算法生成最大似然树构造初始贝叶斯网络;
(2)对所有互信息大于阈值且在当前图中无边的结点对n1、n2:①找出它们邻接路径上的邻居结点,设n1、n2的邻居结点的结点集分别为S1和S2;② 令集合S1和S2中较小的一个作为条件集合C;③计算条件互信息v=I(n1,n2|c),如果v<ε,则返回分离;否则,如果C只包含一个结点,那么转去步骤⑤,否则,对每一个i,令Ci=c{C中的第i个结点},vi=I(n1,n2|Ci);④如果vmin<ε,则返回分离,否则返回步骤③;⑤如果S2没有用过,那么用S2作为条件集C,返回步骤③;否则,返回失败。⑥如果这对结点在当前图中能够被分离,则检测下一对结点,否则,向网中添加连接这对结点的边。
(3)对每一条图中存在边的结点对,如果除这条边外它们之间还存在其他路径,那么暂时从图中移掉这条边,然后对这对结点进行步骤①~⑥的检验;如果这对结点不能被分离,则仍将前面移掉的边加入图中,否则永久移除这条边;
(4)用碰撞识别V结构的方法定向网络中的边,对不能构成V结构的边用打分的方法对其进行定向。
4 实验
用IRIS实际数据、Zoo Data、Glass Identification Data作为网络学习的数据集,这3组数据是UCI数据集中3个用于分类的数据集。
其中IRIS数据和Glass Identification Data是连续的,所以在用数据学习贝叶斯网络前需要对数据进行模糊离散化处理。以下实验中的每个属性的离散化标度是任意选择的。实验1,比较经PCA降维的数据构造贝叶斯网络并进行分类的结果与未经PCA降维的数据分类结果的准确率,如表1所示。
用经PCA降维的数据和未经降维的数据集分别进行贝叶斯网络结构的学习,所用时间如表2所示。