摘要：隨著信息技術(shù)的高速發(fā)展，人們積累的數(shù)據(jù)量急劇增長，如何從海量的數(shù)據(jù)中提取有用的知識成為當(dāng)務(wù)之急。數(shù)據(jù)挖掘就是為順應(yīng)這種需要應(yīng)運(yùn)而生發(fā)展起來的數(shù)據(jù)處理技術(shù)。其主要任務(wù)是關(guān)聯(lián)分析、分類、預(yù)測時序模式和偏差分析等。是知識發(fā)現(xiàn)（knowledge discovery in database）的關(guān)鍵步驟。數(shù)據(jù)挖掘技術(shù)是人們長期對數(shù)據(jù)庫技術(shù)進(jìn)行研究和開發(fā)的結(jié)果。起初各種商業(yè)數(shù)據(jù)是存儲在計(jì)算機(jī)的數(shù)據(jù)庫中的，然后發(fā)展到可對數(shù)據(jù)庫進(jìn)行查詢和訪問，進(jìn)而發(fā)展到對數(shù)據(jù)庫的即時遍歷。數(shù)據(jù)挖掘使數(shù)據(jù)庫技術(shù)進(jìn)入了一個更高級的階段，它不僅能對過去的數(shù)據(jù)進(jìn)行查詢和遍歷，并且能夠找出過去數(shù)據(jù)之間的潛在聯(lián)系，從而促進(jìn)信息的傳遞。

關(guān)鍵詞：Data Mining；數(shù)據(jù)倉庫；OLAP；K均值算法；K中心點(diǎn)算法

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9599 （2012） 20-0000-03

1 基本概念

對于技術(shù)人員來說，Data Mining[1]指的是由許多看似沒有規(guī)則并且混亂不完整的現(xiàn)實(shí)數(shù)據(jù)中，提煉出其深層次并且不易為人所知的，卻具有潛在價值的數(shù)據(jù)信息和資料的過程。對于商業(yè)人員而言，Data Mining則可以幫助他們合理整理商業(yè)數(shù)據(jù)的好方法，因?yàn)樗梢詫@些Database里將大部分的業(yè)務(wù)數(shù)據(jù)執(zhí)行提煉、變換、剖析以及一些模型化操作，之后得到可以幫助商業(yè)決策的信息，比如牛奶和嬰兒尿布的關(guān)聯(lián)性信息?？偟膩碚f，Data Mining的工作就是對數(shù)據(jù)進(jìn)行關(guān)聯(lián)性分析，提煉出規(guī)則。它有以下幾個重要的元素[2]：

1.1 知識

人類通過不斷的實(shí)戰(zhàn)而得到的寶貴經(jīng)驗(yàn)；被檢測的相關(guān)數(shù)據(jù)狀態(tài)的變化規(guī)則；從數(shù)據(jù)中提取得到的不具體事物。知識的形式可能為數(shù)據(jù)模板、關(guān)聯(lián)規(guī)則、數(shù)據(jù)變動、數(shù)據(jù)異?；蛘咂渌邔?shí)際用途的結(jié)構(gòu)。

1.2 模式

針對集合（Collection） 里的所有元素，能夠使用語言（Language） 來展示這些元素本質(zhì)上的特征，然后整理得到一個表達(dá)式（Expression） ， 里所說的元素是 中的某個子集 。僅僅在 比 里所有數(shù)據(jù)的展示方法更加簡單的時候， 會成為模式。

1.3 概念/類別描述

指對數(shù)據(jù)集構(gòu)建一個簡潔的總體性描述并/或描述它與某一對照數(shù)據(jù)集的差別。

1.4 關(guān)聯(lián)分析

從一個項(xiàng)目集中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則（Association Rules），該Rules表現(xiàn)了被挖掘的數(shù)據(jù)綜合起來會得到的屬性-值條件這樣的元組。

1.5 分類與估值

分類指通過分析一個類別已知的Database的特點(diǎn)來建立一組模型M，M能夠被用來預(yù)測類別未知的以后的數(shù)據(jù)。該分類模型可以表現(xiàn)為多種形式：分類規(guī)則（ ），決策樹或者數(shù)學(xué)公式，甚至是神經(jīng)網(wǎng)絡(luò)。估值與分類類似，只不過它要預(yù)測的不是類別，而是一個連續(xù)的數(shù)值。

1.6 時間序列分析

也就是預(yù)測（ ），是指通過對大量時間序列數(shù)據(jù)的分析找到特定的規(guī)則和感興趣的特性，包括搜索相似序列或者子序列，挖掘序列模式、周期性、趨勢和偏差。

2 OW與OLAP

數(shù)據(jù)倉庫（OW或OWH）[3]指的是在公司管理和決策里面向主題的（Subject-oriented）、集成的（Integrated）、與時間有關(guān)的（Time-related）、不能被改動的數(shù)據(jù)集合，所謂面向應(yīng)用，指的是系統(tǒng)實(shí)現(xiàn)過程中主要圍繞著一些應(yīng)用或功能。而面向主題則考慮一個個的問題域，對問題域涉及到的數(shù)據(jù)和分析數(shù)據(jù)所采用的功能給予同樣的重視；OW里的數(shù)據(jù)來源于很多不同的Database，由于歷史的原因，每個Database的組織結(jié)構(gòu)通常是不同的，當(dāng)這些不同結(jié)構(gòu)的數(shù)據(jù)還沒輸入到OW的時候，必須經(jīng)歷一個集成過程；OW以維的形式對數(shù)據(jù)進(jìn)行組織，時間維是數(shù)據(jù)倉庫中很重要的一個維度，并且數(shù)據(jù)倉庫中的數(shù)據(jù)時間跨度大，從幾年甚至到幾十年，稱為歷史數(shù)據(jù)；面向應(yīng)用的事務(wù)Database應(yīng)該不斷的執(zhí)行數(shù)據(jù)插入（Insert）、更新（Update）操作，而對于OW里的數(shù)據(jù)只是做初始的導(dǎo)入和記錄查詢操作。OW的組成如圖1-1所示。

圖1-1 OW組成圖

OW的管理器包含三個[4]：（1）加載管理器，即Load Manager，執(zhí)行提煉與Load程序；（2）倉庫管理器，即Warehouse Manager，執(zhí)行數(shù)據(jù)的Arrange與Convert程序、Backup與Kept程序；（3）查詢管理器，即Query Manager，執(zhí)行Query和Manage程序。

，即 ，是OW的分析展示工具，它創(chuàng)建的基礎(chǔ)是數(shù)據(jù)的多維視圖（Multidimensional Views，即MV），其特點(diǎn)包含以下兩個：一是 ，表現(xiàn)在其對User的請求信息可以快速的Response以及交互式（interactive）操作；二是 ，是 的核心。 與 的區(qū)別如表1-1所示。

表1-1 與 的區(qū)別

用戶職員、IT人員知識工作人員

功能日常操作決策支持

數(shù)據(jù)庫設(shè)計(jì)Application-orientedSubject-oriented

數(shù)據(jù)特點(diǎn)當(dāng)前的，更新的；

詳細(xì)的，關(guān)系型的；

孤立的歷史的；

匯總的，多維的；

集成的

使用repetitivead-hoc

存取方式讀/寫；

索引大量的掃描

工作單元簡單的事務(wù)辦理復(fù)雜的查詢

記錄訪問量幾十上百萬

用戶數(shù)量數(shù)以千計(jì)數(shù)以百計(jì)

數(shù)據(jù)庫規(guī)模100MB-GB100GB-TB

按照數(shù)據(jù)的集成方式， 可以分為兩種：基于多維Database的 （MD-OLAP）和基于關(guān)系Database的 （ROLAP）。MD-OLAP響應(yīng)速度快、執(zhí)行效率高，但源于結(jié)構(gòu)的局限，靈活性不高；比較而言，ROLAP因?yàn)槭墙⒂诤芏喱F(xiàn)存Database（或者OW）的基礎(chǔ)上，它的可變性和擴(kuò)展性會更好，而且其所能承受的數(shù)據(jù)量會更大、對于多維數(shù)據(jù)的操作性更強(qiáng)。因此，ROLAP盡管在Response速度、操作的效率上沒MD-OLAP好，卻還是被很多人使用?，F(xiàn)有的 工具大多基于ROLAP。

對OW中數(shù)據(jù)的操作是針對MV（又被稱為超立方體）開展的?；贛V的經(jīng)典操作為：切片、切塊以及旋轉(zhuǎn)等。切片就是說在一個多維數(shù)組（MA）上裁剪出某個二維的子集；切塊是指在一個MA上裁剪出某個三維的子集；旋轉(zhuǎn)指的是隨意轉(zhuǎn)動MV展示的方位，使得人們能夠根據(jù)不同視角更加清楚和直觀地觀測數(shù)據(jù)信息。

將 與數(shù)據(jù)挖掘結(jié)合起來，發(fā)展出一種為數(shù)據(jù)挖掘服務(wù)的具有新型 的數(shù)據(jù)倉庫，即 （ ）將更能滿足需要。

3 基本算法

本文主要是對重要資料進(jìn)行聚類（Clustering）和整理（Arrange），而經(jīng)典的兩個Clustering算法是： 均值算法和 中心點(diǎn)算法[5]。

3.1 均值算法（KMA）

KMA是一種簡便、實(shí)用的不受監(jiān)督的Clustering算法。它在已知簇的個數(shù)時，能夠很好地對數(shù)據(jù)信息進(jìn)行聚類并分析。其基本思想為：首先，在所有數(shù)據(jù)元素中任意選擇 個成為聚類的中心點(diǎn)；然后，計(jì)算其它點(diǎn)到這些聚類中心點(diǎn)的距離，通過對簇中距離平均值的計(jì)算，不斷改變這些聚類中心的位置，直到這些聚類中心不再變化為止。該算法的大致流程如圖1-2所示：

圖1-2算法流程

算法如下：

輸入： 個數(shù)據(jù)的數(shù)據(jù)集合和已知有 個簇

輸出： 個數(shù)據(jù)所屬的 個簇中的哪個的信息

算法步驟：

1）隨機(jī)從 個數(shù)據(jù)中選擇 個當(dāng)作初始的簇中心CC；

2）將剩余的 個數(shù)據(jù)按照一定的距離函數(shù)DF劃分到最相近的簇；

3）repeat；

4）按一定的DF得出所有簇里的數(shù)據(jù)所有屬性的平均值，并且把它當(dāng)作新的CC；

5）重新將 個數(shù)據(jù)按照一定的距離函數(shù)劃分到最相近的簇；

6）直到簇的中心不會變動為止。

3.2 中心點(diǎn)算法（KCA）

KCA是KMA的一個改進(jìn)，它的基本思想為：一開始給每個簇任意的給予某個樣本（Sample）作為中心點(diǎn)（Center），而剩下來的這些點(diǎn)根據(jù)距離的大小進(jìn)行劃分；隨后用其它的非Center數(shù)據(jù)作為Center，并查看聚類情況。如果替換的聚類總代價小于零，那么就執(zhí)行替換直到中心點(diǎn)不再發(fā)生變化，也就是說達(dá)到代價最小值時停止算法。KCA流程跟KMA類似，如圖1-3所示。

圖1-3算法流程

算法如下：

輸入： 個簇，共有 個Sample

輸出：各樣本屬于 個簇的信息

算法步驟：

1）任意選擇 個Sample作為初始Center；

2）repeat；

3）將非Center的數(shù)據(jù)依照與各Center的距離劃分到最近的簇中；

4）隨機(jī)的在非Center中選擇一個Sample；

5）計(jì)算使用該點(diǎn)做Center來代替原Center的代價；

6） 用該點(diǎn)替換原Center，形成新的簇集合；

7）直到Center不會有變動為止。

本文在寫作過程中得到了陳志剛老師多次精心指導(dǎo)，在此表示感謝.

參考文獻(xiàn)：

[1]M.Berry and G.Linoff.Data Mining Techniques.John Wiley，1997.

[2]William S.Cleveland.The Elements of Graphing Data，revised，Hobart Press，1994.

[3]R.Kennedy，Lee，Reed，and Van Roy.Solving Pattern Recognition Problems.Prentice-Hall，1998.

[4]U.Fayyad，Piatetsky-Shapiro，Smyth，and Uthurusamy.Advanced in Knowledge Discovery and Data Mining.MIT Press，1996.

[5]Vasant Dhar and Roger Stein.Seven Methods for Transforming Corporate Data into Business Intelligence.Prentice Hall，1997.