Locality-sensitive hashing K-means algorithm for large-scale datasets
-
摘要: 大型数据集高效处理策略是煤矿安全监测智能化、采掘智能化等煤矿智能化建设的关键支撑。针对K−means算法面对大型数据集时聚类高效性及准确性不足的问题，提出了一种基于局部敏感哈希（LSH）的高效K−means聚类算法。基于LSH对抽样过程进行优化，提出了数据组构建算法LSH−G，将大型数据集合理划分为子数据组，并对数据集中的噪声点进行有效删除；基于LSH−G算法优化密度偏差抽样（DBS）算法中的子数据组划分过程，提出了数据组抽样算法LSH−GD，使样本集能更真实地反映原始数据集的分布规律；在此基础上，通过K−means算法对生成的样本集进行聚类，实现较低时间复杂度情况下从大型数据集中高效挖掘有效数据。实验结果表明：由10个AND操作与8个OR操作组成的级联组合为最优级联组合，得到的类中心误差平方和（SSEC）最小；在人工数据集上，与基于多层随机抽样（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消耗时间（CPU−C）均为最优。Abstract: Efficient processing strategy for large datasets is a key support for coal mine intelligent constructions, such as the intelligent construction of coal mine safety monitoring and mining. To address the problem of insufficient clustering efficiency and accuracy of the K-means algorithm for large datasets, a highly efficient K-means clustering algorithm based on locality-sensitive hashing (LSH) is proposed. Based on LSH, the sampling process is optimized, and a data grouping algorithm LSH-G is proposed. The large dataset is divided into subgroups and the noisy points in the dataset are removed effectively. Based on LSH-G, the subgroup division process in the density biased sampling (DBS) algorithm is optimized. And a data group sampling algorithm, LSH-GD, is proposed. The sample set can more accurately reflect the distribution law of the original dataset. On this basis, the K-means algorithm is used to cluster the generated sample set, achieving efficient mining of effective data from large datasets with low time complexity. The experimental results show that the optimal cascade combination consists of 10 AND operations and 8 OR operations, resulting in the smallest sum of squares due to error of class center (SSEC). On the artificial dataset, compared with the K-means algorithm based on multi-layer simple random sampling (M-SRS), the K-means algorithm based on DBS, and the K-means algorithm based on grid density biased sampling (G-DBS), the K-means algorithm based on LSH-GD achieves an average improvement of 56.63%, 54.59%, and 25.34% respectively in clustering accuracy. The proposed algorithm achieves an average improvement of 27.26%, 16.81%, and 7.07% in clustering efficiency respectively. On the UCI standard dataset, the K-means clustering algorithm based on LSH-GD obtains optimal SSEC and CPU time consumption (CPU-C).
-
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 numbers2.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. 实验分析
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 通过聚类的准确性和高效性对算法性能进行评价。将类中心误差平方和（The Sum of Squares due to Error of Class Center，SSEC）作为聚类准确性评价指标，将聚类过程所消耗的CPU时间（CPU Time Consumption，CPU−C）作为聚类高效性评价指标。上述2种指标均采用重复进行10次实验后计算平均值的方式获取。
$$ C = \sum\limits_{c = 1}^k {{{\left\| {{v_{c}} - {m_c}} \right\|}^2}} $$ (1) 式中：C为SSEC的值；vc为数据集经过抽样生成的样本集聚类后产生的实际中心。
给定样本集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中的函数为$$h\left( {{\boldsymbol{x}}} \right) = \left[ {\frac{{u + {\boldsymbol{t}} \cdot {\boldsymbol{x}}}}{w}} \right] $$ (2) 式中：
$ 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 $ 的合理选择范围：$$ {w \mathord{\left/ {\vphantom {w 2}} \right. } 2} \leqslant {d_{{\rm{avg}}}} \leqslant 2w \Rightarrow {{{d_{{\rm{avg}}}}} \mathord{\left/ {\vphantom {{{d_{{\rm{avg}}}}} 2}} \right. } 2} \leqslant w \leqslant 2{d_{{\rm{avg}}}} $$ (3) $$ {d_{{\rm{avg}}}} = \sqrt {\sum\limits_{q = 1}^\varepsilon {{{\left( {\frac{{{{\textit{z}}_{q\max}}{ } - {{\textit{z}}_{q\min }}}}{r}} \right)}^2}} } \\ $$ (4) 式中：
$ {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个样本集的SSECTable 2. The SSEC of 19 sample sets under different cascaded combinationsA 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 3.3 基于人工数据集的算法准确性实验
选用SSEC作为聚类准确性实验的评价指标。针对表1所示的14个人工数据集，使用算法1—算法4进行实验，分析数据量变化、数据维度变化及数据类个数变化对聚类准确性的影响。针对每个人工数据集，以筛选每个数据集数据总量的1%作为抽样目标，分别运用4种算法作用于筛选所得的数据，计算SSEC。
选用数据集1—数据集6进行实验，分析数据量变化对聚类准确性的影响，结果见表3。根据数据集数据量特点，以数据集1为对比基准，每种算法的SSEC变化趋势如图4所示。
表 3 不同数据量数据集的SSECTable 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 选用数据集2、数据集7—数据集10进行实验，分析数据维度变化对聚类准确性的影响。将获得的SSEC值转换为每个维度的平均SSEC值作为最终统计结果，见表4。根据数据集维度特点，以数据集2为对比基准，得到每种算法的SSEC变化趋势，如图5所示。
表 4 不同维度数据集的SSECTable 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 选用数据集2、数据集11—数据集14进行实验，分析数据类个数变化对聚类准确性的影响。将获得的SSEC值转换为每个类的平均SSEC值作为最终统计结果，见表5。根据数据集类个数特点，以数据集2为对比基准，得到每种算法的SSEC变化趋势，如图6所示。
表 5 不同类个数数据集的SSECTable 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 ![]()
图 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−CTable 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 选用数据集2、数据集7—数据集10进行实验，分析数据维度变化对聚类高效性的影响，结果见表7。根据数据集维度特点，以数据集2为对比基准，每种算法的CPU−C变化趋势如图8所示。
表 7 不同数据维度数据集的CPU−CTable 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 ![]()
图 8 数据维度变化对聚类高效性的影响Figure 8. Impact of data dimension change on clustering efficiency选取数据集2、数据集11—数据集14进行实验，分析数据类个数变化对聚类高效性的影响，结果见表8。根据数据集类个数特点，以数据集2为对比基准，每种算法的CPU−C变化趋势如图9所示。
表 8 不同类个数数据集的CPU−CTable 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 ![]()
图 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−CTable 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 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均为最优。
-
![]()
图 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) $ ![]()
图 2 不同级联数量情况下LSH−G算法筛选出的数据点噪声变化
Figure 2. Noise variation of data points screened by LSH-G algorithm under different cascade numbers
![]()
图 6 数据类个数变化对聚类准确性的影响
Figure 6. Impact of data class number change on clustering accuracy
![]()
图 8 数据维度变化对聚类高效性的影响
Figure 8. Impact of data dimension change on clustering efficiency
![]()
图 9 数据类个数变化对聚类高效性的影响
Figure 9. Impact of data class number change on clustering efficiency
表 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
表 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 不同数据量数据集的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 不同维度数据集的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 不同类个数数据集的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 不同数据量数据集的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 不同数据维度数据集的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 不同类个数数据集的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 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
-
[1] 杜毅博,赵国瑞,巩师鑫. 智能化煤矿大数据平台架构及数据处理关键技术研究[J]. 煤炭科学技术,2020,48(7):177-185. DOI: 10.13199/j.cnki.cst.2020.07.018 DU Yibo,ZHAO Guorui,GONG Shixin. Study on big data platform architecture of intelligent coal mine and key technologies of data processing[J]. Coal Science and Technology,2020,48(7):177-185. DOI: 10.13199/j.cnki.cst.2020.07.018
[2] 武福生,卜滕滕,王璐. 煤矿安全智能化及其关键技术[J]. 工矿自动化,2021,47(9):108-112. DOI: 10.13272/j.issn.1671-251x.17833 WU Fusheng,BU Tengteng,WANG Lu. Coal mine safety intelligence and key technologies[J]. Industry and Mine Automation,2021,47(9):108-112. DOI: 10.13272/j.issn.1671-251x.17833
[3] 胡青松,张赫男,李世银,等. 基于大数据与AI驱动的智能煤矿目标位置服务技术[J]. 煤炭科学技术,2020,48(8):121-130. DOI: 10.13199/j.cnki.cst.2020.08.015 HU Qingsong,ZHANG Henan,LI Shiyin,et al. Intelligent coal mine target location service technology based on big data and AI driven[J]. Coal Science and Technology,2020,48(8):121-130. DOI: 10.13199/j.cnki.cst.2020.08.015
[4] MAYA G P S,CHINTALA B R. Big data challenges and opportunities in agriculture[J]. International Journal of Agricultural and Environmental Information Systems,2020,11(1):48-66. DOI: 10.4018/IJAEIS.2020010103
[5] 叶鸥,窦晓熠,付燕,等. 融合轻量级网络和双重注意力机制的煤块检测方法[J]. 工矿自动化,2021,47(12):75-80. DOI: 10.13272/j.issn.1671-251x.2021030075 YE Ou,DOU Xiaoyi,FU Yan,et al. Coal block detection method integrating lightweight network and dual attention mechanism[J]. Industry and Mine Automation,2021,47(12):75-80. DOI: 10.13272/j.issn.1671-251x.2021030075
[6] 温瑞英,王红勇. 基于因子分析和K−means聚类的空中交通复杂性评价[J]. 太原理工大学学报,2016,47(3):384-388,404. DOI: 10.16355/j.cnki.issn1007-9432tyut.2016.03.020 WEN Ruiying,WANG Hongyong. Evaluation of air traffic complexity based on factor analysis and K-means clustering[J]. Journal of Taiyuan University of Technology,2016,47(3):384-388,404. DOI: 10.16355/j.cnki.issn1007-9432tyut.2016.03.020
[7] SINAGA K P,YANG M-S. Unsupervised K-means clustering algorithm[J]. IEEE Access,2020,8:80716-80727. DOI: 10.1109/ACCESS.2020.2988796
[8] BAIG A,MASOOD S,TARRAY T A. Improved class of difference-type estimators for population median in survey sampling[J]. Communications in Statistics-Theory and Methods,2019,49(23):5778-5793.
[9] LIAO Kaiyang,LIU Guizhong. An efficient content based video copy detection using the sample based hierarchical adaptive k-means clustering[J]. Journal of Intelligent Information Systems,2015,44(1):133-158. DOI: 10.1007/s10844-014-0332-5
[10] PALMER C R,FALOUTSOS C. Density biased sampling:an improved method for data mining and clustering[J]. ACM SIGMOD Record,2000,29(2):82-92. DOI: 10.1145/335191.335384
[11] HUANG Jianbin,SUN Heli,KANG Jianmei,et al. ESC:an efficient synchronization-based clustering algorithm[J]. Knowledge-Based Systems,2013,40:111-122. DOI: 10.1016/j.knosys.2012.11.015
[12] MINAEI-BIDGOLI B,PARVIN H,ALINEJAD-ROKNY H,et al. Effects of resampling method and adaptation on clustering ensemble efficacy[J]. Artificial Intelligence Review,2014,41(1):27-48. DOI: 10.1007/s10462-011-9295-x
[13] AGGARWAL A, DESHPANDE A, KANNAN R. Adaptive sampling for K-means clustering[C]. 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems/13th International Workshop on Randomization and Computation, Berkeley, 2009: 15-28.
[14] KUMAR K M,REDDY A R M. An efficient K-means clustering filtering algorithm using density based initial cluster centers[J]. Information Sciences,2017,418/419:286-301. DOI: 10.1016/j.ins.2017.07.036
[15] SÁEZ J A,KRAWCZYK B,WOŹNIAK M. Analyzing the oversampling of different classes and types of examples in multi-class imbalanced datasets[J]. Pattern Recognition,2016,57:164-178. DOI: 10.1016/j.patcog.2016.03.012
[16] 胡欢. 多维数据上近似聚集和最近邻查询的高效算法[D]. 哈尔滨: 哈尔滨工业大学, 2021. HU Huan. Efficient algorithms for approximate aggregation and nearest neighbor queries over multi-dimensional data[D]. Harbin: Harbin Institute of Technology, 2021.
[17] 李建忠. 面向社交网络的科技领域事件检测系统的研究与实现[D]. 西安: 西安电子科技大学, 2019. LI Jianzhong. Researches and implementation of technology event detection in social networks[D]. Xi'an: Xidian University, 2019.
[18] 周萌. 基于多粒度级联森林哈希学习的图像检索[D]. 重庆: 重庆邮电大学, 2019. ZHOU Meng. Multi-grained cascade forest based hashing for image retrieval[D]. Chongqing: Chongqing University of Posts and Telecommunications, 2019.
[19] NELSON K P,THISTLETON W J. Comments on "Generalized Box-Müller method for generating q-Gaussian random deviates"[J]. IEEE Transactions on Information Theory,2021,67(10):6785-6789. DOI: 10.1109/TIT.2021.3071489
[20] 谷晓忱,张民选. 一种基于FPGA的高斯随机数生成器的设计与实现[J]. 计算机学报,2011,34(1):165-173. DOI: 10.3724/SP.J.1016.2011.00165 GU Xiaochen,ZHANG Minxuan. Design and implementation of a FPGA based Gaussian random number generator[J]. Chinese Journal of Computers,2011,34(1):165-173. DOI: 10.3724/SP.J.1016.2011.00165
[21] ARNAIZ-GONZÁLEZ Á,DÍEZ-PASTOR J-F,RODRÍGUEZ J J,et al. Instance selection of linear complexity for big data[J]. Knowledge-Based Systems,2016,107:83-95. DOI: 10.1016/j.knosys.2016.05.056
-
期刊类型引用(2)
1. 季瑞翔. 一种基于视觉感知的带式输送机煤量测量方法研究. 山东煤炭科技. 2024(05): 110-114 . 
百度学术
2. 解海燕，李杰，赵国栋. 非结构化高维大数据异常流量时间点挖掘算法. 计算机仿真. 2024(07): 474-478 . 百度学术
其他类型引用(1)
计量
- 文章访问数: 308
- HTML全文浏览量: 63
- PDF下载量: 21
- 被引次数: 3
