1、自適應(yīng)數(shù)據(jù)庫中基于特征向量的聚類算法的研究與改進The Research And Improvement of the Cluster Based on Feature Vectors in Autonomic Database強彥 陳俊杰 高燕飛（太原理工大學(xué) 計算機與軟件學(xué)院，山西 太原 030024）3.基于特征向量的聚類算法3.1 選取特征向量當(dāng)負載的特征化部件接受到客戶端輸入的負載后，就要根據(jù)負載的特征向量分類。那么首先就要選取特征向量，通過實驗分析一些特征向量（包括表名、索引、SQL語句中的動詞等等）對負載運行時間的影響，最后發(fā)現(xiàn)SQL語句的動詞select, insert, up

2、date, delete對負載運行時間的影響最大，其次是表名，索引。所以在這里我們首先選取一組特征向量，即SQL語句的動詞select, insert, update, delete，根據(jù)特征向量把負載（n條SQL語句）分為四類，記為S1，S2，S3，S4，S1=所有包含“select”的SQL語句，S2=所有包含“insert”的SQL語句， S3=所有包含“update”的SQL語句， S4=所有包含“delete”的SQL語句。3.2 運行K-means算法把這4類S1，S2，S3，S4當(dāng)作是K-means算法初始的分類；然后運行K-means算法，最后還是得到4類，記為L1，L2，L3

3、，L4，K-means算法描述如下：1、初始的分類記為S1，S2，S3，S4，K=4，I=1； / I表示K-means算法中迭代的次數(shù)2、計算初始聚類的中心Zm（I），m=1，2，3，4；/在這里計算每一類SQL語句的平均運行時間；Zm（I）= j =1，2，nm ； (1)其中，nm表示第m類中包含SQL語句的個數(shù)；3、分別計算每條SQL語句與這四個聚類中心的距離（即：每條SQL語句運行時間與每類平均運行時間的差值的絕對值）D( Xi, Zm(I) )，把SQL語句歸到離聚類中心距離最近的類中；D( Xi, Zm )=XiZm i = 1，2，n，m = 1,2 ,3,4； (2) 4、重

4、復(fù)執(zhí)行第2和第3步，直到聚類中心不再改變，即Zm（I+1）=Zm（I），把新的分類記為L1，L2，L3，L4。3.3 計算概率值運行完K-means算法后，根據(jù)分類的個數(shù)，建立一個K×K的矩陣，在這里是建立一個4×4的矩陣，如圖4所示： 圖4：4×4的矩陣 圖5：實驗得到的數(shù)據(jù)； (3)Pij表示根據(jù)特征向量分類預(yù)測SQL語句運行時間的準確性；Pij越大，說明預(yù)測出的準確性越大。所以，選取每一行最大的點Pij，如果Pijt（假設(shè)t60%），且所有選取的Pij中i值不等，說明根據(jù)特征向量分類預(yù)測SQL語句運行時間是比較準確的，分類完成。如果上述條件不滿足，則說明根據(jù)

5、特征向量分類預(yù)測SQL語句運行時間的準確性不大，也就是說特征向量的選取是不合適的，就需要增加特征向量。3.4 增加特征向量當(dāng)特征向量選取不合適時，就要增加特征向量，接下來把表名W1，W2（根據(jù)表的大小區(qū)分）作為特征向量加入。例如，客戶端模擬輸入100條SQL語句作為初始數(shù)據(jù)，根據(jù)SQL語句動詞分為4類，運行K-means算法后，建立的矩陣，如圖5所示：從圖5中可以看出，第二行和第三行的最大值都沒有大于t，所以要增加特征向量，在這里只需要把第二行和第三行對應(yīng)的最初S2和S3類根據(jù)表名分類就可以了；第一行和第四行的概率最大值都大于t值說明S1和S4分類還是比較準確的,這里就不增加特征向量了，還是保

6、持原有的S1和S4類。這樣就得到6類，接著運行K-means算法，計算概率值。選取每一行概率值最大的點Pij，如果Pijt（假設(shè)t60%），且所有選取的Pij中i值不等，說明根據(jù)特征向量分類預(yù)測SQL語句運行時間是比較準確,分類完成。如果上述條件不滿足，就需要增加特征向量索引，接著重復(fù)上述算法。3.5 優(yōu)化類當(dāng)分類完成后，就要優(yōu)化類的個數(shù)，也就是要計算每一個類中心（Zm）與其它類中心的距離。如果距離小于W（假設(shè)W=1秒），則合并這兩個類；重復(fù)計算，直到類的個數(shù)不變，輸出分類結(jié)果。4.實驗結(jié)果根據(jù)上述算法，初步實現(xiàn)了一個自適應(yīng)數(shù)據(jù)庫中基于特征向量的聚類算法程序，并對初始的100條SQL語句進行了

7、實驗。實驗結(jié)果如表1所示：表1 實驗結(jié)果表一組特征向量的分類特征向量每行最大的Pij值調(diào)節(jié)K值后的分類特征向量每行最大的Pij值S1Select100%L1Select，表1或表275%S2Insert50%L2Insert，表167%S3Update55%L3Insert，表2100%S4Delete75%L4Delete，表1或表275%L5Update，表167%L6Update，表267%通過上表可以看出，初始的100條SQL語句根據(jù)SQL語句動詞分類，運行K-means算法后，每行最大的Pij值達不到設(shè)定的值。當(dāng)運用基于特征向量的聚類算法后，每行最大的Pij值達到設(shè)定的值了。圖6表示

8、運用基于特征向量算法控制前后對比圖:圖6:基于特征向量算法控制前后對比圖其中，用戶滿意率是指負載的運行時間是否達到用戶的滿意。從上圖中可以看出，在運用基于特征向量聚類算法后，用戶的滿意率提高了。5.結(jié)論本文主要介紹了在自適應(yīng)數(shù)據(jù)庫中負載的分類方法，在這里運用了基于特征向量的聚類算法，通過實驗驗證，這種方法分類后使類內(nèi)數(shù)據(jù)的聚合度比較高，通過分類的結(jié)果預(yù)測運行時間比較準確。缺點是該算法時間消耗比較大，但是該算法可用于初始負載分類，而初始負載分類都是離線的，所以對于時間的消耗還是可以接受的。參考文獻：1B. Niu, P. Martin, W. Powley, R. Horman and P. B

9、ird. “Workload Adaptation in Autonomic DBMSs”, Proceedings of CASCON 2006, Toronto, Canada, Oct. 1619, 2006, pp. 161 - 173.2 R. Xu, D. Wunsch II. Survey of Clustering Algorithms. IEEE Transactions on Neural Networks, Vol. 16, No. 3, May 2005, pp. 645 678.3欒麗華.聚類算法研究.南京師范大學(xué).2004年4李鎖花,孫志揮,周曉云.基于特征向量的分布式聚類算法.計算機應(yīng)用. 第26卷第2期2006年2月5劉振巖.數(shù)據(jù)挖掘分類算法的研究與應(yīng)用.首都師范大學(xué).