[發明專利]一種雙閾值順序聚類方法

在審

• 申請號: 202010087028.9
• 申請日: 2020-02-11
• 公開（公告）號: CN111368876A
• 公開（公告）日: 2020-07-03
• 發明（設計）人: 晏開;謝勝利
• 申請（專利權）人: 廣東工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 張金福

本發明公開了一種雙閾值順序聚類方法，應用于順序聚類系統中，所述順序聚類系統包括數據庫與處理器，所述方法包括以下步驟：S1：處理器從數據庫提取數據集X＝{x}ⁿ，規模為n，n∈N；S2：處理器確定閾值和閾值的取值范圍，其中，S3：處理器確定聚類簇數量Q的值；S4：根據閾值閾值和聚類簇數量Q進行順序聚類，直到所有數據點都被歸類。本發明相對于其他的聚類算法，運算更快，復雜度更低；相對于基礎的順序算法，對閾值的選取有了一定的改進。本發明中的范圍選取法能有一定的容錯率，但能降低因閾值的不合理和隨機的數據順序而產生的正確率；該方法對聚類結果的簇數量有了限制，不再完全依賴閾值和數據順序。

技術領域

本發明涉及機器學習和數據挖掘領域，更具體地，涉及一種雙閾值順序聚類方法。

背景技術

聚類是一種無監督的數據分析方法，主要處理沒有先驗信息的數據，廣泛用于數據挖掘領域。一般認為將物理或抽象的數據對象集合分成由相似的數據對象組成的多個分組或者簇的過程被稱為聚類，參見圖1。圖1是具有4個自然簇的二維數據，每個顏色代表一個自然分組。由聚類所生成的分組或者簇是一組數據對象的集合，同一個分組或者簇中的數據對象彼此相似，不同分組或者簇中的數據對象彼此相異。簇內數據對象越相似，聚類效果越好。

目前發展起來的聚類方法有很多種，大多為層次聚類和劃分聚類。而順序聚類算法獨立于其他聚類方法，它們更直接而且更快速，適用于密集型聚類。這種算法需要把特征向量依次使用一次或多次，過程簡單但也有缺點。

順序聚類算法對整個數據集X(有N個數據/向量)進行一次掃描，每次迭代中，計算當前向量與聚類的距離。因為最后的聚類數Q被認為遠小于N，所以可見算法的復雜度是O(N)。

現有的順序聚類算法閾值的設定沒有依據。若閾值過小，會生成不必要的聚類；若閾值過大，那么聚類的簇數量太少，聚類效果不明顯。所以閾值的選取極為關鍵，而這也是該算法存在的問題。

發明內容

本發明提供一種雙閾值順序聚類方法，降低因閾值的不合理和隨機的數據順序而產生的正確率。

為解決上述技術問題，本發明的技術方案如下：

一種雙閾值順序聚類方法，應用于順序聚類系統中，所述順序聚類系統包括數據庫與處理器，所述方法包括以下步驟：

S1：處理器從數據庫提取數據集X＝{x}ⁿ，規模為n，n∈N；

S2：處理器確定閾值和閾值的取值范圍，其中，

S3：處理器確定聚類簇數量Q的值；

S4：根據閾值閾值和聚類簇數量Q進行順序聚類，直到所有數據點都被歸類。

傳統地順序聚類算法依賴閾值選擇不合適的值可能導致無意義的聚類結果，因此，本發明提出一種范圍性的閾值來解決困難。閾值和的范圍值能在一定程度上提高容錯率，但兩個閾值的選取還是沒有依據，很難選取。可以采用多次執行算法作圖分析得出。

參考k-means的思想，定義一個平均畸變程度(將每個簇的質點與簇內樣本點的平方距離誤差和稱為畸變程度，計算所有簇的畸變程度得出平均畸變程度)。該定義用來衡量聚類結果的可信度。因為平均畸變程度能體現出聚類結果的可信度，畸變程度越小則說明聚類后的每個簇中點都很緊湊，符合聚類的要求，若畸變程度大，則說明聚類后的簇中點相對松散，不是很好的聚類結果。但如果過度追求可信度，將值設的過大，則聚類結果會出現較多的簇，雖然每個簇中的點都緊湊，但簇中點太少，簇太多，從而達不到聚類的效果。

優選地，步驟S2中確定閾值和閾值具體為：

S2.1：每次以相同的順序表示數據，不同的閾值執行多次順序聚類；