北京交通大学机器学习(于剑)课后习题解答

1第二章1充分性：由样本可分性公理有)~(,ixikk，即对任意对象总有唯一一个类与其最相似。所以)1),(maxarg(ikXiXxSimk。必要性：由)1),(maxarg(ikXiXxSimk，有对任意一个对象与其最相似的类有且仅有一个。所以有)~(,ixikk。2满足归类公理有样本可分性公理：)~(,ixikk（1）类可分性公理：)~(,ixkik（2）归类等价公理：XX~（3）由1式有)),()(),((,jkXikXXxSimijjXxSimik，即)),(),()((,,jkXikXXxSimXxSimijjik。由3式归类等价公理有认知表示和外延表示归类能力等价，即jkikjkXikXuuXxSimXxSim),(),(所以有))((,,jkikuuijjik。由2式有)),()(),((,jkXikXXxSimijjXxSimki，即)),(),()((,,jkXikXXxSimXxSimijjki。由3式归类等价公理有认知表示和外延表示归类能力等价，即jkikjkXikXuuXxSimXxSim),(),(，所以有))((,,jkikuuijjki。3归类等价公理XX~，U为硬划分，即由1,0iku，有对于一个样本而言只有属于与不属于某类且ciiku11，所以每个样本对于c类而言有且仅有属于一类由归类等价公理XX~，即样本的认知表示和外延表示归类能力等价，所以有对任意对象总有唯一一个类与其最相似。所以样本可分性公理成立。1,1,0,111Nkikikciikuuu2且11Nkiku，有对于每一类总有至少有一个对象属于该类。由归类等价公理XX~，即样本的认知表示和外延表示归类能力等价，所以有对任意一类至少有一个样本与其最相似。所以类可分性公理成立。4由非正则划分，有))()((jkikuuijjki又一般情况下归类等价公理总是满足的，所以XX~所以)),(),()((jkXikXXxSimXxSimijjki。5样本可分性公理有类可分性公理有由指派算子和相似算子有)max(argXiukiki)~),(max(argXiXxSimkikXi由归类等价公理有XX~，所以),(maxargmax(argikXiikiXxSimuk。6样本可分性公理类可分性公理由指派算子和相似算子)),(),()((,,)),()(),((,)~(,jkXikXjkXikXkXxSimXxSimijjikXxSimijjXxSimikixik)),(),()((,,)),()(),((,)~(,jkXikXjkXikXkXxSimXxSimijjkiXxSimijjXxSimkiixki)),(),()((,,)),()(),((,)),(min(arg,)~(,jkXikXjkXikXikXikXxDsXxDsijjikXxDsijjXxDsikiXxDsikixik)),(),()((,,)),()(),((,)),(min(arg,)~(,jkXikXjkXikXikXikXxDsXxDsijjkiXxDsijjXxDskiiXxDskiixki3)max(argXiukiki)~),(min(argXiXxDskikXi由归类等价公理有XX~，所以),(minargmax(argikXiikiXxDsuk7)),(),()((,,jkYikYYySimYySimijjik即对任意一个对象，该对象与任意两类的相似度都不同，则必然存在最大的一个。即)),(),()((,,jkYikYYySimYySimijjik所以有)),(max((arg,iYySimikiki即)~(,iyikk所以样本可分性公理成立。8由归类等价公理有XX~YY~所以，若YX~~，则YX若YX，则YX~~所以归类等价公理成立的条件下，YXYX~~。即YX~~等价于YX。9由指派算子)max(argXiukiki有3,2,1,1,2,3,1,2654321XXXXXX10第三章12pxxxKppk,)(/12)(21exp21)|(xxp4第四章1如下数据集只有两个样本2211,,,yxyxX其中在该数据集上有多个回归函数达到目标函数的最小值，如211)(xxxF，12)(12xxF都使回归函数到达目标函数的最小值。2由岭回归推导的最后表示式有ABIAAWT1，在上述数据集上其中所以代入上式有7),4,3(3),2,1(2211yxyx423111A73B73423111201410141046421Wnkknkkuxnxnu1221)(11nknkknkkxx112222120)()(110)(1222)(21ln212ln21)|(lnkkxxp0)()(2121)(1))|(ln(22222kkkxxxp5当0时，矩阵IAAT不可逆，无法求出显示解当MM,时，则3Lasso回归如在广告推广问题上，一种算法FFM把广告推广中每一类的输入特征的属性的取值看作输出特征，多个输入特征的属性值进行笛卡尔积，将输出特征维度拉的很高，这样导致了在样本数据不多情况下会出现过拟合现象，常用逻辑回归加L1范的形式，即Lasso回归防止过拟合。第五章1推导过程：由W是一组正交向量基，所以0;1,,,ijijijjTijijiwwji由拉格朗日乘子法有，拉格朗日函数为00xLdiiTkTkTikdiTjkijkTidiiTkTkTikdiTjkTjdjTikTidiiTkTkTikdijjTkdjTiiTkdiiTkTkTikdiiiTkdiiiTkdiiTkTkTikdiiiTkdiiiTkTkkdiiiTkkkXkkXxwxxxxwxxwxxxxwwxxxxwxxwxxwwxxwwxxxxwxxwwxxwwxxwxxxxwxxwwxxwwxxwxxxxwxxwwxxwwxxxxxxwwxxxxxxDsxxDs10020100100201010100201010100201010100202101002022100))()(())()(())()((2))(())(())()((2))(())(())()((2))(())(())()((2))(())(()(2))(()(),(),(min6求导有：由后式代入上式，且dii1等于协方差矩阵的迹，所以有所以的通解为2非负矩阵分解相异性度量采用如下则有：采用拉格朗日乘子法，有拉格朗日函数为HBWAWHXHWL,,exp),(2其中A，B是拉格朗日乘子。对W，H求偏导有：dijTiikdiiTkTkTikk)1())()((kkdiTiipxxwwIxL)()(2010iikiTkkiwwxxxxwL2))((200kkNxx0iikiTkkwwxxxx))((0000xLjjdiTiipkjjdiTiipkjwwIwwINxxjjjj110任意2exp),(WHXxxDskX0,0.exp2,HWtsWHXminkHWBWWHXWHXBWWHXWHXHL)(2exp0)(2exp22AHWHXWHXAHWHXWHXWL)(2exp0)(2exp227由KTT条件有0,0ijijijijWAHB3图像稀疏编码第六章1聚类分析例子如在商业上，采用聚类分析来来发现不同的客户群，并且通过购买模式刻画不同的客户群的特征。23如Pakhira等人提出的一个能同时评价硬聚类和模糊聚类结果的有效性指标这里其中v是数据集的聚类中心，Jm是FCM或者HCM算法中的目标函数值，Dc是所有不同聚类原型之间的距离总和，最优的聚类数通过求解PBV的最大值获得。可以看出PBV满足聚类有效性指标，其中Jm表示类内距离尽可能的小则最优，即满足类紧致性准则，Dc则表示类间距离总和越大越优，同时聚类效果不能无限扩大类别数c，所以1/c来限制聚类类数，而E只与数据整体上的分布有关。可以看出PBV满足聚类有效性指标。第七章p64N1假设0)(2exp2ijijWHWHXWHX0)(2exp2ijijHWWHXWHX211)(cmPBDJEccVnjjvxE118由拉格朗日乘子法有拉格朗日函数为（1）对（1求导）由代入（1）式NkkciiNkkNkkxpxpxSim1111)ˆ|(logmax)ˆ|(max)ˆ,(max11ciiciikiikiikxpxp1)ˆ|(ˆ)ˆ|(ˆ0)ˆ|(ˆ)ˆ|(ˆ11NkciikiikixpxpL0)ˆ()ˆ|(ˆ)ˆ)(ˆ|(ˆˆ12112NkiikikNkciikiiikikiixxpxxpL0))()((1,)ˆ|(ˆ))()()(ˆ|(ˆ211131iTiiNkikNkciikiiiTiikiixxxpxxxpLNkikiN11ˆ22/2exp21)ˆ|(iTpipkxxxP22/2exp21)ˆ|(iiTipipkxxxP)1()ˆ|(log111ciiNkkciixpL9所以所以在第一个假设下基于混合高斯分布的聚类算法如下：第一步：初始化参数,,E步：根据参数更新隶属度ikM步：根据更新的隶属度ik，采用最大似然估计更新参数ii,,重复迭代EM步直到收敛。2假设同上有NkikNkTikikikNkikNkkikixxxi11211))((ciikiikiikxpxp1)ˆ|(ˆ)ˆ|(ˆNkikNkTikikikiNkikNkkikiNkikixxxN11111))((1ˆ22/2exp21)ˆ|(xxxPTppkNkikiN11ˆNkikNkTikikikNkikNkkikixxx11211))((10所以在第一个假设下基于混合高斯分布的聚类算法如下：第一步：初始化参数,