[發明專利]基于量子計算的譜聚類方法、裝置、電子設備及存儲介質

在審

• 申請號: 202210154362.0
• 申請日: 2022-02-21
• 公開（公告）號: CN114219048A
• 公開（公告）日: 2022-03-22
• 發明（設計）人: 方圓;王偉;李蕾;竇猛漢
• 申請（專利權）人: 合肥本源量子計算科技有限責任公司
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N10/60
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了一種基于量子計算的譜聚類方法、裝置、電子設備及存儲介質，方法包括：獲取待聚類的數據集，分別制備數據集內所有數值的量子態，并將所有數值的量子態每兩個作為第一預設量子線路的初態；運行并測量第一預設量子線路，第一預設量子線路用于計算量子態間的相似度；根據測量結果得到量子態間的相似度，基于相似度構建用于譜聚類的拉普拉斯矩陣；根據拉普拉斯矩陣，確定數據集對應的待聚類樣本，并根據待聚類樣本完成譜聚類。利用本發明實施例，能夠將量子計算與譜聚類算法進行結合，發揮量子計算的并行加速優勢，降低處理傳統譜聚類任務時所需要的計算量。

技術領域

本發明涉及量子計算技術領域，尤其涉及一種基于量子計算的譜聚類方法、裝置、電子設備及存儲介質。

背景技術

聚類算法是一種經典的無監督機器學習方法，對于給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大，其作用是將具有相似特征的樣本聚為一類。

目前，譜聚類算法是聚類算法中對于分布較稀疏的點聚類效果比較好的一種聚類算法，譜聚類算法需要處理的數據量與樣本的數量正相關，當樣本的數量足夠大時，譜聚類算法處理數據需要的計算復雜度也會變大，如何降低譜聚類算法的計算復雜度就成為了一個亟待解決的問題。

發明內容

本發明提供了一種基于量子計算的譜聚類方法、裝置、電子設備及存儲介質，將量子計算與譜聚類算法進行結合，發揮量子計算的并行加速優勢，降低處理傳統譜聚類任務時所需要的計算量。

第一方面，本發明實施例提供一種基于量子計算的譜聚類方法，包括：

獲取待聚類的數據集，分別制備所述數據集內所有數值的量子態，并將所述所有數值的量子態每兩個作為第一預設量子線路的初態；

運行并測量所述第一預設量子線路，所述第一預設量子線路用于計算所述量子態間的相似度；

根據測量結果得到所述量子態間的相似度，基于所述相似度構建用于譜聚類的拉普拉斯矩陣；

根據所述拉普拉斯矩陣，確定所述數據集對應的待聚類樣本，并根據所述待聚類樣本完成譜聚類。

可選地，所述根據測量結果得到所述量子態間的相似度，基于所述相似度構建用于譜聚類的拉普拉斯矩陣，包括：

根據所述量子態間的相似度生成與所述數據集對應的相似矩陣；

根據所述相似矩陣的對角線生成度矩陣，并根據所述相似矩陣與所述度矩陣構建拉普拉斯矩陣。

可選地，所述根據所述拉普拉斯矩陣，確定所述數據集對應的待聚類樣本，包括：

將所述拉普拉斯矩陣按照預設方式標準化，計算所述標準化后的拉普拉斯矩陣的n個特征向量，將所述n個特征向量作為待聚類樣本。

可選地，所述根據所述待聚類樣本進行譜聚類，包括：

分別計算每個所述特征向量與其他n-1個特征向量的距離；

根據所述距離以及第一預設條件對所述待聚類樣本進行簇的劃分，其中，所述第一預設條件包括簇的個數以及每個簇對應簇心。

可選地，所述方法還包括：

判斷劃分后的所述簇是否滿足第二預設條件；

若不滿足所述第二預設條件，則更新所述簇心并根據更新后的簇心重新計算所述相似度。

可選地，所述判斷劃分后的所述簇是否滿足第二預設條件，包括：

獲取所述簇心更新的次數；

若所述次數不小于第一預設值，判斷為滿足第二預設條件；

若所述次數小于第一預設值，則判斷為不滿足第二預設條件。

可選地，所述判斷劃分后的所述簇是否滿足第二預設條件，包括：

獲取所述簇心的更新對應的偏移距離；