[發明專利]一種基于多階段分層采樣的層次聚類方法和系統

有效

• 申請號: 201310752850.2
• 申請日: 2013-12-31
• 公開（公告）號: CN103699678A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 趙朋朋;劉袁柳;吳健;鮮學豐;崔志明
• 申請（專利權）人: 蘇州大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 常亮

1.一種基于多階段分層采樣的層次聚類方法，其特征在于，包括：

基于預設的輸入屬性集，從數據源中隨機采樣預設個數的樣本，所采集的預設個數的樣本構成的集合標記為初始樣本集；

利用所述初始樣本集，構建基于所述輸入屬性集的M層查詢策略，并基于分層的估計方差被最小化原則，為所述M層查詢策略中的每層查詢策略分配相應的樣本個數，其中，所述估計方差基于估計均值獲取，所述估計均值具體為所述初始樣本集輸出屬性值的平均值，所述M為大于1的自然數；

利用所述M層查詢策略，對所述數據源進行分層采樣，得到代表性較高的樣本，每層采樣的樣本個數為該層采樣所使用的查詢策略被分配的樣本個數，所述分層采樣得到的所有樣本構成代表性樣本集；

對所述代表性樣本集中的各樣本進行聚類，得到k個簇，其中，每個簇包括至少一個樣本，所述k為大于1的自然數；

基于所述k個簇的邊界點，對所述數據源進行邊界點采樣，得到不確定性較高的樣本，所述邊界點采樣得到的所有樣本構成不確定性樣本集；

對由所述初始樣本集、代表性樣本集以及不確定性樣本集構成的合集中的樣本進行聚類，并估計聚類中心，估計出的聚類中心作為所述數據源的聚類中心。

2.根據權利要求1所述的方法，其特征在于，所述利用所述初始樣本集構建基于所述輸入屬性集的M層查詢策略之前還包括：

設置迭代參數x，并為x賦值1。

3.根據權利要求2所述的方法，其特征在于，所述對所述k個簇進行邊界點采樣，得到不確定性樣本集之后，還包括：

判斷x的值是否小于預設的迭代次數β；

當判斷結果為小于時，則x值加1，將所述初始樣本集、所述代表性樣本集以及所述不確定性樣本集進行合集，將所述合集替代所述初始樣本集作為新的初始樣本集，并轉至執行步驟：利用所述初始樣本集，構建基于所述輸入屬性集的M層查詢策略；

當判斷結果為不小于時，則轉至執行步驟：對由所述初始樣本集、代表性樣本集以及不確定性樣本集構成的合集中的樣本進行聚類，并估計聚類中心，估計出的聚類中心作為所述數據源的聚類中心。

4.根據權利要求1-3任意一項所述的方法，其特征在于，所述利用所述初始樣本集，構建基于所述輸入屬性集的M層查詢策略具體包括：

利用所述初始樣本集，構建基于所述輸入屬性集的策略樹，所述策略樹中根節點除外的各層與所述輸入屬性集中的各輸入屬性一一對應，所述策略樹中每一節點對應相應輸入屬性的一個域值，策略樹每層中各節點對應的輸入屬性域值不同；

獲取所述策略樹中每一根節點至葉子節點的路徑上包括的各個輸入屬性及所述輸入屬性對應的域值，將所述各個輸入屬性及其對應的域值標記為該葉子節點對應的查詢策略。

5.根據權利要求4任意一項所述的方法，其特征在于，還包括：

抑制策略樹構建過程中對策略樹層次的過度分層。

6.根據權利要求1所述的方法，其特征在于，所述數據源具體為Deep?Web數據源。

7.一種基于多階段分層采樣的層次聚類系統，其特征在于，包括：

隨機采樣模塊，用于基于預設的輸入屬性集，從數據源中隨機采樣預設個數的樣本，所采集的預設個數的樣本構成的集合標記為初始樣本集；

分層查詢策略構建模塊，用于利用所述初始樣本集，構建基于所述輸入屬性集的M層查詢策略，并基于分層的估計方差被最小化原則，為所述M層查詢策略中的每層查詢策略分配相應的樣本個數，其中，所述估計方差基于估計均值獲取，所述估計均值具體為所述初始樣本集輸出屬性值的平均值，所述M為大于1的自然數；

分層采樣模塊，用于利用所述M層查詢策略，對所述數據源進行分層采樣，得到代表性較高的樣本，每層采樣的樣本個數為該層采樣所使用的查詢策略被分配的樣本個數，所述分層采樣得到的所有樣本構成代表性樣本集；

初始聚類模塊，用于對所述代表性樣本集中的各樣本進行聚類，得到k個簇，其中，每個簇包括至少一個樣本，所述k為大于1的自然數；

邊界采樣模塊，用于基于所述k個簇的邊界點，對所述數據源進行邊界點采樣，得到不確定性較高的樣本，所述邊界點采樣得到的所有樣本構成不確定性樣本集；

聚類模塊，用于對由所述初始樣本集、代表性樣本集以及不確定性樣本集構成的合集中的樣本進行聚類，并估計聚類中心，估計出的聚類中心作為所述數據源的聚類中心。