第 ４５卷 第 ３期
２００９年 ５月
南 京 大 学学 报 （自然 科 学 ）
ＪＯＵＲＮＡＬ ＯＦ ＮＡＮＪＩＮＧ ＵＮＩＶＥＲＳＩＴＹ
（ＮＡＴＵ ＲＡＬ ＳＣＩＥＮ ＣＥＳ）
Ｖ ｏ１．４５，Ｎｏ．３
Ｍ ａｙ，２００９
Ｄｅｓｉｇｎ ａｎｄ ｓｉｍ ｕｌａｔｉｏｎ ｏｆ ａ ｄｏｃｕｍ ｅｎｔ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ
ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ
Ｗ ｅｉ Ｊｉａｎ—Ｘｉａｎｇ ’ ．Ｌｉｕ Ｈ ｕａｉ。．Ｓｕ Ｘｉｎ—Ｎ ｉｎｇ
（１．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｍａｎａｇｅｍｅｎｔ，Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，２１００９６，Ｃｈｉｎａ）
（２．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ，Ｎａｎｊｉｎｇ Ｃｏｌｌｅｇｅ ｆｏｒ Ｐｏｐｕｌａｔｉｏｎ Ｐｒｏｇｒａｍｍｅ Ｍａｎａｇｅｍｅｎｔ，２１００４２，Ｃｈｉｎａ）
（３．Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｉｃａｌ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎａｎｊｉｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，２１００４２。Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ： Ａｍｏｎｇ ｖａｒｉｏｕｓ ｄｏｃｕｍｅｎｔ ａｌｇｏｒｉｔｈｍｓ，Ｋ—ｍｅａｎｓ ｉｓ ａ ｃｌａｓｓｉｃａｌ ｏｎｅ． Ｈｏｗｅｖｅｒ ｉｔ ｉｓ ａ ｇｒｅｅｄｙ
ａｌｇｏｒｉｔｈｍ ， ｗｈｉｃｈ ｉｓ ｓｅｎｓｉｔｉｖｅ ｔｏ ｔｈｅ ｃｈｏｉｃｅ ｏｆ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒ ａｎｄ ｉｓ ｍｕｃｈ ｅａｓｉｅｒ ｔｏ ｒｅｓｕｌｔ ｉｎ ｌｏｃａｌ
ｏｐｔｉｍ ｉｚａｔｉｏｎ．Ａ ｓ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ （ＧＡ）ｉｓ ａ ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｂｅｓｔ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒ ｃａｎ
ｂｅ ｆｏｕｎｄ ｅａｓｉｌｙ，ａ ｎｅｗ ｄｙｎａｍ ｉｃ ｄｏｃｕｍｅｎｔ ｃｌｕｓｔｅｒｉｎｇ ｍ ｅｔｈｏｄ ｂａｓｅｄ ｏｎ ＧＡ ｉｓ ｐｒｅｓｅｎｔｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．
Ｒｅｖｉｅｗｉｎｇ ａｌｌ ｋｉｎｄｓ ｏｆ ｔｒａｄｉｔｉｏｎａｌ ｄｏｃｕｍ ｅｎｔ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄｓ，ｔｈｅ ｐａｒｔｉａｌ ｓｉｍ ｉｌａｒｉｔｙ ｏｆ ｋｅｙｗｏｒｄｓ ｗａｓ
ｎｏｔ ｔａｋｅｎ ｉｎｔｏ ａｃｃｏｕｎｔ，ＳＯ ｔｈｅ ｄｏｃｕｍｅｎｔ ｓｉｍｉｌａｒ ｍａｔｒｉｘ ｉｓ ａ ｓｐａｒｓｅ ｍａｔｒｉｘ．Ｔｏ ｓｏｍｅ ｅｘｔｅｎｔ，ｔｈｅ ａｃｃｕｒａｃｙ
ｏｆ ｄｏｃｕｍｅｎｔ ｓｉｍｉｌａｒｉｔｙ ｉｓ ｉｎｆｌｕｅｎｃｅｄ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｓｏｍｅ ｎｅｗ ｆｏｒｍｕｌａｓ ａｒｅ ｇｉｖｅｎ ｗｈｉｃｈ ａｒｅ ｉｍｐｒｏｖｅｄ
ｂａｓｅｄ ｏｎ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｍｅｔｈｏｄ．Ｔｈｅ ｆｏｒｍ ｕｌａｓ ｔａｋｅ ｔｈｅ ｐａｒｔｉａｌ ｓｉｍｉｌａｒｉｔｙ ｏｆ ｋｅｙｗｏｒｄｓ ｉｎｔｏ ａｃｃｏｕｎｔ，ｔｈｕｓ
ｉｍ ｐｒｏｖｉｎｇ ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｏｆ ｓｉｍ ｉｌａｒｉｔｙ． Ｉｎ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ， ｔｈｅ ｓｉｎｇｌｅ ｉｎｄｉｖｉｄｕａｌ ｉｓ
ｐｒｅｓｅｎｔｅｄ ｂｙ ａ ｍａｔｒｉｘ ｗｈｉｃｈ ｃｏｎｓｉｓｔｓ ｏｆ Ｋ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ．Ａｌｌ ｉｎｄｉｖｉｄｕａｌｓ ａｒｅ ｅｎｃｏｄｅｄ ｂｙ ｆｌｏａｔｉｎｇ—ｐｏｉｎｔ
ｎｕｍｂｅｒｓ． Ｔｈｅ ｒｅｃｉｐｒｏｃａｌ ｏｆ ｔｈｅ ｓｕｍ ｏｆ ｍｅａｎ ｓｑｕａｒｅ ｄｅｖｉａｔｉｏｎ ｏｆ ｉｎｔｒａ ｃｌａｓｓ ｄｉｓｔａｎｃｅ ｐｌｕｓ ｏｎｅ ｉｓ ａｄｏｐｔｅｄ ａｓ
ｔｈｅ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ． Ｔｈｅ ｓｍａｌｌｅｒ ｔｈｅ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ，ｔｈｅ ｌｉｔｔｌｅｒ ｐｒｏｂａｂｉｌｉｔｙ ｔｈａｔ ｔｈｅ ｉｎｄｉｖｉｄｕａｌ ｃａｎ ｂｅ
ｓｅｌｅｃｔｅｄ ｔｏ ｅｎｔｅｒ ｔｈｅ ｎｅｘｔ ｇｅｎｅｒａｔｉｏｎ．Ｔｈｅ ｏｐｔｉｍａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒ ｉｓ ｆｉｎａｌｌｙ ｆｏｕｎｄ ｂｙ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｉｔｅｒａｔｉｏｎ
ｐｒｏｃｅｓｓ：ｓｅｌｅｃｔｉｏｎ，ｃｒｏｓｓｏｖｅｒ，ｍｕｔａｔｉｏｎ ａｎｄ ＳＯ ｏｎ．Ｔｈｅ ｓｉｍ ｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｔｈｉｓ
ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｃａｎ ｒｅａｃｈ ｏｖｅｒ ９８ ｐｅｒｃｅｎｔ ａｎｄ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｓｕｐｅｒｉｏｒ ｔｏ Ｋ—ｍｅａｎｓ ｉｎ ｐｅｒｆｏｒｍａｎｃｅ． Ｔｈｕｓ，
ｔｈｅ ａｌｇｏｒｉｔｈｍ ｏｆ ｔｈｉｓ ｐａｐｅｒ ｉｓ ａｎ ｅｆｆｅｃｔｉｖｅ ｍｅｔｈｏｄ ｏｆ ｄｏｃｕｍｅｎｔ ｃｌｕｓｔｅｒｉｎｇ．
Ｋｅｙ ｗｏｒｄｓ： ｄｏｃｕｍ ｅｎｔ ｃｌｕｓｔｅｒｉｎｇ，ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ，ｓｉｍｉｌａｒｉｔｙ，ｃｌｕｓｔｅｒ ｃｅｎｔｅｒ
基 于 遗传 算 法 的 文档 聚 类算 法 的设 计 与 仿 真
魏 建 香 ，刘 怀。，苏 新 宁
（１．南 京 大学 信 息 管 理系 ，南 京 ，２１００９３）
（２．南 京人 口管 理 干 部 学 院 信 息 科 学 系 ，南 京 ，２１００４２）
（３．南京师范大学电气与 自动化工程学 院，南京 ，２１００４２）
摘 要 ： 在 各 种 聚类 算 法 中 ，Ｋ—ｍｅａｎｓ是一 种 基 于划 分 的 经 典 算 法 ．但 是 由于 Ｋ ｍｅａｎｓ方法 对 于 初 始 中心 点 的 选
择非常敏感 ，有可能 导致 聚类结果 收敛于 局部 ，本 文提 出了一种基 于遗传算 法来 对类 中心 点 进 行全 局寻 优 的 文档
Ｆｏｕｎｄａｔｉｏｎ Ｉｔｅｍ ：Ｎａｔｉｏｎａ１ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ（１０７７１０７６）
Ｒｅｃｅｉｖｅｄ Ｄａｔｅ：２００８— １１～ １ｌ
＊ Ｃｏｒｒｅｓｐｏｎｄｉｎｇ Ａｕｔｈｏｒ，Ｅ—ｍａｉｌ：ｊｘｗｅｉ＠ ｆｏｘｍａｉｌ．ｃｏｒｎ
剩余6页未读，继续阅读
资源评论
