利用空间切割技术的密度式聚类方法

摘要

利用空间切割技术的密度式聚类方法，包括以下步骤：输入参数和资料集；执行K-means算法；执行IDBSCAN算法；找出群集边界点；判断是否需要进行合并；合并群集；判断是否达到合并结束条件。本发明能够大幅度的减少KIDBSCAN所需花费的数据聚类时间，且在聚类正确率与错误数据去除率均较高，具有良好的实际应用价值。

主权项

利用空间切割技术的密度式聚类方法，包括以下步骤：Step1：输入参数和资料集；需输入的参数包括：群数K：该参数是源于K‑means，其用途是设定数据集将被分为多少类；半径Eps：半径与最少包含点两参数是源于IDBSCAN，半径参数的概念是指使用着认为以某点为圆心的半径距离的数据点都可以被视为邻居点；最少包含点Minpts：是指邻居点数量要大于或等于此参数所设定的值，才能够将这些数据点视为同一群；Step2：执行K‑means算法；K‑means算法针对所设定的参数K，将数据集划分为K个子空间群集，每一数据点均拥有分群编号Cluster ID，再依照分群编号予以归类；Step3：执行IDBSCAN算法；IDBSCAN针对经由K‑means所分出的K个群集分别进行分群，当进行扩张询问时，IDBSCAN扫描的范围仅止于一个群集之内；Step4：找出群集边界点；找出群集边界点是为了减少数据量，以提高后续合并的效率；由于合并动作是以群集之间的最近距离进行合并，只需要各群集的边界点来做距离计算即可，故靠近群集核心的数据点是可以被忽略的；Step5：判断是否需要进行合并；一开始所设定的参数K，不仅决定将空间切割为多少子空间，也是决定最后数据集应被分为几群的依据，假如经由IDBSCAN分群过后，群集数量大于K群，则进行Step6将群集合并，否则结束分群；Step6：合并群集；合并方式本发明采取群集之间的最近距离，即群集间最接近的两个数据点的距离，计算公式如下：$d_{min}(C_i,C_j)={\min }_{P\in C_i,P^{\prime }\in C_j}||P-P^{\prime }||$公式中C_i与C_j代表经由IDBSCAN分群后的第i个和第j个群集，P与P′各自代表两群集内的数据点，从所有群集间找出距离最近的两群集进行合并动作，每次仅进行一次的合并，合并完成后会将当前的群集数减1；Step7：判断是否达到合并结束条件；此阶段是判别当前的群集数是否达到之前所设定的群数K，如符合条件则分群结束，否则回到Step6继续进行合并。