样本聚类方法、装置、设备及存储介质

摘要

本发明实施例公开了一种样本聚类方法、装置、设备及存储介质，涉及数据处理领域，其包括：统计样本集中每个样本对应的第一样本距离，第一样本距离为样本与样本的第S近邻样本之间的距离；在全部第一样本距离中，获取设定距离范围内的第一样本距离；基于设定距离范围内的第一样本距离计算距离均值；基于每个样本对应的K近邻样本集合，确定每个样本的全部连接样本，其中，K＞S，样本与样本的连接样本为互为近邻样本且存在连接关系；根据连接样本、距离均值和S值对样本集中的样本进行聚类，距离均值为扫描半径，S值为聚类最小包含样本数。采用上述方法可以解决现有技术中DBSCAN算法对于密度不均的样本集无法合理聚类的技术问题。

权利要求

1.一种样本聚类方法，其特征在于，包括：

统计样本集中每个样本对应的第一样本距离，所述第一样本距离为所述样本与所述样本的第S近邻样本之间的距离；

在全部所述第一样本距离中，获取设定距离范围内的第一样本距离；

基于所述设定距离范围内的第一样本距离计算距离均值；

基于每个所述样本对应的K近邻样本集合，确定每个样本的全部连接样本，其中，K＞S，所述样本与所述样本的连接样本为互为近邻样本且存在连接关系；

根据所述连接样本、所述距离均值和S值对所述样本集中的样本进行聚类，所述距离均值为扫描半径，所述S值为聚类最小包含样本数。

2.根据权利要求1所述的样本聚类方法，其特征在于，所述根据所述连接样本、所述距离均值和S值对所述样本集中的样本进行聚类包括：基于所述距离均值对全部所述连接样本进行过滤，以滤除第二样本距离大于所述距离均值的连接样本，所述第二样本距离为样本与所述样本的连接样本之间的距离；

基于S值和过滤后得到的连接样本对所述样本集中的样本进行聚类。

3.根据权利要求2所述的样本聚类方法，其特征在于，所述基于S值和过滤后得到的连接样本对所述样本集中的样本进行聚类包括：依次统计每个样本的连接样本总数量；

将所述连接样本总数量大于S值的样本作为核心样本；

在得到的全部核心样本中，选择任一核心样本作为当前样本；

访问所述当前样本的全部连接样本；

将访问得到的每个连接样本分别作为顶点，并访问所述顶点对应的全部连接样本；

重复将访问得到的每个连接样本分别作为顶点，并访问所述顶点对应的全部连接样本的操作，直到访问不到新的连接样本为止；

将未被访问过的任一核心样本更新为当前样本，并返回执行访问所述当前样本的全部连接样本的操作，直到全部核心样本均被访问为止；

将所述当前样本及基于当前样本访问得到的连接样本聚类为簇。

4.根据权利要求1所述的样本聚类方法，其特征在于，所述基于每个所述样本对应的K近邻样本集合，确定每个样本的全部连接样本包括：获取每个样本对应的K近邻样本集合；

根据全部所述K近邻样本集合，构建邻接矩阵，所述邻接矩阵中每个元素代表对应两个样本间的近邻关系；

统计所述邻接矩阵中非零元素，以确定每个样本的全部连接样本。

5.根据权利要求4所述的样本聚类方法，其特征在于，所述统计所述邻接矩阵中非零元素，以确定每个样本的全部连接样本包括：在所述邻接矩阵中，获取处于对称位置的元素组，所述元素组包括第i行第j列的第一元素和第j行第i列的第二元素；

若所述第一元素和所述第二元素中包含至少一个零元素，则将所述第一元素和第二元素均设置为零元素；

遍历所述邻接矩阵的全部元素组后，更新所述邻接矩阵；

统计更新后的邻接矩阵中非零元素，并将所述非零元素对应的两个样本确定为互为近邻样本且具有连接关系；

基于所述互为近邻样本，得到每个样本的全部连接样本。

6.根据权利要求1所述的样本聚类方法，其特征在于，所述在全部所述第一样本距离中，获取设定距离范围内的第一样本距离包括：基于全部所述第一样本距离，构建频数分布直方图；

统计所述频数分布直方图中各bin的频数，以确定设定距离范围；

获取设定距离范围内的第一样本距离。

7.根据权利要求6所述的样本聚类方法，其特征在于，所述统计所述频数分布直方图中各bin的频数，以确定设定距离范围包括：获取所述频数分布直方图中频数最大bin；

计算相邻后位bin之间的频数落差，所述后位bin为所述频数分布直方图中位于频数最大bin后方的bin；

确认频数落差最大的相邻后位bin，并在所述最大的相邻后位bin中选择位于后方的bin；

将所述频数最大bin对应的第一样本距离和所述位于后方的bin对应的第一样本距离作为设定距离范围的距离阈值。

8.根据权利要求1所述的样本聚类方法，其特征在于，所述基于所述设定距离范围内的第一样本距离计算距离均值包括：获取所述第一样本距离处于所述设定距离范围内的样本数量；

对所述设定距离范围内每个第一样本距离进行相加，以得到样本总距离；

将所述样本总距离与所述样本数量的商值作为距离均值。

9.根据权利要求1所述的样本聚类方法，其特征在于，所述统计样本集中每个样本对应的第一样本距离之前，还包括：构建样本集中每个样本的K近邻图，所述K近邻图中每条边的权值为对应样本间的距离。

10.一种样本聚类装置，其特征在于，包括：距离统计模块，用于统计样本集中每个样本对应的第一样本距离，所述第一样本距离为所述样本与所述样本的第S近邻样本之间的距离；

距离获取模块，用于在全部所述第一样本距离中，获取设定距离范围内的第一样本距离；

均值计算模块，用于基于所述设定距离范围内的第一样本距离计算距离均值；

连接确定模块，用于基于每个所述样本对应的K近邻样本集合，确定每个样本的全部连接样本，其中，K＞S，所述样本与所述样本的连接样本为互为近邻样本且存在连接关系；

样本聚类模块，用于根据所述连接样本、所述距离均值和S值对所述样本集中的样本进行聚类，所述距离均值为扫描半径，所述S值为聚类最小包含样本数。

11.一种样本聚类设备，其特征在于，所述样本聚类设备包括：一个或多个处理器；

存储器，用于存储一个或多个程序；

当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如权利要求1-9中任一所述的样本聚类方法。

12.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现如权利要求1-9中任一所述的样本聚类方法。

说明书

样本聚类方法、装置、设备及存储介质

技术领域

[0001] 本发明实施例涉及数据处理技术领域，尤其涉及一种样本聚类方法、装置、设备及存储介质。

背景技术

[0002] 聚类分析指将物理或抽象对象的集合分组为由类似的对象组成的多个类的分析过程。如今，聚类分析被广泛用于各类领域中，并且随着聚类分析的广泛应用，各类聚类算法应运而生。例如，K-MEANS算法、K-MEDOIDS算法、BIRCH算法、CURE算法、DBSCAN算法、OPTICS算法等。其中，DBSCAN算法是一个比较有代表性的基于密度的聚类算法，其需要人工输入两个参数：一个为扫描半径，记为eps；另一个为最小包含点数，记为minPts，并通过两个参数在样本集中找到密度相连对象的最大集合。发明人在实现本发明的过程中，发现现有技术存在如下缺陷：基于DBSCAN算法对样本集进行聚类时，对于密度不均的样本集而言，若扫描半径较小，则对于密度稀疏的样本而言，容易被认为是噪声点而剔除，若扫描半径较大，则易将距离较远的样本聚为一类，此时，无法保证样本聚类的准确性。

[0003] 综上，如何在DBSCAN算法下，对于密度不均的样本集进行合理聚类，成为了亟待解决的问题。

发明内容

[0004] 本发明提供了一种样本聚类方法、装置、设备及存储介质，以解决现有技术中DBSCAN算法对于密度不均的样本集无法合理聚类的技术问题。

[0005] 第一方面，本发明实施例提供了一种样本聚类方法，包括：

[0006] 统计样本集中每个样本对应的第一样本距离，所述第一样本距离为所述样本与所述样本的第S近邻样本之间的距离；

[0007] 在全部所述第一样本距离中，获取设定距离范围内的第一样本距离；

[0008] 基于所述设定距离范围内的第一样本距离计算距离均值；

[0009] 基于每个所述样本对应的K近邻样本集合，确定每个样本的全部连接样本，其中，K＞S，所述样本与所述样本的连接样本为互为近邻样本且存在连接关系；

[0010] 根据所述连接样本、所述距离均值和S值对所述样本集中的样本进行聚类，所述距离均值为扫描半径，所述S值为聚类最小包含样本数。

[0011] 进一步的，所述根据所述连接样本、所述距离均值和S值对所述样本集中的样本进行聚类包括：

[0012] 基于所述距离均值对全部所述连接样本进行过滤，以滤除第二样本距离大于所述距离均值的连接样本，所述第二样本距离为样本与所述样本的连接样本之间的距离；

[0013] 基于S值和过滤后得到的连接样本对所述样本集中的样本进行聚类。

[0014] 进一步的，所述基于S值和过滤后得到的连接样本对所述样本集中的样本进行聚类包括：

[0015] 依次统计每个样本的连接样本总数量；

[0016] 将所述连接样本总数量大于S值的样本作为核心样本；

[0017] 在得到的全部核心样本中，选择任一核心样本作为当前样本；

[0018] 访问所述当前样本的全部连接样本；

[0019] 将访问得到的每个连接样本分别作为顶点，并访问所述顶点对应的全部连接样本；

[0020] 重复将访问得到的每个连接样本分别作为顶点，并访问所述顶点对应的全部连接样本的操作，直到访问不到新的连接样本为止；

[0021] 将未被访问过的任一核心样本更新为当前样本，并返回执行访问所述当前样本的全部连接样本的操作，直到全部核心样本均被访问为止；

[0022] 将所述当前样本及基于当前样本访问得到的连接样本聚类为簇。

[0023] 进一步的，所述基于每个所述样本对应的K近邻样本集合，确定每个样本的全部连接样本包括：

[0024] 获取每个样本对应的K近邻样本集合；

[0025] 根据全部所述K近邻样本集合，构建邻接矩阵，所述邻接矩阵中每个元素代表对应两个样本间的近邻关系；

[0026] 统计所述邻接矩阵中非零元素，以确定每个样本的全部连接样本。

[0027] 进一步的，所述统计所述邻接矩阵中非零元素，以确定每个样本的全部连接样本包括：

[0028] 在所述邻接矩阵中，获取处于对称位置的元素组，所述元素组包括第i行第j列的第一元素和第j行第i列的第二元素；

[0029] 若所述第一元素和所述第二元素中包含至少一个零元素，则将所述第一元素和第二元素均设置为零元素；

[0030] 遍历所述邻接矩阵的全部元素组后，更新所述邻接矩阵；

[0031] 统计更新后的邻接矩阵中非零元素，并将所述非零元素对应的两个样本确定为互为近邻样本且具有连接关系；

[0032] 基于所述互为近邻样本，得到每个样本的全部连接样本。

[0033] 进一步的，所述在全部所述第一样本距离中，获取设定距离范围内的第一样本距离包括：

[0034] 基于全部所述第一样本距离，构建频数分布直方图；

[0035] 统计所述频数分布直方图中各bin的频数，以确定设定距离范围；

[0036] 获取设定距离范围内的第一样本距离。

[0037] 进一步的，所述统计所述频数分布直方图中各bin的频数，以确定设定距离范围包括：

[0038] 获取所述频数分布直方图中频数最大bin；

[0039] 计算相邻后位bin之间的频数落差，所述后位bin为所述频数分布直方图中位于频数最大bin后方的bin；

[0040] 确认频数落差最大的相邻后位bin，并在所述最大的相邻后位bin中选择位于后方的bin；

[0041] 将所述频数最大bin对应的第一样本距离和所述位于后方的bin对应的第一样本距离作为设定距离范围的距离阈值。

[0042] 进一步的，所述基于所述设定距离范围内的第一样本距离计算距离均值包括：

[0043] 获取所述第一样本距离处于所述设定距离范围内的样本数量；

[0044] 对所述设定距离范围内每个第一样本距离进行相加，以得到样本总距离；

[0045] 将所述样本总距离与所述样本数量的商值作为距离均值。

[0046] 进一步的，所述统计样本集中每个样本对应的第一样本距离之前，还包括：

[0047] 构建样本集中每个样本的K近邻图，所述K近邻图中每条边的权值为对应样本间的距离。

[0048] 第二方面，本发明实施例还提供了一种样本聚类装置，包括：

[0049] 距离统计模块，用于统计样本集中每个样本对应的第一样本距离，所述第一样本距离为所述样本与所述样本的第S近邻样本之间的距离；

[0050] 距离获取模块，用于在全部所述第一样本距离中，获取设定距离范围内的第一样本距离；

[0051] 均值计算模块，用于基于所述设定距离范围内的第一样本距离计算距离均值；

[0052] 连接确定模块，用于基于每个所述样本对应的K近邻样本集合，确定每个样本的全部连接样本，其中，K＞S，所述样本与所述样本的连接样本为互为近邻样本且存在连接关系；

[0053] 样本聚类模块，用于根据所述连接样本、所述距离均值和S值对所述样本集中的样本进行聚类，所述距离均值为扫描半径，所述S值为聚类最小包含样本数。

[0054] 第三方面，本发明实施例还提供了一种样本聚类设备，包括：

[0055] 一个或多个处理器；

[0056] 存储器，用于存储一个或多个程序；

[0057] 当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如第一方面所述的样本聚类方法。

[0058] 第四方面，本发明实施例还提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如第一方面所述的样本聚类方法。

[0059] 上述样本聚类方法、装置、设备及存储介质，通过统计样本集中每个样本与其第S近邻样本之间的第一样本距离，并基于第一样本距离得到距离均值，同时，基于每个样本的K(K＞S)近邻样本集合，确定每个样本对应的连接样本，该连接样本与样本之间为互为近邻样本且具有连接关系，之后，基于聚类最小包含样本数(S值)以及扫描半径(距离均值)对具有连接关系的样本进行聚类的技术手段，解决了现有技术中DBSCAN算法对于密度不均的样本集无法合理聚类的技术问题，通过第一样本距离确定合理的扫描半径，之后，基于扫描半径对互为近邻样本进行聚类，保证了聚类合理性，当样本集中的样本分布密度不均时，通过互为近邻样本可以避免将稀疏分布的样本与密集分布的样本聚类成簇。同时，通过频数分布直方图确定距离均值，无需用户输入，减小了手动调参的工作量。

附图说明

[0060] 图1为本发明实施例一提供的一种样本集分布示意图；

[0061] 图2为本发明实施例一提供的一种样本聚类方法的流程图；

[0062] 图3为本发明实施例一提供的另一种样本集分布示意图；

[0063] 图4为本发明实施例二提供的一种样本聚类方法的流程图；

[0064] 图5为本发明实施例二提供的一种K近邻图；

[0065] 图6为本发明实施例二提供的一种频数分布直方图；

[0066] 图7为本发明实施例二提供的一种邻接矩阵示意图；

[0067] 图8为本发明实施例二提供的另一种邻接矩阵示意图；

[0068] 图9为本发明实施例三提供的一种样本聚类装置的结构示意图；

[0069] 图10为本发明实施例四提供的一种样本聚类设备的结构示意图。

具体实施方式

[0070] 下面结合附图和实施例对本发明作进一步的详细说明。可以理解的是，此处所描述的具体实施例用于解释本发明，而非对本发明的限定。另外还需要说明的是，为了便于描述，附图中仅示出了与本发明相关的部分而非全部结构。

[0071] DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。通常，DBSCAN需要人工输入两个参数：eps和minPts。针对样本集中的某个对象(即某个样本)而言，若eps的值为E，则将该对象的扫描半径E内的区域记为该对象的E邻域。若该对象的E邻域内的样本点数大于或等于minPts，则将该对象记为核心对象。对于样本P和样本Q，若样本Q在样本P的E邻域内，且样本P为核心对象，那么，样本Q从样本P直接密度可达。对于样本P1、样本P2、……、样本Pn，若样本Pi从样本Pi-1直接密度可达，那么样本Pn从样本P1密度可达。设定样本O到样本P密度可达，样本O到样本Q密度可达，那么样本P和样本Q密度相连。对于DBSCAN而言，其目的是找到密度相连对象的最大集合。

[0072] 对于密度不均的样本集，如图1所示的样本集，其中，图1为本发明实施例一提供的一种样本集分布示意图，参考图1，左半部分的样本较为密集，右半部分的样本较为稀疏。此时，若将eps设置较小的值，例如，将eps设置为图1中圆圈11对应的半径，此时，对于右半部分的样本而言，由于扫描不到其他样本，因此，会被认为是噪声点并滤除。这样会导致右半部分的样本大量被滤除，影响聚类准确性。若将eps设置较大的值，例如，将eps设置为图1中圆圈12对应的半径，那么，在扫描时会将左半部分和右半部分的样本聚为一类，或者，使得左半部分的大量样本聚为一类，进而影响聚类准确性。

[0073] 综上，本发明实施例提供一种样本集聚类方法，以解决对于密度不均的样本集无法合理聚类的问题。

[0074] 实施例一

[0075] 图2为本发明实施例一提供的一种样本聚类方法的流程图。实施例中提供的样本聚类方法可以由样本聚类设备执行，该样本聚类设备可以通过软件和/或硬件的方式实现，该样本聚类设备可以是两个或多个物理实体构成，也可以是一个物理实体构成。例如，样本聚类设备可以是电脑、手机、平板或交互智能平板等具有数据运算、分析能力的智能设备。

[0076] 具体的，参考图2，该样本聚类方法具体包括：

[0077] 步骤110、统计样本集中每个样本对应的第一样本距离，第一样本距离为样本与样本的第S近邻样本之间的距离。

[0078] 示例性的，样本集中包括多个样本，每个样本的数据类型相同。其中，样本的数据类型可以根据实际情况设定，实施例对此不作限定。进一步的，实施例中以对样本集中的样本进行聚类为例描述样本聚类方法。可选的，样本集的获取方式实施例不作限定，其可以是样本聚类设备自行采集的数据，也可以是用户输入的数据，还可以是对特定数据进行处理后得到的数据。通常，样本集中每个样本代表一个数据特征。例如，样本集中每个样本表示同一用户在设定周期内每天不同时间段内的位置数据。

[0079] 典型的，以图1为例，样本集中的样本散落在特征空间不同的位置。通常，样本位置与样本自身代表的特征有关，特征越相似，样本间的距离越近。可选的，预先设定特征放置规则，进而根据该规则确定样本位置。其中，特征放置规则的具体内容可以根据实际情况设定。例如，针对位置数据而言，在特征空间内划分经纬度，之后，基于各样本的位置数据包含的经纬度确定各样本在特征空间的位置。

[0080] 进一步的，获取样本集后，样本聚类设备可以计算样本集中任意两个样本之间的距离。其中，距离的计算方式实施例不作限定，例如，采用欧式距离、闵可夫斯基距离、曼哈顿距离等方式确定样本间的距离。通常，两个样本间距离越近，表明两个样本越相似。

[0081] 示例性的，样本的第S近邻样本是指距离该样本第S近的样本。针对任一样本，样本聚类设备可以计算该样本与其他样本的距离，并根据各距离，确定距离该样本第S近的样本，并记为第S近邻样本。其中，S为正整数，其具体数值可以结合实际情况设定。进一步的，S值表示聚类最小包含样本数。即对样本集聚类后得到多个簇，每个簇最少包含S个样本。一般而言，第S近邻样本的数量为1，有些情况下，第S近邻样本的数量可能是多个，此时，可以任选一个第S近邻样本。

[0082] 可选的，在确定第S近邻样本前，对每个样本绘制对应的K近邻图，其中，K为正整数且大于S，通常，K的具体数值可以根据实际情况设定。进一步的，对于某个样本的K近邻图而言，顶点为该样本，且图中包含距离该样本最近的K个近邻样本，同时，将样本与K个近邻样本分别相连，且任一连线的权值为该连线的两个样本之间的距离。举例而言，K等于8时，获取距离样本最近的8个样本，并将其分别连线，此时，连线两端的样本可以认为有连接关系，且其连线的权值为两个样本之间的距离。确定K近邻图后，便可以根据K近邻图得到样本的第S近邻样本，以及相应的距离。

[0083] 进一步的，将样本与第S近邻样本间的距离记为第一样本距离。

[0084] 步骤120、在全部第一样本距离中，获取设定距离范围内的第一样本距离。

[0085] 具体的，设定距离范围是统计第一样本距离后得到的，用于计算扫描半径时的参考数据。通常，对于样本密度不均的样本集而言，样本稀疏的区域内，第一样本距离通常较大，样本密集的区域内，第一样本距离通常较小。此时，为了保证扫描半径的准确性，需要参考设定距离范围，仅获取设定距离范围内的第一样本距离得到扫描半径。一般而言，设定距离范围内的第一样本距离是全部第一样本距离中具有代表性的数据。

[0086] 示例性的，统计每个第一样本距离对应的样本数量。其中，样本数量为50，表示存在50个样本的第一样本距离相同。进一步的，根据样本数量确定设定距离范围。例如，基于样本数量构建频数分布直方图，其中，频数分布直方图的bin的具体数量可以结合样本集的样本总数量确定。进一步的，频数分布直方图中横轴代表第一样本距离，纵轴代表第一样本距离的样本数量。获取频数分布直方图中频数最大bin，其中，频数最大bin对应的样本数量最多。之后，在频数最大bin的后位bin中，计算任意相邻两个bin之间的样本数量差值，选择差值最大的相邻两个bin。其中，后位bin是指从横轴而言位于频数最大bin后方的bin。进一步的，选择相邻两个bin中位于后方的bin，并将该后方的bin和频数最大bin对应的两个第一样本距离确定为设定距离范围的两个距离阈值。或者是，获取频数最大bin后设定位数的后位bin，并将设定位数的后位bin和频数最大bin对应的两个第一样本距离确定为设定距离范围的两个距离阈值。再如，统计每个第一样本距离对应的样本数量后，由人工基于样本数量确定设定距离范围。实施例中，以将差值最大的后方bin和频数最大bin对应的两个第一样本距离作为设定距离范围的两个距离阈值为例进行描述。其中，频数最大bin对应的第一样本距离较小，因此，将其作为设定距离范围的较小距离阈值，以在聚类时，保证扫描到足够数量特征相似的样本。差值最大的后方bin对应的第一样本距离较大，因此，将其作为设定距离范围的较大距离阈值。通常，差值最大的后方bin表明该bin对应的样本数量减少幅度最大，即说明从该bin对应的第一样本距离开始，样本数量越来越少，相应的，样本和其第S近邻样本间特征差异越来越大，因此，将该bin对应的第一样本距离作为设定距离范围的较大阈值，可以在计算扫描半径时，忽略差异较大的样本，进而保证聚类准确度。

[0087] 步骤130、基于设定距离范围内的第一样本距离计算距离均值。

[0088] 具体的，统计在设定距离范围内的全部样本及相应的第一样本距离。之后，将设定距离范围内的全部第一样本距离相加，并将相加结果记为样本总距离。同时，统计设定距离范围内的样本总数量，并将样本总距离除以样本总数量，进而将得到的商记为距离均值。此时，该距离均值表示扫描半径。

[0089] 步骤140、基于每个样本对应的K近邻样本集合，确定每个样本的全部连接样本，其中，K＞S，样本与样本的连接样本为互为近邻样本且存在连接关系。

[0090] 具体的，计算每个样本与其他各样本之间的距离后，获取与该样本距离最近的K个样本，组成该样本对应的K近邻样本集合，其中，K近邻样本集合中的每个样本可以记为近邻样本，即样本与近邻样本间存在近邻关系。如果预先构建样本的K近邻图，则本步骤可以直接获取K近邻图中的样本作为K近邻样本集合。

[0091] 进一步的，连接样本是指与当前样本具有连接关系的样本，通常，具有连接关系的两个样本可以记为互为近邻样本，互为近邻样本可以理解为两个样本对应的K近邻样本集合中均包含另一个样本。具体的，获取当前样本的K近邻样本集合，之后，再获取K近邻样本集合中每个近邻样本的K近邻样本集合。确定当前样本是否包含在每个近邻样本的K近邻样本集合中，若当前样本包含在某个近邻样本的K近邻样本集合中，则将该近邻样本和当前样本确定为互为近邻样本，并保存近邻样本和当前样本间连接关系，此时，将该近邻样本记为当前样本的连接样本。其中，保存连接关系的方式可以是在样本集中，绘制两个样本之间的连线。进一步的，按照上述步骤便可以确定每个样本对应的全部连接样本。相应的，对于K近邻样本集合中的非连接样本，可以不保存其连接关系。

[0092] 此外，还可以通过邻接矩阵的方式确定连接样本。具体的，基于K近邻样本集合构建邻接矩阵，其中，邻接矩阵中每个元素用于表示对应的两个样本是否为近邻关系。若是近邻关系，则对应的元素为非零元素，若不是近邻关系，则对应的元素为零元素。进一步的，确定邻接矩阵中任一组位置对称的元素是否均为非零元素，若是，则说明两个样本对应的K近邻样本集合中均包含另一个样本，即两个样本为互为近邻样本且具有连接关系。遍历邻接矩阵的全部对称元素后，便可以确定每个样本的连接样本。

[0093] 举例而言，图3为本发明实施例一提供的另一种样本集示意图。参考图3，K为5，对于样本A，其K近邻样本集合包含与样本A为实线连接的5个样本，其中，有两个样本与样本A的连线部分重合。对于样本B，其K近邻样本集合包含与样本B为实线连接的4个样本以及样本A。虽然样本B的K近邻样本集合中包含样本A，但是样本A的K近邻样本集合中不包含样本B，因此，样本B和样本A不是互为近邻样本，此时不保存样本A和样本B的连接关系。按照上述方式遍历全部样本后，便可以得到与每个样本具有连接关系的连接样本。

[0094] 需要说明的是，实施例不限定步骤140与步骤110-步骤130的执行顺序，实际应用中，也可以先执行步骤140，再执行步骤110-步骤130，或者是步骤140与步骤110-步骤130同步执行。

[0095] 步骤150、根据连接样本、距离均值和S值对样本集中的样本进行聚类，距离均值为扫描半径，S值为聚类最小包含样本数。

[0096] 其中，聚类最小包含样本数为minPts。示例性的，将距离均值作为扫描半径，将S值作为minPts对样本集中的样本进行DBSCAN聚类。具体的，选择某个样本作为当前样本，之后，以距离均值作为扫描半径对当前样本的周围区域进行扫描。此时，在扫描过程中，仅获取当前样本的连接样本，之后，若连接样本的数量大于S，则将当前样本和扫描得到的连接样本聚类为簇。

[0097] 或者是，确定每个样本的连接样本总数量，若连接样本总数量大于S，则将该样本作为核心样本。遍历样本集中的全部样本后，找到全部的核心样本。之后，任选一核心样本作为当前样本，并获取当前样本的全部连接样本。进一步的，将获取到的连接样本作为顶点，继续获取每个连接样本的全部连接样本，之后，再将获取到的连接样本作为顶点，并继续获取其对应的全部连接样本，重复此操作，直到遍历不到新的连接样本为止，此时，将得到的全部连接样本和当前样本聚类为簇。之后，获取未被处理的核心样本，并继续按照上述步骤得到连接样本，进而形成新的簇。当确定每个核心样本均被处理后，确定聚类结束。可以理解的是，在聚类过程中，若获取的某个连接样本为核心样本，则在后续过程中，不会再对该核心样本进行任何处理。

[0098] 此时，针对于图3的样本集而言，在聚类的过程，样本A和样本B不会聚类成簇，样本A会与其特征相似且密度较密集的其他样本进行聚类，样本B会与其特征相似且密度较稀疏的其他样本进行聚类，保证了聚类合理性。

[0099] 上述，通过统计样本集中每个样本与其第S近邻样本之间的第一样本距离，并基于第一样本距离得到距离均值，同时，基于每个样本的K(K＞S)近邻样本集合，确定每个样本对应的连接样本，该连接样本与样本之间为互为近邻样本且具有连接关系，之后，基于聚类最小包含样本数(S值)以及扫描半径(距离均值)对具有连接关系的样本进行聚类的技术手段，解决了现有技术中DBSCAN算法对于密度不均的样本集无法合理聚类的技术问题，通过第一样本距离确定合理的扫描半径，之后，基于扫描半径对互为近邻样本进行聚类，保证了聚类合理性，当样本集中的样本分布密度不均时，通过互为近邻样本可以避免将稀疏分布的样本与密集分布的样本聚类成簇，进而保证聚类准确性。

[0100] 实施例二

[0101] 图4为本发明实施例二提供的一种样本聚类方法的流程图。本实施例是在上述实施例的基础上进行具体化。参考图4，本实施例提供的样本聚类方法包括：

[0102] 步骤201、构建样本集中每个样本的K近邻图，K近邻图中每条边的权值为对应样本间的距离。

[0103] 具体的，计算每个样本与其他各样本之间的距离后，绘制某个样本的K近邻图时，将该样本作为顶点，并根据样本之间的距离获取距该样本最近的K个样本以及对应的距离。之后，分别绘制顶点与K个样本的连线，并将顶点与对应样本的距离作为该连线的权值。举例而言，图5为本发明实施例二提供的一种K近邻图。参考图5，其为图3中样本C的K近邻图，其中，K为6，根据样本C与其他样本的距离获取距离样本C最近的K个样本以及距离，之后，绘制样本C与K个样本的连线，并将距离作为连线的权值。需要说明的是，图5中示出的连线的权值仅用于描述K近邻图，并非对距离或距离计算的限定。实际应用中，权值可以不示于K近邻图中。一般而言，基于K近邻图，可以得到样本集中各样本之间的连线关系，即近邻关系。

[0104] 需要说明的是，构建K近邻图的好处是便于后续确定第一样本距离、连接样本等，即便于后续计算。

[0105] 步骤202、统计样本集中每个样本对应的第一样本距离，第一样本距离为样本与样本的第S近邻样本之间的距离。

[0106] 由于S＜K，因此，可以在每个样本的K近邻图中，获取距离其最近的第S近邻样本，并根据样本和第S近邻样本的连线的权值确定第一样本距离。

[0107] 步骤203、基于全部第一样本距离，构建频数分布直方图。

[0108] 具体的，统计每个第一样本距离的出现次数，并将该次数作为对应第一样本距离的频数，之后，基于各频数构建频数分布直方图。实际应用中，考虑到存在数值很接近的第一样本距离，例如，两个第一样本距离分别为0.585和0.593，其具体的数值比较接近，此时，若每个第一样本距离对应一个频数，会增加统计复杂度及频数分布直方图复杂度，因此。实施例中，预先对第一样本距离进行分组，之后，统计在每个分组内第一样本距离的出现次数，并将出现次数作为该分组对应的频数。例如，距离0.55-0.65的分组内有1100个第一样本距离，因此，该分组对应的频数为1100。需要说明的是，分组规则实施例不作限定。进一步的，在建立频数分布直方图时，用横坐标表示距离(本示例中为第一样本距离)，纵坐标表示样本数(即频数)。此时，每个距离分组可以记为一个bin。通常，bin的数量跟样本集的样本总数量相关。例如，样本集的样本总数量在5000以下，此时，bin的数量可以设为10，样本总数量超过5000后，设定每增加500个样本，bin的数量增加1。可选的，考虑到有些分组内频数很少，在后续计算时，其参考意义较低，因此，可以结合实际情况，忽略该距离分组的频数。

[0109] 例如，图6为本发明实施例二提供的一种频数分布直方图。参考图6，该频数分布直方图的横坐标为距离，纵坐标为样本数，即频数，且bin为10。由图6可知每个bin对应的距离范围以及频数，并且，bin从1至10顺序排列。

[0110] 设置频数分布直方图的好处是，清楚显示各距离范围内频数分布情况，以及易于显示各距离范围之间频数的差别。

[0111] 步骤204、统计频数分布直方图中各bin的频数，以确定设定距离范围。

[0112] 实施例中，设定基于各bin的频数确定设定距离范围。此时，该步骤具体包括步骤2041-步骤2044：

[0113] 步骤2041、获取频数分布直方图中频数最大bin。

[0114] 具体的，统计各距离范围对应的频数，之后，获取最大的频数对应的bin，并记为频数最大bin。例如，参考图6，基于纵坐标确定频数最大bin为5。

[0115] 步骤2042、计算相邻后位bin之间的频数落差，后位bin为频数分布直方图中位于频数最大bin后方的bin。

[0116] 示例性的，根据bin的排列顺序，将位于某个bin后方的任一bin记为该bin的后位bin。实施例中，获取频数最大bin的全部后位bin。以图6为例，频数最大bin的后位bin为第6个bin至第10个bin。

[0117] 进一步的，相邻bin是指顺序相邻的两个bin，例如，图6中，第1个bin和第2个bin为相邻bin，第2个bin和第3个bin为相邻bin，依次类推。实施例中，获取后位bin中的相邻bin，并计算相邻bin中两个bin的频数差值，其中，频数差值为正数且记为频数落差。在计算频数差值时，可以是对相邻的两个bin对应的频数做减法，若结果为正数，则直接将该结果作为频数落差，若结果为负数，则将该结果的绝对值作为频数落差。

[0118] 可选的，实施例中，统计频数落差时，还可以计算频数最大bin与其相邻后位bin之间的频数落差，并将该频数落差与各相邻后位bin之间的频数落差一同作为本步骤的计算结果。

[0119] 步骤2043、确认频数落差最大的相邻后位bin，并在最大的相邻后位bin中选择位于后方的bin。

[0120] 通常，频数落差越大，表明相邻bin中位于后方的bin与位于前方的bin之间的频数相差越多，进而确定相邻bin中位于后方的bin对应的样本数量明显减少。实施例中，统计各频数落差后，选择频数落差最大的相邻后位bin，此时，在该相邻后位bin中，位于后方的bin对应的样本数量明显减少，且位于该bin后方的bin对应的样本数量很少，其代表性较低，在计算距离均值时，对准确性贡献较小，因此，可以在计算时可以忽略不计。据此，实施例中设定选择频数落差最大的相邻后位bin中位于后方的bin作为本步骤的计算结果。举例而言，参考图6，分别计算第6个bin与第7个bin之间的频数落差、第7个bin与第8个bin之间的频数落差、第8个bin与第9个bin之间的频数落差以及第9个bin与第10个bin之间的频数落差。计算各频数落差后，确定，第6个bin与第7个bin之间频数落差的频数落差最大，此时，选择位于后方的第7个bin。

[0121] 步骤2044、将频数最大bin对应的第一样本距离和位于后方的bin对应的第一样本距离作为设定距离范围的距离阈值。

[0122] 具体的，由于每个bin对应一个距离范围，因此，确定设定距离范围时，可以是选择每个距离范围的最小值作为距离阈值。例如，频数最大bin对应的距离范围的最小值作为设定距离范围中小的距离阈值，将后方的bin对应的距离范围的最小值作为设定距离范围中大的距离阈值。也可以是选择每个距离范围的最大值作为距离阈值。例如，频数最大bin对应的距离范围的最大值作为设定距离范围中小的距离阈值，将后方的bin对应的距离范围的最大值作为设定距离范围中大的距离阈值。还可以是结合实际情况，选择频数最大bin对应的距离范围的最小值作为设定距离范围中小的距离阈值，将后方的bin对应的距离范围的最大值作为设定距离范围中大的距离阈值。例如，参考图6，将第5个bin对应的距离范围中的最小值作为设定距离范围中的小的距离阈值，将第7个bin对应的距离范围中的最大值作为设定距离范围中的大的距离阈值。也可以是确定每个距离范围的居中距离值，并将居中距离值作为距离阈值。

[0123] 通常，将频数最大bin对应的第一样本距离和位于后方的bin对应的第一样本距离作为设定距离范围的距离阈值的好处是，后续计算距离均值后，可以保证通过该距离均值聚类到较多样本，且滤除距离较远的样本，即保证了距离均值的合理性。

[0124] 可以理解的是，步骤2041-步骤2044仅为确定设定距离范围的可选方式。实际应用中，还可以结合频数分布直方图采用其他方式确定设定距离范围。

[0125] 步骤205、获取设定距离范围内的第一样本距离。

[0126] 步骤206、获取第一样本距离处于设定距离范围内的样本数量。

[0127] 具体的，由于一个样本对应一个第一样本距离。因此，可以统计在设定距离范围内的第一样本距离的总个数，并将总个数作为样本数量。也可以结合频数分布直方图确定样本数量，此时，将频数最大bin以及位于后方的bin之间的各bin对应的频数相加，以得到样本数量。例如，参考图6，将第5个bin、第6个bin以及第7个bin对应的频数相加，便可以得到样本数量。

[0128] 步骤207、对设定距离范围内每个第一样本距离进行相加，以得到样本总距离。

[0129] 具体的，将设定距离范围内的每个第一样本距离相加，并将结果记为样本总距离。或者是，基于频数分布直方图得到样本总距离，此时，可以将对应bin的频数乘以对应距离范围的居中距离值，之后，在再将得到的结果相加，进而得到样本总距离。例如，参考图6，获取第5个bin对应距离范围，之后，选择距离范围的居中距离值。将第5个bin对应的居中距离值和频数相乘得到第一结果，之后，按照同样的计算方式得到第6个bin对应的第二结果以及第7个bin对应的第三结果，之后，将三个结果相加，以得到样本总距离。

[0130] 步骤208、将样本总距离与样本数量的商值作为距离均值。

[0131] 具体的，用样本总距离除以样本数量，便可以得到设定距离范围内第一样本距离的平均距离。实施例中，将平均距离记为距离均值，并将距离均值设置为扫描半径。相比于现有DBSCAN算法中人为指定扫描半径，本实施例可以集合样本集的实际情况自适应得到扫描半径，且利用了统计学原理确定扫描半径，保证了扫描半径的合理性。

[0132] 步骤209、获取每个样本对应的K近邻样本集合。

[0133] 具体的，基于每个样本的K近邻图，获取每个样本的K个近邻样本，并组成K近邻样本集合。即将K近邻图中除顶点外的全部样本组成顶点的K近邻样本集合。

[0134] 步骤210、根据全部K近邻样本集合，构建邻接矩阵，邻接矩阵中每个元素代表对应两个样本间的近邻关系。

[0135] 其中，邻接矩阵是用一个一维数组存放样本集所有样本；用一个二维数组存放样本集间关系的数据。邻接矩阵可以分为有向图邻接矩阵和无向图邻接矩阵。实施例中，以无向图邻接矩阵为例。具体的，将每个样本按顺序排列，排列后，每个样本对应一个编号。其中，排列规则实施例不做限定。进一步的，将排列后的样本分别作为矩阵的横轴和纵轴，之后，用横轴和纵轴的交点元素表明对应两个样本之间是否为近邻关系。具体的，若某个样本包含在另一个样本的K近邻样本集合中，则该样本与另一个样本为近邻关系，此时，将以该样本为纵坐标，另一个样本为横坐标的交点元素记为非零元素。其中，非零元素的具体值可以根据实际情况设定。实施例中，以非零元素为1为例。实际应用中，非零元素还可以为对应的距离值，或其他数值。相应的，若某个样本不包含在另一个样本的K近邻样本集合中，则该样本与另一个样本为非近邻关系，此时，将以该样本为纵坐标，另一个样本为横坐标的交点元素记为零元素，即记为0。举例而言，图7为本发明实施例二提供的一种邻接矩阵示意图。参考图7，当前共有8个样本，此时，将8个样本按顺序赋予1-8编号。之后，在横轴和纵轴上排列的8个样本，即将8个样本编号作为横坐标和纵坐标，之后，根据样本间的近邻关系构建二维矩阵。此时，二维矩阵中第i行第j列的元素表明第j个样本是否为第i个样本的近邻样本。
例如，第2行第3列的元素为1，则表明编号为2的样本对应的K近邻样本集合中包含编号为3的样本。再如，第7行第1列的元素为0，则表明编号为7的样本对应的K近邻样本集合中不包含编号为1的样本。通常，确定K近邻样本集合后，便可以根据K近邻样本集合为邻接矩阵内的元素进行赋值。通常，第i行第i列的元素表明样本与自身的连接关系，实施例中，将该元素记为1。可以理解的是，图7中横向的1-8编号和纵向的1-8编号为样本编号，不计在行数和列数中。

[0136] 可选的，实际应用中，样本集包含很多的样本，此时，可以基于每个样本构建一个邻接矩阵，并将相应样本及对应的K近邻样本集合中的样本作为邻接矩阵的横轴和纵轴，通过该邻接矩阵可以确定样本与K个近邻样本间的近邻关系。或者是，基于样本集构建一个邻接矩阵。此时，通过该邻接矩阵可以确定样本集中各样本间的近邻关系。

[0137] 步骤211、统计邻接矩阵中非零元素，以确定每个样本的全部连接样本。

[0138] 具体的，若某个样本的K近邻样本集合包含另一样本，而另一样本的K近邻样本集合不包含该样本，则确定两个样本为非互为近邻样本，在聚类时可以忽略。因此，需要找到全部的互为近邻样本，并基于互为近邻样本确定各样本的连接样本。实施例中，通过邻接矩阵中的非零元素确定互为近邻样本。例如，两个样本的编号分别为5和6，并记为样本5和样本6。此时，邻接矩阵中，第5行第6列的元素表明样本5的K近邻样本集合中是否包含样本6，第6行第5列的元素表明样本6的K近邻样本集合中是否包含样本5。若两个元素均为非零元素，则说明样本5和样本6相互包含，即样本5和样本6为互为近邻样本，且保存样本5和样本6的连接关系，此时，将样本5记为样本6的连接样本，同样，将样本6记为样本5的连接样本。按照上述方式，统计每个非零元素，便可以得到每个样本的连接样本。

[0139] 可选的，实施例中，在统计非零元素时，设定该步骤具体包括步骤2111-步骤2115：

[0140] 步骤2111、在邻接矩阵中，获取处于对称位置的元素组，元素组包括第i行第j列的第一元素和第j行第i列的第二元素。

[0141] 具体的，将邻接矩阵中处于对称位置的两个元素记为元素组。其中，对称位置是指横纵坐标相反的两个位置。例如，第i行第j列和第j行第i列为对称位置，此时，将两个对称位置对应的元素记为一个元素组。进一步的，将第i行第j列的元素记为第一元素，其表明第i个样本对应的K近邻样本集合中是否包含第j个样本。将第j行第i列的元素记为第二元素，其表明第j个样本对应的K近邻样本集合中是否包含第i个样本。通过获取对称位置的元素组，便可以得到对应两个样本间的近邻关系。

[0142] 步骤2112、若第一元素和第二元素中包含至少一个零元素，则将第一元素和第二元素均设置为零元素。

[0143] 进一步的，确定第一元素和第二元素中是否包含至少一个零元素，若第一元素和第二元素中包含至少一个零元素，则将第一元素和第二元素均设置为零元素，否则，保持第一元素和第二元素不变，并执行步骤2123。其中，第一元素和第二元素中包含至少一个零元素表明对应的两个样本中至少有一个样本的K近邻样本集合中不包含另一个样本，即两个样本为非互为近邻样本。此时，将第一元素和第二元素均修改为零元素，即取消两个元素间的近邻关系。举例而言，参考图7，第1行第8列的第一元素为1，第8行第1列的第二元素为0，且第一元素和第二元素属于对称位置的元素组，因此，将第1行第8列的第一元素修改为0，即取消样本1和样本8的近邻关系。

[0144] 步骤2113、遍历邻接矩阵的全部元素组后，更新邻接矩阵。

[0145] 具体的，遍历处于对称位置的全部元素组后，更新邻接矩阵。以图7中所示的邻接矩阵为例，此时，遍历图7中的全部元素组后，更新该邻接矩阵，并得到图8所示的邻接矩阵。其中，图8为本发明实施例二提供的另一种邻接矩阵示意图。

[0146] 步骤2114、统计更新后的邻接矩阵中非零元素，并将非零元素对应的两个样本确定为互为近邻样本且具有连接关系。

[0147] 具体的，更新后的邻接矩阵中任一非零元素对应的两个样本为互为近邻样本。因此，基于更新后的邻接矩阵中的非零元素，边可以确定全部互为近邻样本。进一步的，考虑到更新后的邻接矩阵为对称化的邻接矩阵，因此，在获取非零元素时，可以仅获取对称位置中的一个非零元素，并根据该非零元素确定两个样本为互为近邻样本。确定互为邻近样本后，可以在样本集中保留互为近邻样本间的连线。

[0148] 步骤2115、基于互为近邻样本，得到每个样本的全部连接样本。

[0149] 具体的，获取包含某个样本的全部互为近邻样本，并将获取的全部互为近邻样本中的另一样本作为该样本的全部连接样本。

[0150] 步骤212、基于距离均值对全部连接样本进行过滤，以滤除第二样本距离大于距离均值的连接样本，第二样本距离为样本与样本的连接样本之间的距离。

[0151] 具体的，实施例中将样本与其对应的连接样本之间的距离记为第二样本距离，即将互为近邻样本间的距离记为第二样本距离。进一步的，若第二样本距离大于距离均值，则说明对应的两个样本虽然为互为近邻样本，但是其具体的特征差异较大，若聚类在一起会影响聚类结果的准确性。因此，实施例中设定剔除两个样本的连接关系，即将两个样本确定为非互为近邻样本。此时，可以在样本集中删除两个样本间的连线。同时，将邻接矩阵中对应的元素调整为零元素。可以理解的是，按照上述方式便可以过滤每个样本对应的连接样本，且仅保留小于距离均值的连接样本。此时，该步骤也可以理解为基于扫描半径对样本集中各样本的连接关系进行扫描，以得到准确的连接关系。

[0152] 步骤213、基于S值和过滤后得到的连接样本对样本集中的样本进行聚类。

[0153] 具体的，该步骤包括步骤2131-步骤2139：

[0154] 步骤2131、依次统计每个样本的连接样本总数量。

[0155] 具体的，根据样本集中各样本间的连线，确定每个样本的连线总数量，进而得到连接样本总数量。一般而言，每个样本对应的连接样本总数量为基于距离均值过滤后保留的连接样本的总数量。可以理解的是，实际应用中，也可以仅记录互为相邻样本间的连接关系，而不在样本集中体现。此时，可以根据记录的连接关系确定每个样本的连接样本，进而得到连接样本总数量。

[0156] 步骤2132、将连接样本总数量大于S值的样本作为核心样本。

[0157] 具体的，将每个样本的连接样本总数量与S值进行比较，若连接样本总数量大于S值，则将对应样本记为核心样本。按照上述方式，遍历每个样本后，便可以得到样本集中的全部核心样本。其中，核心样本可以理解为聚类过程中，可以作为起始点的样本。通常，每个样本及其连接样本因为特征相似度较高，通常会被聚类为一簇，若某个样本的总数量小于S值，则说明后续聚类得到的簇中存在样本数量低于聚类最小包含样本数的可能，因此，在聚类时，不会选择该样本作为起始点，即不会选择该样本作为核心样本。

[0158] 步骤2133、在得到的全部核心样本中，选择任一核心样本作为当前样本。

[0159] 具体的，任选一个核心样本作为本次聚类的起始点，并记为当前样本。需要说明的是，实施例中，以随机方式确定当前样本。实际应用中，还可以设定当前样本选择规则，并通过该规则选择当前样本。通常，确定当前样本后，将该核心样本标记为被访问过。

[0160] 步骤2134、访问当前样本的全部连接样本。

[0161] 具体的，根据当前保留的连接关系，获取与当前样本具有连接关系的全部连接样本，并将获取的全部连接样本标记为被访问过。

[0162] 步骤2135、将访问得到的每个连接样本分别作为顶点，并访问顶点对应的全部连接样本。

[0163] 进一步的，将当前得到的每个连接样本分别作为一个顶点，之后，根据当前保留的连接关系，继续获取与每个顶点具有连接关系的全部连接样本。此时，每个顶点也可以认为一次聚类中的子起始点。

[0164] 步骤2136、确认是否访问得到新的连接样本。若访问得到新的连接样本，则返回执行步骤2135，若访问不到新的连接样本，则执行步骤2137。

[0165] 具体的，根据当前保留的连接关系，继续获取与每个顶点具有连接关系的全部连接样本时，确定是否得到新的连接样本，即是否得到没有标记为被访问过的连接样本。若得到新的连接样本，则说明当前还有新的特征相似的样本，此时，可以返回执行步骤2135，即将新得到的连接样本作为顶点，继续访问该顶点的全部连接样本，直到得不到新的连接样本为止。若得不到新的连接样本，则说明当前已经找到基于核心样本的全部特征相似的样本。此时，可以认为本次聚类结束，并执行2137。

[0166] 需要说明的是，在本次聚类过程中，若某个核心样本被认为是连接样本，则将该核心样本标记为被访问过的样本。

[0167] 步骤2137、确认是否还存在未被访问的核心样本。若存在，则执行步骤2138，否则，执行2139。

[0168] 具体的，确定当前是否还有未被访问的核心样本，即确定当前是否还有未被标记为被访问过的核心样本。若存在未被访问的核心样本，则将该核心样本更新为当前样本，并开始新一次的聚类过程，即执行步骤2138。若确认核心样本均被访问过，则说明当前已经访问了全部可被聚类的起始点，无法再找到聚类起始点，因此，执行步骤2139。

[0169] 步骤2138、将未被访问过的任一核心样本更新为当前样本。返回执行步骤2134。

[0170] 具体的，若未被访问过的核心样本数量大于1，则采用随机的方式选定当前样本。若未被访问过的核心样本数量为1，则将该核心样本作为当前样本。之后，返回执行步骤
2134，即开始一次新的聚类。

[0171] 步骤2139、将当前样本及基于当前样本访问得到的连接样本聚类为簇。

[0172] 具体的，一次聚类过程可以认为是一个访问过程，此时，设定将每次聚类得到的全部连接样本和当前样本聚类为一簇。通常，对于样本集而言，存在几次聚类过程便可以得到相应数量的簇。可选的，将始终未被访问过的样本记为噪声点。

[0173] 举例而言，针对于图3的样本集而言，样本B的K(K＝5)近邻样本集合中包含样本A，样本A的K近邻样本集合中包含样本B，此时，样本A和样本B间的连接关系会被踢出，即删除样本A和样本B间虚线。在后续聚类过程中，无论访问样本A的连接样本还是访问样本B的连接样本，均不会将样本A和样本B聚类成簇，进而保证了聚类合理性。

[0174] 上述，通过构建每个样本的K近邻图，基于K近邻图获取第一样本距离，其中，第一样本距离为样本与第S(S＜K)近邻样本之间的距离，之后，基于第一样本距离构建频数分布直方图，并根据频数分布直方图确定距离均值，同时，基于K近邻图构建邻接矩阵，并对称邻接矩阵，以确定具有连接关系的样本，之后，通过距离均值对具有连接关系的样本进行过滤，并基于过滤后的连接关系以及S值对样本集进行聚类的技术手段，解决了现有技术中DBSCAN算法对于密度不均的样本集无法合理聚类的技术问题，通过对称邻接矩阵及基于距离均值过滤具有连接关系的样本的方式，可以在样本的分布密度不均时，避免不同密度的样本聚成一个簇，影响聚类准确性。同时，通过频数分布直方图确定距离均值，无需用户输入，减小了手动调参的工作量，并且通过统计的方式确定距离均值，保证了距离均值的合理性，进而保证聚类准确性。

[0175] 实施例三

[0176] 图9为本发明实施例三提供的一种样本聚类装置的结构示意图。参考图9，该样本聚类装置包括：距离统计模块301、距离获取模块302、均值计算模块303、连接确定模块304以及样本聚类模块305。

[0177] 其中，距离统计模块301，用于统计样本集中每个样本对应的第一样本距离，所述第一样本距离为所述样本与所述样本的第S近邻样本之间的距离；距离获取模块302，用于在全部所述第一样本距离中，获取设定距离范围内的第一样本距离；均值计算模块303，用于基于所述设定距离范围内的第一样本距离计算距离均值；连接确定模块304，用于基于每个所述样本对应的K近邻样本集合，确定每个样本的全部连接样本，其中，K＞S，所述样本与所述样本的连接样本为互为近邻样本且存在连接关系；样本聚类模块305，用于根据所述连接样本、所述距离均值和S值对所述样本集中的样本进行聚类，所述距离均值为扫描半径，所述S值为聚类最小包含样本数。

[0178] 上述，通过统计样本集中每个样本与其第S近邻样本之间的第一样本距离，并基于第一样本距离得到距离均值，同时，基于每个样本的K(K＞S)近邻样本集合，确定每个样本对应的连接样本，该连接样本与样本之间为互为近邻样本且具有连接关系，之后，基于聚类最小包含样本数(S值)以及扫描半径(距离均值)对具有连接关系的样本进行聚类的技术手段，解决了现有技术中DBSCAN算法对于密度不均的样本集无法合理聚类的技术问题，通过第一样本距离确定合理的扫描半径，之后，基于扫描半径对互为近邻样本进行聚类，保证了聚类合理性，当样本集中的样本分布密度不均时，通过互为近邻样本可以避免将稀疏分布的样本与密集分布的样本聚类成簇，进而保证聚类准确性。

[0179] 在上述实施例的基础上，样本聚类模块305包括：样本过滤子模块，用于基于所述距离均值对全部所述连接样本进行过滤，以滤除第二样本距离大于所述距离均值的连接样本，所述第二样本距离为样本与所述样本的连接样本之间的距离；聚类子模块，用于基于S值和过滤后得到的连接样本对所述样本集中的样本进行聚类。

[0180] 在上述实施例的基础上，聚类子模块包括：总数量统计单元，用于依次统计每个样本的连接样本总数量；核心样本确定单元，用于将所述连接样本总数量大于S值的样本作为核心样本；当前样本选择单元，用于在得到的全部核心样本中，选择任一核心样本作为当前样本；第一访问单元，用于访问所述当前样本的全部连接样本；第二访问单元，用于将访问得到的每个连接样本分别作为顶点，并访问所述顶点对应的全部连接样本；第三访问单元，用于重复将访问得到的每个连接样本分别作为顶点，并访问所述顶点对应的全部连接样本的操作，直到访问不到新的连接样本为止；样本更新单元，用于将未被访问过的任一核心样本更新为当前样本，并返回执行访问所述当前样本的全部连接样本的操作，直到全部核心样本均被访问为止；簇聚类单元，用于将所述当前样本及基于当前样本访问得到的连接样本聚类为簇。

[0181] 在上述实施例的基础上，连接确定模块304包括：集合获取子模块，用于获取每个样本对应的K近邻样本集合；邻接矩阵构建子模块，用于根据全部所述K近邻样本集合，构建邻接矩阵，所述邻接矩阵中每个元素代表对应两个样本间的近邻关系；非零元素统计子模块，用于统计所述邻接矩阵中非零元素，以确定每个样本的全部连接样本。

[0182] 在上述实施例的基础上，非零元素统计子模块包括：元素组获取单元，用于在所述邻接矩阵中，获取处于对称位置的元素组，所述元素组包括第i行第j列的第一元素和第j行第i列的第二元素；置零单元，用于若所述第一元素和所述第二元素中包含至少一个零元素，则将所述第一元素和第二元素均设置为零元素；矩阵更新单元，用于遍历所述邻接矩阵的全部元素组后，更新所述邻接矩阵；近邻关系确定单元，用于统计更新后的邻接矩阵中非零元素，并将所述非零元素对应的两个样本确定为互为近邻样本且具有连接关系；连接样本确定单元，用于基于所述互为近邻样本，得到每个样本的全部连接样本。

[0183] 在上述实施例的基础上，距离获取模块302包括：直方图构建子模块，用于基于全部所述第一样本距离，构建频数分布直方图；频数统计子模块，用于统计所述频数分布直方图中各bin的频数，以确定设定距离范围；第一距离获取子模块，用于获取设定距离范围内的第一样本距离。

[0184] 在上述实施例的基础上，频数统计子模块包括：最大bin获取单元，用于获取所述频数分布直方图中频数最大bin；落差计算单元，用于计算相邻后位bin之间的频数落差，所述后位bin为所述频数分布直方图中位于频数最大bin后方的bin；bin确认单元，用于确认频数落差最大的相邻后位bin，并在所述最大的相邻后位bin中选择位于后方的bin；阈值确定单元，用于将所述频数最大bin对应的第一样本距离和所述位于后方的bin对应的第一样本距离作为设定距离范围的距离阈值。

[0185] 在上述实施例的基础上，均值计算模块303包括：样本数量获取子模块，用于获取所述第一样本距离处于所述设定距离范围内的样本数量；总距离子模块，用于对所述设定距离范围内每个第一样本距离进行相加，以得到样本总距离；商值计算子模块，用于将所述样本总距离与所述样本数量的商值作为距离均值。

[0186] 在上述实施例的基础上，还包括：K近邻图构建模块，用于统计样本集中每个样本对应的第一样本距离之前，构建样本集中每个样本的K近邻图，所述K近邻图中每条边的权值为对应样本间的距离。

[0187] 本发明实施例提供的样本聚类装置包含在样本聚类设备中，且可用于执行上述任意实施例提供的样本聚类方法，具备相应的功能和有益效果。

[0188] 实施例四

[0189] 图10为本发明实施例四提供的一种样本聚类设备的结构示意图。如图10所示，该样本聚类设备包括处理器40、存储器41、输入装置42以及输出装置43；样本聚类设备中处理器40的数量可以是一个或多个，图10中以一个处理器40为例；样本聚类设备中的处理器40、存储器41、输入装置42以及输出装置43可以通过总线或其他方式连接，图10中以通过总线连接为例。

[0190] 存储器41作为一种计算机可读存储介质，可用于存储软件程序、计算机可执行程序以及模块，如本发明实施例中的样本聚类方法对应的程序指令/模块(例如，样本聚类装置中的距离统计模块301、距离获取模块302、均值计算模块303、连接确定模块304和样本聚类模块305)。处理器40通过运行存储在存储器41中的软件程序、指令以及模块，从而执行样本聚类设备的各种功能应用以及数据处理，即实现上述的样本聚类方法。

[0191] 存储器41可主要包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需的应用程序；存储数据区可存储根据样本聚类设备的使用所创建的数据等。此外，存储器41可以包括高速随机存取存储器，还可以包括非易失性存储器，例如至少一个磁盘存储器件、闪存器件、或其他非易失性固态存储器件。在一些实例中，存储器41可进一步包括相对于处理器40远程设置的存储器，这些远程存储器可以通过网络连接至样本聚类设备。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。

[0192] 输入装置42可用于接收输入的数字或字符信息，以及产生与样本聚类设备的用户设置以及功能控制有关的键信号输入。输出装置43可包括显示屏等显示设备。

[0193] 上述样本聚类设备包含样本聚类装置，可以用于执行任意样本聚类方法，具备相应的功能和有益效果。

[0194] 实施例五

[0195] 本发明实施例还提供一种包含计算机可执行指令的存储介质，所述计算机可执行指令在由计算机处理器执行时用于执行一种样本聚类方法，该方法包括：

[0196] 统计样本集中每个样本对应的第一样本距离，所述第一样本距离为所述样本与所述样本的第S近邻样本之间的距离；

[0197] 在全部所述第一样本距离中，获取设定距离范围内的第一样本距离；

[0198] 基于所述设定距离范围内的第一样本距离计算距离均值；

[0199] 基于每个所述样本对应的K近邻样本集合，确定每个样本的全部连接样本，其中，K＞S，所述样本与所述样本的连接样本为互为近邻样本且存在连接关系；

[0200] 根据所述连接样本、所述距离均值和S值对所述样本集中的样本进行聚类，所述距离均值为扫描半径，所述S值为聚类最小包含样本数。

[0201] 当然,本发明实施例所提供的一种包含计算机可执行指令的存储介质,其计算机可执行指令不限于如上所述的方法操作,还可以执行本发明任意实施例所提供的样本聚类方法中的相关操作。

[0202] 通过以上关于实施方式的描述，所属领域的技术人员可以清楚地了解到，本发明可借助软件及必需的通用硬件来实现，当然也可以通过硬件实现，但很多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如计算机的软盘、只读存储器(Read-Only Memory,ROM)、随机存取存储器(Random Access Memory,RAM)、闪存(FLASH)、硬盘或光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述的方法。

[0203] 值得注意的是，上述样本聚类装置的实施例中，所包括的各个单元和模块只是按照功能逻辑进行划分的，但并不局限于上述的划分，只要能够实现相应的功能即可；另外，各功能单元的具体名称也只是为了便于相互区分，并不用于限制本发明的保护范围。

[0204] 注意，上述仅为本发明的较佳实施例及所运用技术原理。本领域技术人员会理解，本发明不限于这里所述的特定实施例，对本领域技术人员来说能够进行各种明显的变化、重新调整和替代而不会脱离本发明的保护范围。因此，虽然通过以上实施例对本发明进行了较为详细的说明，但是本发明不仅仅限于以上实施例，在不脱离本发明构思的情况下，还可以包括更多其他等效实施例，而本发明的范围由所附的权利要求范围决定。