[發明專利]聚類實現方法和裝置

有效

• 申請號: 201611040671.6
• 申請日: 2016-11-10
• 公開（公告）號: CN106778812B
• 公開（公告）日: 2020-06-19
• 發明（設計）人: 王龍;李超
• 申請（專利權）人: 百度在線網絡技術（北京）有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京品源專利代理有限公司 11332
• 代理人: 孟金喆;胡彬

本發明實施例公開了一種聚類實現方法和裝置，涉及數據處理技術領域。所述方法包括：對待聚類數據集的聚類中心進行初始化；根據聚類中心，計算與待聚類數據集中的各數據點分別對應的最近聚類中心，其中，在計算所述最近聚類中心過程中消除了數據點自身平方計算帶來的冗余；根據待聚類數據集中的各數據點的所述聚類中心的計算結果，更新聚類中心；返回執行根據聚類中心，計算與待聚類數據集中的各數據點分別對應的最近聚類中心的操作，直至滿足聚類迭代結束條件。本發明實施例的技術方案，優化了現有的K?means聚類算法，降低了K?means聚類算法的計算復雜度。

技術領域

本發明實施例涉及數據處理技術，尤其涉及一種聚類實現方法和裝置。

背景技術

所謂聚類，是指將物理或抽象對象的集合分成由類似的對象組成的多個類的過程。由聚類所生成的簇是一組數據對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。聚類分析又稱群分析，它是研究(樣品或指標)分類問題的一種統計分析方法，同時也是數據挖掘的一個重要算法。

其中，K-means(也稱為K均值)是一類非常經典的基于劃分的聚類分析方法，是十大經典數據挖掘算法之一，其算法簡單、收斂速度快且易于實現，應用領域非常廣泛。K-means算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近它們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。

在超大規模圖片(典型的，百億級)聚類中一般需要使用K-means算法，但是在對圖片的聚類過程中對算法的時間消耗和空間消耗都非常大。因此，如何降低K-means算法的計算復雜度，以及減少空間消耗，是當前人們廣泛研究的重點問題。

發明內容

有鑒于此，本發明實施例提供一種聚類實現方法和裝置，以優化現有的K-means聚類算法，降低K-means聚類算法的計算復雜度。

第一方面，本發明實施例提供了一種聚類實現方法，包括：

對待聚類數據集的聚類中心進行初始化，其中，初始化聚類中心的數量與預設的聚類數目相匹配；

根據所述聚類中心，計算與所述待聚類數據集中的各數據點分別對應的最近聚類中心，其中，在計算所述最近聚類中心過程中消除了數據點自身平方計算帶來的冗余；

根據所述待聚類數據集中的各數據點的所述最近聚類中心的計算結果，更新所述聚類中心；

返回執行根據所述聚類中心，計算與所述待聚類數據集中的各數據點分別對應的最近聚類中心的操作，直至滿足聚類迭代結束條件。

第二方面，本發明實施例還提供了一種聚類實現裝置，包括：

聚類中心初始化模塊，用于對待聚類數據集的聚類中心進行初始化，其中，初始化聚類中心的數量與預設的聚類數目相匹配；

最近聚類中心計算模塊，用于根據所述聚類中心，計算與所述待聚類數據集中的各數據點分別對應的最近聚類中心，其中，在計算所述最近聚類中心過程中消除了數據點自身平方計算帶來的冗余；

聚類中心更新模塊，用于根據所述待聚類數據集中的各數據點的所述最近聚類中心的計算結果，更新所述聚類中心；

重復迭代模塊，用于返回執行根據所述聚類中心，計算與所述待聚類數據集中的各數據點分別對應的最近聚類中心的操作，直至滿足聚類迭代結束條件。

本發明實施例提供的聚類實現方法及裝置，在使用K-means聚類算法的過程中，通過分析確定K-means聚類算法自身算法的執行步驟中存在的冗余，使用巧妙的變換消除了在計算各個數據點的最小聚類中心時，數據點自身平方計算帶來的冗余，優化了現有的K-means聚類算法，降低了K-means聚類算法的計算復雜度。

附圖說明