第 ２６ 卷第 １０ 期 ２００９ 年 １０ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏｌ．２６ Ｎｏ．１０ Ｏｃｔ．２００９ 倡 针 对 非 均 匀 数 据 集 的 DBSCAN 过 滤 式 改 进 算 法 熊忠阳， 吴林敏， 张玉芳 （ 重庆大学 计算机学院， 重庆 ４０００４４） 摘　要： 针对在数据分布不均匀时，由于 ＤＢＳＣＡＮ 使用统一的全局变量，使得聚类的效果差，提出了一种基于过 滤的 ＤＢＳＣＡＮ 算法。 该算法的思想是：在调用传统的 ＤＢＳＣＡＮ 算法前，先对数据集进行预处理，针对所有点的 k唱ｄｉｓｔ数据进行一维聚类，自动计算出不同的 Ｅｐｓ；然后再根据每个 Ｅｐｓ 分别调用传统的 ＤＢＳＣＡＮ 算法，从而找出 非均匀数据集的各种聚类。 实验结果表明，改进算法对密度不均匀的数据能够有效聚类。 关键词： 聚类； ＤＢＳＣＡＮ； 过滤； 非均匀密度； 数据挖掘 中图分类号： ＴＰ３０１畅６　　　文献标志码： Ａ　　　文章编号： １００１唱３６９５（２００９）１０唱３７２１唱０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２００９．１０．０３５ ＤＢＳＣＡＮ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｆｉｌｔｒａｔｉｏｎ ｆｏｒ ｄａｔａｓｅｔｓ ｗｉｔｈ ｖａｒｉｅｄ ｄｅｎｓｉｔｉｅｓ ＸＩＯＮＧ Ｚｈｏｎｇ唱ｙａｎｇ， ＷＵ Ｌｉｎ唱ｍｉｎ， ＺＨＡＮＧ Ｙｕ唱ｆａｎｇ （College of Computer Science， Chongqing University， Chongqing ４０００４４， China） Abstract： Ｗｈｅｎ ｄａｔａ ｄｉｓｔｒｉｂｕｔｉｏｎ ｗａｓ ｎｏｔ ｅｖｅｎ，ＤＢＳＣＡＮ ｗａｓ ｃｌｕｓｔｅｒｉｎｇ ｑｕａｌｉｔｙ ｄｅｇｒａｄｅｓ ｆｏｒ ｕｓｉｎｇ ｔｈｅ ｓａｍｅ ｇｌｏｂａｌ ｖａｒｉａｂｌｅ． Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｆｉｌｔｒａｔｉｏｎ唱ｂａｓｅｄ ＤＢＳＣＡＮ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ｂａｓｉｃ ｉｄｅａ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｗａｓ ｔｈａｔ， ｂｅｆｏｒｅ ａｄｏｐｔｉｎｇ ｔｒａｄｉｔｉｏｎａｌ ＤＢＳＣＡＮ ａｌｇｏｒｉｔｈｍ， ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｄａｔａ ｐｏｉｎｔ’ｓ k唱ｄｉｓｔ ｐｌｏｔ，ｕｓｉｎｇ １唱ｄｉｍｅｎｓｉｏｎ ｃｌｕｓｔｅｒｉｎｇ ｔｏ ｇｅｔ ａｌｌ ｔｈｅ ｃｌｕｓｔｅｒｓ， ｔｈｅｎ ｇｅｔｔｉｎｇ ｓｅｖｅｒａｌ ｖａｌｕｅｓ ｏｆ ｐａｒａｍｅｔｅｒ Ｅｐｓ ｆｏｒ ｄｉｆｆｅｒｅｎｔ ｄｅｎｓｉｔｉｅｓ．Ｗｉｔｈ ｄｉｆｆｅｒｅｎｔ ｖａｌｕｅｓ ｏｆ Ｅｐｓ，ａｄｏｐｔｅｄ ＤＢＳＣＡＮ ａｌｇｏｒｉｔｈｍ ｉｎ ｏｒｄｅｒ ｔｏ ｆｉｎｄ ｏｕｔ ｃｌｕｓｔｅｒｓ ｗｉｔｈ ｖａｒｉｅｄ ｄｅｎｓｉｔｉｅｓ ｓｉｍｕｌｔａｎｅｉｔｙ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔ ｄｅｍｏｎｓｔｒａｔｅｓ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｉｓ ｅｆｆｅｃｔｉｖｅ ｏｎ ｃｌｕｓｔｅｒｉｎｇ ｔｈｅ ｄａｔａｓｅｔｓ ｗｉｔｈ ｖａｒｉｅｄ ｄｅｎｓｉｔｉｅｓ． Key words： ｃｌｕｓｔｅｒｉｎｇ； ＤＢＳＣＡＮ； ｆｉｌｔｒａｔｉｏｎ； ｖａｒｉｅｄ ｄｅｎｓｉｔｉｅｓ； ｄａｔａ ｍｉｎｉｎｇ 网格的方法和基于模型的方法 定义 ２　边界对象。 如果 p 在半径 Ｅｐｓ 邻域内含有的对 象小于 ｍｉｎＰｔｓ，但在某核心对象的 Ｅｐｓ 邻域范围内，则称 p 为 边界对象。 定义３　噪声对象。 如果 p 在半径Ｅｐｓ 邻域内含有的对象 小于 ｍｉｎＰｔｓ，且它不在其他核心对象的 Ｅｐｓ 邻域范围内，称 p 为噪声对象。 定义４　直接密度可达。 在对象集 D 中，如果 p 在 q 的 Ｅｐｓ 邻域内，且 q 是一个核心对象，则称 p 从 q 出发是直接密度 可达的。 定义５　密度可达。 如果存在一个对象链 p１，p２，…，pn， pi ＝q，pn ＝p， 对 pi∈D（１≤i≤n），pi ＋１ 是 pi 从 关 于 Ｅｐｓ 和 ｍｉｎＰｔｓ 直接密度可达的， 则对 象 p 是从 对 象 q 关 于 Ｅｐｓ 和 ｍｉｎＰｔｓ 密度可达的 ＤＢＳＣＡＮ 通过检查数据集中每个点的 Ｅｐｓ 邻域进行聚类。 如果一个点 p 的Ｅｐｓ 邻域包含了多于ｍｉｎＰｔｓ 个点，则创建一个 以 p 作为核心对象的新类；然后ＤＢＳＣＡＮ 反复寻找从这些核心 对象直接密度可达的对象，这个过程涉及一些密度可达类的合 并；当没有新的点可以被添加到任何类时，该过程结束。 　　聚类是将数据对象分组成为多个类，在同一个类中的对象 之间具有较高的相似度，而不同类中的对象则差别较大。 在许 多应用中，可将一个类中的数据对象作为一个整体处理，因此 当分析一个较大的、复杂的、连续的、有着许多变量的数据集和 完全未知的结构时，聚类是一个非常有用的工具。 聚类的方法 可以分为五类，即划分方法、层次方法、基于密度的方法、基于 ［１］。 ＤＢＳＣＡＮ 属于基于密度的 聚类算法。 该算法将具有足够高密度的区域划分成类，并可以 在带有噪声的空间数据库中发现任意形状的类。 但有一个比 较明显的弱点，即当数据分布不均匀时，由于使用统一的全局 变量，使得聚类的效果差。 针对上述问题，本文提出了一种基于过滤的 ＤＢＳＣＡＮ 改 进算法。 1　DBSCAN 算法 ＤＢＳＣＡＮ 算法根据给定的密度阈值识别一个类。 密度阈 值由 Ｅｐｓ 和 ｍｉｎＰｔｓ 两个参数决定。 其中：Ｅｐｓ 表示半径；ｍｉｎＰｔｓ ［２］。 表示核心点在 Ｅｐｓ 半径范围内至少应该含有的点的数量 原始 ＤＢＳＣＡＮ 算法描述如下： ＤＢＳＣＡＮ 的一些基本定义如下（ 对于给定的对象集 D 和参数 ａ）初始化，输入聚类数据。 Ｅｐｓ、ｍｉｎＰｔｓ）： ｂ）任意选取一个数据点 xi。 定义 １　核心对象。 如果对象 p 在半径 Ｅｐｓ 邻域内至少 ｃ）如果 xi 没有被划分到某一个类，且是核心对象，则扩展 包含 ｍｉｎＰｔｓ 个对象，则称 p 为核心对象。 收稿日期： ２００８唱１２唱２５； 修回日期： ２００９唱０２唱２６　　基金项目： 重庆市科委自然科学基金计划资助项目（２００７ＢＢ２３７２） 作者简介：熊忠阳（１９６２唱），男，重庆人，博导，主要研究方向为网格技术、数据挖掘与应用； 吴林敏（１９８４唱），男，四川广安人，硕士研究生， 主要 研究方向为数据挖掘（ｗｕｌｉｎｍｉｎ唱１１１＠１６３．ｃｏｍ）；张玉芳（１９６７唱），女，重庆人，硕导，主要研究方向为数据挖掘、商业智能． ［３］。 

计 算 机 应 用 研 究 　 数量 ·２２７３· 以 xi 为核心对象的类，即找出从 xi 所有密度可达的点。 ｄ）若所有的数据点均被处理，则结束；否则，转 ｂ）［４］。 ＤＢＳＣＡＮ 的时间复杂度为 O（n２）；如果采用空间索引，其 复杂度可降为 O（n ｌｏｇ n），n 表示数据集中含有数据对象的 ［５］。 2　基于过滤的 DBSCAN 算法 在传统ＤＢＳＣＡＮ 算法中，为了确定参数Ｅｐｓ 和ｍｉｎＰｔｓ，ＤＢ唱 ＳＣＡＮ 将计算任意对象与它的第 k 个最邻近的对象之间的距 离（即 k唱ｄｉｓｔ），k 值由用户指定，然后根据 k唱ｄｉｓｔ 由小到大排序， 绘出 k唱ｄｉｓｔ 图。 在指定 k 值后，参数 ｍｉｎＰｔｓ 则等于 k ＋１，即在 半径 Ｅｐｓ 范围内，包括核心点在内至少应该含有 k ＋１ 个点才 能被聚为类。 另外，在确定参数 Ｅｐｓ 时，由用户指定一个百分 比（如８５％），然后根据 k唱ｄｉｓｔ 图取出对应的 k唱ｄｉｓｔ 作为 Ｅｐｓ。 下面先对 k唱ｄｉｓｔ 图稍作说明：如果单就 k唱ｄｉｓｔ 在图中的表 示来说，它其实是一系列的点。 如图３ 中的 C２ 部分含有四个 点（k ＝３），这些点的纵坐标均为１．４，表示在原数据集中３唱ｄｉｓｔ 为１．４ 的数据点有四个，具体为原数据集中的哪四个点则无须 知道。 又比如假设数据集 D 一共有 １０ 个点。 其中有五个点 的３唱ｄｉｓｔ 为１，其余五个点的３唱ｄｉｓｔ 为４；将各３唱ｄｉｓｔ 按从小到大 排序后，于是得到 ３唱ｄｉｓｔ 图中各个点的坐标：p１（１，１），p２（２， １），…，p５（５，１），p６（６，４），p７（７，４），…，p１０（１０，４）。 如果将 k唱ｄｉｓｔ 图中这一系列的点连接起来，就变成了k唱ｄｉｓｔ 曲线，如图１ 所示。 图１ 中有两条曲线 A 和 B，分别对应了两 个不同的数据集。 其中：曲线 A 表示数据集的密度分布比较均 匀，只有一种主要密度水平；曲线 B 则表明数据集为非均匀数 据集，它至少含有三个不同层次的密度水平。 在实际应用中，由于传统 ＤＢＳＣＡＮ 算法只采用统一的全 局变量 Ｅｐｓ，这使得它只能针对单一的密度水平进行聚类。 而 当数据点的密度分布出现曲线 B 的这种情况时，传统的 ＤＢ唱 ＳＣＡＮ 算法的聚类效果较差。 离 距 邻 近 最  第                   图 图 图 密度分布不均衡的数据图    如图２ 所示，图２ 中一共五个类，即 C１、C２、C３、C４、C５。 其 中左边类的密度较高，而右边类较低。 如果参照左边类的密度 来决定全局的 Ｅｐｓ，则右边的两个类就可能变成很多个类，同 时产生很多噪声点；如果参照右边类的密度来决定全局的 Ｅｐｓ，那么左边的 C１、C２、C３ 很可能合并为一个类 ［６］。 因此，本 文提出了基于过滤的 ＤＢＳＣＡＮ 算法。 该算法主要包括两个 步骤： ａ）数据预处理，计算 Ｅｐｓi： （ａ）计算出每个点的 k 距离； （ｂ）对一维的 k 距离数据进行聚类，筛选聚类结果，得到 代表原始数据集主要密度水平的类； （ｃ）根据一维聚类结果，计算出参数 Ｅｐｓi。 第 ２６ 卷 ｂ）将 Ｅｐｓi 从小到大排序，根据每个 Ｅｐｓi，调用传统的 ＤＢ唱 ＳＣＡＮ 算法进行过滤式聚类。 算法的详细过程如下： ａ）计算 Ｅｐｓi。 在对一维的 k 距离数据进行聚类时，本文也 采用传统的 ＤＢＳＣＡＮ 算法进行聚类；然后，对一维聚类结果进 行筛选处理，去掉噪声类。 所谓噪声类，是指聚类结果中只含 很小比例数据点的类，这些类并不能代表原始数据集的主要密 度水平，因此需要去掉噪声类。 图３ 表示 k唱ｄｉｓｔ 图（为了表示方便，没有将各点连成 k唱ｄｉｓｔ 曲线），图４ 为原始数据集。 在图３ 中，纵坐标为 k唱ｄｉｓｔ，横坐标 则表示该 k唱ｄｉｓｔ 值对应了某个数据点。 为了更直观地表达，将 一维的聚类结果在 k唱ｄｉｓｔ 图中显示。 对 k唱ｄｉｓｔ 聚类后，得到 C１、 C２、C３ 共三个类。 其中 C２ 即为噪声类，因为它只代表很小比 例的数据点，不能代表原始数据集的主要密度水平。                                    图 图 图  原始数据集   为了去掉噪声类，将一维聚类结果进行如下处理： 在传统的 ＤＢＳＣＡＮ 算法中，根据 k唱ｄｉｓｔ 图确定 Ｅｐｓ 参数 时，需要用户指定一个百分比例，以截取 k唱ｄｉｓｔ 图中相应位置 的值作为 Ｅｐｓ 参数的值。 同样，也可以用该方法进行噪声类的 处理：（ａ）将各 k唱ｄｉｓｔ 类根据其含有的数据点的数量进行降序 排列，则较前面的类将代表数据集的主要密度；（ｂ）与传统ＤＢ唱 ＳＣＡＮ 一样需要一个百分比例，从而得到代表原始数据集主要 密度水平的类。 如图３，一维聚类得 C１（２１）、C２（４）、C３（２０）， 降序排列后为 C１（２１）、C３（２０）、C２（４），取ｐｅｒｃｅｎｔ ＝８０％，从 C１ 开始选择，直到选择的类之和大于或等于总数据点的８０％；因 此，依次取得 C１、C３，其中 C２ 为噪声类。 根据一维聚类结果计算 Ｅｐｓi： 计算各个 k唱ｄｉｓｔ 类的中的平均 k唱ｄｉｓｔ 和最大 k唱ｄｉｓｔ，并按平 均 k唱ｄｉｓｔ 从小到大排序。 假设排序后的类对应为 C１ C２…Cn， 平均 k唱ｄｉｓｔ 序列为 d１ d２ …di…dn； 则 Ｅｐｓ１ ＝（ d１ ＋d２）／２… Ｅｐｓi ＝（ di ＋di ＋１）／２ …Ｅｐｓn －１ ＝（ dn －１ ＋dn）／２，Ｅｐｓn ＝ｍａｘ （Cn），即针对最后一个 Ｅｐｓn，用类中的最大 k唱ｄｉｓｔ 值作为 Ｅｐｓn 的值。 Ｅｐｓi 的计算过程示例如表１ 所示。 表 １　Ｅｐｓi 的计算过程示例 计算步骤 每步的结果 和最大 k 距离 得到代表主要密度水平的类 C１（２１）、C２（４）、C３（２０） （ａ）k唱ｄｉｓｔ 聚类结果 （ｂ） 按含有的数据点数量降序排列； C１（２１）、C３（２０）、C２（４） （ｃ） 取 ｐｅｒｃｅｎｔ ＝８０％，去掉噪声类， C１（２１）、C３（２０） （ｄ） 计算各个类的平均 k 距离 d１ ＝１，d３ ＝３；ｍａｘ（C１） ＝１，ｍａｘ（C３） ＝３ （ｅ） 将平均 k 距离的值按升序排列； d１ ＝１，d３ ＝３ Ｅｐｓ１ ＝（d１ ＋d３）／２ ＝２；Ｅｐｓ２ ＝ｍａｘ（C３） ＝３ （ｆ） 计算得出 Ｅｐｓi； 　　ｂ）过滤式的聚类。 将前面所得的 Ｅｐｓi 按升序排列，然后 根据不同的 Ｅｐｓi，依次调用 ＤＢＳＣＡＮ 算法进行过滤式聚类。 将 Ｅｐｓi 升序排列是为了先将密度高的数据进行聚类，随后再 

熊忠阳，等：针对非均匀数据集的 ＤＢＳＣＡＮ 过滤式改进算法 第 １０ 期 依次根据较大的 Ｅｐｓi，将密度较稀的数据分别进行聚类。 每当 下一次聚类开始时，去掉前面已经聚成类的点，以防止重复 聚类。 3　实验与分析 3畅1　数据描述 本实验采用 ＭＡＴＬＡＢ 实现，为了能够直观地观察和分析 结果，实验采用二维数据。 如图 ５ 所示，图中有两个密度明显 不同的区域，因为数据集分类明显，所以该数据集能较好地用 来检验聚类结果的有效性。 另外，由于基于密度的算法已经被 证明可以发现任意形状的类，本文在任意形状方面将不再过多 探讨。 3畅2　实验过程与结果 进行一维聚类得 R１、R２、R３、R４，如图６ 所示。 计算出各个点的 k唱ｄｉｓｔ（k ＝４），将其从小到大排列，然后 ·３２７３· 　　　 　　ｂ）根据不同的 Ｅｐｓi，调用 ＤＢＳＣＡＮ 算法进行过滤式聚类。 在采用空间索引的情况下，这一步所使用的时间为 O（n ｌｏｇ n）；因此，整个算法的时间复杂度为 O（n ｌｏｇ n）。 　　在该实验中，如果采用传统的 ＤＢＳＣＡＮ 算法，则 Ｅｐｓ 只能 选择一个统一的全局变量。 如果 Ｅｐｓ ＝１．５，则图中 C１ 将能 被成功聚类，而 C２ 会被标志为噪声点；如果 Ｅｐｓ ＝２，则 C１ 和 C２ 将被合并为一个类。 因此，当数据密度不均匀时，传统的 ＤＢＳＣＡＮ算法聚类效果很差。 针对这个问题，本文提出了基 于过滤的 ＤＢＳＣＡＮ 改进算法，实验结 果表明该算法有效并 可行。 4　结束语 当数据分布不均匀时，由于传统 ＤＢＳＣＡＮ 使用统一的全 局变量，聚类的效果差。 针对这个问题，本文提出了一种基于 过滤的 ＤＢＳＣＡＮ 改进算法。 该算法针对数据集中存在的不同 密度水平，自动产生相应的 Ｅｐｓi，然后依次调用传统的 ＤＢ唱 ＳＣＡＮ 进行聚类。 实验结果表明该算法对于数据分布不均匀 的情况能够有效地聚类。 当然，由于改进算法采用了数据预处 理的方式，如何提高算法的效率将是下一步的研究方向。 参考文献： ［１］ 蔡元萃，陈立潮．基于数据分区的并行［Ｊ］．科技情报开发与经济， ２００７，17（１）：１４５唱１４６． ［２］ ＨＡＮ Ｊｉａ唱ｗｅｉ，ＫＡＭＢＥＲ Ｍ．Ｄａｔａ ｍｉｎｉｎｇ ｃｏｎｃｅｐｔｓ ａｎｄ ｔｅｃｈｎｉｑｕｅｓ ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｈｉｇｈｅｒ Ｅｄｕｃａｔｉｏｎ Ｐｒｅｓｓ，２００１． ［３］ 周水庚，周傲英，曹 晶．基 于 数 据 分 区 的 ＤＢＳＣＡＮ 算 法［Ｊ］．计 算 机研究与发展，２０００，37（１０）：１１５３唱１１５９． ［４］ 荣秋生，颜 君 彪，郭 国 强．基 于 ＤＢＳＣＡＮ 聚 类 算 法 的 研 究 与 实 现 ［Ｊ］．计算机应用，２００４，24（４）：４５唱４６． ［５］ 张枫，邱保志．基于网格的高效 ＤＢＳＣＡＮ 算法［Ｊ］．计算机工程与 应用，２００７，43（１７）：１６７唱１６９． ［６］ 何中 胜， 刘 宗 田， 庄 燕 滨．基 于 数 据 分 区 的 并 行 ＤＢＳＣＡＮ 算 法 ［Ｊ］．小型微型计算机系统，２００６，27（１）：１１５唱１１６． ［７］ ＬＩＵ Ｐｅｎｇ，ＺＨＯＵ Ｄｏｎｇ，ＷＵ Ｎａｉ唱ｊｕｎ．ＶＤＢＳＣＡＮ：ｖａｒｉｅｄ ｄｅｎｓｉｔｙ ｂａｓｅｄ ｓｐａｔｉａｌ ｃｌｕｓｔｅｒｉｎｇ ｏｆ ａｐｐｌｉｃａｔｉｏｎｓ ｗｉｔｈ ｎｏｉｓｅ ［Ｊ］．Service Systems and Service Management，２００７，22（７）：１唱４． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ．Ｍｏｎｔｒｅａｌ：［ｓ． ｎ．］，１９９５：９２４唱９２９． ［３］ ＭＹＲＡ Ｓ，ＬＵＫＡＳ Ｆ．Ａ ｄａｔａ ｍｉｎｅｒ ａｎａｌｙｚｉｎｇ ｔｈｅ ｎａｖｉｇａｔｉｏｎａｌ ｂｅｈａｖｉｏｒ ｏｆ Ｗｅｂ ｕｓｅｒｓ ［ＥＢ／ＯＬ］．（２００１唱０９唱１７）．ｈｔｔｐ：／／ｗｗｗ．ｗｉｗｉ．ｈｕ＿ｂｅｒ唱 ｌｉｎ．ｄｅ／ｍｙｒａ／ｗ＿ａｃａｉｉ０１．ａｓｐｘ． ［４］ ＧＯＤＯＹ Ｄ，ＡＭＡＮＤＩ Ａ．Ｍｏｄｅｌｉｎｇ ｕｓｅｒ ｉｎｔｅｒｅｓｔｓ ｂｙ ｃｏｎｃｅｐｔｕａｌ ｃｌｕｓｔｅ唱 ｒｉｎｇ［Ｊ］．Information Systems，２００６，31（４，５）：２４７唱２５５． ［５］ 邢东山，沈钧毅，宋擒豹．用户浏览偏爱模式挖掘算法的研究［Ｊ］． 西安交通大学学报，２００２，36（４）：３６９唱３７２． ［６］ ＢＲＵＳＩＬＯＶＳＫＹ Ｐ．Ｐｒｅｄｉｃｔｉｖｅ ｓｔａｔｉｓｔｉｃａｌ ｍｏｄｅｌｓ ｆｏｒ ｕｓｅｒ ｍｏｄｅｌｉｎｇ ［Ｊ］．User Modeling and User唱adapted Interaction，２００１，11（１）： ５唱１８． ［７］ ＣＨＥＮ Ｍ Ｓ，ＰＡＲＫ Ｊ Ｓ，ＹＵ Ｐ Ｓ．Ｅｆｆｉｃｉｅｎｔ ｄａｔａ ｍｉｎｉｎｇ ｆｏｒ ｐａｔｈ ｔｒａｖｅｒ唱 ｓａｌ ｐａｔｔｅｒｎｓ［Ｊ］．IEEE Trans on Knowledge and Data Enginee唱 ring，１９９８，10（２）：２０９唱２２１．                                                   图 图 图 实验数据    将其 按 所 含 数 据 点 的 数 量 降 序 排 列： R３ （２３３２）、 R１ （２３０４）、R２（１９２）、R４（１６７）；取 ｐｅｒｃｅｎｔ ＝８５％，得到代表主要密 度水平的类：R３（２３３２）、R１（２３０４）；然后按表 １ 所示的步骤进 行计算，得出 Ｅｐｓi：Ｅｐｓ１ ＝１．５， Ｅｐｓ２ ＝２。 根据不同的 Ｅｐｓi，依次调用 ＤＢＳＣＡＮ 算法进行过滤式聚 类。 如图５，当 Ｅｐｓ１ ＝１．５ 时，图中标为“· ”的点被聚为 C１，此 时标为“倡”的点则被识别为噪声点，然后，被聚为 C１ 的点将 被过滤掉；当 Ｅｐｓ２ ＝２ 时，图中标为“倡” 的区域被聚为 C２，整 个实验过程结束。 算法时间复杂度分析：过滤算法主要分为以下两步： ａ）对数据进行预处理，并计算出 Ｅｐｓi，这一步所用的时间 为 O（n ｌｏｇ n）； （ 上接第 ３６９６ 页） 检索领域中的研究热点。 本文提出了结合用 户浏览时间和内容选择机制来发现用户的个人浏览兴趣，动态 维护用户的个人兴趣剖像，进而构建个人兴趣搜索智能 ａｇｅｎｔ 子系统 ＳＳＰＩＳＩＡ 来搜集、组织、挖掘和应用用户的个人兴趣信 息，并在此基础上实现了基于 ＳＳＰＩＳＩＡ 数据收集的个人兴趣增 量挖掘算法。 最后通过实验表明，该结构和算法能够有效地跟 踪用户的个人兴趣变化，并且具有良好的适应性，进而为实现 个性化信息检索奠定了基础。 笔者下一步将进一步从语法、语 义和语用的角度探讨用户模型的形成和应用，提高个性化信息 检索的效率。 参考文献： ［１］ 曾春，邢春晓，周立柱．个性化服务技术综述［Ｊ］．软件学报，２００２， ［２］ ＬＩＥＢＥＭＡＮ Ｈ Ｌ．Ａｎ ａｇｅｎｔ ｔｈａｔ ａｓｓｉｓｔｓ Ｗｅｂ ｂｒｏｗｓｉｎｇ［Ｃ］ ／／Ｐｒｏｃ ｏｆ 13（１０）：１９５２唱１９６１．