面向大规模文档聚类及相关技术的研究-lm

1、面向大规模文档聚类及相关技术的研究博士生：刘铭导师：王晓龙 教授2008-06-28主要内容n课题来源及研究的目的和意义n国内外在该方向的研究现状及分析n前期的理论研究与试验论证工作的结果n学位论文的主要研究内容、实施方案及其可行性论证 n论文进度安排，预期达到的目标 n为完成课题已具备和所需的条件、外协计划及经费 n预计研究过程中可能遇到的困难、问题，以及解决的途径 课题来源及研究的目的和意义n课题来源国家自然科学基金重点项目-问答式信息检索的理论与方法研究（60435020）国家863目标探索导向类项目-面向大规模文本信息的快速聚类和认知技术研究（2007AA01Z172）课题来源及研究的

2、目的和意义n研究的目的和意义聚类技术是一个来源已久且与人们的生活息息相关的实用技术，在现实生活中有很多领域需要聚类技术，尤其随着信息产业的发展、网络的进步，人们每天接触的信息与日剧增，如何对这些大规模的信息进行处理已经成为当今研究的热点，而聚类技术恰可作为该问题的一个很好的解决办法；在现实世界中，人们很难确定数据（尤其是网络信息）的类别标注，也同样无法确定数据应归宿的类别总数，聚类技术就是此情况下一个很好的处理方法，因为在聚类中我们不需要知道数据的类别标注，同样也不需要任何训练数据，其应用更加便捷，聚类也可以用于很多算法的预处理阶段；随着网络信息的剧增，用户每天接触的信息种类繁多、数量巨大，而

3、这些网络数据中又以文本数据居多。对于这些数量巨大的文本信息，急需一种自动分析技术以协助用户获取有用信息，因此如何能够对大规模文本进行快速及有效的聚类是一个非常有实用价值的研究领域； 主要内容n课题来源及研究的目的和意义n国内外在该方向的研究现状及分析n前期的理论研究与试验论证工作的结果n学位论文的主要研究内容、实施方案及其可行性论证 n论文进度安排，预期达到的目标 n为完成课题已具备和所需的条件、外协计划及经费 n预计研究过程中可能遇到的困难、问题，以及解决的途径 国内外在该方向的研究现状及分析聚类的定义：n聚类就是对大量未知标注的数据集，按数据的内在相似性将数据划分为多个类别，使类别内数据相

4、似度较大而类别间数据相似度较小；聚类的基本要素：n定义数据之间的相似度：l采用何种方式计算数据之间的相似性；n聚类有效性函数（停止判别条件）：l在聚类算法的不同阶段会得到不同的类别划分结果，可以通过聚类有效性函数来判断多个划分结果中哪个是有效的；l使用有效性函数作为算法停止的判别条件，当类别划分结果达到聚类有效性函数时即可停止算法运行；n类别划分策略（算法）：l通过何种类别划分方式使类别划分结果达到有效性函数；国内外在该方向的研究现状及分析相似度分类：nEuclidean Distance：n交叉熵：nCosine：nBased on Semantic：nUnbalance Similarit

5、y：12211s(,)rimjmmrrimjmmmA ACoAAijA A1(,)()rimjmmEuclideanAAijA A222111()1(,)-log ()(*log)(*log)22rnnimjmimjmimimjmjmiiiAAHAAAAAAijA A211(,)(,)()rrimjnimjnmnSemanticSemantic AAAAijA A21(,)()rmimjmmUnbalancewAAijA A国内外在该方向的研究现状及分析聚类有效性函数：n最小误差（ ）:n最小方差:n聚类熵（CE）:21 | |iiiicx Cieiiix Ccx mCxmJxmC个类别，待聚

6、类数据 ， 为类别 的中心，221|iiix CxCSxxn eJ11 111; ;(,)(,)jjknjjoijjjijioojjnkkjjjiooojijpppCpCnnEne ppe pC国内外在该方向的研究现状及分析聚类算法分类：n基于划分: K-means, K-medoidsn分裂法(partitioning methods)：给定一个有N个元组的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类。n基于层次: HFCn层次法(hierarchical methods)：对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。n基于

7、密度: DBSCANn基于密度的方法(density-based methods)：基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”聚类的缺点。n基于网格: CLIQUE , STINGn基于网格的方法(grid-based methods)：将数据空间划分成为有限个网格单元 (cell)，并且所有的处理都是以网格单元为对象的，其突出的优点就是处理速度很快。n基于模型的方法 : EMn基于模型的方法(model-based methods)：给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的类别。国内外在

8、该方向的研究现状及分析自组织映射聚类：nSOM（自组织映射）的由来： 1991，由Kohonen提出，模拟人脑中的神经元层；n人脑中不同的神经元区域负责不同的功能；n一旦有外部刺激，与刺激相关的神经元会被激励，并且其附近神经元也会受到激励；国内外在该方向的研究现状及分析国内外在该方向的研究现状及分析n神经元结构：一维 二维 层次国内外在该方向的研究现状及分析神经元分布密度：n输入数据的分布密度为：n将与输入数据最相似的神经元记为获胜神经元n获胜神经元临近的N个神经元n N=0，不调整临近神经元：n 调节临近的N个神经元：分布密度推论：n输入数据分布密度:n神经元分布密度:n神经元竞争获胜的概率

9、 输入数据中与w相似的数据的比例：n推论： 2/3()P x( )P x222/3 1/(33(1) )()nnP x;()( ), ()() ()( )iiijijiijjjip wq xw w f wf wxw xwp wq x;()( ), = ()()()( )iiijiijjijjjf wq xw wxw xwp wp wf wq x12( )f w( )p w( )q x国内外在该方向的研究现状及分析SOM优点:u通过神经元结构使算法对初始值设置不敏感；u通过近似梯度下降调整神经元向量使模型不容易陷入局部最优；u神经元分布能够近似模拟数据分布；u将高维数据映射到二维平面上能够在一定

10、程度上处理高维数据；SOM缺点：u算法迭代时间较长；uSOM算法需要预先设定类别数即神经元数，而初始参数（类别数）在实际应用中不容易获得；主要内容n课题来源及研究的目的和意义n国内外在该方向的研究现状及分析n前期的理论研究与试验论证工作的结果n学位论文的主要研究内容、实施方案及其可行性论证 n论文进度安排，预期达到的目标 n为完成课题已具备和所需的条件、外协计划及经费 n预计研究过程中可能遇到的困难、问题，以及解决的途径 前期的理论研究与试验论证工作的结果n本报告主要的研究问题可以分为两类：l特征抽取；l大规模文档聚类问题；n主要研究了基于特征分布以及基于语义词汇链的特征抽取方法，并通过其降低

11、特征空间的维度，加快聚类速度和提高聚类准确率；n采用基于SOM的压缩神经元聚类算法进行大规模文档的快速聚类；特征抽取n问题描述：l给定特征集合D，选择特征集合的子集S，并使训练数据的类别划分结果在S的基础上不低于其在特征集合D的基础上；nFilterl通过优化独立的目标函数进行特征权值评价或特征抽取，处理速度较快，不需要结合固定的聚类或分类算法，不能保证特征抽取结果能够提高特定算法准确率；代表方法：互信息，最小相关度，特征最小冗余度；lRelief (Kira & Rendell 1992） Focus（Almuallim & Pfleger 1991) nWrapper (J

12、onn, Kohavi, Pfleger1994)l结合固定算法进行特征抽取，其特征优化的目标函数一般是算法的目标函数，特征抽取的时间复杂度较高；特征分布n特征对文档的区分能力：文档集合为 ，对应的特征空间为 ，第P 个特征为 。设文档集合中具有特征 的文档子集为 。将文档看作二维平面上分布的点，将具有此特征的文档子集和不具有此特征的文档子集看作图中的两个点集，以两个点集中心作为特征对文档的区分能力；其含义是具有特征的文档集合与不具有特征的文档集合的中心距离越远，说明这两个点集相互覆盖的范围越小，说明特征能够很好的将文档区分为两个子集，反之说明特征并不能提供任何区分文档的能力；DOCFEATU

13、REpFeature()pDOC FeaturepFeature特征分布n特征对文档的凝聚能力：仍然如同上述的假设，设文档集合中具有特征 的文档子集为 ，同时计算中各文档的特征向量到其中心向量的平均欧式距离。然后将 中各文档的特征向量中 对应的维度置为0，即不考虑特征对文档的影响，重新计算 中各文档的特征向量与中心向量的平均欧式距离。将这两个平均距离的差值作为特征对文档的凝聚能力；该差值反映了有无特征 后文档子集 的内聚度的改变程度，如果值很小说明特征存在与否对文档的内聚度没有太大改变。反之说明特征能够在一定程度上能够很好的凝聚相似文档；pFeature()pDOC FeaturepFeatu

14、repFeature()pDOC Feature()pDOC Feature()pDOC Feature实验结果 聚类能力排在前十位的特征词聚类能力排在前十位的特征词 聚类能力排在后十位的特征词聚类能力排在后十位的特征词特征词特征词聚类能力聚类能力文档数文档数特征词特征词聚类能力聚类能力文档数文档数项目项目0.51454165服务服务0.00430922153媒介媒介0.50192843学生学生0.00422108137政治政治0.46091451时间时间0.00410058119主席主席0.46060539地区地区0.0036044673投资投资0.44429889教学教学0.0032461

15、5102赛季赛季0.42173196细胞细胞0.002831487日报日报0.42055523计算机计算机0.0027039569证券证券0.41754343研究研究0.002570918记者记者0.40371076钓鱼者钓鱼者0.002138673商业商业0.39948671闭幕闭幕0.002127884从1998年人民日报新闻语料中随机选取10000篇新闻作为测试语料集，计算每个特征的聚类能力(Cluster ability)值，并在下表列出了聚类能力值排在前十个的特征词和后十个的特征词。实验结果测试语料：10000篇新闻作为测试语料，以自组织聚类算法作为判别准则，检测了是否进行特征选择后

16、算法的聚类时间以及特征空间的维度；如果不经特征选择其特征空间为6701维，而进行特征选择后其特征空间为3917维，减少了大约2/5，因此大大降低了聚类时间；前期的理论研究与试验论证工作的结果n结合语义的特征抽取：l通过构造词汇链来反映文章的主题信息，并依据词汇链反映的主题信息从特征空间中抽取能够代表主题的关键词作为特征词，可以有效降低特征空间的维度，并且减少了相似特征的冗余度。 n词汇链技术：l词汇链是1991年由Hirst提出的是以相关或相似的词语构成的一条链，其能够有效代表文章的主题信息 。n知网(HOWNET)语义辞典：l“知网”是由董振东博士完成的中文语义辞典，是一个以汉语和英语中的词

17、语所代表的概念为描述对象，以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库。前期的理论研究与试验论证工作的结果词汇链构造算法:对文章进行分词及过滤停用词后即可获得文章的词空间WordSet；顺序扫描文章的词空间，设此时扫描的词为词空间的第i个词Wordi，Wordi的第j个义类为Wordij。设文章的词汇链集合为ChainSet， 第k个词汇链为Chaink；如果词Wordi只含有一个义类，则计算该义类Wordij与文中每条词汇链的关联关系(RelationShip) ，并找到与义类Wordij具有最大关联关系的链(MaxChain)；如果最大关联关系超过一定阈值，则将

18、词Wordi插入到词汇链MaxChain中，并标记词Wordi在链中对应的义类为Wordij，否则新建一条链，并将词Wordi插入到新建的链中，同时标记词Wordi在新建的链中对应的义类为Wordij；如果词Wordi含有多个义类，则按照上述方法依次处理这多个义类；从每条词链中选择权重最大，即能充分代表该链信息的词作为文档的聚类特征，将所有文档的特征取并集即为文档集合的特征空间；前期的理论研究与试验论证工作的结果n从1998年人民日报新闻语料中随机选取10000篇新闻作为测试语料集，下表为运行词汇链算法后得到的词汇链结果：l词汇链构造算法基本能够将特征空间内相似的特征凝聚为一条链，每条链能够反

19、映文档集合中的某一主题信息；序号特征链1冠军 赛事 比赛 训练 全能 决赛 竞技 预赛 总局 奥委会 运动员 裁判 得分 执教 教练 抽签 俱乐部 国家队 晋级 火炬 开幕 2市场经济 供应 价格 需求 供求 通货膨胀 销售 收入 商品 零售 资金 投资 货币 基金 消费 理财 证券 外资 盈利 营销 行情3电脑 配件 内存 硬件 光盘 笔记本 主板 软件 检索 操作系统 升级 容量 显示器 驱动器 芯片 网络 因特网 指令 视频 接口 光纤4陆地 口岸 区域 地形 城市 国内 首都 乡村 城镇 海岸 基地 绿洲 县城 地段 空间 海域 内陆 海外 沙漠 岛屿 水域 港口5教师 员工 学校 学

20、生 课堂 报告 成绩 中专 函授 辍学 学业 学历 学费 高考 学龄 毕业 留级 报考 教研 课程 辅导 证书 导师前期的理论研究与试验论证工作的结果基于语义特征抽取聚类实验结果方式方式抽取的特征数抽取的特征数51015类内类内相似度相似度类间类间相似度相似度类内类内相似度相似度类间类间相似度相似度类内类内相似度相似度类间类间相似度相似度Date Set 1A0.38120.31230.42120.30140.40140.3380B0.48110.36210.52460.37020.53130.3452Date Set 2A0.38140.32530.44920.32070.43960.356

21、1B0.46140.33270.49650.36720.50120.4008Date Set 3A0.39750.31740.43810.35380.47530.3476B0.47610.35930.51160.35490.54100.3710Date Set 4A0.41120.32260.42700.34820.49770.3947B0.50860.37200.54880.39220.52420.3973Date Set 5A0.45800.37290.47970.35740.47370.3954B0.52130.41280.57120.39130.57560.43761998人民日报新闻

22、作为基准数据集，并从中分别随机抽取1000篇文档构成5个测试数据集；A：代表仅采用统计信息获得的聚类特征构造文档特征向量得到的聚类结果；B：代表采用词汇链获得的聚类特征构造文档特征向量得到的聚类结果；前期的理论研究与试验论证工作的结果文档聚类与传统聚类区别：l以词作为聚类特征 ，特征空间为词空间，文档特征向量为词向量，文档特征集合仅是特征空间的一个非空子集；大规模文档聚类特有问题：l随文档集合增大，特征空间维度剧增，文档的特征向量急剧稀疏，大部分文档的相似度趋近于0，并且大量文档存在由相似特征引入的语义相似性； 基于SOM大规模文档聚类-VPSOM：l以特征的权值作为特征代表文档类所描述信息的

23、能力，并从特征空间中选择能够将不同文档类进行有效区分的特征构造神经元的特征集合。经过如上处理后改变了对聚类问题的描述，将聚类问题转化为寻找能够将文档集合进行有效区分的多个特征集合，并以此特征集合将文档集划分为多个类别； VPSOM算法初始结构构造（一）n极大极小值原理：l在文档集合中具有极大极小值的两个文档属于不同的文档类的可能性非常大，当选择的具有极大极小值的文档数小于真实类别数时极大极小值的变化幅度较小。 n极大极小聚点选择：l1 设文档集合为DOC，选择作为聚点的文档数最多为p，设已经选择的聚点集合为Select，s为已选择的聚点数，初始时设s=0，设VecMin中存放了Select中每

24、个聚点的极大极小值；l2 从文档集合中选取相似度最小的两个文档-Doci和Docj作为初始聚点AC1和AC2，计算这两个文档的余弦相似度：d(Doci,Docj)，以0和d(Doci,Docj)分别作为聚点AC1和AC2极大极小值，并将其压入到VecMin中。同时通过矩阵B将Doci和Docj从其它文档对应的相似度向量VecDirect中删除， ；l3 如果 则找到聚点集合中的每个聚点与该聚点对应的相似度向量VecDirect中第一个文档的相似度的最小值，此文档即为根据公式(1)得到的第s+1个聚点，设此聚点对应的文档为Docmin，将Docmin压入Select中，并将此相似度值压入VecM

25、in中；l4 如果 则按照公式(2)计算Select中每个聚点对应的深度，保留位于最大深度前的聚点；( ) |( )-( -1)|(1)-( )|Depth iVecMin iVecMin iVecMin iVecMin i1argminmax (,),1,2,., &kskrrDocSelectACd Doc ACrsACSelect12s+1p1sp 2ssVPSOM算法初始结构构造（二）A行为文档集合，列为特征空间，Aij为特征空间中第j个特征在文档集合中第i篇文档中的权重。VecDirect采用余弦相似度计算矩阵A中各文档对应的行向量间的相似度，同时为每篇文档构造一个相似度向量

26、VecDirect，第i篇文档的相似度向量为VecDirecti，将文档集合中的每篇文档按照此文档与第i篇文档的相似度由大到小的顺序存放在VecDirecti中。B行列均为文档集合，Bij代表第j篇文档在第i篇文档的相似度向量VecDirecti中的位置。时间性能分析：l聚点选择中通过p限制了聚点的个数，也限制了划分文档集合得到的类别数。实验表明：聚类中的类别数一般小于文档集合大小的平方根，因此我们以文档集合大小的平方根为p赋值； l上述聚点选择算法的时间复杂度为 ，其中算法循环p次，每次循环时在第3步中最多需要扫描p个聚点，由于 ，n 为文档数。所以通过极大极小值选择聚点的时间复杂度为O(n

27、)；下表为上述聚点选择中的数据结构：( * )O pppnVPSOM算法初始结构构造（三）n初始结构构造算法：l1 设文档集合为DOC，神经元集合为NEURON，以上述每个文档聚点作为一个神经元，并将神经元组织为扇形结构；l2 计算每篇文档与神经元集合中每个神经元的相似度，并为每个神经元建立一个MAP向量，向量中第i维的值为DOC中第i篇文档与此神经元的相似度；l3 计算神经元集合中任两个神经元对应的MAP向量的余弦相似度，同时通过索引Index记录与每个神经元最相似的神经元的序号；l4 从神经元集合NEURON中随机选择一个神经元放入扇形结构中的任意位置，设此神经元为Neuroni，并将Ne

28、uroni从NEURON中删除；l5 按Index选择与Neuroni具有最大相似度的神经元，设此神经元为Neuronj，将Neuronj放到扇形结构中与Neuroni相邻的位置上，同时将Neuronj从NEURON中删除；l6 检测NEURON是否为空，如为空则结束；否则按步骤5循环处理与上一次插入到扇形结构中的神经元最相似的神经元，直到NEURON为空；n时间性能分析：l分析上述初始化算法可以得到：设初始化时共有s个神经元， ，n为文档集合的大小，步骤1的时间复杂度为 ，步骤2中计算文档与神经元的相似度以构造MAP向量的时间复杂度为 ，步骤3中计算神经元间MAP向量的相似度的时间复杂度为

29、，步骤4、5、6构造扇形结构的时间复杂度为 ，所以上述初始化算法的时间复杂度为 。 spn(1)O( * )O s n( * )O s s( *)()O s ns ssO sn( )O s前期的理论研究与试验论证工作的结果n检测是否使用初始化后算法VPSOM的聚类时间以及MQE (Je)l左图代表了是否采用极小极大值初始化后，VPSOM算法对于不同文档数的聚类时间。l右图代表了是否采用极小极大值初始化后， VPSOM算法的MQE值随时间的变化曲线图。 神经元特征权值训练n权值训练步骤：l1 从文档集合DOC中随机选取一个文档，设此文档为Dock；l2 计算Dock的与神经元集合NEURON中各

30、神经元的相似度，找到与Dock具有最大相似度的神经元，并记其为获胜神经元；l3 按照公式(1)调整获胜神经元中特征的权值，同时调整位于获胜神经元邻域范围内的神经元的特征的权值；l4 检测算法是否满足收敛条件。如满足，则停止；否则运行步骤1234直至收敛；n权值调整函数：l公式(1)介绍了如何根据文档Dock的某个特征DocFeature调整神经元Neuronb的相应特征的权值：( )(1) ( )( ) ; ()( )(_( )*()*)1 )0.50.1 bbbkNeuronWeight h tNeuronWeight h tIf DocFeatureFeatureVector Neuron

31、DocWeight zLearnRate tdistNeighborhood ; ()bIf DocFeatureFeatureVector Neuron1文档与神经元相似度计算n文档与神经元相似度计算：l1) 在传统自组织映射聚类算法中，特征的权值对应于此特征神经元代表的文档类中的权值的平均分布。因此可以采用欧式距离或余弦相似度等方法，通过计算文档中每个特征的权值和此特征在神经元中的权值的差距情况计算文档与神经元的相似度。而本算法以特征的权值来反映该特征作为映射到神经元的文档类所描述信息的代表的能力，因此无法使用欧式距离或余弦相似度等相似度计算方法；l2) 由于我们压缩了神经元的特征集合，因

32、此文档中的每个特征并不一定在神经元的特征集合中出现，而欧式距离或余弦相似度需要文档中的每个特征均出现于神经元的特征集合中；l设文档 的特征集合和神经元 的特征集合的交集为 大小记为 。假设该交集中的某个特征 对应于文档 的特征集合中的第z个特征，对应于神经元 的特征集合的第y个特征，则文档 与神经元 的相似度函数如下：(,)0; |sec| |()| /3( )*( )*log(|sec( )( )kikikkikiSim Doc NeuronIfIntertFeatureFeatureSet DocDocWeight zNeuronWeight yIntertFeDocWeight zNeu

33、ronWeight yintsec|); kikierfeature IntertFeatureatureElsekDociNeuronkiInterFeature|kiInterFeatureinterfeaturekDociNeuroniNeuronkDoc前期的理论研究与试验论证工作的结果采用Yahoo网站的2007年新闻作为算法的测试语料，该新闻语料包含了体育、医疗、社会、财经、教育等多个种类，是一种平衡语料，包含大约十万篇文档共298M。将VPSOM与K-means、层次聚类、GSOM、GHSOM 对于十万篇文档的聚类时间做了对比; 前期的理论研究与试验论证工作的结果以两种方法测定算

34、法VPSOM的准确率，其中第一种方法测试了在不限制类别数的情况下算法的性能；第二种方法测试了在限制类别数的情况下算法的性能。n第一种方法：运行算法直到收敛，生成多个类别，设算法生成的类别集合为 ，其中第i个文档类为 ，将此文档类人工划分为多个子类别，设这多个子类别的集合为 ，以人工划分的具有最多文档数的子类作为类别的代表，设此子类别为 ，将其它子类别包含的文档视为不相关文档，则文档类的准确率： 。取所有类别的准确率的平均值作为算法的准确率；n第二种方法：使用算法对文档集合进行聚类，当文档聚合为500个类别后停止类别增加，然后仅进行神经元调整。每个类随机查看15 条文档，如果有一篇文档与该类的主

35、题内容不符，则视为错误归类，设错误归类的文档数为 ，则每个类别的准确率为： 取所有类别的准确率的平均值作为算法的准确率；C iC()iItraSet CmaxItraC| / |MaxiItraCCErrorNum(15-)/15ErrorNum前期的理论研究与试验论证工作的结果三种自组织映射算法均有很高的准确率，且随着文档数的增多，准确率变化的幅度也不是很大；K-means、层次聚类随文档数增多性能下降很快仅适用于中等规模的文档聚类 ；在三种自组织算法中VPSOM的准确率最高，由于只选取能够有效代表每个类别的特征构造神经元的特征集合，可以剔除无关特征对聚类结果的干扰，使得算法具有很高的准确率

36、；主要内容n课题来源及研究的目的和意义n国内外在该方向的研究现状及分析n前期的理论研究与试验论证工作的结果n学位论文的主要研究内容、实施方案及其可行性论证 n论文进度安排，预期达到的目标 n为完成课题已具备和所需的条件、外协计划及经费 n预计研究过程中可能遇到的困难、问题，以及解决的途径 学位论文的主要研究内容聚类特征选择：n特征选择是聚类算法的基础，好的聚类特征能够有效提高聚类结果的有效性，期望通过衡量特征对文档的区分能力并结合语义技术选择能够充分反映文本主题的特征作为聚类特征，使其能够有效降低特征空间的维度同时提高聚类算法的有效性。大规模文档聚类技术：n随着网络信息的剧增，如何能够更快更有

37、效的处理大规模的数据变得越来越重要。目前可以通过如下方法进行大规模文档的聚类：l通过特征选择算法以及空间变换思想对特征矩阵进行降维；l通过压缩类别的特征集合，仅选择能够有效区分各文档类的特征构造特征集合；l通过结合语义的相似度函数以及权值调整函数发现文档间的隐含语义相似性；学位论文的主要研究内容半监督聚类技术n传统聚类技术是不依靠输入数据的任何先验知识的，而现时生活中，用户对于输入数据可能会存在某些先验知识或限制条件，这样就必须对传统的聚类技术进行改变，使之能够适应用户对输入数据提供的某些先验知识，即半监督聚类。n进行半监督聚类可以采用以下两种方法：l改变聚类的搜索策略，使其搜索方式满足用户的

38、限制条件；l改变相似度计算方法，根据限制条件确定不同特征在相似度度量中的不同作用；聚类算法的应用n将聚类应用于搜索引擎中，对搜索引擎返回的信息进行聚类以提高用户的检索效率。主要内容n课题来源及研究的目的和意义n国内外在该方向的研究现状及分析n前期的理论研究与试验论证工作的结果n学位论文的主要研究内容、实施方案及其可行性论证 n论文进度安排，预期达到的目标 n为完成课题已具备和所需的条件、外协计划及经费 n预计研究过程中可能遇到的困难、问题，以及解决的途径 论文进度安排，预期达到的目标n论文进度安排：n2007.42007.7 查阅资料、熟悉聚类算法及其应用技术，确定研究内容；n2007.92008.3 实现基于分布及基于语义的特征抽取方法