[發明專利]一種數據挖掘系統中數據聚類的方法、系統及裝置

有效

• 申請號: 201010102976.1
• 申請日: 2010-01-28
• 公開（公告）號: CN102141988A
• 公開（公告）日: 2011-08-03
• 發明（設計）人: 高丹;徐萌;鄧超;羅治國;周文輝;孫少陵;陶濤;何鴻凌;何清;趙衛中;馬慧芳
• 申請（專利權）人: 中國移動通信集團公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 郭潤湘

技術領域

本發明涉及數據挖掘技術領域，尤其涉及一種數據挖掘系統中數據聚類的方法、系統及裝置。

背景技術

數據挖掘又稱數據庫中的知識發現，是指從大量的不完全的、有噪聲的、模糊的數據中提取隱含的、未知的、非平凡的及有潛在應用價值的信息或模式，融合了數據庫、人工智能、機器學習、統計學等多個領域的理論和技術。數據挖掘工具能夠對將來的趨勢和行為進行預測，從而很好地支持人們的決策。

在數據挖掘處理中，聚類(Clustering)是將數據對象分組成為多個類或簇(cluster)，屬于同一個簇的對象之間具有較高的相似度，屬于不同簇的對象之間具有較低的相似度。相似度一般根據描述對象的屬性值計算得到，而對象之間的距離是常用的度量方式。目前，聚類分析已經廣泛地用在許多領域，例如，在商務領域，聚類能幫助市場分析人員從客戶基本庫中發現不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。通過聚類，能夠對客戶消費行為及消費心理等多種因素進行分析，從而得出客戶在消費習慣、生活方式、社會聯系等方面的特征，按不同特征劃分客戶群，并針對不同客戶群進行不同的市場營銷活動和客戶服務。

目前，聚類方法多采用PAM(PArtitioning?method，劃分方法)(也稱k-中心點對象算法)，PAM是給定一個有N個元組或者紀錄的數據集，構造K個分組，每一個分組代表一個聚類，K＜N，其中，構造的K個分組滿足下列條件：

(1)每一個分組至少包含一個數據紀錄；

(2)每一個數據紀錄屬于且僅屬于一個分組；

對于給定的K，首先給出一個初始的分組方法，以后通過反復迭代的方法改變分組，使得每一次改進之后的分組方案都優于前一次分組，即同一分組中的對象的相似度越高越好，不同分組中對象的相似度越小越好。

PAM用簇中位置最靠近中心的對象作為代表對象，然后反復地用非代表對象來代替代表對象，試圖找出更好的中心點對象，在反復迭代的過程中，所有可能的“對象對”被分析，每個對中的一個對象為中心點對象，另一個為非代表對象。一個對象代表可以被最大平方-誤差值減少的對象代替。一個非代表對象Oh是否是當前一個代表對象Oi的一個好的替代，對于每個非中心點對象Oj，有以下四種情況需要考慮，然后計算，如果為負，則可以替換：

(1)Oj當前隸屬于Oi，如果Oi被Oh替換，且Oj離另一個Om最近，那么Oj被分配給Om，則替換代價為Cjih＝d(j，m)-d(j，i)，其中，i?。絤。

(2)Oj當前隸屬于Oi，如果Oi被Oh替換，且Oj離Oh最近，那么Oj被分配給Oh，則替換代價為Cjih＝d(j，h)-d(j，i)。

(3)Oj當前隸屬于Om，m?。絠，如果Oi被Oh替換，且Oj仍然離Om最近，那么Oj被分配給Om，則替換代價為Cjih＝0。

(4)Oj當前隸屬于Om，m?。絠，如果Oi被Oh替換，且Oj離Oh最近，那么Oj被分配給Oh，則替換代價為Cjih＝d(j，h)-d(j，m)。

根據以上原理，PAM的計算過程如圖1所述，主要包括如下步驟，其中，假設要得到的簇的數目為k，并且數據庫中包含n個對象：

步驟101、任意選擇k個對象作為初始的簇中心點對象；

步驟102、依次計算每個非中心點對象到k個中心點對象的距離，并指派每個非中心點對象給離他最近的中心點對象所表示的簇，直到所有非中心點對象被指派到對應的簇中；

步驟103、選擇一個未被選擇的中心點對象Oi；

步驟104、選擇一個未被選擇的非中心點對象Oh；

步驟105、計算用Oh代替Oi的總代價并記錄在S中；

步驟106、重復步驟104至步驟105直到所有非中心點對象都被選擇過；

步驟107、重復步驟103至步驟106直到所有中心點對象都被選擇過；

步驟108、在S中記錄的總代價有小于0的存在，則利用對應最小S值的非中心點對象替代中心點對象，形成新的k個中心點對象的集合；

步驟109、重復步驟103至步驟108直到S中記錄的總代價都大于0。

CLARA(Cluster?Larger?Application，隨機搜索聚類算法)也是較常見的聚類方法，該算法先抽取數據集合的多個樣本，然后用PAM方法在抽樣的樣本中尋找最佳的k中心點對象，返回最好的聚類結果作為輸出。