.234. 智能系统学报 第12卷 P:≈ ∑，e(自)产+Phc)(8) 000个样本点。图7(a)所示为原算法[]的聚类结 e cell(E)y≠i 果，其参数d.值是一个经验值0.03，即选取最小2% eigoe.（x;）= 的距离做截断：图7(b)所示为改进算法的聚类结 Ce neighbor(cell() 果，其参数d.值是通过密度估计嫡最小化得到的优 (9) 化值，略大于论文)实验采用的经验值，但聚类质 其中P恤.(x,)的计算公式代表邻近网格 量相对更好，而且抗噪声能力更好。 单元内的样本点对P:的贡献。此时计算任一样本 0.5 点的局部密度估计值所需时间开销仅为空间索引时 间，即O(log(na),nd<n为非空网格单元数， 而构造空间索引结构所需时间为O(og(n)),算 法总的时间复杂度近似为O(log(nd))。具体算法 描述如下： 2.3改进算法描述 给定数据集D={x1,x2,…,x},改进的快速搜 0.5 索密度峰值的聚类算法可以描述如下。 -0.8-0.6-0.4-0.200.20.40.6 算法改进的搜索密度峰值的聚类算法 (a)原算法(d.=0.03) (ICADEP) 0.5 输入数据集D={x1,x2,…,xn},抽样个数 nsample 输出数据划分Π。 算法步骤： I)随机抽取nap。个样本点组成抽样数据集 SampleSet; 2)d.=Optimal_Parameter(SampleSet);/用抽 样数据集优化估计密度参数d。; -08060402.002040.6 3)Map CreateMap(D,- );/以 为尺度 (b)ICADEP算法(d.=0.05) 图74000个随机样本点的聚类结果比较 对空间进行网格划分并构建索引树： Fig.7 Comparison of clustering results of 4000 random 4)p =Density_Estimation(D,Map,d);// sample points 算所有样本点的局部密度估计值P1,P2,…,Pn; 图8(a)所示为原算法聚类结果，参数d.选取 5)8=NN_Distance(D,Map,p);/按照局部 最小2%的距离做截断，即d.=2.23:而图8(b)所示 密度估从大到小的顺序，计算所有样本点的高密度 的改进算法聚类结果中，通过密度估计嫡最小化得 最所邻距离81，…，6n; 到的优化d。值虽然略小于论文实验的经验值，即 6)C=Decision_Graph(D,p,δ)：//形成决策 d.=2.02,但聚类结果同样能够正确识别原始数据分 图，根据用户交互，确定代表聚类中心的样本子集： 布的7个内在的数据类。 7)Π=Partition(D,C);/将所有非中心样本 20 15 点沿着密度估计值递增的最近邻方向，迭代划分给 10 相应的聚类中心，实现数据划分。 - 3实验结果与比较 -5 这里采用图1、2所示的测试数据集检验改进算 法ICADEP的有效性。所有程序用软件Matlab2011 102势 -15 实现，测试在一台PC机(i5-3210MCPU、8GHz内 20-15-10-5 05101520 存、Win7)上进行，聚类结果如图7~9所示。图7所 (a)原算法(d。=2.23) 示的测试数据包含6个聚类和一些噪声数据，共4ρｉ ≈ ∑ ｘｊ∈ｃｅｌｌ ｘｉ ( ) ∧ｊ≠ｉ ｅ － ｄ ｉｊ ｄ ｃ ( ) ２ ＋ φｎｅｉｇｈｂｏｒ＿ｃｅｌｌｓ ｘｉ ( ) （８） φｎｅｉｇｈｂｏｒ＿ｃｅｌｌｓ（ｘｉ） ＝ Ｃ∈ｎｅｉｇｈ∑ｂｏｒ（ｃｅｌｌ（ｘｉ ）） ｎｃ·ｅ － ｄ ｘ ｉ ，ｘ ｃ ( ) ｄ ｃ ( ) ２ （９） 其中 φｎｅｉｇｈｂｏｒ＿ｃｅｌｌｓ ｘｉ ( ) 的计算公式代表邻近网格 单元内的样本点对 ρｉ 的贡献。 此时计算任一样本 点的局部密度估计值所需时间开销仅为空间索引时 间，即 Ｏ（ ｌｏｇ（ ｎｇｒｉｄ ）），ｎｇｒｉｄ ＜＜ｎ 为非空网格单元数， 而构造空间索引结构所需时间为 Ｏ（ ｌｏｇ（ ｎｇｒｉｄ ）），算 法总的时间复杂度近似为 Ｏ（ｌｏｇ（ｎｇｒｉｄ ））。 具体算法 描述如下： ２．３ 改进算法描述 给定数据集 Ｄ ＝ ｘ１ ，ｘ２ ，…，ｘｎ { } ，改进的快速搜 索密度峰值的聚类算法可以描述如下。 算法 改 进 的 搜 索 密 度 峰 值 的 聚 类 算 法 （ＩＣＡＤＥＰ） 输入 数据集 Ｄ ＝ ｘ１ ，ｘ２ ，…，ｘｎ { } ，抽样个数 ｎｓａｍｐｌｅ ； 输出 数据划分P。 算法步骤： １）随机抽取 ｎｓａｍｐｌｅ 个样本点组成抽样数据集 ＳａｍｐｌｅＳｅｔ； ２） ｄｃ ＝ Ｏｐｔｉｍａｌ＿Ｐａｒａｍｅｔｅｒ （ＳａｍｐｌｅＳｅｔ）； ／ ／ 用抽 样数据集优化估计密度参数 ｄｃ ； ３）Ｍａｐ ＝ ＣｒｅａｔｅＭａｐ（Ｄ， ｄｃ ２ ）； ／ ／ 以 ｄｃ ２ 为尺度 对空间进行网格划分并构建索引树； ４） ρ ＝ Ｄｅｎｓｉｔｙ＿Ｅｓｔｉｍａｔｉｏｎ（Ｄ， Ｍａｐ， ｄｃ ）； ／ ／ 计 算所有样本点的局部密度估计值 ρ１ ，ρ２ ，…，ρｎ ； ５） δ ＝ ＮＮ＿Ｄｉｓｔａｎｃｅ（Ｄ， Ｍａｐ， ρ ）； ／ ／ 按照局部 密度估从大到小的顺序，计算所有样本点的高密度 最所邻距离 δ１ ，…，δｎ ； ６）Ｃ ＝ Ｄｅｃｉｓｉｏｎ＿Ｇｒａｐｈ（Ｄ， ρ， δ ）； ／ ／ 形成决策 图，根据用户交互，确定代表聚类中心的样本子集； ７）P＝ Ｐａｒｔｉｔｉｏｎ （Ｄ， Ｃ）； ／ ／ 将所有非中心样本 点沿着密度估计值递增的最近邻方向，迭代划分给 相应的聚类中心，实现数据划分。 ３ 实验结果与比较 这里采用图 １、２ 所示的测试数据集检验改进算 法 ＩＣＡＤＥＰ 的有效性。 所有程序用软件 Ｍａｔｌａｂ２０１１ 实现，测试在一台 ＰＣ 机（ ｉ５－３２１０Ｍ ＣＰＵ、８ＧＨｚ 内 存、Ｗｉｎ７）上进行，聚类结果如图 ７～９ 所示。 图 ７ 所 示的测试数据包含 ６ 个聚类和一些噪声数据，共 ４ ０００ 个样本点。 图 ７（ ａ） 所示为原算法［１］ 的聚类结 果，其参数 ｄｃ 值是一个经验值 ０．０３，即选取最小 ２％ 的距离做截断；图 ７（ ｂ） 所示为改进算法的聚类结 果，其参数 ｄｃ 值是通过密度估计熵最小化得到的优 化值，略大于论文［１］ 实验采用的经验值，但聚类质 量相对更好，而且抗噪声能力更好。 （ａ）原算法［１］ （ ｄｃ ＝ ０．０３ ） （ｂ）ＩＣＡＤＥＰ 算法（ ｄｃ ＝ ０．０５ ） 图 ７ ４ ０００ 个随机样本点的聚类结果比较 Ｆｉｇ．７ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｆ ４ ０００ ｒａｎｄｏｍ ｓａｍｐｌｅ ｐｏｉｎｔｓ 图 ８（ａ）所示为原算法聚类结果，参数 ｄｃ 选取 最小 ２％的距离做截断，即 ｄｃ ＝ ２．２３；而图 ８（ｂ）所示 的改进算法聚类结果中，通过密度估计熵最小化得 到的优化 ｄｃ 值虽然略小于论文［１］实验的经验值，即 ｄｃ ＝ ２．０２，但聚类结果同样能够正确识别原始数据分 布的 ７ 个内在的数据类。 （ａ）原算法［１］ （ ｄｃ ＝ ２．２３ ） ·２３４· 智 能 系 统 学 报 第 １２ 卷