[發(fā)明專利]基于輪廓系數(shù)的差分隱私保護(hù)K-means聚類方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810264776.2
• 申請(qǐng)日: 2018-03-28
• 公開（公告）號(hào): CN108549904A
• 公開（公告）日: 2018-09-18
• 發(fā)明（設(shè)計(jì)）人: 張亞玲;劉娜
• 申請(qǐng)（專利權(quán)）人: 西安理工大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62;G06F17/30
• 代理公司: 西安弘理專利事務(wù)所 61214
• 代理人: 韓玙

本發(fā)明公開了一種基于輪廓系數(shù)的差分隱私保護(hù)K?means聚類方法，具體按照以下步驟實(shí)施：步驟1、對(duì)數(shù)據(jù)集D中的所有數(shù)據(jù)做歸一化處理；步驟2、將具有N條記錄的數(shù)據(jù)集D平均分為K個(gè)集合；步驟3、對(duì)于集合C_k求各記錄的屬性向量之和及記錄數(shù)步驟4、計(jì)算每個(gè)記錄a_i到k個(gè)聚類中心u_k的距離；步驟5、計(jì)算該聚類的記錄數(shù)量num和各記錄的屬性向量之和sum；步驟6、計(jì)算k個(gè)聚類的輪廓系數(shù)S_k，并對(duì)num_k和sum_k添加隨機(jī)噪聲步驟7、計(jì)算新的聚類中心；步驟8、計(jì)算新的聚類中心和上次迭代的聚類中心的距離，若小于閾值，算法結(jié)束，本發(fā)明解決了現(xiàn)有技術(shù)中存在的分布式環(huán)境下大數(shù)據(jù)聚類分析中信息泄露嚴(yán)重的問題。

技術(shù)領(lǐng)域

本發(fā)明屬于信息安全技術(shù)領(lǐng)域，具體涉及一種基于輪廓系數(shù)的差分隱私保護(hù)K-means聚類方法。

背景技術(shù)

數(shù)據(jù)挖掘作為當(dāng)前大數(shù)據(jù)環(huán)境下獲取信息的重要方法，通過統(tǒng)計(jì)、機(jī)器學(xué)習(xí)和模式識(shí)別等多種方法來獲取有用的信息，這些信息廣泛應(yīng)用于商務(wù)管理、生產(chǎn)控制、市場分析和科學(xué)研究等領(lǐng)域。聚類分析是一種典型的數(shù)據(jù)挖掘方法，其主要思想是將數(shù)據(jù)聚集為若干類，使得各個(gè)聚類之間的差別最大，聚類內(nèi)的數(shù)據(jù)差別最小。K-means算法是一種思想簡單，聚類收斂速度快的，被廣泛應(yīng)用于各個(gè)領(lǐng)域的聚類算法。

在大數(shù)據(jù)聚類分析中，敏感信息的隱私泄露問題成為此類應(yīng)用的一個(gè)嚴(yán)重障礙。如何高效的實(shí)現(xiàn)數(shù)據(jù)挖掘，同時(shí)保護(hù)個(gè)體的隱私，就是隱私保護(hù)的數(shù)據(jù)挖掘算法要解決的問題。差分隱私保護(hù)是2006年Dwork首次提出的，能適應(yīng)于任意背景知識(shí)下的攻擊技術(shù)，并且因?yàn)樗皇軘?shù)據(jù)集的大小限制而受到關(guān)注。在K-means聚類分析中，通過差分隱私保護(hù)技術(shù)能夠有效的減少個(gè)體隱私的泄露，具有差分隱私保護(hù)的K-means聚類算法具有重要的實(shí)際應(yīng)用意義。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種基于輪廓系數(shù)的差分隱私保護(hù)K-means聚類方法，解決了現(xiàn)有技術(shù)中存在的分布式環(huán)境下大數(shù)據(jù)聚類分析中信息泄露嚴(yán)重的問題。

本發(fā)明所采用的技術(shù)方案是，基于輪廓系數(shù)的差分隱私保護(hù)K-means聚類方法，其特征在于，具體按照以下步驟實(shí)施：

步驟1、將數(shù)據(jù)集分為M個(gè)大小相同的數(shù)據(jù)片分別執(zhí)行Map任務(wù)和Reduce任務(wù)，假設(shè)數(shù)據(jù)集為D，數(shù)據(jù)集中的總記錄數(shù)為N，記錄記為a_i，其中，1≤i≤N，記錄的維數(shù)為d，聚類個(gè)數(shù)為K，第k個(gè)中心點(diǎn)記為u_k，1≤k≤K，隱私預(yù)算ε，第t次迭代中第k個(gè)聚類的隨機(jī)噪聲為t為迭代次數(shù)；

步驟2、對(duì)數(shù)據(jù)集D中的所有數(shù)據(jù)做歸一化處理；

步驟3、將有N條記錄的數(shù)據(jù)集D平均分為K個(gè)集合C_k，1≤k≤K，集合C_k有N/K條數(shù)據(jù)；

步驟4、對(duì)于集合C_k求各記錄的屬性向量之和及記錄數(shù)分別對(duì)和添加隨機(jī)噪聲得到和計(jì)算初始中心點(diǎn)

步驟5、計(jì)算每個(gè)記錄a_i到k個(gè)聚類中心u_k的距離；

步驟6、計(jì)算該聚類的記錄數(shù)量num和各記錄的屬性向量之和sum；

步驟7、計(jì)算第k個(gè)聚類的輪廓系數(shù)S_k，并對(duì)num_k和sum_k添加隨機(jī)噪聲

步驟8、計(jì)算新的聚類中心

步驟9、計(jì)算新的聚類中心和上次迭代的聚類中心的距離，若小于閾值，則結(jié)束，輸出聚類集合，否則返回步驟5。

本發(fā)明的特點(diǎn)還在于，

步驟2中做歸一化處理時(shí)所有的點(diǎn)分布到[0,1]^d空間中。