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

在審

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

1.一種初始樣本選擇方法，其特征在于，包括：

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

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

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

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

2.根據權利要求1所述的方法，其特征在于，所述從每一個所述子連通圖中的節點對應的樣本中選擇一個樣本作為初始樣本，包括：

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

3.根據權利要求1所述的方法，其特征在于，所述從每一個所述子連通圖中的節點對應的樣本中選擇一個樣本作為初始樣本，包括：

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

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

4.根據權利要求1所述的方法，其特征在于，所述生成所述原始連通圖的最小生成樹，包括：

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

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

5.根據權利要求1所述的方法，其特征在于，所述生成所述原始連通圖的最小生成樹，包括：

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

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

6.一種初始樣本選擇裝置，其特征在于，包括：

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

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

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

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

7.根據權利要求6所述的裝置，其特征在于，所述選擇模塊包括：

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

8.根據權利要求6所述的裝置，其特征在于，所述選擇模塊包括：

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

第二選擇單元，用于選擇與最大求和結果對應的樣本作為初始樣本。

9.根據權利要求6所述的裝置，其特征在于，所述生成模塊包括：

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

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

10.根據權利要求6所述的裝置，其特征在于，所述生成模塊包括：

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

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