流數據的聚類分類算法研究.pdf

1、近年來，隨著信息處理應用的發(fā)展，許多應用中的數據是以流的形式產生的，數據呈現出“連續(xù)數據流”的形式而不是傳統(tǒng)的靜態(tài)存儲結構形式。這些應用領域包括金融證券信息分析、網絡傳輸監(jiān)控、計算機網絡安全、通信數據管理、web應用、生產制作、傳感器網絡等。這些應用產生的數據形式稱為數據流。與傳統(tǒng)數據庫不同，數據流具有如下特點：(1)數據總量的無限性；(2)數據到達的快速性；(3)數據到達次序的無約束性；(4)除非可以保存，每個元素均只能被處理一次。

2、 數據流的上述特點對數據流上的挖掘提出了如下要求：首先，算法必須能夠進行實時在線挖掘，快速處理每一個元組，并實時輸出挖掘處理結果。其次，由于相對于無限規(guī)模的數據流而言，內存通常是有限的，這就要求算法的空間復雜度要低，往往需要在數據量的對數范圍內。再次，由于算法實時在線挖掘以及對空間復雜度的限制，算法往往只能得到近似解，且需要具有一定的精確度保證。最后，算法要具有較強的適應性，包括對數據流不斷進化的底層模型的適應性，處理離群點能力等

3、。 學術界己經對數據流上的挖掘問題進行了很多研究工作，但仍存在許多問題尚待研究和解決。 本文研究了數據流上的聚類問題和分類問題，做了以下一些工作： (1)提出了基于相關系數的多數據流聚類算法。使用相關系數作為數據流間距離的度量，將有相同變化趨勢的數據流聚為一類。我們使用衰減系數來使得新數據比舊數據在聚類結構中有更大的重要性，采用更新時間片段的機制很好地反映了聚類結構的變化過程。我們采用動態(tài)k-means，不斷的試

4、探性地調整聚類的個數，通過比較聚類質量，選取最優(yōu)的類的個數，提高聚類質量。 此外，我們基于相關系數的度量，提出了另一種滿足用戶需求的聚類算法框架。算法分為前臺和后臺兩個部分：在前臺部分，我們提出了一種新穎的保存匯總信息的機制；后臺階段，根據用戶的聚類請求，讀取相應長度的信息進行聚類。滿足了用戶對不同長度的聚類需求。 (2)提出了一種基于譜分量相似度的多數據流的聚類算法框架。使用自回歸模型對數據流序列作譜分析，把數據流表示

5、為譜參數的和。通過將相位設為零后，使用譜分量信息計算兩條數據流之間的相關性。 (3)提出了一種基于網格密度的數據流聚類算法GDCS算法。算法采用了在線／離線雙層框架，它在前臺在線層快速實時地將到達的數據點放入相應的單元格，在后臺離線層不斷地更新單元格的密度并將網格單元聚成類。此外，算法適時檢測和剔除孤立點以改進系統(tǒng)的時間空間有效性。實驗表明，算法具有更優(yōu)的聚類效率和聚類質量，能發(fā)現任意形狀的類，且能有效識別實時數據流的變化行為。