羅賢坤 吳 磊
摘 要:介紹了建立案例索引的兩種不同方法,通過分析將多級索引應用于聚類分析方法,將聚類分析方法應用于實驗儀器設備預約問題中,具有重要的理論意義和實用價值。
關鍵詞:案例索引;聚類分析;預約
1 案例索引的建立
1.1 單級索引
單級索引比較簡單,適用于案例庫中案例不太多的情況??砂茨硞€屬性的取值進行索引,如在儀器設備推薦預約服務系統(tǒng)中我們可以按照儀器設備的儀器類別這一屬性進行索引。
1.2 多級索引
多級索引技術對于案例庫較龐大的情況很有效,可以提高案例檢索的效率。下面介紹采用采用聚類分析方法來為案例庫建立二級索引時的案例組織方法,設整個案例庫有N個案例,Casebase=<casel,case2,…,caseN>,首先對所有的案例進行聚類分析(即把相似的案例按某種方法先進行歸類),得到M類抽象案例:
AbstractCasebase=<Acasel,Acase2,…,AcaseM>,其中M≤N
這M類抽象案例作為第一級索引,每類抽象案例中又含有數(shù)個具體案例,Acasei=<caseil,casei2,…,caseiS>, S為第i類抽象案例中所含具體案例數(shù)量。這些具體案例再按照案例的某項屬性的取值進行索引形成第二級索引,如圖1所示。
2 多級索引中聚類方法的應用
聚類將數(shù)據(jù)對象分組成為多個類或簇,在同一個簇中的對象之間具有較高的相似度,而不同的簇中的對象差別較大。聚類分析的方法可以對相似案例進行歸類,形成抽象案例以進行二級或多級索引。我們知道很多多聚類方法,如劃分方法(Partioningmethod)、層次方法(hierarchical method)、基于密度的方法(density-based method)、基于網(wǎng)格的方法(grid-based method)、基于模型的方法(model-based method),它們各有優(yōu)點。聚類中常用的兩類數(shù)據(jù)結構是數(shù)據(jù)矩陣和相異度矩陣。
數(shù)據(jù)矩陣(data matrix):它用p個屬性來表現(xiàn)n個對象(案例),例如用年齡、身高、體重、性別等屬性來表現(xiàn)對象“人”。這種數(shù)據(jù)結構是關系標的形式,或者表示為n×p的矩陣:
相異度矩陣(dissimilarity matrix):存儲n個對象兩兩之間的近似性,表現(xiàn)形式是一個n×n的矩陣。
在這里玠(i,j)是對象i和j之間相異性的量化表示,通常是一個非負的數(shù)值,當對象i和j越相似,其值越接近0;兩個對象越不同,其值越大。
下面用劃分方法進行案例聚類。
給定一個含N個案例的案例庫,劃分方法構建案例庫的K個劃分,每個劃分表示一個抽象案例,并且K≤N。劃分方法要求用戶輸入抽象案例的數(shù)目K,然后把案例庫中案例劃分為K類抽象案例。K值的確定可以采用統(tǒng)計的方法獲得。
在實際應用中,絕大多數(shù)聚類過程采用了以下兩個比較流行的啟發(fā)式方法:
(1)K-平均法,該算法中,每個抽象案例用其所對應的具體案例的平均值來表示。
(2)K-中心點法,該算法中,每個抽象案例用接近聚類中心的一個具體案例來表示。
在CBR系統(tǒng)中使用聚類方法只需在系統(tǒng)初次運行時進行一次案例聚類,以后就可以快速地進行案例的檢索,極大減少了案例檢索的空間,有效地提高了案例檢索效率。當有新的案例加入案例庫后只需把它加入最相似的一類抽象案例即可。對于用戶對檢索到的具體案例不滿意的情況,可以綜合同一抽象案例類中的所有具體案例的解決方案,向用戶提供一個綜合的決策支持。
參考文獻
[1]Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘概念與技術[M].機械工業(yè)出版社,2005:223~254.
[2]Watson I.Applying Case-Based Reasoning:Tedmiques for Enterprise Systems[M].San Francisco,California:Morgan Kaufmann Publishers,1997.