[發明專利]初始樣本選擇方法及裝置

在審

• 申請號: 201611147797.3
• 申請日: 2016-12-13
• 公開（公告）號: CN106778864A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 董超;崔朝輝
• 申請（專利權）人: 東軟集團股份有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京集佳知識產權代理有限公司11227
• 代理人: 薛嬌,王寶筠

技術領域

本發明涉及聚類技術領域，更具體地說，涉及一種初始樣本選擇方法及裝置。

背景技術

在數據挖掘過程中，通常會應用到聚類。聚類是將物理或抽象對象的集合(即樣本集合)分成由類似的對象組成的多個類的過程。由聚類所生成的簇是一組數據對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。目前，在較常用的聚類算法中，有一類聚類算法，例如，K-Means算法，K-Medoids算法等，在算法開始之前，需要從樣本集合中選擇k個樣本作為初始樣本(也叫初始聚類中心)，這個過程一般是在樣本集合中隨機選擇k個樣本作為初始樣本。然而，不同的初始樣本所導致的算法的收斂速度也不同，還會影響最終的聚類效果。因此，隨機選擇k個初始樣本容易出現聚類算法的收斂速度慢、聚類效果差的問題。

因此，如何選擇初始樣本以克服聚類算法的收斂速度慢、聚類效果差的問題成為亟待解決的問題。

發明內容

本發明的目的是提供一種初始樣本選擇方法及裝置，以克服聚類算法的收斂速度慢、聚類效果差的問題。

為實現上述目的，本發明提供了如下技術方案：

一種初始樣本選擇方法，包括：

構建樣本集合中樣本的原始連通圖；所述原始連通圖中的每一個節點表征所述樣本集合中的一個樣本，所述原始連通圖中的節點兩兩相連，所述原始連通圖中任意兩個節點之間邊的權重為該兩個節點所表征的兩個樣本的相似度；

生成所述原始連通圖的最小生成樹；

刪除所述最小生成樹中相似度最小的K-1條邊，得到K個子連通圖，K為聚類算法需要選擇的初始樣本的個數；

從每一個所述子連通圖中的節點對應的樣本中選擇一個樣本作為初始樣本。

本發明實施例用通過上述方法獲取的K個子連通圖模擬樣本的分布情況，因而從K個子連通圖中選擇的初始樣本更接近真實的聚類中心，基于本發明提供的初始樣本選擇方法選擇的初始樣本，克服了通過隨機選擇初始樣本點導致聚類算法的收斂速度慢、聚類效果差的問題。

上述方法，優選的，所述從每一個所述子連通圖中的節點對應的樣本中選擇一個樣本作為初始樣本，包括：

從每一個所述子連通圖中的節點對應的樣本中，隨機選擇一個樣本作為初始樣本。

上述方法，優選的，所述從每一個所述子連通圖中的節點對應的樣本中選擇一個樣本作為初始樣本，包括：

對于所述子連通圖中的節點對應的樣本中的每一個樣本，將該樣本到所述子連通圖中的節點對應的樣本中的其它樣本之間的相似度求和，得到與該樣本對應的求和結果；

選擇與最大求和結果對應的樣本作為初始樣本。

與前一實施例相比，本實施例所選擇的初始樣本更加接近真實的聚類中心。

上述方法，優選的，所述生成所述原始連通圖的最小生成樹，包括：

從所述樣本集合中選擇一個樣本作為所述最小生成樹的初始節點；

將所述樣本集合中未加入所述最小生成樹的樣本依次加入所述最小生成樹，包括：每次將一個樣本加入所述最小生成樹之后，獲取每一個未加入所述最小生成樹的樣本，與已加入所述最小生成樹中的各個樣本之間的相似度；確定最大相似度；將該最大相似度對應的一個未加入所述最小生成樹的樣本與該最大相似度對應的已加入所述最小生成樹的樣本相連，直至所有樣本均加入到所述最小生成樹。

上述方法，優選的，所述生成所述原始連通圖的最小生成樹，包括：

按照兩兩樣本之間的相似度從大到小的順序，依次將滿足預設條件的兩個樣本相連，直至所述樣本集合中的每一個樣本均與所述樣本集合中的至少一個其它樣本相連；

其中，兩個樣本滿足預設條件包括：所述兩個樣本相連后，所有已連接的樣本未構成任何回路。

一種初始樣本選擇裝置，包括：

構建模塊，用于構建樣本集合中樣本的原始連通圖；所述原始連通圖中的每一個節點表征所述樣本集合中的一個樣本，所述原始連通圖中的節點兩兩相連，所述原始連通圖中任意兩個節點之間邊的權重為該兩個節點所表征的兩個樣本的相似度；

生成模塊，用于生成所述原始連通圖的最小生成樹；

刪除模塊，用于刪除所述最小生成樹中相似度最小的K-1條邊，得到K個子連通圖，K為聚類算法需要選擇的初始樣本的個數；

選擇模塊，用于從每一個所述子連通圖中的節點對應的樣本中選擇一個樣本作為初始樣本。