网格聚类

网格聚类（共7篇）

网格聚类 篇1

摘要：在网格的研究中, 网格资源的合理选择和充分利用是网格技术追求的目标, 为了更为有效的解决网格资源的选择, 本文提出了一种基于模糊聚类和属性权重的资源选择方法, 它以模糊聚类为基础, 根据资源各属性对具体网格应用的重要度确定属性权重, 最后确定资源分类。文章最后以一个具体实例说明该方法的资源分类过程。

关键词：网格,网格资源,模糊聚类,权重

1、引言

网格[1]是一项新的技术, 是下一代并行分布式计算方法, 它试图在因特网上整合大量分布、动态、异够资源的全面贯通, 协同工作。因此资源的管理问题就成为了网格基础问题之一, 资源选择的合理与否直接影响了网格应用的效率。由于网格资源具有异够性, 多样性等特点存在一定的模糊性, 很难准确的计算资源的相似程度。因此本文介绍一个以模糊聚类算法为基础, 并以各个节点资源属性对网格应用的重要性为权重的资源选择分类方法。

本文将从以下方面介绍网格环境中资源的分类。首先介绍模糊聚类方法, 然后介绍将夹角余弦法、欧式距离法结合起来, 通过加权平均构造新的模糊相似矩阵;最后介绍网格节点资源的表示方法及举例说明资源分类的具体过程。

2、模糊聚类分析

2.1 传统模糊聚类方法

模糊聚类分析是当前模糊数学中应用最多的几个方法之一, 在现实世界中, 事物本身就具有模糊性, 按一般经典数学来描述实现的分类往往不能令人满意, 而利用模糊聚类分析进行分类, 更符合实际。一个分类要满足等价关系, 即自反性、对称性和传递性, 模糊等价关系是模糊聚类分析的基础。模糊聚类的主要步骤为:确定对象, 建立模糊相似矩阵和布尔矩阵聚类[2,3]。

确定对象, 假设聚类问题有n个待分类对象X={X1, …, Xm}, n个对象有m个属性指标, 对象Xi的属性评价指标数据的向量为 (Xi1, Xi2, …, Xin) (i=1, 2, …, m) 。对X应用式 (1) 建立模糊相似矩阵R= (rij) n×n, 其中rij=rji, rii=1。以极差标准化处理求rij, 其公式如下:

其中MINj=MIN (xij) , 即资源第j项性能中最小值;MAXj=MAX (xij) , 即资源第j项性能中最大值。

在模糊等价矩阵中, 取λ∈[0, 1]截取矩阵。得到相应的布尔矩阵, 因为布尔矩阵是对称的, 主对角线下部和上部是一样的, 为了方便计算, 只取左下半部分, 去掉主对角线右上部分。用竖线和横线将矩阵中的1与主对角线上的1连接;主对角线上的1代表Xi, 通过这样的编网连接的对象归为一类。在不同的水平截距λ下, 得到不同的归类对象。

2.2 属性权重的相似矩阵构建

建立模糊相似矩阵又称为标定, 即标出衡量被分类的对象之间相似程度的统计量rij (i=1, 2, …n, j=1, 2, …n) 。设论域U={xl, x2, x3, …, xn}, xi={xil, xi2, xi3, …, xim}, 依据传统聚类方法确定相似系数, 建立模糊相似矩阵, xi与xj的相似程度rij=R (xi, xj) 。确定rij=R (xi, xj) 的方法主要是借用传统聚类分析中的夹角余弦法构建相似系数、欧式距离法以及其他方法。

而以上方法在计算相似矩阵时没有考虑各个属性指标重要度之间的差异, 认为它们具有相同的权重。实际上各个指标的重要度是不同的, 因此对相似矩阵的贡献也是不一样的, 相似系数法是描述样本之间的相关关系程度, 而距离法是描述样本之间的值接近程度。因此, 单一用相似系数法或距离法来进行聚类分析必然存在不足。因此利用各个属性指标的权重向量分别构造加权相似系数和加权距离系数。将夹角余弦法、欧式距离法结合起来, 通过加权平均构造新的相似度, 利用新的相似度可以得到新的相似度矩阵, 如式 (2) 所示:

其中权重向量表示具体应用对各属性指标的重要度,

表示Xi与Xj的加权相似系数,

表示Xi与Xj的加权欧式距离。

3、网格资源聚类过程

3.1 网格资源的表示方法

网格资源之间虽然没有严格的属性区分, 但是在某些层面上有一定的关联, 因此更适合模糊聚类。最大相似性资源的聚类分析是以资源的属性为基础的, 所以资源描述方式直接影响聚类结果。在综合分析网格资源节点资源属性的基础上, 我们定义以下4个特征属性来描述系统中的资源[4]: (1) 服务能力 (x1) , 表示该资源在单位时间内向用户提供的服务量, 通常根据网格资源节点加入网格时的参数确定; (2) 服务质量 (x2) , 表示用户对资源提供服务的满意程度, 采用网格QOS[5]评价函数进行量化; (3) 使用价格 (x3) , 表示用户使用该资源的成本, 也是源节点加入网格时的参数确定; (4) 功能特征 (x4) , 主要描述资源的服务类型, 如计算资源用1表示、存储资源用2表示等。在这些指标中, 除了功能特征外, 其余各项指标的数据会随着网格系统的运行而动态改变。根据以上特征属性, 网格资源可用一个四维数据向量表示为:X= (x1, x2, x3, x4) 。

3.2 模糊聚类过程

假设网格系统中有n个资源接点, 每个资源节点属性用m维向量表示, 则节点资源集合X={X1, X2, X3, …, Xn}, 其中第i个资源节点:Xi={Xi1, Xi2, Xi3, …, Xim}, i∈[1, n]。这里我们取n=5m=4。即对5个资源, 每个资源有4个特征属性进行讨论, 如表1所示:

根据表1的数据, 下面用模糊聚类分析法来划分资源。

(1) 由于资源属性数据不全是[0, 1]区间的数, 为了避免大数吃小数的现象, 应用式 (1) 对原始数据进行极差标准化处理[6]后所得数据如表1右半部分所示。用X1, X2, …X5表示分类对象, 则Xi对应的属性指标分别用xi1, xi2, xri3, xi4表示, 那么资源对象可表示为:

(2) 模糊相似矩阵。应用式 (2) 计算在权重w= (0.25, 0.25, 0.1, 04) 的模糊相似矩阵:

(3) 通过设定不同的截距λ值, 得到不同的聚类结果。取λ=0.8, 得到的布尔矩阵

最终的聚类结果为{X1, X3, X4}, {X2}, {X5}, 从分类结果可以看出, 把服务类型比较接近的资源X1, X3, X4聚为一类, 这也与我们按照现实经验分类结果较为一致。

4、结论

在网格中, 存在大量的资源, 如何对这些归类和利用, 是整合网格资源的一个关键, 也是网格不同于以往因特网的一个重要方面。本文应用模糊聚类方法, 分类网格资源, 是网格资源管理的一个新思路。在该思路下, 考虑实际应用对属性评价指标的不同引入基于资源属性权值的加权模糊聚类, 这样网格资源可以根据具体的网格应用更有效的利用, 从而全面提高了网格资源的有效配置, 为网格资源的全面连通整合奠定了基础。

参考文献

[1].徐志伟, 冯百明.网格计算技术, 北京:电子工业出版社, 2004.

[2].Buckley J J, Hayashi Y.Fuzzy Genetic Algorithm and Applications[J].Fuzzy Sets and Systems, 1994 (61) :129-1136.

[3].卢秋根.模糊聚类算法的研究与实现[J].电脑知识与技术, 2008 (9) :1987-1990.

[4].刘晓锋, 吴亚娟, 李明东.一种基于模糊聚类的资源发现策略[J].计算机应用, 2007 (9) .

[5].梁泉, 杨扬, 梁开健.网格系统的服务质量保障与控制综述[J].控制与决策, 2007 (2) .

[6].沈睿芳, 郭立甫, 时希杰.数据挖掘中的数据预处理模型与算法研究[J].计算机系统应用, 2005 (7) .

网格聚类 篇2

关键词：聚类,最优区间分割,密度,CLIQUE算法

1 引 言

在早期,聚类分析作为统计学的一个分支,主要集中在基于距离的聚类分析。随着机器学习研究领域的兴起,聚类成为无指导学习的一个例子。聚类分析是依据样本间关联的量度标准将其自动分成几个群组,使同一群组内的样本相似,而属于不同群组的样本相异的一组方法[1]。现在,聚类算法已成功地应用在空间数据库、模式识别、图像处理、过程优化、生物学以及市场营销、配方设计等许多领域中,并取得了良好效果。根据对象数据间相似度和对聚类评价准则的不同,常用的聚类方法可分为:划分方法、层次的方法、基于密度的方法、基于网格的方法和基于模型的方法等。为了进一步提高聚类算法在处理高维海量数据时的准确性和有效性,本文重点研究与改进CLIQUE算法,并通过实验加以仿真。

2 CLIQUE算法分析

CLIQUE聚类算法综合了基于密度和网格的聚类算法的特点。它对于大型数据库中高维数据的聚类非常有效。给定一个多维数据点的数据集合,数据点在数据空间中通常不是均匀分布的。CLIQUE将数据空间分割成网格单元,把落到某一个网格单元中点的个数当成这个单元的密度。可以指定一个阂值,当某一个网格单元中点的个数大于阂值时,就说这个单元格是稠密的。聚类就可定义为相连的密集单元的最大集合[1]。

CLIQUE对元组的输入顺序不敏感,无需假设任何规范的数据分布。CLIQUE自动发现最高维的子空间,高密度聚类存在于这些子空间中。它随输入数据的大小线性的扩展,当数据维数增加时具有良好的可伸缩性,但是它也存在着很多局限性,主要有以下几点[2]。

(1) 边缘区域精度问题。

由于算法采用硬划分技术,在类的边界区域。其包含的点数比较少,有可能被误认为非密集单元,这样就容易破坏类的边缘区域,降低结果的准确性。

(2) 孤立点问题。

CLIQUE算法不能自动去除数据集中的孤立点,需要增加额外的步骤去除孤立点,这就增加了算法复杂性。

(3) 子空间的剪枝问题。

CLIQUE算法应用一种剪枝技术来减少密集单元候选集的数目。通过把在同一个子空间中的密集单元分组,并且找出每一个子空间中密集单元选出的数据覆盖。覆盖大的子空间将被选出其余的将被剪枝。这种技术可能遗失一些密集单元。

(4) 算法的精确性问题。

算法中很多步骤都大大简化,并且用的是近似算法,所以聚类结果的精确性会降低。

3 CLIQUE算法的改进

在CLIQUE算法中采用最小描述长度来剪枝的方法,这样可能会漏掉一些密集单元,就会使聚类的精确性大大降低。而改进的新算法,将样本数据向坐标轴上投影,利用基于密度的算法将样本进行区域分割。根据样本的分布特性进行网格分割得到的区间会比等宽分割得到的区间更加精确,并且数目也更少;对获得的最优分割区间,再采用基于数据集划分的聚类发现算法,得到基于子空间的聚类[3]。

在已经确定的区间分割中,为了保证每一个分割可以将不同的聚类分开,在考虑处理样本向坐标轴上投影时,采用一种基于密度相连的方法实现。为更好地描述改进算法,在各个样本所在的不同一维空间的投影坐标中,提出以下概念:

概念1:(d近邻)假设一数据点q与给定对象P在i维空间中的投影距离不超过d,那么这个数据点q就称为该对象在i+1维空间关于d的近邻,这些数据点的集合用ad(p)表示,设D是要进行聚类的样本在一维空间中的投影坐标,那么ad(p)定义为:

ad(p) = {q ∈ D | dist (p,q) ≤ d}

概念2:(核对象)对于一个给定对象,如果在参数d半径的大小内包含等于MinPts或者超过MinPts的近邻,那么则称它为核对象。

概念3:(直接密度可达)对于给定的MinPts,d和数据点P,若要从对象q可以直接密度可达,则p需要满足的条件是:

(1) p ∈ ad(q)

(2) | ad(q) | > MinPts

概念4:(密度可达)对于给定的MinPts,d和数据点P,从对象R可以密度可达,P需要满足的条件是:存在一串对象P1,P2,…,Pn;P1=P,Pn=Q,其中从Pi+1可以直接密度可达Pi。

然后通过检查数据库中的数据在i维空间投影的每个点的参数半径d近邻来寻找在次维空间的网格划分区域。如果包含在一个点P,并且参数半径d中的点数目大于MinPts的区域内,则创建一个以P作为核心对象的网格区域。然后,反复的寻找从这些核心对象直接密度可达的对象,这个过程可能会涉及一些密度可达区域的合并。执行这个过程,一直到没有新的点可以添加到任何网格区域时,该过程结束。

通过前面可知,算法用基于密度的方法来优化网格,使得分割区间数目大大减少,并且不需要生成最小覆盖的过程,结果直接就是DNF范式。相比较而言,CLIQUE原算法中采用的平均分割区间方法将会出现在聚类发现的每一步过程中,比最优分割区间方法来会产生更多的候选聚类项集;另外,在CLIQUE中,采用贪心算法生成相连密集算法的最小覆盖,产生DNF范式,也使得复杂度比用最优分割区间方法有所增加。

根据基于优化分割区间的算法,可以得到在每一维上的一维聚类的区间,然后通过优化分割区间的方法进行Clique聚类[4]。

4 CLIQUE聚类过程流程图

通过对原算法的研究,可知如果一个n维单元是密集的,那么它在n-1维空间上的投影也是密集的。也就是说,给定一个n维的候选密集单元,检查它的n-1维投影单元,发现任何一个不是密集的,则知道第n维的单元也不可能是密集的。因此可以从n-1维空间中发现的密集单元来推测n维空间中潜在的或候选的密集单元。并且CLIQUE算法是按照以下步骤进行的[5]:识别含有聚类的密集子空间;识别聚类;生成聚类的最小描述。

结合所要改进之处,可得图1。

5 改进算法的分析

改进算法不仅具有CLIQUE本来的特点,如:良好的可扩展性、较强的噪声处理能力、对输入数据样本的顺序不敏感、可以发现任意形状的聚类、聚类结果易于控制等特点,而且它还有着原算法所不具有的优点[6,7]:

(1) 有较低的时间复杂度。因为将数据样本向坐标轴上投影,所以也就减少了坐标轴上的聚类区域,使得聚类子空间的数目显著减少,也省去了覆盖相邻密度单元的步骤;

(2) 较好的可扩展性。当数据增多时数据分布特性更加明显,数据量越多,效率就越高;

(3) 聚类结果有着较高的精确度。用基于最优分割区间的算法能够更加精确地刻画聚类的边界,并且不采用剪枝算法,这样就可以得到更加精确的聚类结果。

实验的目的是验证改进CLIQUE算法的可行性和有效性,显示出算法的优势。同时对算法出现的若干问题进行分析,为算法的下一步改善提供实验依据[8]。用户可以通过输入参数来控制产生数据集的结构和大小。参数包括数据集的大小、维数和各维上的取值范围[9,10]。

由图2可以看出,随着数据集维数的增加,改进后算法的效率比原算法有较大提高,性能也有了进一步的改善。通过比较可知新算法有更好的聚类效果。

6 结 语

CLIQUE算法是聚类分析中的一种常用方法,由于算法在区域边界精度和子空间剪枝等方面存在问题,限制了该算法的性能,本文在原算法的基础上进行了尝试性的改进并提出一种改进方案,可以有效地提高算法的准确性和处理数据的能力。在理论和实验方面证明改进后的算法与原算法相比是可行而有效的。为了提高处理超大型复杂数据的性能,今后有待于在并行处理方面多做研究。

参考文献

[1]Han J,Kamber M.Data Mining Concepts and Techniques[M].Morgan Kaufmann Publishers,2001.

[2]冯永,吴开贵,熊忠阳,等.一种有效的并行高维聚类算法[J].计算机科学,2005,32(3):216-218.

[3]王建会,申展,胡运发.一种实用高效的聚类算法[J].软件学报,2004,15(5):697-705.

[4]业宁,李威,梁作鹏.一种Web用户行为聚类算法[J].小型微型计算机系统,2004,25(7):1 364-1 367.

[5]邵峰晶,于忠清.数据挖掘原理与算法[M].北京:中国水利水电出版社,2003.

[6]Wang W,Yang J,Muntz R.A Statistical Information Grid Ap-proach to Spatial Data Mining[C].In Proc.1997 Int.Conf.VeryLarge Databases,Athens,Greece,1997:186-195.

[7]Hinneburg A,Keim D.An Efficient Approach to Clusteringin Large Multimedia Databases with Noise[C].In:Proc.1998 Int.Conf Knowledge Discovery and Data Mining,NewYork:AAAI Press,1998:58-65.

[8]Alexander Hinneburg,Daniel A Keim.An EfficientApproach to Clustering in Large Multimedia Databases withNoise[C].KDD,1998:58-65.

[9]Ci Song,Guizani Mohsen,Sharif Hamid.Adaptive Clusteringin Wireless Sensor Networks by Mining Sensor Energy Data[C].Computer Communications,2007:2 968-2 975.

网格聚类 篇3

1 GRDCA聚类算法

单元c所代表区域中包含的数据点的数目称为该单元的密度, 记为N (c) 。对于空间任一单元c, 如果N (c) >0则称单元c为非空单元。非空单元的集合称为非空单元集合, 记为Cne={c|N (c) >0}。在低维空间, 非空单元的数目与维数d成指数关系。在高维数据空间, 绝大多数单元是空的, 因此非空单元的数目与N成线性关系。

定义1 (参考点) 。如果单元c�Cne, 则单元c所代表区域中所包含的数据点的密度中心ref (c) 称为单元c的参考点。

定义2 (单元间距离) 。设c, c’是两个非空单元, c, c’间距离定义为:

定义3 (邻接单元) 。给定距离阈值τ, 非空单元c的邻接单元定义为:

邻接单元的参考点称为邻接的参考点。

定义4 (核心单元) 。对于空间任一单元c, 如果N (c) ≥δ (δ为密度阈值) , 则称该单元为核心单元。核心单元的集合称为核心单元集合, 记为Cd。

定义5 (直接密度可达) 。对于给定距离阈值τ和密度阈值δ, 称单元c’从单元c直接密度可达, 如果满足:

定义6 (密度可达) 。对于给定距离阈值τ和密度阈值δ, 称单元c’从单元c密度可达, 如果存在一系列单元c1, c2, …, ck, c1=c, ck=c’, ci+1从ci直接密度可达。

定义7 (密度连接) 。对于给定距离阈值τ和密度阈值δ, 称单元c’与单元c密度连接, 如果c’和c都从单元c”密度可达。

定义8 (类) 。一个类C是Cne的一个非空子集, 且满足下列条件的所有单元所代表的点的集合。

(1) 对于任意核心单元c和c’, 如果c�C且c’从单元c密度可达, 则c’�C。

(2) 对于任意核心单元c和c’, 如果c, c’�C, 则c’与c密度连接。

1.1 GRDCA算法

1.1.1 数据结构

基于网格单元的重要性, 我们首先介绍网格单元的数据结构。每个网格单元包含4部分信息:网格单元的参考点X坐标Xref和Y坐标Yref;网格单元代表区域内所有的点的X坐标之和Xsu m和Y坐标之和Ysu m;单元的密度 (网格单元代表区域内点的总数) Ns;网格单元代表区域内的数据点的集合Ps。

1.1.2 算法描述

GR DCA算法可分为四步:第1步, 将数据点映射到相应的网格单元, 计算所有非空单元的描述信息, 即非空单元的参考点坐标、非空单元所包含的数据点的数目并将这些数据点添加到集合Ps。第2步, 基于密度可达和密度连接对核心单元进行聚类。第3步, 用基于参考点的重新构建网格单元的方法对仍不属于任何类的非空单元进行聚类。第4步, 对类的边界单元的邻接单元中的数据点进行整合。

2 算法的性能分析

2.1 聚类效果

GR DCA算法可以很好地处理任意形状的数据集, 同时也较好地屏蔽了异常数据的影响。

2.2 输入参数的设定

GRDCA算法有2个主要参数:距离阈值τ、密度阈值δ。参数的选择会影响算法的聚类结果和执行效率。

在GRDCA算法中, 距离阈值τ, 密度阈值δ的选取可以近似得到。我们经过实验发现, 在τ取整个数据空间的1/50~1/10 0时就可以取得较好的效果, 如:D S1是30×30的二维空间, 取距离为0.5。

2.3 执行效率

我们选择D B S CA N算法与GR DCA算法进行算法的比较, D B S C A N算法是一种效率比较高的聚类算法。实验证明, GR DCA算法的效率优于DB SCA N算法。此外, 由于DB SCA N算法需要建立索引, 而建立索引的时间代价是很大的;如果把建立索引的时间也考虑进去, 则GRDCA算法将会大大优于DBSCAN算法。

3 结论

在本文中我们提出了一种使用参考点来描述数据空间几何特征的方法, 并提出了一种基于参考点和密度的快速聚类算法GRDCA, GRDCA算法保持了基于网格的聚类算法可以发现任意形状的聚类和对噪音数据不敏感的优点;适合对大规模数据的挖掘。我们的理论分析和实验结果也证明了上述结论。

网格聚类 篇4

1.1文本聚类分析的方法。

文本聚类是在类未知的情况下, 根据文本内容的相关性来组织集合, 将文本划归为不同的类, 以帮助决策者进行决策分析。根据聚类算法思想的不同, 文本聚类的基本方法分为五类:基于划分的聚类分析法、基于层次的聚类分析法、基于密度的聚类分析方法、基于网格的聚类分析方法、基于模型的的聚类分析方法[1]。

目前大多数的文本集聚类分析算法在小数据集上有很好的聚类效果, 但对于海量的大文本数据集, 往往很难得到很好的聚类效果。要实现对大文本的聚类分析, 首先要考虑算法的特性, 只有具有并行性特征的聚类分析算法才更适合[2]。

1.2文本聚类分析的过程。

文本聚类是将文本对象集合划分为多个由相似对象组成的簇族的过程。文本聚类分析的基本步骤如下: (1) 特征抽取。选择适当的特征值, 对于需要关心的信息, 赋予更高的权重, 对于不重要的特征, 赋予较低的权值, 还可以通过设定一定的阈值将之剔除。在特征抽取中, 主要目的就是进行信息的删减。 (2) 计算相似度。判断两个文本之间到底是否“相似”, 并给出定量的分析结果。相似度度量方法有很多, 欧氏距离公式是一个简单的常用方法, 被用来计算两个特征向量之间的相似性[3]。 (3) 聚类处理。目前聚类算法有很多种, 在实际处理中, 需要根据数据类型、聚类目的和应用范畴选择不同的聚类算法。

1.3文本聚类相似度的计算。

计算文本对象的相似度是文本聚类分析中最重要的步骤。度量二个对象之间的相似度一般有二种方法:一是对所有的对象做特征投影, 二是距离计算。前者主要从直观的图形上反映对象之间的相似度, 后者是通过衡量对象之间的差异度来反映它们之间的相似度关系。常用的距离计算方法有:欧氏距离、麦哈顿距离、夹角余弦和相关系数等[1]。

二、Map Reduce在文本聚类分析中的应用

2.1分布式计算框架Map Reduce。

随着云计算技术的出现和发展, 特别是开源的云平台的建立, 为文本聚类分析的并行化研究和实现提供了很好的条件。开源的Hadoop框架平台提供了分布式数据库HBase、分布式文件系统HDFS和分布式计算框架Map Reduce[4]。

Map Reduce是一种简化的分布式编程模型和高效的任务调度模型, 非常适合大规模数据集的并行运算。Map Reduce计算模型通过底层对数据分割、任务分配、并行处理、容错处理等细节问题进行封装, 使用户只需集中精力解决并行计算的任务即可, 使程序设计的任务得到了简化, 使安全性和可靠性得到了很大提高[4]。

2.2Map Reduce过程。

Map Reduce主要通过Map (映射) 和Reduce (简化) 这两个步骤来并行处理大规模数据。Map Reduce的具体过程如下: (1) 根据所提供的库, 把大文本数据分成多个相互独立的数据块文件; (2) Master服务器把这些不同的数据块文件分配给不同的Worker服务器; (3) 通过Map过程进行高度的并行处理和计算, 不同的Map之间是相互独立的; (4) Master服务器协调各Worker服务器进行Reduce过程, 将各服务器的中间结果进行汇集整理, 形成最后结果并输出[5]。

2.3Map Reduce特点。

Map Reduce分布式处理框架非常适合处理大文本数据, 而且它能将很多繁琐的细节隐藏起来, 极大地简化程序员的开发工作;Map Reduce的伸缩性非常好, 每增加一台服务器, 就相当于将一台服务器的计算能力汇入到集群中, 而一般的分布式处理框架, 在伸缩性方面都有很大的制约[6]。

三、基于Map Reduce和网格密度的文本聚类分析算法

3.1算法思想。

设数据集为m个n维数据对象。首先定义一个密度阈值r, 对数据对象的每一维属性进行S等分, 整个数据空间就被划分成Sn个网格单元;然后把这数据对象全部映射到这些网格单元中去, 同时记录每个网格单元中的数据对象的数目, 数据对象的数目大于等于密度阈值t的网格单元称为高密度单元, 反之称之为低密度单元, 最后把相邻的高密度单元进行连接, 形成簇类[7]。

3.2算法流程。

基于网格密度的文本聚类算法流程如下: (1) 定义一个密度阈值r; (2) 根据数据对象的个数m和维数n, 确定网格划分值S; (3) 把数据空间划分为Sn个网格单元; (4) 将数据集中的数据对象映射到网格单元中; (5) 扫描网格单元, 统计每个网格单元中数据对象的个数, 计算网格单元的中心和重心; (6) 如果网格单元中数据对象数目大于等于r, 则标识为高密度网格单元;如果网格单元中数据对象数目小于r, 则标识为低密度网格单元[8]; (7) 连接邻近的高密度网格单元, 合并高密度网格单元邻近的边界点, 形成簇类。

连接邻近的高密度网格单元是指:对于两个高密度网格单元, 如果它们的网格单元间距小于或等于网格单元的对角线长度则把它们聚成一个簇类;合并高密度网格单元邻近的边界点是指:对于一个高密度网格单元和一个低密度网格单元, 如果它们网格单元重心之间的欧几里得距离小于或等于网格单元的对角线长度的一半, 则把低密度网格单元中的数据对象划入邻近的高密度网格单元的簇类中;其它的数据对象都被视为噪音或者孤立点舍弃[7]。

3.3算法优化和改进。

基于网格密度的聚类算法应用了网格分块的思想, 实现了在各个网格上的聚类操作, 提高了聚类分析的速度, 但它仍是串行化操作, 当文本数量的规模很大时, 仍会面临着速度瓶颈的问题。通过对该算法的分析可以知道, 数据对象到网格单元的映射和非空网格单元的合并, 是该算法的核心也是最耗时的部分[7]。因此, 我们可以利用分布式计算框架Map Reduce的思想对该算法进行并行化改进。基于Map Reduce和网格密度的文本聚类分析算法主要分为两步:

(1) 数据对象到网格单元映射的并行化处理。其中Map函数的主要任务是分块读取数据对象, 把它们映射到相应的网格单元, 并对相应的网格单元中数据对象的数目进行累加, 并把中间结果交给相应的Reduce过程;Reduce函数的主要任务是根据Map得到的中间结果, 把具有相同网格单元的中间结果放入相同的Reduce任务中, 计算出每个网格单元中的数据对象, 识别高密度与低密度网格单元, 然后交给下一次Map Reduce过程[7]。

(2) 非空网格单元的合并聚类的并行化处理。其中M a p函数的主要任务是分块进行非空网格单元的合并聚类, 它以某一维为分块入手点, 把整个数据空间分成若干块, 对每块进行内部聚类, 并把中间结果交给相应的Reduce过程;Reduce函数的主要任务是根据Map部分得到的中间结果, 把局部簇类进行全局合并, 输出聚类结果[7]。

改进后的并行聚类算法与其相对应的串行算法相比, 聚类结果有较高一致性, 说明该算法具有良好的有效性。同时, 该算法能大大的加快了聚类分析的速度, 尤其对于大数量的数据, 具有很好的加速比和可扩展性[9]。

四、结束语

本文引入云计算技术, 采用分布式计算框架Map Reduce, 与聚类分析中的网格方法和密度方法相结合, 采用分布式并行处理技术, 大大提高了文本聚类分析的速度, 尤其对海量大文本数据的聚类分析有很好的效果。

摘要：为解决大数据文本聚类分析的瓶颈, 分析了云计算和文本聚类分析的关键技术, 利用云计算及分布式计算框架MapReduce的技术优势, 构建了基于MapReduce和网格密度的文本聚类分析算法, 为大数据文本聚类分析的应用提供了新的思路和技术基础。

关键词：大数据,云计算,数据挖掘,聚类分析,网格密度

参考文献

[1]冯晓云.基于云计算的文本聚类算法研究[D].南京:南京理工大学, 2014.

[2]李乔, 郑啸.云计算研究现状综述[J].计算机科学, 2011, 38 (4) :32-36.

[3]赵宏伟, 宋宝燕.云计算环境下一种高效的资源管理策略[J].计算机科学, 2012, 39 (2) :212-215.

[4]万至臻.基于MapReduce模型的并行计算平台的设计与实现[D].杭州:浙江大学, 2008.

[5]牛新征, 佘堃.面向大规模数据的快速并行聚类划分算法研究[J].计算机科学, 2012, 39 (1) :134-137.

[6]郑湃, 崔立真, 王海洋等.云计算环境下面向数据密集型应用的数据布局策略与方法[J].计算机学报, 2010, 33 (8) :1472-1480.

[7]赵广才.基于云计算的空间聚类分析研究[D].郑州:河南工业大学, 2012.

[8]李建锋, 彭舰.计算环境下基于改进遗传算法的任务调度算法[J].计算机应用, 2011, 31 (1) :184-186.

网格聚类 篇5

聚类是数据挖掘中的一项重要技术, 它的目标是将数据集分成若干个集合, 同一个集合中的对象是相似的, 不同集合中的对象是不相似的。基于相似性已经有很多聚类算法, 这些聚类算法大致可分为基于距离的聚类算法、基于密度的聚类算法、基于层次的聚类算法和基于网格的聚类算法等。

传统的K-Means算法是一种基本距离的聚类方法, 其基本思想为:首先, 随机地选择K个对象, 每个对象初始地代表了一个类的中心或平均值。对数据集中剩余的每个对象, 根据其与各个类中心的距离, 将它归于最近的类, 然后重新计算每个类的平均值。这个过程不断重复, 直到准则函数收敛。传统的K-Means算法的缺陷是如果各个类的形状和大小差别很大, 则可能会出现将大的类分割的现象, 同时, 由于孤立点和噪声数据的存在, 使得初始聚类数据点的选取很困难, 而初始聚类数据点的选取又直接影响到最终的聚类精度, 所以存在很大的局限性。

本文是针对传统K-Means算法聚类结果的缺陷, 提出了一种基于网格的K-Means聚类算法。实验表明, 该算法能处理任意形状和大小的聚类, 对孤立点和噪声数据也能很好地识别, 并且在去除孤立点和噪声数据方面可以达到一定的精度。

1 网格聚类的概念

给定一个n维数据集合, 其属性 (a1, a2, …, an) 都是有界的, 不妨设第i维上的值在[li, hi], i=1, 2, …, n中, 则S=[l1, h1]×[l2, h2]×…×[ld, hn]就是n维数据空间。

定义1:将每一维分成k个不相交的区间段, 每个区间都是左闭右开的等长的区间, 这样将数据空间分割成一个个网格单元。

网格单元在第i维上的长度为δi= (hi-li) / k, 第i个区间段可由Iij= (li+ (j-1) *δi, li+j*δi) , 其中j=1, 2, …, k, 网格单元的总数是kn。

定义2:将每个网格单元的每一维平均分成两等份, 从而形成2n个单元, 这些单元称为网格的子单元。

定义3:网格单元的相邻单元是指与所给单元有共同边界或有共同点的那些单元。

定义4:如果一个网格单元中数据点的个数大于给定的密度值MinPts时, 我们称该单元为高密度单元;反之称该单元为低密度单元。

定义5:如果一个网格单元是低密度单元, 并且其相邻的网格单元都是低密度的, 则该网格单元中的数据点作为孤立点和噪声数据处理。

在实际聚类过程中, 应该将孤立点和噪声数据丢弃, 如果一个网格单元是低密度的, 并且其相邻网格单元存在高密度单元, 那么这个低密度网格单元中的点可能是一个类的边界点, 也可能是噪声数据。为此, 我们要将该网格单元划分为相应的网格子单元, 然后对这些网格子单元进行处理, 即如果一个网格子单元的相邻网格单元存在高密度单元, 则视这个网格子单元中的数据点是类的一部分, 将其合并到相邻的高密度单元中;如果一个网格子单元的相邻网格单元不存在高密度单元, 则视该网格子单元中的数据为孤立点和噪声数据。这样做可以一定程度上提高聚类的质量。

2 基于网格的K-Means算法

基于网格的K-Means算法描述如下:

(1) 根据网格聚类中的k值划分n维数据空间。

(2) 将需要测试的数据集E中的每个数据点分别分布到对应的网格单元中, 同时并计算出每个网格单元中数据点的个数。

(3) 根据给定的密度阈值MinPts标识每个网格单元并去除孤立点噪声数据。

(4) 使用传统的K-Means聚类算法对高密单元进行聚类。

算法中, 第一步是根据网格聚类中k的值将n维数据空间中的每一维划分为k个大小相等的区间, 形成kn个网格单元。然后处理每一个网格单元, 将其每一维两等份, 这样就形成了2n个网格子单元;第二步是对需要测试的数据集E进行一遍扫描, 然后根据E中的每个数据点分别分布到相应的数据空间中, 同时计算出每个网格单元中的数据点的个数即每个网格单元的密度;第三步是根据给定的密度阈值MinPts处理每一个网格单元, 如果一个网格单元中数据点的个数大于等于密度阈值MinPts, 则该单元被标记为高密度单元, 否则就会被标记为低密度单元, 对低密度单元中的数据作为噪声数据处理;最后一步是对去除噪声数据的数据集使用传统的K-Means聚类算法进行聚类。

3 结语

基于网格聚类的思想, 提出了一种基于网格的K-Means聚类算法, 该算法使用了网格技术在一定程度上去除了孤立点和噪声数据, 减少了原始K-Means算法将大的聚类分开的可能。实验表明, 该算法能处理任意形状和大小的聚类, 对孤立点和噪声数据也能很好地识别, 并且在去除孤立点和噪声数据方面可以达到一定的精度。

摘要：K-Means算法是聚类方法中常用的一种划分方法。随着数据量的增加, K-Means算法的局限性日益突出。基于网格划分的思想, 提出了一种基于网格的K-Means聚类算法, 该算法使用了网格技术在一定程度上去除了孤立点和噪声数据, 减少了原始K-Means算法将大的聚类分开的可能。实验表明, 该算法能处理任意形状和大小的聚类, 对孤立点和噪声数据也能很好地识别, 并且在去除孤立点和噪声数据方面可以达到较好的精度。

关键词：聚类算法,K-Means,网格

参考文献

[1]韩家炜.数据挖掘——概念与技术[M].北京:机械工业出版社, 2001.

[2]CHIH-MINGHSU, MING-SYAN CHEN.Subspace clustering ofhigh dimensional spatiall data with noises[A].PAKDD 2004[C].LNAI 3056.

[3]LEVENT ERTOZ, MICHAEL STEUBBACG, VIPIN KUMAR.Finding clusters of different sizes, shapes, and densities in noisy, high dimensional data[C].SIAM International Conference on DataMining (SDM'03) .

[4]CHIH-MING HSU, MING-SYAN CHEN.Subspace clustering ofhigh dimensional spatial data with noises[C].PAKDD, 2004.

网格聚类 篇6

关键词：海洋牧场,模糊聚类,三角网构建,可视化

0 引 言

海洋牧场是指在某一海域内,通过建设大型人工孵化厂,大规模投放人工鱼礁,实施先进的鱼群控制技术,利用自然的海洋生态环境,将人工放流的经济海洋生物聚集起来,建设海上放养鱼虾贝类的大型人工渔场[1]。由于海洋牧场处于近海,受大陆、河流、气候和季节的影响,海水的温度、盐度、颜色和透明度、水流等都有明显的变化,这些变化情况是海洋牧场研究人员主要关注的。传统的方法是研究人员对用各种仪器监测到的数据进行观察和分析,这种方法不够直观,给海洋牧场的研究带来了一定的困难。解决这个困难的一个有效方法是进行海洋牧场可视化研究。科学计算可视化的目标就是把由数值计算或实验获得的大量数据转换成人的视觉可以直接接受的计算机图像。一幅图像能把大量的抽象数据有机地组合在一起,展示数据所表现的内容及相互关系,使人们摆脱直接面对大量抽象数字的复杂情形,使把握全局成为可能[2]。海水温度是海洋牧场研究中需要重点关注的一个基本因素,海水温度的数据离散,其时空分布及变化规律对研究者来说极其抽象,因此,本文试图对海水温度的可视化问题进行研究。

1 相关工作

国内外在温度可视化方面已做了很多的研究,取得了一定的成果。文献[3]在温度场快速计算中,借助传热学原理建立相应的温度场模型,然后利用数值分析方法处理温度场模型,实现模拟仿真并结合CUDA技术实现并行计算,从而提高了温度场的生成速度,这种方法对可以实时监测的、涉及范围较小的、热量传递有一定规律的固体温度场可视化具有较好的效果,但是不适用于海洋水体温度场这种大范围的离散数据可视化。文献[4]对海水温度盐度可视化进行了研究,首先利用多重二次型插值法对散乱体数据建模,然后用光照模型对其进行整体可视化,并利用Marching Cube算法绘制等温面,实现了海洋温度的可视化,并用实验验证了该方法对海洋水团研究的效果。这种方法对数据量小的情况效果较好,但数据量大了以后会有以下不足:多重二次型法中的多元一次方程组求解和光线投射法中大循环与迭代相叠加,使得算法运行时间较长;并且,Marching Cube算法逐个处理数据场中的体素,分类出与等值面相交的体素,提取体素中的等值面切片,并将这些切片连接生成等值面,该算法生成等温面时可能会出现空洞现象[5]。在提取切片时Marching Cube规定了14种切片样式,图1箭头左侧的两个体素切片图便是其中两种,在将这两组切片连接生成等值面时可能会出现箭头右侧所示的空洞情况。

等温面是一个光滑的三维曲面,若存在空洞,则是需要克服的缺陷,这就需要找到一种无空洞的温度可视化方法。一个海水区域的温度可由多个等温面结合来描述,这样海洋温度可视化问题便转化为离散点曲面构建问题。

Delaunay三角网构建技术又称为三角网的无缝拼接技术,常用于离散点曲面构建问题上,它是将任意给定的点集按照最大角最小化原则(即所有三角形的最小内角和最大)生成唯一的一组三角网格[6,7,8]。该算法在二维三角网格拼接中取得了不错的效果,三维网格拼接技术的研究还未见报道。

通过对Delaunay三角网构建技术记性研究,发现Delaunay三角网的无缝拼接可以解决等温面出现空洞的问题,基于Delaunay三角网的无缝拼接技术提出了一种新的海洋温度可视化算法——等温场曲面构建可视化。

2 等温场曲面构建可视化

从构建无空洞等温面的角度出发,利用三角网格构建技术对温度进行可视化。该可视化算法分三步:第一步,聚类得到等温数据集;第二步,根据离散的等温面数据构建三维曲面;第三步,添加三角形定点颜色用OpenGL绘制等温面。为了解决运行速度问题,本文没有采取复杂的光线投射法,而是将颜色的(HSB)模式与海水温度值建立对应关系,最后转化为RGB模式进行着色。

2.1 等温数据的获取

等温数据即为温度大体相同的一组数据集,等温数据集的划分过程是一个聚类的过程。传统的聚类分析是一种硬划分,它把每个待辨识的对象严格地划分到某个类别,具有非此即彼的性质,因此这种分类的类别界限是分明的[9]。温度的划分并没有严格的属性,只是根据数据值本身划分,这样在划分中同一个温度数据有可能属于两个不同等温面,所以等温数据的获取存在着不确定性,适合进行软划分,不宜采用传统聚类方法。由于模糊聚类得到的是样本属于各个类别的隶属程度,表达了样本类属的中介性,即建立起了样本对于类别的隶属描述,能更客观地反应现实世界[10],因此模糊聚类是实现软划分的有效算法,模糊聚类算法中最为常用的是模糊C-均值聚类算法[11]。

模糊C-均值聚类算法的基本思想是:先将n个点分成c类,定义每一个类有一个聚类中心,聚类中心表示的是每个类的平均特征,可以认为是这个类的代表点。然后根据点与聚类中心的距离,形成一些具有相同性质的模糊子集,每一个点与聚类中心有一个隶属度。一个类是一系列点组成的模糊子集,每个点对于不同的聚类中心有不同隶属度,由此,可以形成在一定隶属度条件下的分类。最后按照模糊集合中的最大隶属原则就能够确定每个点归为哪个类。

为了提取等温面数据,首先规定隶属度范围和等温面的数量范围(即分类的个数范围),然后循环遍历这两个范围内的数据,最后确定满足划分原则的隶属度和等温面个数。划分的原则是任意两个类别内的数据不交叉,任意一个类内的数据不得小于10(此数可根据最后等温面效果图做相应调整),分类数量最多。

2.2 构建等温面

聚类得到的等温数据集是一些离散的点集,如何利用离散点生成三维曲面是本节研究的重点。

正如二维空间中一条曲线段可由有限个直线段近似表示一样,在三维空间中一个曲面也可由有限个三角面表示。所以上述问题便转化成为离散点生成三角网的问题。二维空间中构建三角网的技术已非常成熟,而三维空间中还存在困难。在三维空间中,如果点数较大的情况下计算量会非常大、效率较低[12]。等温面存在一个特点,即等温面上的任意一点与其在水平面上的投影存在一一对应的关系。换个角度来说,对水平面上的投影进行垂直拉升便可得到等温面。据此可以利用二维三角网构建技术来构建三维三角网,从而降低计算量、提高效率。

2.2.1 基于Delaunay的三维曲面构建

根据二维Delaunay三角网的构建技术[13],先对数据进行二维投影,然后构建Delaunay三角网,最后对二维三角网进行垂直拉升生成三维三角网。算法如下:

输入:某等温面的离散三维点集。

输出:三维三角形集合。

步骤:

step 1 对数据点在XOY坐标平面上投影(去除z坐标)。

step 2 生成凸包。

(1) 求出点集中满足min(x-y)、min(x+y)、max(x-y)、max(x+y)的四个点,并按逆时针方向组成一个点的链表。这4个点是离散点中与包含离散点的外接矩形的4个角点最近的点。将这4个点构成的多边形作为初始凸包。

(2) 对于每个凸包上的点I,设它的后续点为J,计算矢量线段IJ右侧的所有点到IJ的距离,求出距离最大的点K。

(3) 将K插入I、J之间,并将K赋给J。

(4) 重复(2)-(3),直到点集中没有在线段IJ右侧的点为止。

(5) 将J赋给I,J取其后续点,重复(2)-(4)。

(6) 当凸包中任意相邻两点连线的右侧不存在离散点时,结束点集凸包求取过程。

step 3 环切边界法凸包三角剖分。在凸包链表中每次寻找一个由相邻两条凸包边组成的三角形,在该三角形的内部和边界上都不包含凸包上的任何其它点。将这个点去掉后得到新的凸包链表。重复这个过程,直到凸包链表中只剩三个离散点为止。将凸包链表中的最后三个离散点构成一个三角形,结束凸包三角剖分过程。

step 4 离散点内插。

(1) 找出外接圆包含待插入点的所有三角形,并构成凸多边形插入区域。

(2) 将插入点与多边形所有顶点相连,构成新的Delaunay三角形。

(3) 重复(1)-(2),直到所有非凸壳离散点都插入完为止。

step 5 对二维三角网进行垂直拉升(添加z坐标值)生成三维三角网格。

2.2.2 三角网细分

由于数据稀少会导致Delaunay算法形成的三角网比较粗糙,三角网的疏密程度对等温面的精确是有非常大的影响的。为了提高精度,对形成的三角网做了细分。

细分的过程是一个迭代的过程。一次迭代过程为取三角形三条边的中点,将三个中点连线把一个三角形分为四个小三角形。细分的程度取决于迭代的次数,迭代次数越多,细分越精细,但耗时也越多。随着迭代次数的增加运行时间呈指数上升,图形的精度越来越高。通过多次实验发现,迭代次数大于3时,三角形细分无明显效果,但运行时间会大幅上升,迭代次数小于3时三角网格较为粗糙,因此,最终选择迭代3次。迭代次数与数据的稀疏程度有关,数据密集时由原始点构成的三角网格比较精细,因此不需要多次,迭代次数应可以减少;数据稀疏时,由原始数据点构成的三角网格比较粗糙,需要多次迭代,因此迭代次数应增加。

2.3 可视化

采取颜色法进行温度可视化。通过颜色与海水温度值建立对应关系,用色相代表等温面的值,用亮度代表等温面的浮动变化,这样人们可以借助视觉上的颜色变化感觉到海水温度数值的变化。

颜色与温度的对应关系如下:

色相(H)=360/n

饱和度(S)=1

亮度(B)=(cT-minT)/(2maxT-2minT)

其中n代表等温面的个数,cT代表当前点的温度值,minT代表该等温面的最小温度值,maxT代表等温面的最大温度值。

OpenGL绘制时需用RGB模式绘制,所以最后将HSB模式转化为RGB模式。

3 实 验

为了验证算法的性能,设计了实验对散乱体数据可视化算法和等温场曲面构建算法进行比较。实验用PC配置如下:CPU为Intel Core 2 E8400 3.0GHz,内存为2.0GB,显卡为NVIDIA GeForce G100。采用编程语言为C++,开发环境Microsoft Visual Studio 2005。数据集是黄海某海域三月份测试的温度数据。数据量300,数据范围1000平方米,高度范围0-50米,温度变化范围3-10℃。散乱体可视化中的包围盒的大小为100米×100米×10米,等温场曲面构建算法中的分类数量为3,模糊聚类中的隶属度为0.9,每个类中的点数大于40。实验主要测试空洞的产生情况,相同温度下比较两种算法产生等温面的相似情况,以及比较两种算法的运行速度。

实验1 空洞的产生情况

实验目的:测试两种算法空洞现象出现情况。

实验方法:观察等温场曲面构建算法产生的所有等温面并于散乱体数据可视化算法产生的对应温度的等温面进行比较。

实验结果:等温场曲面构建算法产生的所有等温面均无空洞,散乱体数据可视化算法在温度为9.7℃时等温面出现如图2所示的空洞现象,图3为等温场曲面构建算法产生在9.7℃等温面对比图。两图的对比可以看出图3与图2轮廓相似,但是图3没有图2中的空洞现象,同时由于图3用模糊聚类对温度数据进行了近似处理,因此等温面的精确度不如图2。

实验2 等温面的可视化效果

实验目的:比较在无空洞情况下两种算法产生等温面的效果。

实验方法:生成统一侧面的两种等温面通过观察比较两种算法在6.9℃产生的等温面的形状,凹凸性。

实验结果:两种算法产生的等温面形状相似,凹凸性略有差异。从图4与图5的对比中可以看出图4左侧凹陷的部分在图5中出现凸起效果。

凹凸性有差异说明了等温场曲面构建可视化算法精度不够,其原因是等温场曲面构建可视化中所用的模糊聚类得到的等温面的温度数据是近似数据,在6.9℃上下游浮动,这样就会带来误差,从而导致凹凸性的差异。

实验3 算法运行效率的比较

实验目的:比较两种算法的运行效率。

实验方法:计算在运用光照投射法情况下散乱体数据可视化算法所用的时间,去掉光射投射法情况下所用的时间,以及等温场曲面构建可视化算法所用的时间。

实验结果:实验结果如表1所示。结果证明光照投射法是影响运行效率的主要原因。在去掉光射投射法后,等温场曲面构建可视化算法的运行效率比散乱体数据可视化算法的运行效率要高1倍左右。

从上述实验结果可以看出,改进的方案有效地解决了空洞和运行时间长的两个问题。但该方案也存在着不足,等温面的数据由聚类算法得到,因此只能可视化出以聚类中心为温度值的一些等温面,不能可视化出所有的等温面,所以精度不是很高。

4 结 语

对海洋牧场温度可视化进行深入研究的基础上,提出了基于三角网生成技术和模糊聚类算法的海洋温度可视化技术,该方法可以避免空洞现象的出现而且运行时间较短。但该算法在生成等温面时精度不够。下一步的工作是研究更为适合等温面的差值算法来对三角网格进行细分,改进模糊聚类算法提高精度,应用并行处理技术来提高等温面的生成速度,添加时间轴生成随时间变化的等温面以及添加盐度等其他指标,实现多指标混合可视化。

网格聚类 篇7

随着智慧医疗服务运作模式的网络化,医疗服务资源、服务能力和服务需求呈现明显的跨时空分布特性,基于网格(Grid)技术的医疗信息服务运作管理,能使医疗服务需求者(或虚拟角色)有效地获取、发布、共享和管理医疗信息知识资源,并为患者和其他需要医疗服务的用户提供所需的知识信息服务,辅助实现知识创新、协同工作、问题解决和决策支持。网格(Grid)技术是是近年来国际上兴起的一种重要的信息技术,是继传统INTERNET、Web之后的第三个信息传输和利用大浪潮,又高性能计算机、数据资源、IN-TERNET三种技术的有机组合和发展,目的是将计算机能力和信息资源像电力网一样通过网络形式方便的传送给需要的用户[1]。传统的INTERNET实现了计算机硬件的连通,WEB实现了网页的连通,而基于网格技术的医疗信息服务的运作管理是将互联网、高性能计算机、大型数据库、生物传感器、远程医疗设备等融为一体,实现医疗服务运作管理全面共享,将计算资源、医学信息资源、医疗信息资源等资源进行了整合,消除医疗信息鸿沟和医疗服务运作管理的资源孤岛。

2 研究背景

基于网格技术的医疗服务运作管理过程中的数据收集和医学知识积累为医疗服务提供了信息基础,医疗信息数据的采集、分析、利用,医学服务知识的发现、表达和分享,都为患者提供个性化服务和提高服务水平有着重要影响。如医疗服务机构在提供卫生服务时,完善医疗诊断信息数据收集,应用数据仓库和数据挖掘技术掌握患者就诊规律和偏好,以实现准确的医疗卫生需求预测和门诊服务知识管理,进而实现先进的医疗信息化管理水平和对现有的医疗服务资源的利用率并能提高患者的满意度。医疗服务机构提供专业化的医疗知识和技术服务,医疗服务运作机构的所有载体信息均能以数字化的形式获得,患者通过网络或者其它形式访问专业的医疗服务运作机构的医学文献信息数据库系统或者实现网上就诊。医疗服务运作机构作为医疗信息资源的中心,如何提高自己的服务运作管理水平,吸引更多患者,提高患者的访问兴趣,成为医疗运作服务的一项主要工作。同时医疗服务管理运作机构的信息中心对医学Web站点的设计和功能提出了专业的要求,即要求Web具有智能性,能快速、准确地找到患者所需医疗信息[2];能为不同患者提供不同的医疗服务;能允许患者根据自己的需要定制页面;能为患者提供医疗保健产品营销策略信息等等。但是目前完全彻底地实现这些功能是困难的,它需要在人工控制智能和医学语言理解等方面有突破性进展,而一个有效的解决办法,就是在网格环境下,利用Web数据挖掘技术,从中得到有用的医疗服务信息[3]。

在网格环境下医疗服务具有无可比拟的运作优点,网格技术为患者或医疗需求的用户提供同意的网络访问接口,将异地获取的访问结果进行预定的组合计算,对于患者提出的医疗需求的请求,通过适当的访问协议如SOAP、XML、HTTP等,进行通信,实现底层信息的包装和交互操作。它所提供的单一系统映像,具有透明性、可靠性、负载平衡等功能[4],极大地提高了医疗服务管理运作机构医学信息资源的使用效率。

医学数据挖掘(Data Mining)就是从医学信息数据库中抽取隐含的、未知的、具有潜在应用价值的医学信息的过程。其名字源于它类似于在山脉中挖掘有价值的矿藏。近年来将医学数据挖掘(Data Mining)技术应用于Web即Medical Web Mining的研究渐成热点,Medical Web Mining技术通常被分成两个部分,即Web医疗服务信息内容的挖掘(Web Content Mining)和Web医疗信息服务用法的挖掘(Web Usage Mining),这种分化的趋势越来明显,例如内容挖掘通常应用于医学智能网络信息检索,用法挖掘则主要应用于医疗个性化服务及患者访问模式的发现中,尤以Medical web日志文件的挖掘为焦点。虽然日志文件的挖掘,对分析系统的使用情况、协助管理者优化系统结构可以起到一定的作用,但仅靠对服务器日志文件的挖掘并不能达到很好的效果[5]。浏览器的缓存、防火墙的普遍使用以及IP地址的动态分配等,都使得通过日志文件无法确认患者的身份并准确分析出其访问序列。

3 网格环境下医疗服务运作机构患者访问信息资源兴趣的路径聚类研究

聚类分析作为一种重要的分析技术,在很多科学领域都得到了广泛的应用,对空间和时间数据的聚类分析一直是研究的热点之一。早期的研究主要是针对静态数据进行的聚类[6],近些年来,移动物体的聚类在天气预报、医疗信息服务管理等领域都得到了广泛的应用。随着物联网技术的飞速发展,医疗服务领域每天都产生并传递着大量的医疗信息数据。医疗服务运作机构通过书刊资料、网络等形式传播医疗健康知识,他们以其独特的资源优势与服务方式,已经成为医疗服务的信息资源中心和患者接受医疗服务、健康保健及医疗护理的主要地点。由于网络医疗服务资源的地理分布性,这些数据通常表现为门类繁多、来源不同、格式不一、管理混乱等特点,大量的数据可能成为包袱,甚至成为垃圾。因此,为改变“数据过剩”而又“信息贫乏”的困窘,很有必要对所得到的医学数据进行抽样与提取,以发现数据的本质内涵,选取我们所想要的医疗信息资源。医学数据挖掘领域已经成功开展了这方面的研究,一些技术在原始数据中的应用可发现有用的信息,使得患者或医疗服务需求的用户最终可以更好地获取自己想要的医疗服务信息[7]。

3.1 网格环境下医疗服务信息数据挖掘和聚类路径的重要性

网格境下的医学数据挖掘技术,特别是在Internet上建立医学信息数据挖掘服务器,患者访问信息资源兴趣的路径聚类与数据库服务器配合,实现患者访问兴趣的路径聚类和数据挖掘将成为本世纪数据挖掘的研究热点[8]。医学数据挖掘技术所涉及的是结构化数据,网格环境下Web是一个无统一结构、无完整性约束、无集中控制、无事务管理、无标准查询语言和数据模型、可无限扩充的一个松散的分布式信息系统,从理论上讲,对其医学数据的挖掘是困难的,获取的医学知识是不可靠的。而medical Web服务器的log日志具有完美的结构,每当患者访问medical Web站点时,所访问的页面、时间、患者ID等信息,在log日志中都有相应的记录。分析medical Web日志,捕捉患者日志中微妙联系,发现患者浏览站点的共同行为,挖掘出其中有用的医疗信息,将其利用到网站上,对于网站提高访问量、拓展市场及站点的医学智能化设计具有重大意义,并让患者很方便地共享医疗信息服务资源。网格环境下的医疗信息资源共建共享不是去创造患者对医疗信息的需要,而是要在思维上摆脱物流的观点,接受医疗信息共享本当无冲突的理念;在技术上设法努力寻求人工智能医疗、虚拟技术等现代手段支持;在理论上以系统工程、人机工程和智能医疗等理论工具为基础,找到一种患者需要的、全新的信息共建与共享模式,使医疗服务、信息服务、网格技术三者最佳整合,去满足患者的医疗信息需要,充分提高医疗信息资源的利用率。

3.2 基于网格的医疗信息服务数据挖掘和聚类方法(Grid-based Medical information service clustering method)

3.2.1 医学信息服务数据挖掘

患者会话对医疗服务信息数据挖掘来讲,显得粗糙,仍不够精确,需把医疗服务会话进一步分成具有一定语义的事务。医疗服务的会话是指同一个患者连续请求医疗服务的页面。不同患者访问的医疗服务的页面属于不同的医疗服务会话,如果同一患者访问的页面跨越时间较长,可认为患者的访问不止一次,可使用时间戳timeout,如果患者访问页面时间差超过了timeout,则认为患者开始了一个新的会话。在此基础上对患者所需求的医疗服务相关的事务进行识别,采用最大前向引用路径来定义医疗服务事务,对于每个患者会话,从开始页面为起点,每个最大前向引用路径为一个事务,最终按时间排序的所有访问医疗相关的事务构成我们进行挖掘的医学信息资源服务事务集。经过对医疗信息数据的清洗、医疗服务会话识别、医学事务识别后,形成要进行聚类医疗信息服务事务集。每一个患者访问医疗信息服务事务相当于患者对站点的一条访问路径。患者的访问医疗信息服务事务集就是全体患者在一个时间段内对站点的访问路径集。找到患者访问医疗信息服务事务集之后,就可以在其上按路径进行聚类。

3.2.2 医疗服务日志挖掘

就是运用数据挖掘的思想来对服务器中的医疗日志进行分析处理。在网格环境下医疗信息服务运作机构聚类之前,首先要对医学信息站点日志进行预处理,从中识别出有关患者的医疗健康的相关事务。先进行数据清洗,即将日志转化为适合数据挖掘的可靠的精确的医学信息数据,删除日志中与医学信息数据挖掘不相关的冗余项。日志记录包括患者的IP地址、患者的ID、患者请求访问的与医疗相关的URL页面、请求方法、访问时间、传输协议、传输的字节数、错误代码等属性,而与医疗信息服务的数据挖掘相关的只有患者IP地址、患者请求访问的医学信息URL页面及访问时间,其他费医疗服务相关的属性可以去掉。医疗服务相关的URL页面中除了患者关心的医疗服务信息正文外,往往还有医学图像、声音、医学视频等辅助信息,挖掘日志的目的是找出患者的共同访问模式,关于医学辅助信息的记录是无用的,可以删除。这可通过检查医学信息URL的后缀来实现,后缀为gif,jpeg,…等无关请求的记录都去掉。当然,如果医疗服务网站内容主要是图片的话,则须另行考虑,然后在此基础上进行会话识别[9]。医疗服务运作机构管理者通过挖掘服务器的医疗日志文件,得出患者的访问模式,从而可以进一步分析和研究日志记录的对医疗服务需求的规律,以改进网站的组织结构及其性能,构造自适应网站,还可以通过统计和关联分析,增加个性化的医疗服务,发现潜在的患者群体。对一个医疗数据对象的集合进行分析,它要划分的类是未知的,这种情况下,采用聚类是比较适合的。通过聚类,能够识别密集的和稀疏的区域,能够从网站患者访问路径中发现不同的患者特征,从而发现全局的分布模式,以及医疗数据属性之间的有趣的相互关系[10]。

3.2.3 患者访问页面的次序聚类

从医疗服务运作机构站点组织者来看,总是希望患者的浏览行为与页面间超链接设置相一致。患者对medical Web站点的访问存在某种有序关系,这种有序关系反映的是患者的一种访问兴趣,也就是说群体患者的访问兴趣和他们的访问序列有很强的相关性,关注患者浏览每一页面访问时间、持续时间及源链接,形成一个患者访问事务的超集,其中包括所有患者的访问路径。能从客户端收集到的最细微的信息就是患者访问链接流,以及访问时间及驻留时间,其它信息均可由这些信息派生出来。网站访问时段对聚类的结果影响较大,对不同时段的访问患者有明显的聚类效果[11];随着聚类数的提高,聚类中心的平均长度的明显提高,能够更好的对访问患者进行分类,满足医疗服务的个性化服务。

3.2.4 划分医疗信息服务的聚类算法的应用

基于密度的聚类算法处理数字属性效果最好,而处理字符属性效果较差,基于网格的医疗信息服务聚类算法克服了这些缺点,它继承了属性空间中的拓扑结构,将对点的处理转化为对空间的处理,通过对空间的划分达到医疗信息服务数据聚类的目的。医疗信息服务的聚类算法其优点是对医疗信息服务数据的排序不敏感并且可以处理不同属性的医疗信息服务数据。该类型的算法实际上综合了划分聚类算法和层次聚类算法的思想,是这两种算法发展的必然融合[12]。

3.2.5 基于网格的医疗信息服务聚类方法

通过空间划分实现医疗服务信息聚类,其基本思想是将空间划分为有限数目的医疗服务网格单元形成医疗服务信息网格结构,所有聚类操作都在网格结构上进行[13]。该方法的主要优点是算法的处理时间与医疗服务对象个数无关,具有良好的效率和可扩展性,但聚类质量依赖于医疗服务网格划分的量化尺度。基于网格的医疗信息服务聚类算法采用网格段汇总数据,医疗服务信息网格段存储在医疗服务网格目录中并在目录中按不同医疗服务尺度存放医疗服务信息数据[14]。每个段的密度定义为其中点的数目与其空间尺度的比值。基于网格的医疗信息服务聚类方法的主要优点是对医疗类相关信息服务处理速度快,处理时间独立于数据对象的数目,仅依赖于量化空间中每一维上的医疗信息服务单元数目。但所有的网格聚类算法都存在量化尺度的问题,一般来说,医疗信息服务划分太粗糙造成不同聚类的对象被划分到同一个单元的可能性增加(量化不足);相反,划分得太细致就会得到许多小的聚类(量化过度)。通常的方法是先从小单元的医疗信息服务开始寻找聚类,再逐渐增大单元的体积,重复这个过程直到发现满意的医疗信息服务聚类为止[15]。

3.2.6 医疗服务信息路径聚类