[發(fā)明專利]一種結(jié)合方差與距離改進的K-means算法

在審

• 申請?zhí)枺?/td>: 202110934672.X
• 申請日: 2021-08-16
• 公開（公告）號: CN113642648A
• 公開（公告）日: 2021-11-12
• 發(fā)明（設(shè)計）人: 張宇;梁超
• 申請（專利權(quán)）人: 哈爾濱理工大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種結(jié)合方差與距離改進的K-means算法，其特征在于，該方法包括以下步驟：

步驟1：確定聚類個數(shù)k；

步驟2：從樣本數(shù)據(jù)集中選出候選初始聚類中心點集；

步驟3：從候選初始聚類中心點集中選取k個初始聚類中心；

步驟4：對樣本數(shù)據(jù)進行分配，同時存儲每個樣本數(shù)據(jù)的簇標簽；

步驟5：更新聚類中心，計算并存儲每個新聚類中心與其他新聚類中心間的最短距離；

步驟6：將已分配好的樣本數(shù)據(jù)進行重新分配；

步驟7：返回到步驟5更新聚類中心，直到聚類中心不再發(fā)生變化或者到達指定的迭代次數(shù)為止。

2.根據(jù)權(quán)利要求1所述的一種結(jié)合方差與距離改進的K-means算法，其特征在于，所述步驟1中，確定聚類個數(shù)，具體步驟為：

步驟1-1設(shè)定聚類個數(shù)的最大值為其中n為樣本數(shù)據(jù)的個數(shù)；

步驟1-2計算不同k值對應(yīng)的簇內(nèi)誤差平方和(Sum of the Squared Errors,SSE)值，通過觀察SSE的下降幅度確定最終的聚類個數(shù)。

3.根據(jù)權(quán)利要求1所述的一種結(jié)合方差與距離改進的K-means算法，其特征在于，所述步驟2中，候選初始聚類中心點集的選取，具體步驟為：

步驟2-1首先計算樣本數(shù)據(jù)的平均距離和平均密度；

步驟2-2判斷每個樣本數(shù)據(jù)在以自身為圓心，以平均距離為半徑的圓內(nèi)所包含的樣本數(shù)據(jù)個數(shù)是否不小于平均密度，若是，則認為該樣本數(shù)據(jù)屬于候選初始聚類中心點集。

4.根據(jù)權(quán)利要求1所述的一種結(jié)合方差與距離改進的K-means算法，其特征在于，所述步驟3中，從候選初始聚類中心點集中選取k個初始聚類中心，具體步驟為：

步驟3-1計算候選初始聚類中心點集中每個樣本數(shù)據(jù)的方差，并選取具有最小方差的樣本數(shù)據(jù)作為第一個初始聚類中心；

步驟3-2計算候選初始聚類中心點集中剩余樣本數(shù)據(jù)與第一個初始聚類中心的歐式距離，并選取距離最遠的樣本數(shù)據(jù)作為第二個初始聚類中心；

步驟3-3當選取第i(i＞2)個初始聚類中心時，首先計算候選初始聚類中心點集中剩余樣本數(shù)據(jù)與之前初始聚類中心的歐式距離，并保留最小的距離，再從這些最小距離中選出最大距離所對應(yīng)的樣本數(shù)據(jù)作為下一個初始聚類中心；

步驟3-4重復(fù)以上過程，直到選出的初始聚類中心個數(shù)到達指定的聚類個數(shù)。

5.根據(jù)權(quán)利要求1所述的一種結(jié)合方差與距離改進的K-means算法，其特征在于，所述步驟4中，根據(jù)就近原則將每個樣本數(shù)據(jù)分配給距離其最近的初始聚類中心所代表的簇中，同時根據(jù)聚類結(jié)果對每個樣本數(shù)據(jù)的簇標簽進行存儲。

6.根據(jù)權(quán)利要求1所述的一種結(jié)合方差與距離改進的K-means算法，其特征在于，所述步驟5中，在下一次迭代時，計算每個簇中任意一樣本數(shù)據(jù)到當前簇中其余樣本數(shù)據(jù)的距離之和，并選取距離之和最小的樣本數(shù)據(jù)作為新的聚類中心，同時將每個新聚類中心與其他新聚類中心間的最短距離存儲到當前新聚類中心所代表的簇中。

7.根據(jù)權(quán)利要求1所述的一種結(jié)合方差與距離改進的K-means算法，其特征在于，所述步驟6中，樣本數(shù)據(jù)的重新分配，具體步驟為：

步驟6-1計算每個樣本數(shù)據(jù)到新聚類中心的歐式距離，如果該樣本數(shù)據(jù)與新聚類中心的距離小于當前新聚類中心所代表的簇中存儲的最短距離的一半，則默認該樣本數(shù)據(jù)仍屬于原來的簇，否則，計算該樣本數(shù)據(jù)與所有新聚類中心的距離，并分配給距離其最近的新聚類中心所代表的簇中；

步驟6-2更新每個樣本數(shù)據(jù)對應(yīng)的簇標簽。

8.根據(jù)權(quán)利要求1所述的一種結(jié)合方差與距離改進的K-means算法，其特征在于，所述步驟7中，重新分配后需返回到步驟5對聚類中心進行更新，并與上一次迭代的聚類中心進行比較，若不再發(fā)生變化或者到達指定的迭代次數(shù)則停止聚類，并輸出最終的聚類結(jié)果。