基于邻域粗糙集的增量特征选择

第２１卷第１１期　计算机技术与发展　Ｖ０Ｉ．２１　Ｎｏ．１ｌ　２０１１年ｌ１月　ＣＯＭＰＵＴＥＲ　ＴＥＣＨＮ０ＬＯＧＹ　ＡＮＤ　ＤＥＶＥＬ（）ＰＭＥＮＴ　Ｎｏｖ．２Ｏ１ｌ　基于邻域粗糙集的增量特征选择　李楠　２，谢娟英　（１．陕西师范大学计算机科学学院，陕西西安７１００６２；　２．商洛学院计算机科学系，陕西商洛７２６０００）　摘要：ｆｆ对连续型属性的数据集，当有新样本加入时，可能引起最佳属性约简子集变化的问题。提出了基于邻域粗糙集　的特征子集增量式更新方法。根据新增样本对正域的影响，分情况对原数据集的属性约简子集进行动态更新，以便得到　增加样本后的新数据的最佳属性约简子集。这种对原约简集合进行的有选择的动态更新可以有效地避免重复操作，降低　算法复杂度，只有在最坏的情况下才需要对整个数据集进行重新约简。并以一个实例进行分析说明。实例分析表明，先　对新增样本进行分析，然后选择性对新数据集进行约简可以有效地避免重复操作，得到新数据集的最佳属性约简子集。　关键词：邻域粗糙集；增量式更新；特征选择；正域　中圈分类号：ＴＰ３０１．６　文献标识码：Ａ　文章编号：１６７３—６２９Ｘ（２０１１）１１—０１４９—０４　Ａ　Ｆｅａｔｕｒｅ　Ｓｕｂｓｅｔ　Ｓｅｌｅｃｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｎｅｉｇｈｂｏｒｈｏｏｄ　Ｒｏｕｇｈ　Ｓｅｔ　ｆｏｒ　Ｉｎｃｒｅｍｅｎｔａｌ　Ｕｐｄａｔｉｎｇ　Ｄａｔａｓｅｔｓ　ＬＩ　Ｎａｎ‘　。Ｘ１Ｅ　Ｊｕａｎ—ｙｉｎｇ　ｆ　１．Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ。Ｓｈａａｎｘｉ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ。Ｘｉ’ａｒｔ　７１００６２。Ｃｈｉｎａ；　２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ。Ｓｈａｎｇｌｕｏ　Ｃｏｌｌｅｇｅ。Ｓｈａｎｇｌｕｏ　７２６０００。Ｃｈｉｎａ）　ＡＩＮｔｒａｅｔ：Ａｆｅａｔｕｒｅ　ｓｕｂｓｅｔ　ｓｅｌｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍｉｓ　ｐｒｅｓｅｎｔｅｄｂａｓｅｄ　Ｏｎ　ｎｅｉｇｈｂｏｒｈｏｏｄ　ｒｏｕｇｈ　Ｓｅｔｔｈｅｏｒｙｆｏｒｔｈｅ　ｄａｔａｓｅｔｓｗｈｉｃｈ　ａｒｅ　ｕｐＩｈ伽ｂｙ　ｔｈｅｉｎｃｒｅｍｅｎｔｉｎｔｈｅｉｒ　ｓａｍｐｌｅｓ　Ｉｔｉｓｗｅｌｌ　ｋｎｏｗｎｔｈａｔｔｈｅｉｎｃｒｅｍｅｎｔｉｎ　ｓａｍｐｌｅｓ　ｃａｎ　ｃａｕＳｅｔｈｅ　ｃｈａｎｇｅａｂｌｅｉｎｔｈｅ　ｒｅｄｕｃｔｉｏｎ　ｏｆ　ａｔｔｒｉｂｕｔｓｅ　ｏｆ　ｔｈｅｉｔ．Ｄｉｄ　ａｍｒｏｎｇｈ－ｐａｃｅｄ　ａｎａｌｙｓｉｓｔＯｔｈｅ　ｖａｒｉｅｔｙ　ｏｎｐｏｓｉｉｔｖｅ　ｒｅｇｉｏｎ　ｂｒｏｕｇｈｔ　ｂｙｔｈｅ　ｎｅｗ　ａｄｄｅｄ　ｓａｍｐｌｅｔＯｔｈｅ　ｄａｔａｓｅｔ－ａｎｄ　ｄｉｓｃｕｓｓｅｄ　ｈｔｅＳｅｌｅｃｔｉｖｅ　ａｐｄ￣ｎｇｔＯｔｈｅｆｅａｔｕｒｅ　ｓｕｂＳｅｔ　ｌａＵｒｉｂｕ￣ｒｅｄｕｃｔｉｏｎ）ａｃｃｏｒｄｉｎｇｔｏ　ａｌｌｔｈｅ　ｃａｓｅｓ．ＴｈｅＳｅｌｅｃｔｉｖｅ　ｕｐｄａｔｉｎｇｔｏｔｈｅ　ｏｒｉｇｉ￣ｒｅｄｕｃ－　ｄｏｎ　ｏｆａｔｔｒｉｂｕｔｅｓ　ｏｆｔｈｅ　ｄａｔａｓｅｔ　ｏ８１１　ａｖｏｉｄ　ｔｈｅ　ｕｎｗａｎｔｅｄ　ｏｐｅｒａｔｉｏｎｓ．ａｎｄ　ｒｅｄｕｃｅ　ｔｈｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆｔｈｅ　ｆｅａｔｕｒｅ　ｓｕｂＳｅｔ　Ｓｅｌｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ．　Ｆｉｎａｌｌｙ。ｇａｖｅ　ａ　ｒｅａｌ　ｅｘａｍｐｌｅ　ａｎｄ　ｄｅｍｏｎｓｔｒａｔｅｄｔｈｅａｌｇｏｒｉｔｈｍ．　Ｉｃｅｓｗｏｒｄｓ：ｎｅｉｈｇｂｏｒｈｏｏｄ　ｒｏｕｇｈＳｅｔ；ｉｎｃｒｅｍｅｎｔａｌ　ｕｐｄａｔｉｎｇ；ｆａｅｔｕｒｅ　ｓｕｂＳｅｔＳｅｌｅｃｔｉｏｎ；ｐｏｓｉｔｉｖｅ　Ｏ引　言　究热点，是特征选择的主要方法之一　。而大量的　数据中的冗余和不相关数据不仅对发现和总结数　研究都仅适用于符号型数据。胡清华等人提出了邻域　据内在规律没有帮助，反而会影响对数据的学习，因　粗糙集的属性约简¨¨　】，能够有效地处理连续性数值　此，众多学者提出了大量的约简算法对数据进行约简。　型数据，避免基于粗糙集的属性约简所需要的数据离　粗糙集理论是一种有效处理不完整、不精确信息的数　散化对数据精确度的影响。　．　学分析工具，能有效地从大量的数据中发现潜在的规　然而，基于粗糙集理论的属性约简算法主要是针　律和隐含的信息…。自提出以来，便得到了广泛应　对确定的数据集合进行。现实问题的不确定性，数据　用　。　集合的属性或样本有可能会动态地增加，这就需要对　近年来，粗糙集理论成为数据挖掘领域的一个研　增量式的数据集进行约简。每增加一个属性或样本都　重新计算新数据集合的约简是非常费时的，并且没有　收稿日期：２０ｌｌＪｏ４—０５；修回日期：２０ｌ１—０７－１０　充分利用已有的信息，故而出现了增量式的属性约简　基金项目：中央高校基本科研业务费专项资金重点项目（ＧＫ２００９　ｏｔｏｏ６）；陕西省自然科学基础研究计划项目（２０１０ＪＭ３００４）；中央高　算法研究　。　校基本科研业务费专项资金项目（ＧＫ２０１００１００３）　在邻域粗糙集的基础上，文中详细分析了样本增　作者简介：李楠（１９８１一）。女，陕西澄城人，硕士研究生，研究方向　加对原数据集和约简数据集正域的影响，提出了基于　为机器学习、计算智能、模式识别与数据挖掘；谢娟英，副教授，硕士　邻域粗糙集的增量式属性约简方法，有效地减少了重　生导师，研究方向为机器学习、计算智能、模式识别与数据挖掘。　复工作，提高了属性约简的效率。　・１５０・　计算机技术与发展　第２１卷　１邻域粗糙集相关概念　对于连续型的数值数据，通过计算样本间的距离　来判断其相似程度，判断样本间的近邻关系。信息系　统ＩＳ＝＜Ｕ，Ａ＞中，　为样本集合，也称为论域｛　，　…，，　｝，Ａ为属性集合，也称为特征集合｛ｏ　，ｏ　，　…，ｏ　｝，用来描述每一个样本的特征信息。信息系统　ＩＳ＝＜Ｕ，Ｃ　ｕ　Ｄ＞，称为一个决策系统，其中ｃ是条件　属性集合，Ｄ表示决策属性集合。　任意样本Ｖ　∈Ｕ，属性子集　Ｃ，以及给定的　邻域半径６，　的曰邻域表示为：　６口（　‘）＝｛　ｌｘｊ∈Ｕ，△　（　ｉ，　ｆ）≤６｝　（１）　的　邻域也就是在属性子集曰所确定的空间　中，与样本　之间距离小于指定邻域半径６的所有样　本构成的集合。　文中计算样本间距离△　（　，　，）的公式为：　△（　）　。　）一ｆ（ＸＩ，Ⅱ　）ｌ　（２　如果ａ（ｘ　，　，）≤６，则表示样本　与　互为近邻，　否则，不为近邻。　对于指定的样本子集　ｕ，在属性子集曰中的　上、下近似可定义为：　ＢＸ＝　（　）　Ｘ，　∈Ｕ｝　（３）　ＢＸ＝｛　Ｉ　６　（　）ｎ　Ｘ≠　，　∈Ｕ｝　（４）　对于给定的邻域决策系统ＮＤＴ＝（Ｕ，Ｃ　ｕ　Ｄ），若　ｘ　，　，…，　是由决策属性所确定的划分，对于属性　子集曰　ｃ，决策Ｄ关于属性子集曰的上、下近似定义　为：　ＢＤ＝ｕ　：。ＢＸｉ　（５）　ＢＤ＝ｕ：：ｌＢＸ　（６）　决策表的下近似也称为决策表的正域：　ＰＯＳＢ（Ｄ）＝ＢＤ　（７）　属性子集确定的正域反映了决策对该子集的依赖　程度，决策Ｄ对属性子集Ｂ的依赖度可表示为：　（８）　依赖度越大说明子集　对决策Ｄ的贡献越大。　如果．ｙ　（Ｄ）＝’，　（Ｄ），则说明属性集合　和ｃ具有相　同的分类能力。如果　中没有冗余的属性，也就是　Ｖ８∈Ｂ，　（Ｄ）＞ｙ　（Ｄ）．说明　是ｃ关于Ｄ的一个　相对约简。　２基于邻域粗糙集的特征选择算法　基于邻域粗糙集的特征选择方法，通过反复迭代，　每次迭代加入能使正域势最大的属性到属性约简集　合，直到正域不再变化，以此来确定数据集合的一个约　简。流程如图１所示。　图１　邻域粗糙集特征选择流程　３基于邻域粗糙集的增量式属性约简算法　数据集的变化包括属性的变化和样本的变化，文　中主要讨论当样本增加时，如何利用原数据集的约简　信息，计算更新后数据集的约简，避免样本增加时，完　全重新计算。　计算约简的关键步骤是计算正域。因此，可以通　过新增样本对正域的影响来判断其对约简的影响，进　一步更新原数据集的约简子集，得到更新后数据集的　约简子集。　对于同样的距离函数△和邻域半径６，邻域决策　系统＜Ｕ，Ｃ　ｕ　Ｄ＞，Ｂ　Ｃ，可以证明＆（　）　（　）。　当数据集新增样本时，讨论该样本对条件属性全集的　正域和约简属性子集的正域影响来确定是否需要重新　计算数据集的约筒子集。　’　假设曰是Ｃ的一个相对约简，　为新增样本。为了　描述方便，下文中用ＰＤ　（Ｄ）表示属性子集　关于决　策Ｄ在论域　中产生的正域。　１．如果　（　）中的所有样本与样本　同类别，则　必有＆（　）中的所有样本与样本　同类别。因此有　ＩＰＯＳＶｓ“（Ｄ）｛＝ｌＰＯＳＶＢ（Ｄ）１＋１＝ＩＰ０ｓ　（Ｄ）ｌ＋１　＝Ｉ　ＰＯＳＶｃ“（Ｄ）ｌ　属性全集与约简属性集合所确定的正域同时增加　一个，因此原约简仍然可能是属性全集的一个约简，只　需要做反向删除即可。　２．如果　（　）中的所有样本与样本　不同类别，　则必有＆（　）中的所有样本与样本　不同类别。　２．１如果６　（　）ｎ　ＰＯＳＯ￣（Ｄ）＝　，则必有６　（　）ｎ　ＰＯＳｖ（Ｄ）＝　因此有　　ｌＰ０ｓ　（Ｄ）Ｉ＝Ｉ　Ｐ０ｓ　（Ｄ）ｌ　第ｌｌ期　李楠等：基于邻域粗糙集的增量特征选择　・１５１・　：ＪＰＯＳＶｃ（Ｄ）ｆ＝ＪＰＯＳｖ”（Ｄ）Ｊ　简曰与全集Ｃ没有相同的正域集合。需要重新计算约　正域未发生变化，因此原约简仍然可能是属性全　简。　集的一个约简。　３．３　６　（　）中的所有样本与样本　部分同类别，找　２．２如果　（　）ｎ　ＰＤｓ　（Ｄ）≠　，则计算　邻域中　到与　不同类别并且属于正域ＰＤｓ　（Ｄ）的样本个数　正域样本的个数　。　Ｎ　ｏ　Ｍ＝Ｉ　（　）ｎ　ＰＤｓ　（Ｄ）Ｉ　３．３．１如果Ｍ＝Ｎ，则　仍然可能是属性全集的一　２．２．：Ｉ如果艿。（　）ｎ　ＰＤｓ　（Ｄ。）＝　，则有：　个约简。　ＪＰＯＳＶＢ“（Ｄ）ｆ：ｆＰＯＳ￣（Ｄ）『一　，　』尸０ｓ　”（Ｄ）Ｉ＝　３．３．２如果　≠Ⅳ，增加样本后，约简　与全集Ｃ　ＩＰＯＳ￣（Ｄ）』，增加样本　后正域发生了变化，需要重　没有相同的正域集合。需要重新计算约简。　新计算约简。　２．２．２如果６。（　）ｎ　ＰＯＳ￣（Ｄ）≠　，计算　邻域中　４实例分析　正域样本的个数Ⅳ。　表１为包含６个样本的数值型属性的决策系统，　Ｎ＝ｌ＆（　）ｎ　ＰＯＳ￣（Ｄ）Ｉ　’　论域Ｕ＝｛　，ｘ：，…，　｝，条件属性集Ｃ＝｛ａ，ｂ，ｃ，ｄ，ｅ，　２．２．２．１如果Ｍ＝Ｎ，则Ｉ　ＰＯＳＶＢ“（Ｄ）ｆ＝　，决策属性子集Ｄ＝｛ｇ｝。　Ｉ　ＰＤｓ　（Ｄ）Ｉ一　＝ｆＰＯＳＶｃ（Ｄ）ｆ一Ⅳ：ＪＰＯＳｖ“（Ｄ）Ｉ因　由ａ（ｘ　，　）＝∑ｆＡｘ　，ａｋ）一ｆ（ｘｊ，ａｋ）Ｉ计算样本　此，　仍然可能是属性全集的一个约简。　间距离，构造临时决策系统（Ｕ，｛ａ，ｇ｝），（Ｕ，｛ｂ，ｇ｝），　２．２．２．２如果Ｍ≠Ｎ，则Ｉ　ＰＤｓ　（Ｄ）ｌ＝　…，（Ｕ，｛ｆ，ｇ｝）。分别计算各临时决策系统的正域样　ｌ　ＰＤｓ　（Ｄ）Ｉ—Ｍ≠ｌ　ＰＯＳＵｃ（Ｄ）ｌ—Ｎ＝ｌ　ＰＯＳＵｃ　（Ｄ）Ｉ　本。以表２所示的一个临时决策信息系统１为例，设　那么增加样本后，约简Ｂ与全集ｃ没有相同的正域。　定邻域半径艿＝０．３得到相应的邻域样本如表３所示。　需要重新计算约简。　表２临时决策系统１　３．如果　（　）中的部分样本与样本　同类别，找　到与　不同类别并且属于正域ＰＤ５　（Ｄ）的样本个数　，则有：　ＩＰ０Ｊｓ　（Ｄ）Ｉ＝『ＰＯＳ￣（Ｄ）ｌ＿　３．１＆（　）中的所有样本与样本　同类别，　ＩＰＤ．ｓ　（Ｄ）Ｉ＝ＩＰＤｓ　（Ｄ）ｌ＋１。增加样本后，约简的　正域与属性全集的正域不同，需要重新计算约简。　３．２　（　）中的所有样本与样本　不同类别。计　算　邻域中正域样本的个数Ⅳ。　表３　临时决策系统１对应邻域　Ｎ＝ｌ＆（　）ｎ　ＰＯＳＶｃ（Ｄ）Ｉ，　ｆＰ０．ｓ　“（Ｄ）ｆ＝ｆＰＤｓ　（Ｄ）Ｉ一Ⅳ　３．２．１如果Ｍ＝Ｎ，　则Ｉ　ＰＯＳＶＢ”（Ｄ）』＝　Ｊ　ＰＤＪｓ　（Ｄ）Ｉ—Ｍ：『ＰＯＳ￣（Ｄ）Ｉ—Ｎ＝Ｉ　ＰＤｓ　“（Ｄ）Ｉ，Ｂ　仍然可能是属性全集的一个约简。　３．２．２如果Ｍ≠Ｎ，１ＰＤＪｓ　（Ｄ）ｌ＝Ｉ尸ｏｓ　（Ｄ）Ｉ＿　Ｍ≠Ｉ　Ｐｏｓ　（Ｄ）１．Ｎ＝ｌ　Ｐ０ｓ　（Ｄ）ｌ，增加样本后，约　表１数值型决策系统　・１５２・　计算机技术与发展　第２ｌ卷　由临时决策系统（Ｕ，｛ａ，ｇ｝）所产生的正域样本　当在数据集中加入样本　，为｛０．８１８５，０．８１１３，０．　为｛　。，　｝。同理，由临时决策系统（Ｕ，｛ｂ，ｇ｝）所产　生的正域样本为｛　）；（Ｕ，｛ｃ，ｇ｝）所产生的正域样　本为｛ｘ４）；（Ｕ，｛ｄ，ｇ｝）所产生的正域样本为｛　）；　（Ｕ，｛ｅ，ｇ｝）所产生的正域样本为｛ｚ。）；（Ｕ，｛ｆ，ｇ｝）　所产生的正域样本为｛　：，　｝。选择正域样本集势最　大的属性Ⅱ加入约简集合，即ｒｅｄ＝｛Ⅱ｝。　再产生新的临时决策系统（Ｕ，ｒｅｄ　Ｕ｛ｂ｝ｕ｛ｇ｝），　２９６５，０．１０５７，０．１２０９，０．２０１１，３｝。通过计算可知，在　增加样本后的（　，｛口，ｃ｝ｕ｛ｇ｝）中，新增样本的邻域　为｛　，　，｝，并且样本与其邻域的类别不同，可得结　论：新增样本在约简数据集中不是正域样本，而在属性　全集中为正域样本，正域变化不同步，需要重新计算约　简。通过计算，得到加入该样本后属性全集的约简集　合变化为｛ｏ，ｅ｝。　通过以上分析可知，当数据集为一致性时，只需要　（Ｕ，ｒｅｄ　Ｕ｛ｃ｝ｕ｛ｇ｝），…，（Ｕ，ｒｅｄ　ｕ｛ｆ｝Ｕ｛ｇ｝），计　算各临时决策系统在剩余样本中的正域。以临时决策　信息系统（Ｕ，ｒｅｄ　ｕ｛ｃ｝ｕ｛ｇ｝）为例，形成临时决策　系统，见表４，并产生相应的邻域样本如表５所示。　表４临时决策系统２　表５临时决策系统２对应邻域　由临时决策系统（Ｕ，ｒｅｄ　ｕ｛ｃ｝ｕ｛ｇ｝）在剩余　样本｛　。，　，　，　｝中所产生的正域样本为｛　，　，　，　‰｝。同理，由临时决策系统（Ｕ，ｒｅｄ　Ｕ｛ｂ｝ｕ｛ｇ｝）所　产生的正域样本为｛　，　】．，也可计算（Ｕ，ｒｅｄ　Ｕ｛ｄ｝　ｕ｛ｇ｝），（Ｕ，ｒｅｄ　Ｕ｛ｆ｝Ｕ｛ｇ｝）所产生的正域样本，　选择产生正域样本最多的属性ｃ加入约简集合，即ｒｅｄ　＝ｒｅｄ　Ｕ｛ｃ｝＝｛ｎ，Ｃ｝。此时，约简集合所确定的正域　集合为样本全集，与属性全集所确定的正域集合相同，　得到数据集的一个约简｛ｏ，ｃ｝。　当在数据集中加入新样本时，根据新加入样本的　特点，更新原数据集合的约简。例如，加入样本　，为　｛０．２９７４，０．５６６０，０．３６２８，０．６９１１，０．３６２６，０．１５４８，２｝，　即Ｕ：Ｕ　Ｕ｛　，｝。首先判断该样本是否属于信息系统　（Ｕ，｛ａ，ｃ｝ｕ｛ｇ｝）的正域。通过计算可知，在（　，　｝ａ，ｃ｝ｕ｝ｇ｝）中，新增样本的邻域为｛　，‰，　｝，并　且所有邻域的类别相同，由此可见，新增样本在约简信　息系统中为正域样本，在属性全集确定的信息系统中　也为正域样本，正域同时增加相同数目，约简保持不　变，仍然为｛口，ｃ｝。　判断新增样本在约简中是否为正域，即可判断是否需　要重新计算约简。而在不一致的数据集中，情况相对　复杂，决策属性相对于条件属性全集的正域不等于全　体样本构成的集合，则需要根据第３部分所列的各种　情况进行详细分析。　５结束语　在邻域粗糙集的基础上，深入讨论增量式数据集　的约简计算方法。结合数值型数据集的特点，根据约　简与正域问的关系，提出根据新增样本对属性全集和　约简集正域的影响，判断约简是否需要更新，从而对增　量式数据集计算新增样本后的数据集约简的算法。该　算法避免了每增加一个样本就重新对数据集进行一次　约简计算。这种选择性的重新计算约简的思想避免了　大量的重复计算，提高了增量式数据集的属性约简效　率。　参考文献：　［１］Ｐａｗｌａｋ　ｚ．Ｒｏｕｇｈ　ｓｅｔｓ：ｔｈｅｏｒｅｔｉｃａｌ　ａｓｐｅｃｔｓ　ｏｆ　ｒｅａｓｏｎｉｎｇ　ａｂｏｕｔ　ｄａｔａ［Ｍ］．［ｓ．Ｉ．］：Ｋｌｕｗｅｒ　Ａｃａｄｅｍｉｃ　Ｐｕｂｌｉｓｈｅｒｓ，１９９１．　［２］　毛国君，段立娟，王实，等．数据挖掘概念与技术［Ｍ］．北　京：机械工业出版社，２０００．　［３］边肇祺，张学工．模式识别［Ｍ］．第２版．北京：清华大学出　版社，１９９８．　［４３　Ｍｏｄｒｚｅｊｅｗｓｂ　Ｍ．Ｆｅａｔｕｒｅ　ｓｅｌｅｃｉｔｏｎ璐ｉｎｇ　ｒｏｕｇｈ　ｓｃｔｓ　ｔｈｅｏｒｙ　［ｃ］／／ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｅｕｒｏｐｅａｎ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａ—　ｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ．Ｌｏｎｄｏｎ，ＵＫ：Ｓｐｒｉｎｇｅｒ－ｖｅｒｌａｇ，１９９３：２１３—　２２６．　［５］ＣｈａｒｔＣＣ．Ａ　ｒｏｕｇｈ　ｓｅｔ　ａｐｐｒｏａｃｈｔＯ　ａｔｔｒｉｂｕｔｅ　ｇｅｎｅｒａｌｉｚａｉｔｏｎｉｎ　ｄａｔａ　ｍｉｎｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｃｉｅｎｃｅｓ，１９９８，１０７：　１６９—１７６．　［６］苗夺谦，胡桂荣．知识约简的一种启发式算法［Ｊ］．计算机　研究与发展，１９９９，３６（６）：６８１—６８４．　［７］　王国胤，于洪，杨大春．基于条件信息熵的决策表约简　［Ｊ］．计算机学报，２００２，２５（７）：７５９—７６７．　［８］谢娟英，谢维信，高薪波．基于树结构的属性约简方法　［ｃ］／／模糊逻辑与计算智能研究进展（上册），中国模糊逻　辑与计算智能联合学术会议论文集．合肥：中国科学技术　（下转第１５５页）　第１１期　宋毅等：个性化搜索中的用户兴趣模型研究　・１５５・　＝　，Ｉｃ∑ｃｏｏｃ（ｑ，ｑ“　式中　——查询在文档中的权重；　（４）　、　［２］　张炜．个性化推荐系统中基于本体的用户兴趣挖掘研究　［Ｄ］．南京：南京理工大学，２００７．　［３］　Ｃｌａｙｐｏｏｌ　Ｍ，Ｌｅ　Ｐ，Ｗａｓｅｄａ　Ｍ，ｅｔ　１ａ．Ｉｍｐｌｉｃｉｔ，ｉｎｔｅｒｅｓｔ　ｉｎｄｉｃａｔｏｒｓ　［Ｃ］／／Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｕｓｅｒ　Ｉｎｔｅｒｆａｃｅｓ．［ｓ．Ｌ］：　［Ｓ．ｎ．］，２００１：３０—４０．　［４］　Ｑｉｕ　Ｆｅｎｇ，Ｃｈｏ　Ｊ．Ａｕｔｏｍａｔｉｃ　Ｉｄｅｎｔｉｉｆｃａｔｉｏｎ　ｏｆ　Ｕｓｅｒ　Ｉｎｔｅｒｅｓｔ　Ｆｏｒ　ＣＯＯＣ（ｇ，ｑ　）——查询ｑ扩展ｑ　的可信度。　经过查询扩展技术，将扩展库中的扩展词放入用　户模型中重新计算用户兴趣类别偏好，得到实验结果　见图３。　Ｐｅｒｓｏｎａｌｉｚｅｄ　Ｓｅａｒｃｈ［Ｃ］／／Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ　Ｃｏｎｆｅｒｅｎｃｅ　Ｃｏｍｍｉｔｔｅｅ．Ｅｄｉｎｂｕｔｈ，Ｓｃｏｔｌａｎｄ：ＡＣＭ，２００６：２３—　２６．　［５］Ｃｈｅｎ　Ｌ，Ｓｙｃａｒａ　Ｋ．Ｗｅｂｍａｔｅ：ａ　ｐｅｒｓｏｎａｌ　ａｇｅｎｔ　ｆｏｒ　ｂｒｏｗｓｉｎｇ　ｎｄ　ａｓｅａｒｃｈｉｎｇ［Ｃ］／／Ｐｒｏｃ．２ｎｄ　Ｉｎｔ．Ｃｏｎｆ．ｏｎ　Ａｕｔｏｎｏｍｏｕｓ　Ａｇｅｎｔｓ　ａｎｄ　Ｍｕｈｉａｇｅｕｔ　Ｓｙｓｔｅｍｓ．［ｓ．１．］：［ｓ．ｎ．］，１９９８：１３２－１３９．　［６］Ｐｒｅｔｓｃｈｎｅｒ　Ａ，Ｇａｕｃｈ　Ｓ．Ｏｎｔｏｌｏｇｙ　ｂａｓｅｄ　ｐｅｒｓｏｎａｌｉｚｅｄ　ｓｅａｒｃｈ　［Ｃ］／／ＩＣＴＡＩ．［ｓ．１．］：［ｓ．ｎ．］，１９９９：３９１—３９８．　［７］　Ｓｕｇｉｙａｍａ　Ｋ，Ｈａｔａｎｏ　Ｋ，Ｙｏｓｈｉｋａｗａ　Ｍ．Ａｄａｐｔｉｖｅ　ｗｅｂ　ｓｅａｒｃｈ　ｂａｓｅｄ　ｏｎ　ｕｓｅｒ　ｐｒｏｆｉｌｅ　ｃｏｎｓｔｒｕｃｔｅｄ　ｗｉｔｈｏｕｔ　ａｎｙ　ｅｆｆｏｒｔ　ｆｒｏｍ　ＵＳｅｒｓ　［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｔｈｉｔｒｅｅｎｔｈ　Ｉｎｔ　Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ　Ｃｏｎｆ．［Ｓ．１．］：［ｓ．ｎ．］，２００４：５－８．　［８］郭岩，白硕．网络规模１３志分析和用户兴趣挖掘［Ｊ］．　计算机学报，２００５，２８（９）：１—３．　［９］　彭彬彬，金翔宇，徐晓刚，等．基于ｓｖｍ增量学习的用户适　应性研究［Ｊ］．计算机科学，２００３（３０）：７５—７６．　图３　扩展后兴趣类别偏好　［１０］李村合，杨献峰，张培颖．基于ｗｅｂ挖掘与相关反馈的多层　经过查询扩展后有效识别了用户兴趣类别偏好。　次用户兴趣挖掘算法［Ｊ］．微计算机应用，２００７，２８（９）：１—　２．［１１］ＳａｌｔｏｎＧ，Ｂｕｃｋｌｅｙ　Ｃ．Ｉｍｐｒｏｖｉｎｇ　ｒｅｔｒｉｅｖａｌｐｅｒｆｏｍｒａｎｃｅ　ｂｙ　ｒｅｔｉｒｅｖａｌ　ｆｅｅｄｂａｃｋ［Ｊ　Ｊ。Ｊｏｕｒｎａｌ　ｏｆｔｈｅ　Ａｍｅｒｉｃｎａ　Ｓｏｃｉｅｔｙ　ｆｏｒ　４结束语　Ｉｆｎｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ，１９９０（４）：２８８—２９７．　研究并且挖掘偏好建模，Ｍ＝［Ｑ，Ｃ，Ｒ（ｑ　，ｃｊ），　，　［１２］Ｌｉｕ　Ｆａｎ，Ｙｕ　Ｃ，ＭｅｎｇＷｅｉｙｉ．ＰｅｒｓｏｎａｌｉｚｅｄＷｅｂＳｅａｒｃｈ　ｂｙＭａｐ－　Ｄ］，实现了挖掘技术，在实现用户兴趣模型中，用户兴　ｐｉｎｇ　Ｕｓｅｒ　Ｑｕｅｒｉｅｓ　ｔｏ　Ｃａｔｅｇｏｒｉｅｓ［Ｃ］／／Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｆｎｏｒｍａ－　趣模型特点是：通过挖掘用户相关信息，每天用户行为　ｔｉｏｎ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｍａｎａｇｅｍｅｎｔ．Ｍｃｌｅａｎ，Ｖｉｒｇｉｎｉａ，ＵＳＡ：　内容发现用户的特点。对于兼类查询问题处理效果良　ＡＣＭ，２００２：４－９．　好，具有很好的扩展性。当然，该方法有不足之处，随　［１３］曾春，邢春晓，周立柱．个性化服务技术综述［Ｊ］．软件学　报，２００２（１３）：１９５３—１９５５．　着时间变化，用户兴趣也会变化。这就要求用户兴趣　［１４］陈媛，苟光磊．个性化服务用户模型研究［Ｊ］．计算机工　模型需要学习和更新　。　程设计，２００８，２９（９）：２４１３—２４１６．　［１５］岳文，陈治平，林亚平．基于查询扩展和分类的信息检索　参考文献：　算法［Ｊ］．系统仿真，２００６，１８（９）：１９２６—１９２９．　［１］　Ｆｒａｇｏｕｄｉｓ　Ｄ．Ｕｓｅｒ　Ｍｏｄｅｌｉｎｇ　ｉｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｄｉｓｃｏｖｅｒｙ：Ａｎ　Ｏ—　［１６］费洪晓，穆王君，刘正．基于文本聚类和权重调整的用户　ｖｅｒｖｉｅｗ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ａｄｖａｎｃｅｄ　Ｃｏｕｒｓｅ　ｏｎ　Ａｒｔｉｉｆｃｉａｌ　兴趣建模算法［Ｊ］．计算机技术与发展，２００７，１７（２）：１２８一　Ｉｎｔｅｌｌｉｇｅｎｃｅ．［ｓ．１．］：［Ｓ．ｎ．］，１９９９：１７－４３．　ｌ２９．　（上接第１５２页）　大学出版社，２００５：３６０—３６４．　ｅｎｃｅｓ，２００８，１７８：３５７７—３５９４．　［９］Ｂｈａｔｔ　Ｒ　Ｂ，Ｇｏｐａｌ　Ｍ．Ｏｎ　ｆｕｚｚｙ－ｒｏｕｇｈ　ｓｅｔｓ　ａｐｐｒｏａｃｈ　ｔｏ　ｆｅａｔｕｒｅ　［１２］Ｈｕ　Ｑ　Ｈ，Ｙｕ　Ｄ　Ｒ，Ｘｉｅ　Ｚ　Ｘ．Ｎｅｉｇｈｂｏｒｈｏｏｄ　ｃｌａｓｓｆｉｅｒｓ［Ｊ］．Ｅｘ－　ｓｅｌｅｃｔｉｏｎ［Ｊ］．Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ　Ｌｅｔｔｅｓｒ，２００５，２６：９６５－９７５．　ｐｅｒｔ　Ｓｙｓｔｅｍｓ　ｗｉｔｈ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００８，３４：８６６－８７６．　［１０］Ｈｕ　Ｑ　Ｈ，Ｐｅｄｒｙｃｚ　Ｗ，Ｙｕ　Ｄ　Ｒ，ｅｔ　ａ１．Ｓｅｌｅｃｔｉｎｇ　Ｄｉｓｃｒｅｔｅ　ａｎｄ　［１３］刘宗田．属性最小约简的增量式算法［Ｊ］．电子学报，１９９９，　Ｃｏｎｔｉｎｕｏｕｓ　Ｆｅａｔｕｒｅｓ　Ｂａｓｅｄ　ｏｎ　Ｎｅｉｇｈｂｏｒｈｏｏｄ　Ｄｅｃｉｓｉｏｎ　Ｅｒｒｏｒ　２７（１１）：９６－９８．　Ｍｉｎｉｍｉｚａｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｓｙｓｔｅｍｓ，Ｍａｎ，ａｎｄ　［１４］林俊伟，叶东毅．基于邻域辨识矩阵的属性约简增量式算　Ｃｙｂｅｎｒｅｔｉｃｓ－Ｐａｒｔ　Ｂ：Ｃｙｂｅｎｒｅｔｉｃｓ，２０１０，４０（１）：１３７－１５０．　法［Ｊ］．计算机应用，２００９，２９（６）：１１９—１２１．　［１１］Ｈｕ　Ｑ　Ｈ，Ｙｕ　Ｄ　Ｒ，ｕｕ　Ｊ　Ｆ，ｅｔ　１ａ．Ｎｅｉｇｈｂｏｒｈｏｏｄ　ｏｒｕｇｈ　ｓｅｔ　ｂａｓｅｄ　［１５］夏富春，苗夺谦，李道国．信息系统属性增量约简算法的设　ｈｅｔｅｏｒｇｅｎｅｏｕｓ　ｆｅａｔｕｒｅ　ｓｕｂｓｅｔ　ｓｅｌｅｃｔｉｏｎ［Ｊ］．Ｉｆｎｏｒｍａｔｉｏｎ　Ｓｃｉ—　计与实现［Ｊ］．计算机工程与应用，２００６，２１：１４９—１５２．