2012年息科学与技术学院算法与数据结构专业技能大赛试题new.doc

2012年信息科学与技术学院 算法与数据结构专业技能大赛试题 说明：1、不限定开发语言 2、最多不超过5人/题 3、题目理解有问题找唐仕喜老师 4、比赛时间为1个月，到2013年1月1日前截止提交 5、10(2)(3)班所有学生都要参加比赛并提交作品，其它班级可参加 6、学院通过答辩评选择出一、二、三等奖若干名，并发放证书和奖品 【试题一】对给定文档，依据下面的思想设计聚类算法，并实现，输出聚类结果。 无向加权图G=＜V，E，W＞，V={d1，d2，…，dn}；其表示形式为一对称矩阵： [wij]n×n，其中W={w1，w2，…，wm}是边权重代表两个文本间相似度。计算文档的词频以及文档间的相似度，将文档粗化的聚成无关或是相关度极小的c个文档子类。首先除去在所有文档中出现的高频词；然后提取剩下词汇的短语存入词根表中。收集这些短语形成一个索引短语集T。短语t在文档di中权重为： tfij定义为短语t在文档中di出现的频率；dft定义为含有短语t的文档数量；L定义为文档di中包含的索引短语的数量；N定义为文档的数量。p_term_documen（tt，di）的值代表着短语t在文档di中的重要性，取值范围是[0，1]。计算出短语的权重，可以将短语表示成向量：di=（wi1，wi2，…，wis），其中0≤wij≤1，s代表索引短语表中词的数量。则两个文档di与dj的相似度可定义为： 由Wij=sim（di，dj），建立模糊相似矩阵W∈Rn×n，其中当i=j时，令Wii=0。由相似矩阵求得传递闭包t(W)，选取一个合适的λ值得到一个λ截集，得到的将是一个0，1矩阵，记为t(R)。由此矩阵可以分成c个文档类，即A={A1，A2，…，Ac}，满足了文档类间的相似性极小，将c个文本集看成c个子图。 判断各个文档子类中如果存在只有一个文档的类，将其并入其他与其相似度最高的子类中，变成c*个子图。 输入c*个子图，用基于谱图分割简单的谱聚类算法对每个子图G的顶点集Vk=（v1，v2，…，vn）进行聚类，得到每个子图的聚类结果及其对应的类别数ki，其中i∈[1，c*]。计算出ki的和即为总的聚类数K。输入一个数据集X={x1，x2，…，xk}，输出由以上的数据集分割出来的k个子集。 计算每个子图的亲密矩阵S，当i≠j时，Sij=exp（-d（xi-x）j/2σ2），Sii=0。构造Laplacian矩阵L，L=D-1/2SD-1/2，其中D为对角阵。计算L的前k个特征值特征向量ζ1，ζ2，…，ζk（重复特征值取其互相正交的特征向量），按照大小顺序将相应的特征向量排列构成矩阵U=[ζ1，ζ2，…，ζk]∈Rn×k，初始化聚类数m=2。令ki=m。取U的前ki个列向量构成矩阵Y，即Y=U（：，1：k），归一化Y为矩阵V，其中 在ki维空间里，每个坐标轴的正负方向分别标记一个聚类。把V的行向量看作是ki维空间的点，将其标记为距离最近的坐标轴所标记的聚类。这样最多可以产生2ki个聚类。除去空聚类和只有少数点的聚类，可以得到此时的聚类数m≤2k。比较m和ki，如果两者不等，重复上面过程。如果m=ki，则所得到的m就是确定的聚类数，同时得到相应聚类数下V的行向量聚类。当且仅当V的第i行为聚类j时，则原始数据点xi为第j类。计算ki的和得到总的聚类数k，和聚类结果。 【试题二】假定每一段都有段落中心，段落中心句是与本段中所有其它语句相关度最高的语句，找段落的中心句。 每个句子看成为一个文档，其相关度的计算思想如下： 设 为第i个文档， 为第i个文档对应的第m个短语， 为第i个文档中第m个短语的特征，则文档与的相关度为： 其中： i= 1， 2 ，3 ，4 包含关系计算： L为包含关系存在的层次。 概念主类计算： α=1 为两个概念主类。 义原在Taxonomy树上的距离节点相似计算如下： 同层相同节点的计算 ： 为同层相同节点数 为同层最大节点数 是层次数 动态角色domain处理（两个det中都存在domain）：= a为相同domain节点个数 为两个det的最深层 两个det相同节点数与总节点数的计算：= a:相同节点个数 :第1个det的节点数 :第2个det的节点数 主类义原相的计算，计算方法同。 惩罚因子： 1；否定关系 0.3；其它指定关系 0.35 短语特征值（tim） 短语的平均权重 标题短语权重最高， 次标题短语权重次之，内容短语权重最低，专业短语权重比普通短语高。 t:不重复短语数 为短语平均频率 文档中短语出现的次数 文档中短语总数 短语平均深度 短语第一次出现原短语数 文档中短语总数 文档（包含短语）的文档频率 包含短语的文