0.   引言

随着5G、人工智能与大数据等相关技术的突破，智能煤矿安全监测、智能化采掘等煤矿智能化解决方案实现了跨越式发展，对煤矿多源海量数据进行集成分析与数据价值挖掘，实现动态诊断与辅助决策，成为推动煤矿智能化发展的关键^[1-2]。大型数据集的内在规律特征可通过占总数据量10%以内的关键数据进行体现，而上述关键数据被淹没在大量冗余数据中。当运用传统数据挖掘算法处理大型数据集时，空间和时间资源消耗急剧提升，会导致分析速度慢或准确率低，甚至出现因内存消耗巨大使得算法无法正常执行的情况^[3-4]。因此，开展面向大型数据集的高效数据挖掘方法具有重要的理论意义和实用价值。

K−means是应用广泛的聚类算法，具备收敛速度快、原理简单的特点^[5]。当面对大型数据集时，K−means算法的问题主要集中在内存和时间开销成倍增长及初始参数选择极为困难2个方面^[6]。上述问题一般通过2种途径解决，一种是优化初始参数选择，另一种是选择一部分实例或特征实现数据集规模减小。本文采用第2种途径展开研究，提出将统计学抽样思想融入基于K−means算法的大型数据集聚类分析中，实现数据集的规模缩减，通过分析关键数据，将分析结果推广到整个数据集中，在降低有效信息损失的前提下，提高K−means算法的处理效率和质量，实现大型数据集聚类分析成功率的提升^[7]。

简单随机抽样（Simple Random Sample，SRS）是目前应用最广泛的抽样方法，大型应用中的聚类方法（Clustering LARge Applications，CLARA）是其典型算法。该算法虽然可以有效缩减数据集的规模，但是如果抽取的样本集不具有代表性，则会导致聚类的准确性下降^[8]。Liao Kaiyang 等^[9]提出了一种基于多层随机抽样（Multi-layer Simple Random Sampling，M−SRS）的K−means算法，可构建不平衡簇树，对检索大型数据集有显著效果，但是聚类结果对初始随机选取的样本数据较为依赖。上述2种典型算法在分布不均匀数据集中的抽样效果均得不到保证。密度偏差抽样（Density Biased Sampling，DBS）是相对较新的抽样策略，C. R. Palmer等^[10]提出了基于DBS的K−means算法，该算法只扫描1遍数据集即可得到近似的DBS结果。Huang Jianbin等^[11]在上述研究的基础上提出了基于网格密度偏差抽样（Grid Density Biased Sampling，G−DBS）的K−means算法，进一步提高了算法在大型数据集上的执行效率和准确性。B. Minaei-Behrouz等^[12]通过重抽样技术确保聚类分析结果的准确性，但是聚类分析结果过度依赖数据样本的输入顺序。A. Aggarwal等^[13]提出了一种高效渐进式抽样算法，可以快速确定最优样本容量，进而获得高质量样本。上述算法均采用基于DBS的抽样方法，抽样过程没有以数据集的数据内容为基础，导致抽样过程建立在不合理的数据组划分之上，抽样所得数据集不能很好地体现原始数据集的分布特征，并且存在大量噪声点，在计算数据密度时产生了较大的时间消耗。

针对上述问题，本文基于局部敏感哈希（Locality-Sensitive Hashing，LSH）算法，提出具备数据合理划分与噪声点筛选能力的子数据组构建算法LSH−G，并将其与DBS方法相结合，提出能更真实反映原始数据集分布规律的样本集构建算法LSH−GD，在此基础上，通过K−means算法对生成的样本集进行聚类，实现较低时间复杂度情况下从大型数据集中高效挖掘有效数据。

1.   LSH基本理论

LSH算法是检查元素间相似度的有效算法，其基本思想：原始特征空间中相似的2个数据点通过相同投影或变换后，仍具有较大概率相似，而在原始特征空间中不相似的点具有较大概率仍不相似^[14-15]。设$ d\left( {{\boldsymbol{x}},{\boldsymbol{y}}} \right) $为数据点$ {\boldsymbol{x}} $与$ {\boldsymbol{y}} $之间的距离，如果函数$ h $满足下列条件，则将该过程中使用的哈希函数$ h $称为$ \left( {{d_1},{d_2},{p_1},{p_2}} \right) $敏感哈希函数^[16]：

1) 如果$ d\left( {{\boldsymbol{x}},{\boldsymbol{y}}} \right) \leqslant {d_1} $，那么$ h\left( {\boldsymbol{x}} \right) = h\left({\boldsymbol{ y}} \right) $的概率至少为$ {p_1} $，即函数$ h $将数据点$ {\boldsymbol{x}} $与$ {\boldsymbol{y}}{{}} $分配到同一个哈希桶的概率大于$ {p_1} $。

2) 如果$ d\left( {{\boldsymbol{x}},{\boldsymbol{y}}} \right) ＞ {d_2} $，那么$ h\left( {\boldsymbol{x}} \right) = h\left( {\boldsymbol{y}} \right) $的概率最大为$ {p_2} $，即函数$ h $将数据点$ {\boldsymbol{x}} $与$ {\boldsymbol{y}} $分配到同一个哈希桶的概率小于$ {p_2} $。

在上述定义中，$ {d_1} $和$ {d_2} $之间的区域属于空白区域（图1），与该区域内的距离值相对应的数据点进入同一个哈希桶的概率无限制。当距离$ {d_1} $和$ {d_2} $接近时，$ {p_1} $和$ {p_2} $也进一步接近。为解决该问题，可将不同的敏感哈希函数结合，以在不改变$ {d_1} $和$ {d_2} $的前提下加大$ {p_1} $和$ {p_2} $之间的差距。

图  1  $ \left( {{d_1},{d_2},{p_1},{p_2}} \right) $敏感哈希函数的概率分布

Figure  1.  Probability distribution of sensitive hashing function $ \left( {{d_1},{d_2},{p_1},{p_2}} \right) $

下载: 全尺寸图片 幻灯片

对给定的多个$ \left( {{d_1},{d_2},{p_1},{p_2}} \right) $敏感哈希函数进行组合，形成$ \left( {{d_1},{d_2},{p_1},{p_2}} \right) $敏感哈希函数族H，通过以下操作得到新的函数族H'^[17]：

1) AND操作：从H中挑选出$ a $个敏感哈希函数${{\text{ }}{h_1}{\text{, }}{h_2}{\text{, }} \cdots ,{\text{ }}{h_a}} $，并给定数据点$ {\boldsymbol{x}} $与$ {\boldsymbol{y}} $，当且仅当上述$ a $个敏感哈希函数均满足$ h\left({\boldsymbol{ x }}\right) = h\left( {\boldsymbol{y}} \right) $时，即只有当$ {\boldsymbol{x}} $与$ {\boldsymbol{y}} $的$ a $个哈希值均相等时，数据点${\boldsymbol{x}}$与$ {\boldsymbol{y}} $才会被投影到相同的哈希桶内。此时构建的新函数族$ H' $称为$ ( {d_1}, {d_2},p_1^a,p_2^a ) $敏感哈希函数族。

2) OR操作：从H中挑选出$ b $个敏感哈希函数$ {{\text{ }}{h_1}{\text{, }}{h_2}{\text{, }} \cdots ,{\text{ }}{h_b}} $，并给定数据点${\boldsymbol{ x}} $与${\boldsymbol{ y }}$，当且仅当上述$ b $个敏感哈希函数中有1个满足$ h\left( {\boldsymbol{x}} \right) = h\left({\boldsymbol{ y}} \right) $时，即只要当$ {\boldsymbol{x}} $与$ {\boldsymbol{y}} $的$ b $个哈希值中的1个相同时，2个数据点就会被投影到相同的哈希桶内，只有当$ {\boldsymbol{x}} $与$ {\boldsymbol{y}} $的$ b $个哈希值均不相同时，数据点${\boldsymbol{ x}} $与$ {\boldsymbol{y}} $才不被投影到同一个哈希桶内。此时构建的新函数族$ H' $称为$ ( {d_1},{d_2}, 1 - {{(1 - {p_1})}^b}, 1 - {{(1 - {p_2})}^b} ) $敏感哈希函数族。

由于AND操作降低了概率$ {p_2} $，同时OR操作提升了概率$ {p_1} $，通过挑选合适的$ a $值与$ b $值，将AND操作和OR操作级联在一起，可以使$ {p_1} $更接近1且$ {p_2} $更接近0^[18]。

2.   基于LSH−GD的K−means算法

基于LSH−GD的K−means算法建立在数据组构建及抽样基础上。运用LSH−GD算法对数据集进行处理后，通过K−means算法对生成的样本集进行聚类，可有效提高聚类准确性和高效性。

2.1   基于LSH的数据组构建算法LSH−G

LSH−G算法通过LSH构建哈希桶，每个哈希桶即为1个子数据组，通过对每个子数据组中的数据进行统计，实现对子数据组的筛选。LSH−G算法只需要对所有数据点进行1次扫描，不需要将所有数据点放入内存，因此具有线性复杂度。与LSH算法相比，LSH−G算法筛选并删除了对整个数据集有影响的噪声点，使整个聚类过程的执行时间急剧减少，更适用于批量处理。

1) 通过敏感哈希函数族处理数据集X的每个数据点$ {{\boldsymbol{x}}_i} $，确定其所属的子数据组$ g_j$，更新$ g_j$中的数据个数$ {n_{g^{}_j}} $。当所有数据点均被执行完后，将所有子数据组$g_j$添加到子数据组集合G中，将所有子数据组的数据个数$ {n_{g^{}_j}} $添加到集合N中。所有数据只需要进行1次处理，可在单通道中使用，不需要将整个数据集X放入内存，且没有对数据进行细节性分析。

2) 对集合N中的数据进行z−score标准化，基于该数据集的均值$ \mu $和标准差$ \sigma $生成正态分布曲线$ Q\left( {\mu ,{\sigma ^2}} \right) $。取小于$ \mu - {\text{1}}{\text{.64}}\sigma $（即标准正态分布中小于−1.64）的数据，将其原始数据组视为集合G中的噪声组，并将其从集合G中删除，完成对数据组的筛选。

LSH−G算法伪代码如下。

下载: 全尺寸图片 幻灯片

LSH−G算法第1）步已将数据集X中的每个数据映射到集合N中，在子数据组集合G的筛选过程中没有对数据集X进行读取，使整个算法保持了线性复杂度。通过对子数据组集合G的筛选，可将数据集噪声点删除，这样虽增加了算法执行步骤，但最终应用于DBS算法中的子数据组数量会大幅度下降，从而避免大量噪声点导致计算时产生巨大时间消耗。

当AND和OR操作的级联数量变化时，LSH−G算法效果会发生变化。运用包含85 000个数据点、3个类和2个维度的数据集开展实验，只用1个OR操作且AND操作数量变化时，LSH−G算法筛选的噪声点变化如图2所示，其中“+”为原始数据点，“×”为LSH−G算法筛选的噪声点。可看出，LSH−G算法虽然可准确识别3个类，但3个类周围存在大量噪声点；随着级联数量增加，筛选的噪声点数量逐渐增多。

图  2  不同级联数量情况下LSH−G算法筛选出的数据点噪声变化

Figure  2.  Noise variation of data points screened by LSH-G algorithm under different cascade numbers

下载: 全尺寸图片 幻灯片

2.2   基于LSH−G的数据组抽样算法LSH−GD

完成子数据组构建后，统计各子数据组数据量，以获取各子数据组密度，密度不同的子数据组对应抽样概率也不同。LSH−GD算法的输入项包括数据集X（数据总量为$ r $）、1组敏感哈希函数族H、样本集期望大小$ M $与抽样参数$ e $。

1) 扫描原始数据集，运用LSH−G 算法构建子数据组集合G及由所有子数据组数据量大小组成的集合N，并完成对所有子数据组的筛选，避免将噪声点带入基于密度偏差的抽样步骤中，导致算法运行过程中出现大量时间消耗。

2) 针对包含$ {l_j} $个数据点的第$ j $个子数据组$ {g_j} $，采用DBS概率函数计算抽样概率$ p\left( {{{l_j}}} \right) $^[10]。根据所得抽样概率，在子数据组${g_j}$中进行DBS，获得由$ {l_j} p\left({l_j}\right) $个样本组成的集合$ {L_j} $，最终由所有子数据组输出的样本集组成总样本集D。

LSH−GD算法伪代码如下。

下载: 全尺寸图片 幻灯片

运用图2(a)所示的包含85 000个数据点的数据集开展实验，运用DBS算法对数据集进行10%抽样，抽样效果如图3（a）所示。运用与图2(b)—图2(f)对应的级联组合，通过LSH−GD算法对数据集进行10%的抽样，抽样效果如图3(b)—图3(f)所示。

图  3  进行10%抽样后得到的样本集

Figure  3.  Sample set obtained after 10% sampling

下载: 全尺寸图片 幻灯片

3.   实验分析

3.1   实验准备

以基于M−SRS的K−means算法（算法1）、基于DBS的K−means算法（算法2）、基于G−DBS的K−means算法（算法3）作为对比算法，对基于LSH−GD的K−means算法（算法4）的性能进行测试。选用基于Box−Muller算法生成的14个人工数据集及属于UCI Machine Learning Repository的5个公开数据集作为数据来源，对4种算法的准确性与高效性分别展开测试 ^[19]。实验平台的CPU配置为Intel(R) Xeon(R) E5−1620 v3 @ 3.50 GHz，内存为16 GiB。

通过实验分析数据集的数据量、维度、类个数不同对4种算法性能产生的影响，为了保证实验所采用的数据集具有相似的内部结构，运用Box−Muller算法生成各个类均规则、各维度数据均处于(0，1)内的14个人工数据集。测试数据集特征见表1。生成上述数据集时，首先需要给定类的个数k并生成类的中心，基于类中心生成满足高斯分布的数据，所以类的理论中心$ \left\{ {{\text{ }}{m_1}{\text{, }}{m_2}{\text{, }} \cdots ,{\text{ }}{m_k}} \right\} $及属于该类的数据均为已知^[20]。

表  1  测试数据集特征

Table  1.  Test dataset characteristics

编号	数据集名称	数据量/个	维度	类个数
1	数据集1	20 000	5	3
2	数据集2	40 000	5	3
3	数据集3	60 000	5	3
4	数据集4	80 000	5	3
5	数据集5	120 000	5	3
6	数据集6	220 000	5	3
7	数据集7	40 000	10	3
8	数据集8	40 000	15	3
9	数据集9	40 000	20	3
10	数据集10	40 000	40	3
11	数据集11	40 000	5	6
12	数据集12	40 000	5	9
13	数据集13	40 000	5	12
14	数据集14	40 000	5	27
15	Pen−based	10 992	16	10
16	Shuttle	14 500	9	7
17	Magic	19 020	10	2
18	Letter Recognition	20 000	16	26
19	Statlog	58 000	9	5

下载: 导出CSV 

| 显示表格

通过聚类的准确性和高效性对算法性能进行评价。将类中心误差平方和（The Sum of Squares due to Error of Class Center，SSEC）作为聚类准确性评价指标，将聚类过程所消耗的CPU时间（CPU Time Consumption，CPU−C）作为聚类高效性评价指标。上述2种指标均采用重复进行10次实验后计算平均值的方式获取。

式中：C为SSEC的值；v_c为数据集经过抽样生成的样本集聚类后产生的实际中心。

给定样本集D时，SSEC取决于上述k个聚类中心，且SSEC越小，聚类效果越好。

3.2   最优级联组合实验

通过运用多个AND操作与OR操作进行级联组合，能够对敏感哈希函数族的子数据组划分效果进行优化，进而影响最终聚类效果，但是组成最优级联组合的AND操作和OR操作的数量未知。因此，通过$ \left( {{w \mathord{\left/ {\vphantom {w 2}} \right. } 2},2w,{1 \mathord{\left/ {\vphantom {1 2}} \right. } 2},{1 \mathord{\left/ {\vphantom {1 3}} \right. } 3}} \right) $（$ w $为哈希桶宽度）敏感哈希函数族H开展面向100种不同级联组合的研究，即1~10个AND操作与1~10个OR操作分别进行级联组合，将OR操作连接在AND操作后，根据实验结果获取最优AND操作和OR操作数量，使基于LSH−GD的K−means聚类算法产生最优SSEC。敏感哈希函数族H中的函数为

式中：$ u $为$ \left( {0,w} \right) $的任意数值；$ {\boldsymbol{t}} $为服从标准正态分布的随机向量。

如果两点间的距离$ d \gg w $，则两点有很小概率进入同一个哈希桶^[21]。根据上述原则，如果哈希桶宽度设置不合理，可导致1个哈希桶中存在的数据过多或过少，从而对噪声点删除结果造成影响，最终影响聚类的准确性与高效性。根据(w/2，2w，1/2，1/3)敏感哈希函数族H的设定，以及图1所示$ ( {d_1},{d_2}, {p_1},{p_2}) $敏感哈希函数的概率分布特点，得到哈希桶宽度$ w $的合理选择范围：

式中：$ {d_{{\rm{avg}}}} $为数据集数据平均距离；$ \varepsilon $为数据集维度；$ {{\textit{z}}_{q\min }} $与$ {{\textit{z}}_{q\max}}{ } $分别为第q个维度下数据的最小坐标与最大坐标。

本文选取合理选择范围的中点作为哈希桶宽度的最终值，即哈希桶宽度$ w=5 d_{{\rm{a v g}}} / 4 $。

将100种级联组合分别作用于表1所示的19个数据集。针对每个数据集，分别运用由每一种级联组合生成的LSH−GD算法进行总数据量的1%抽样，建立样本集。通过K−means算法对上述样本集分别进行聚类，最后通过式(1)计算SSEC，得到100个SSEC后进行归一化处理。完成所有的数据集处理后，将同一种级联组合得到的19个样本集的SSEC归一化数值相加，结果见表2，其中A为AND操作数量，O为OR操作数量。可看出，由10个AND操作与8个OR操作的级联组合得到的SSEC最小，因此将上述AND操作和OR操作数量作为最优级联组合。

表  2  不同级联组合下19个样本集的SSEC

Table  2.  The SSEC of 19 sample sets under different cascaded combinations

A	SSEC
	O=1	O=2	O=3	O=4	O=5	O=6	O=7	O=8	O=9	O=10
1	11.625	11.080	10.325	9.685	9.072	8.586	7.941	7.313	6.841	6.309
2	10.954	10.606	9.852	9.258	8.695	8.181	7.529	6.997	6.358	5.879
3	10.107	9.758	9.355	8.857	8.581	7.885	7.284	6.622	6.021	5.514
4	9.282	9.041	8.758	8.586	8.299	7.602	7.085	6.498	5.884	5.392
5	8.354	7.911	7.689	7.326	7.281	6.989	6.651	6.185	5.646	5.218
6	7.059	6.882	6.711	6.632	6.498	6.286	5.989	5.714	5.327	4.881
7	5.944	5.801	5.693	5.389	5.154	4.997	4.727	4.589	4.301	4.082
8	4.736	4.688	4.512	4.387	4.097	3.827	3.581	3.158	2.929	2.897
9	3.935	3.559	3.332	3.201	3.023	2.835	2.606	2.483	2.298	2.255
10	3.103	3.022	2.915	2.801	2.684	2.537	2.463	2.142	2.197	2.205

下载: 导出CSV 

| 显示表格

3.3   基于人工数据集的算法准确性实验

选用SSEC作为聚类准确性实验的评价指标。针对表1所示的14个人工数据集，使用算法1—算法4进行实验，分析数据量变化、数据维度变化及数据类个数变化对聚类准确性的影响。针对每个人工数据集，以筛选每个数据集数据总量的1%作为抽样目标，分别运用4种算法作用于筛选所得的数据，计算SSEC。

选用数据集1—数据集6进行实验，分析数据量变化对聚类准确性的影响，结果见表3。根据数据集数据量特点，以数据集1为对比基准，每种算法的SSEC变化趋势如图4所示。

表  3  不同数据量数据集的SSEC

Table  3.  The SSEC of datasets with different data size

数据集序号	数据量	SSEC
		算法1	算法2	算法3	算法4
1	20000	0.0812	0.0686	0.0628	0.0527
2	40000	0.0832	0.0781	0.0611	0.0505
3	60000	0.0904	0.0815	0.0587	0.0463
4	80000	0.0926	0.0784	0.0501	0.0412
5	120000	0.1051	0.0801	0.0491	0.0369
6	220000	0.2057	0.0947	0.0452	0.0305

下载: 导出CSV 

| 显示表格

图  4  数据量变化对聚类准确性的影响

Figure  4.  Impact of data size change on clustering accuracy

下载: 全尺寸图片 幻灯片

选用数据集2、数据集7—数据集10进行实验，分析数据维度变化对聚类准确性的影响。将获得的SSEC值转换为每个维度的平均SSEC值作为最终统计结果，见表4。根据数据集维度特点，以数据集2为对比基准，得到每种算法的SSEC变化趋势，如图5所示。

表  4  不同维度数据集的SSEC

Table  4.  The SSEC of datasets with different dimensions

数据集序号	维度	平均SSEC
		算法1	算法2	算法3	算法4
2	5	0.0166	0.0156	0.0122	0.0101
7	10	0.0171	0.0165	0.0144	0.0111
8	15	0.0193	0.0215	0.0142	0.0095
9	20	0.0207	0.0257	0.0132	0.0082
10	40	0.0288	0.0360	0.0124	0.0059

下载: 导出CSV 

| 显示表格

图  5  数据维度变化对聚类准确性的影响

Figure  5.  Impact of data dimension change on clustering accuracy

下载: 全尺寸图片 幻灯片

选用数据集2、数据集11—数据集14进行实验，分析数据类个数变化对聚类准确性的影响。将获得的SSEC值转换为每个类的平均SSEC值作为最终统计结果，见表5。根据数据集类个数特点，以数据集2为对比基准，得到每种算法的SSEC变化趋势，如图6所示。

表  5  不同类个数数据集的SSEC

Table  5.  The SSEC of datasets with different number of data class

数据集序号	类个数	平均SSEC
		算法1	算法2	算法3	算法4
2	3	0.0277	0.0260	0.0204	0.0168
11	6	0.0315	0.0356	0.0178	0.0162
12	9	0.0448	0.0548	0.0173	0.0157
13	12	0.0591	0.0687	0.0198	0.0154
14	27	0.0798	0.0975	0.0251	0.0115

下载: 导出CSV 

| 显示表格

图  6  数据类个数变化对聚类准确性的影响

Figure  6.  Impact of data class number change on clustering accuracy

下载: 全尺寸图片 幻灯片

由表3—表5可得以下结论：与基于M−SRS的K−means算法、基于DBS的K−means算法及基于G−DBS的K−means算法相比，基于LSH−GD的K−means算法在聚类准确性方面的平均提升幅度分别为56.63%、54.59%及25.34%。

由图4—图6可得以下结论：随着数据集的数据量、数据维度及数据类个数逐渐增大，基于M−SRS的K−means算法与基于DBS的K−means算法的聚类准确性表现出降低趋势，并且降低的速率均逐渐增大，基于G−DBS的K−means算法的聚类准确性基本保持稳定，基于LSH−GD的K−means算法的聚类准确性表现出增长趋势。

3.4   基于人工数据集的算法高效性实验

选用CPU−C作为聚类高效性实验的评价指标。针对表1中的14个人工数据集，使用算法1—算法4进行实验，分析数据量变化、数据维度变化及数据类个数变化对聚类高效性的影响。针对每个人工数据集，以筛选每个数据集数据总量的1%作为抽样目标，分别运用4种算法作用于筛选所得的数据，计算CPU−C。

选用数据集1—数据集6进行实验，分析数据量变化对聚类高效性的影响，结果见表6。根据数据集数据量特点，以数据集1为对比基准，每种算法的CPU−C变化趋势如图7所示。

表  6  不同数据量数据集的CPU−C

Table  6.  The CPU-C of datasets with different data size

数据集序号	数据量	CPU−C/s
		算法1	算法2	算法3	算法4
1	20000	4.782	3.964	3.728	3.697
2	40000	5.525	4.698	4.388	4.171
3	60000	6.413	6.422	6.132	5.981
4	80000	8.522	7.335	6.716	6.435
5	120000	12.606	9.318	7.931	7.386
6	220000	16.131	14.969	10.949	9.852

下载: 导出CSV 

| 显示表格

图  7  数据量变化对聚类高效性的影响

Figure  7.  Impact of data size change on clustering efficiency

下载: 全尺寸图片 幻灯片

选用数据集2、数据集7—数据集10进行实验，分析数据维度变化对聚类高效性的影响，结果见表7。根据数据集维度特点，以数据集2为对比基准，每种算法的CPU−C变化趋势如图8所示。

表  7  不同数据维度数据集的CPU−C

Table  7.  The CPU-C of dataset with different dimensions

数据集序号	维度	CPU−C/s
		算法1	算法2	算法3	算法4
2	5	5.525	4.698	4.388	4.171
7	10	6.091	5.131	4.779	4.433
8	15	6.788	5.764	5.286	4.825
9	20	7.645	6.598	5.862	5.276
10	40	10.481	10.771	8.535	7.411

下载: 导出CSV 

| 显示表格

图  8  数据维度变化对聚类高效性的影响

Figure  8.  Impact of data dimension change on clustering efficiency

下载: 全尺寸图片 幻灯片

选取数据集2、数据集11—数据集14进行实验，分析数据类个数变化对聚类高效性的影响，结果见表8。根据数据集类个数特点，以数据集2为对比基准，每种算法的CPU−C变化趋势如图9所示。

表  8  不同类个数数据集的CPU−C

Table  8.  The CPU-C of datasets with different number of class

数据集序号	类个数	CPU−C/s
		算法1	算法2	算法3	算法4
2	3	5.525	4.698	4.388	4.171
11	6	6.223	5.308	4.858	4.801
12	9	6.981	5.991	5.403	5.314
13	12	7.831	6.866	6.286	5.757
14	27	12.481	11.986	9.997	7.634

下载: 导出CSV 

| 显示表格

图  9  数据类个数变化对聚类高效性的影响

Figure  9.  Impact of data class number change on clustering efficiency

下载: 全尺寸图片 幻灯片

由表6—表8可得以下结论：与基于M−SRS的K−means算法、基于DBS的K−means算法及基于G−DBS的K−means算法相比，基于LSH−GD的K−means算法在聚类高效性方面的平均提升幅度分别为27.26%、16.81%及7.07%。

由图7—图9可得以下结论：随着数据集数据量、数据维度与数据类个数逐渐增大，聚类过程计算量逐渐增大，4种算法的聚类高效性均呈现降低趋势，但与基于M−SRS的K−means算法、基于DBS的K−means算法及基于G−DBS的K−means算法相比，基于LSH−GD的K−means算法的聚类高效性降低速率最小。

3.5   基于标准数据集的算法性能验证实验

为验证基于LSH−GD的K−means算法在面对标准数据集时的聚类准确性与高效性，选取数据集15—数据集19（UCI标准数据集）为研究对象，以筛选每个数据集数据总量的1%作为抽样目标，分别运用4种算法进行实验，获得的SSEC与CPU−C见表9。可看出，在5个数据集中，基于LSH−GD的K−means聚类算法获得的SSEC与CPU−C均为最优。

表  9  4种算法在UCI标准数据集上的SSEC与CPU−C

Table  9.  The SSEC and CPU-C of 4 algorithms on the UCI standard dataset

数据集	算法1			算法2			算法3			算法4
	SSEC	CPU−C/s		SSEC	CPU−C/s		SSEC	CPU−C/s		SSEC	CPU−C/s
Pen-based	6298.23	13.691		6717.08	13.083		5916.74	12.626		5495.61	11.764
Shuttle	2965.14	11.972		3117.25	10.836		2403.87	10.491		2214.66	10.037
Magic	2584.62	10.131		2615.54	9.451		2478.77	9.077		2398.23	8.235
Letter Recognition	1098.25	15.799		1311.87	14.082		1027.25	13.221		936.48	11.943
Statlog	2574.18	14.821		2724.83	13.187		2315.25	11.842		2080.54	10.294

下载: 导出CSV 

| 显示表格

3.6   实验结果分析

通过实验可得以下结论：面对数据量变化、数据维度变化及数据类个数变化，与其余3种算法相比，基于LSH−GD的K−means聚类算法在聚类的准确性和高效性方面均表现出明显优势，该优势在UCI标准数据集中也得到了验证。出现上述结果的原因主要有以下方面：

1) 在基于LSH−GD的K−means算法中，虽然运用LSH方法划分子数据组的复杂度大于其余3种算法，但是子数据组划分更合理，而且随着数据量增大，该合理性得到进一步体现，抽样得到的样本集可更真实地反映数据集分布规律，而且由于在子数据组划分过程中对噪声点进行了处理，样本集在聚类过程所需的迭代次数远小于其余3种算法，最终使聚类过程消耗的时间比其余3种算法短。

2) 随着数据集的数据维度逐渐增大，前3种算法的子数据组划分合理性逐步下降，但LSH的AND操作和OR操作级联组合能够很好地应对数据维度增大带来的影响，依然可保证子数据组划分的合理性，进而保证噪声点的准确筛选，使K−means聚类时的迭代次数较少。

3) 随着数据集的数据类个数逐渐增大， LSH−GD算法具有的噪声点过滤功能产生的作用逐渐明显，在算法运行过程中CPU−C的差距主要表现在K−means聚类阶段，与其余3种抽样算法生成的样本集相比， LSH−GD算法生成的样本集中各个类之间的界限清晰，为样本集进行K−means聚类时减少迭代次数建立了基础。

4.   结论

1) 基于LSH方法，提出了数据组构建算法LSH−G，该算法能够将大型数据集合理划分为子数据组，并且根据提出的噪声点筛选原则将数据集中的噪声点进行有效删除。

2) 提出了LSH−GD算法，该算法基于LSH−G子数据组构建算法优化DBS算法中的子数据组划分过程，使样本集能更真实反映原始数据集的分布规律。

3) 将LSH−GD算法融入K−means聚类算法中，使其面对大型数据集挖掘时能够减少迭代次数，同时在聚类准确性和高效性方面有更好表现。

4）实验结果表明：由10个AND操作与8个OR操作组成的级联组合为最优级联组合；在人工数据集上，与基于M−SRS的K−means算法、基于DBS的K−means算法及基于G−DBS的K−means算法相比，基于LSH−GD的K−means算法在聚类准确性方面的平均提升幅度分别为56.63%、54.59%及25.34%，在聚类高效性方面的平均提升幅度分别为27.26%、16.81%及7.07%；在UCI标准数据集上，基于LSH−GD的K−means聚类算法获得的SSEC与CPU−C均为最优。