目标聚类

2024-08-21

目标聚类（精选7篇）

目标聚类篇1

1 引言

视频运动目标的实时检测和定位处于视觉监视系统的底层,是各种后续高级处理如视频分析[1]、视频编码[2]、视频检索[3]及视频监控[4]等应用的基础。本文运用减法聚类算法[5]对视频运动目标进行定位,分析了减法聚类算法的原理,给出了目标定位的框架,研究了本文方法对不同视频运动目标的定位效果,并与经典的基于区域生长的定位方法(简称区域生长法)进行了详细比较。实验结果表明,本文的视频运动目标定位方法具有较好的鲁棒性和实用性。

2 减法聚类算法

聚类算法是一种将数据分类的方法,其主要目的在于找出数据中较相似的几个聚类,并找出各个聚类的代表点,称为中心点或原型。使用这些中心点来代表原先大量的数据点。减法聚类算法是由Chiu[5]提出的一种聚类算法。考虑n维空间的N个数据点(x1,x 2,…,xN),不失一般性,假定数据点均已归一化到一个超立方体空间。考虑每个数据点都可能作为聚类中心,将数据点xi处的密度函数定义为:

这里α=γ/ra2,γ是一个正常量,影响着指数函数曲线的曲率;ra是一个正数,为聚类中心有效邻域的半径,ra定义了数据点xi周边的一个邻域,半径以外的数据点对该点的密度贡献甚微。显然,如果一个数据点有多个邻近的数据点,则该数据点具有较高的密度值。在计算出每个数据点的密度后,选择具有最高密度的数据点作为第一个聚类中心,即每次只能找出一个聚类中心。为了找出新的聚类中心,需修正每个数据点的密度,即在每个数据点的密度上减去一定的密度值:

其中:kP*为第k个聚类中心的密度,xi是需被修正的数据点,xk*为第k个聚类中心,rb为一正常数,定义了一个密度显著衰减的邻域,抑制因子η为大于1的正常数,η的经验值为1.25≤η≤.15,即rb大于ra,可避免出现相离很近的聚类中心。经过修正,在以rb为半径的圆域内,靠近第k个聚类中心xk*的数据点的密度将显著减小,这样使得这些点不太可能被选为下一个聚类中心。联合式(2)~(5)可得:

在修正了每个数据点的密度值后,将具有最大密度的数据点选为聚类中心,再次修正所有数据点的密度,该过程不断迭代,直至找出所有有效的聚类中心,式(7)可作为迭代终止条件:

1P*为第一个聚类中心的密度,其中0<ε≤1。

3 目标定位

本文利用每隔一段时间内每个像素的帧间积累差异信息自适应建立背景模型,用背景差技术检测出前景目标区域[6],在经过适当的空域滤波后,采用Otsu法[7]进行最优阈值化,对阈值化后的二值图像进行下采样,然后采用减法聚类算法对视频运动目标进行定位,定位的整体流程如图1所示。

本文的减法聚类定位方法的实现步骤如下:

1)对二值图像进行1/n下采样,选取适当的n值,可结合图像的格式及目标的大小对n进行选择,当目标面积较大时,适当的下采样有利于缩短算法定位的时间(n≥1);

2)统计目标数据点(前景点)个数N,定义数据结构(考虑数据点密度值及其位置坐标)并分配合适的运算空间;

3)利用式(1)计算每个数据点的密度,求得具有最大密度值的数据点,并选该点为聚类中心,记录k=1时第一个聚类中心点的密度值及其位置坐标(k为迭代次数,每次迭代获得一个聚类中心);

4)利用每次求得的Pk*、xk*,用式(2)对密度Pi进行修正,并进一步寻找新的聚类中心;

5)如果Pk*符合式(7)的条件则退出迭代,即符合结束条件则停止迭代;

6)对得到的m个聚类中心进行标记,本文利用画圆进行标记,其中m≥1。

4 实验结果及分析

为了说明本文方法的有效性、实时性和鲁棒性,在CPU为Celeron 2.4GHz,内存为256 MB,操作系统为Windows XP SP2的PC机上,采用VC++6.0开发环境,对三种不同类型视频序列(320×240格式)的运动目标进行了定位实验,并与区域生长法进行了比较。

4.1 本文方法定位实验

图2为采用本文方法对Highway视频序列第486帧中视频运动车辆的定位效果,图2中标记了聚类中心坐标及本文方法对视频运动目标的定位顺序(1→2→3→4→5→6)。图3为与图2相应的聚类中心密度值随迭代次数k变化的曲线。从图3可以看出,聚类中心的密度随着迭代次数k的增加而减小,当迭代次数k大于7时,聚类中心的密度逐步趋向于0。

4.2 本文方法与区域生长法性能比较

为了进一步说明本文方法的定位效果,将本文方法与区域生长法作比较。图4示意了本文方法与区域生长法对Highway视频序列第486帧运动目标二值化图像的定位效果。

从图4中可以看出,当图像具有较好空域连通特性时(见图4(b)),本文方法与区域生长法具有相同的定位效果,如图4(c)、(d)所示。图5示意了当待定位二值图像(未对阈值化后的图像进行任何形态学处理或其它空域滤波操作的二值图像)的空域连通特性较差时,本文方法与区域生长法的定位效果。从图5可以看出,当待定位的二值图像空域连通特性较差时,本文方法仍然表现出了良好的定位特性,而区域生长法则对运动目标进行了重复定位,如图5(d)的黑色箭头所指的情况。

表1给出了在图4(b)和图5(b)两种情况下,本文方法与区域生长法在处理时间上的比较。从表1可见,本文方法在处理时间上要优于区域生长法。对如图5(b)所示的情况,当二值图像的空域连通特性较差时,区域生长法可能需要定位的区域也相应增多,此时容易发生重定位,所以区域生长法的处理时间也会相应地增加。图6和图7示意了本文方法和区域生长法对人脸和人手的定位效果。图6(b)和图7(a)分别为在运动区域内结合HSV颜色模型,对人脸和人手区域进行检测的效果。从图6(b)和图7(a)中可见,图中所检测到的人脸及人手区域的空域连通特性较差。图6(c)、图6(d)和图7(b)、图7(c)为本文方法和区域生长法在图6(b)和图7(a)检测的基础上,对人脸和人手的定位效果。

4.3 抗噪性实验

一般待定位的二值图像多数含有大小不一的噪声点,图8给出了当待定位的二值图像含有噪声斑点时,本文方法与区域生长法的定位效果。图8(b)含有一些由噪声引起的小斑点(白色圆圈标记的区域),此时,区域生长法也会将该小斑点当成目标进行定位,如图8(d)白色箭头所指的情况,然而,在同一问题上,本文方法则表现出了较好的抗噪性能,如图8(c)所示。

5 结论

本文提出了一种基于减法聚类算法的视频运动目标定位方法,分析了减法聚类算法的原理,给出了该定位方法的框图及具体实现步骤,与基于区域生长的定位方法做了详细比较,并给出了实验结果。本文方法适用于视频或静态图像的目标定位(如多人脸区域的定位),特别适用于当待定位视频序列的二值图像存在较大的噪声斑点或视频运动目标二值图像的空域连通特性较差的场合。实验结果表明,本文方法具有良好的鲁棒性和实用性。

摘要：针对视频运动目标定位的需要,本文给出了一种新的视频运动目标定位方法。该方法运用减法聚类算法对视频运动目标进行定位。分析了减法聚类算法的原理,给出了减法聚类算法的公式推导,目标定位的实现步骤及流程框图。研究了本文方法对不同类型视频运动目标的定位效果,并与基于区域生长的定位方法进行了详细比较。结合实验数据说明了本文方法的定位过程、处理时间及抗噪性能。实验结果表明,本文方法适用于待定位视频序列二值图像存在较大噪声斑点或空域连通特性较差的场合。

关键词：减法聚类,目标定位,区域生长,差异积累

参考文献

[1]Gian Luca Foresti.Object Recognition and Tracking for Remote Video Surveillance[J].IEEE Transactions on Circuits and Systems for Video Technology,1999,9(7):1045-1062.

[2]Fatih Porikli.Real-Time Video Object Segmentation for MPEG Encoded Video Sequences[J].SPIE Conference on Real-Time Imagining VIII,2004,5297:195-203.

[3]Changick Kim.Fast and Automatic Video Object Segmentation and Tracking for Content-Based Applications[J].IEEE Transactions on Circuits and Systems for Video Technology,2002,12(2):122-129.

[4]Jacinto C Nascimento.Performance Evaluation of Object Detection Algorithms for Video Surveillance[J].IEEE Transactions on Multimedia,2006,8(4):761-774.

[5]Chiu S L.Fuzzy model identification based on cluster estimation[J].Intelligent Fuzzy Systems,1994,2:267-278.

[6]Tao Yang,Stan Z Li,Quan Pan,et al.Real-Time and Accurate Segmentation of Moving Objects in Dynamic Scene[C]//International Multimedia Conference Proceedings of the ACM2nd international workshop on Video surveillance&sensor networks.New York,NY,USA:ACM,2004:136-143.

[7]Otsu N.A threshold selection method from gray-level histograms[J].IEEE Transactions on System Man and Cybemetic,1979,9(1):62-66.

[8]Grinias I,Tziritas G.A semi-automatic seeded region growing algorithm for video object localization and tracking[J].Signal Processing:Image Communication,2001,16(10):977-986.

目标聚类篇2

本文运用信息瓶颈 (Information Bottleneck, IB) 方法对运动目标进行子区域划分。该方法的优点是不需要先验信息, 并且可以比较方便地处理基于直方图及概率密度描述的问题, 用IB方法进行运动目标子区域聚类, 以便提取运动目标的特征信息。而传统的聚类方法 (如K-means算法、模糊C均值聚类) 的性能过分依赖距离函数和聚类中心的选择, 还必须预先给定分类类数, 如果距离函数选择得不对, 则算法的效率很差。

利用IB方法对图像区域聚类有由底至上和由顶至下两种方式。由底至上方式:首先将目标区域分割成若干小块, 每小块建立混合高斯模型 (Gaussian Mixture Model, GMM) 表示, 利用IB方法, 将互信息损失最小的两个小块进行聚类, 直到互信息损失达到阈值停止聚类。由顶至下的方式:首先将得到的目标区域划分为一类, 利用IB方法计算互信息损失最小的分割方法, 将目标区域分割为两类, 如此反复, 直到划分子区域的信息损失达到阈值, 停止分类, 实现对目标区域中子区域的聚类。本文将采用由顶至下的方式对目标区域进行聚类。

1 信息瓶颈方法概述

信息瓶颈方法[1,2,3,4,5]是近年来由Tishby提出的利用信息熵比较来实现聚类的方法, 该方法可用于图像的分割、聚类等方面。基本原理是:利用图像本身与其直方图的信息相关性来进行图像的分割与合并, 最终达到信息损失最少的最优化聚类方法。

1.1 基本原理

信息论是运用近代数理统计方法研究信息传输、存储与处理的科学。IB方法可由香农失真率理论[6]推导得出, 香农失真率理论在给定失真率约束的条件下, 可以使分类数目更具体。给出一个随机变量X和失真率度量d (x1, x2) , 想要用不多于R位的数据来表示X的特征, 即是说少于2R个聚类。可以通过扩大平均量化误差来减少聚类数目。香农率失真理论指出, 用R位表示X的最小平均失真可由下面的失真率函数得出:

$D (R) = \min_{p (\hat{x} | x) | Ι (X; \hat{X}) \leq R} E d (x, \hat{x}) (1)$

式中:Ed (x; $\hat{x}$ ) 为平均失真;I (X; $\hat{X}$ ) 是X和 $\hat{X}$ 的互信息, 分别由下式计算:

$\begin{array}{l} E d (x; \hat{x}) = \sum_{x, \hat{x}} p (x) p (x | \hat{x}) d (x, \hat{x}) (2) \\ Ι (X; \hat{X}) = \sum_{x, \hat{x}} p (x) p (\hat{x} | x) \log \frac{p (\hat{x} | x)}{p (\hat{x})} (3) \end{array}$

式中:随机变量 $\hat{X}$ 可近似视为X的分类结果。

IB方法不同于传统的失真率理论, 它避免了任意选取距离或是失真度量。相反, 目标空间Y的分类是通过保留它关于特征空间X的相关信息。在IB方法中, 假设 $\hat{Y}$ →Y→X是一条马尔可夫链, 即给定Y, 聚类 $\hat{Y}$ 和特征空间X是独立的, 考虑下面的失真函数:

$\begin{array}{l} d (y, \hat{y}) = \int p (x | Y = y) (\log \frac{p (x | Y = y)}{p (x | \hat{Y} = \hat{y})}) d x \\ = D_{Κ L} (p (x | Y = y) | | p (x | \hat{Y} = \hat{y})) (4) \end{array}$

令 $f = p (x | y) ‚ g = p (x | \hat{y})$ , 则 $D_{Κ L} (f | | g) = E_{f} (\log \frac{f}{g})$ 是Kullback-Liebler散度[6]。

寻找一个分类 $\hat{Y}$ , 使得在给定聚类效果I (Y; $\hat{Y}$ ) 约束的情况下, 信息损失I (Y; $X) - Ι (\hat{Y}$ ;X) 最小。由聚类 $\hat{Y}$ 导致Y和X的互信息损失可以视为是失真度量的平均值:

I (Y; $X) - Ι (\hat{Y}$ ;X)

$\begin{array}{l} = \sum_{y, \hat{y}, x} p (y, \hat{y}, x) \log \frac{p (y | x)}{p (y)} - \sum_{y, \hat{y}, x} p (y, \hat{y}, x) \log \frac{p (x | \hat{y})}{p (x)} \\ = \sum_{y, \hat{y}, x} p (y, \hat{y}, x) \log \frac{p (x | y)}{p (x | \hat{y})} \\ = \sum_{y, \hat{y}} p (y, \hat{y}) \sum_{x} p (x | y) \log \frac{p (x | y)}{p (x | \hat{y})} \\ = E (D_{Κ L} (p (x | y) | | p (x | \hat{y}))) (5) \end{array}$

根据式 (1) , 式 (4) , 式 (5) 得到:

$D (R) = \min_{p (\hat{y} | y) | Ι (Y; \hat{Y}) \leq R} Ι (Y; X) - Ι (\hat{Y}; X) (6)$

它就是由IB方法得出的最小互信息损失准则, 即找到使目标和特征之间互信息损失最小的聚类。

1.2 算法特点

本文讨论基于信息瓶颈方法的聚类方法特点包括:

(1) 对图像模型 (图像模型可能是离散和连续的) 进行聚类, 而不是对图像像素, 该方法基于密度函数表达式, 因此可方便处理基于直方图描述的问题;

(2) IB方法将类别之间的相似测度与聚类准则统一为最小互信息损失, 而传统聚类方法这两者是不同的, 需要分别计算;

(3) IB方法能自动给出聚类过程的终止条件, 即自动给出平均互信息损失最小准则下的聚类类别个数, 这是传统聚类方法所不具备的。

2 目标的混合高斯模型子区域描述

图像分类第一步是将输入视频图像的原始像素表示转换为矢量表示, 图像表示可能是离散的 (比如直方图) 或是连续的, 直方图在文献中很常见并且已经得到了充分利用[7]。在这一节首先介绍在连续图像中的表示方法, 再讨论利用信息瓶颈方法将混合高斯模型表示的目标区域进行聚类。

2.1 像素点分组

在连续域, 每一幅图像在颜色 (L*a*b) 特征空间都用一个混合高斯模型来表示。应该注意到表示模型是一般化的, 它可以用于任何需要的特征空间 (例如纹理、形状等) 或是这些特征空间的组合。为了使其包含空间信息, 将像素点的所在位置 (x, y) 也添加到特征矢量中。在特征提取之后, 每一个像素点都用一个五维特征矢量表示, 图像作为整体就用一个五维空间的特征矢量集表示。通过对选定特征空间的特征矢量进行分类, 将像素点分类到相似区域中, 这里假设前提是图像颜色和它们在图像平面的空间分布是由混合高斯函数产生的。在图像平面的每一个相似区域由一个高斯分布表示, 图像的区域就用混合高斯模型表示。

如果一个d维随机变量的密度函数是:

$\begin{array}{l} f (y) = \sum_{j = 1}^{k} α_{j} \frac{1}{\sqrt{(2 π)^{d} | Σ_{j} |}} \cdot \\ \exp {- \frac{1}{2} (y - μ_{j})^{Τ} Σ_{j}^{- 1} (y - μ_{j})} (7) \end{array}$

那么它的分布是k阶混合高斯模型。

用最大期望 (EM) 算法来决定特征空间中k阶混合高斯的最大似然参数 (与文献[8]类似) , 用最小描述距离 (MDL) 算法来选择k值。在本文实验中, k取值为4～8。

图1给出了两个对输入图像进行混合高斯建模的例子, 图1 (a) , 图1 (b) 的左图为输入图像, 右图为混合高斯模型建模的图像。由此可以清晰地看到, 每个局部的混合高斯模型都是椭圆形式, 每个椭圆表示图像平面中每个局部的混合高斯模型的平均颜色和空间分布。

图像分类程序的第二步是基于信息论法则, 运用IB方法将被提取图像进行分组到连续的类中, 在目标图像可能被分入的所有类中, 需要的是使目标图像及从它们所提取的特征之间互信息损失最小的类。假设目标空间Y和特征空间X的联合分布为p (y, x) 。根据IB方法, 寻找一个分类 $\hat{Y}$ , 使得在给定聚类效果I (Y; $\hat{Y}$ ) 约束的情况下, 信息损失I (Y; $X) - Ι (\hat{Y}$ ;X) 最小 (式 (6) ) 。

2.2 IB聚类算法

由IB方法提出的最小化问题可通过基于迭代程序[2]的算法近似解决。算法初始时, 可随意进行聚类, 使每一类由一个点组成, 为使因聚类导致的总信息丢失最少, 每一步都对类进行合并, 以使由合并导致的互信息丢失最小。令c1和c2是Y中的两个类, 合并c1和c2丢失的信息为:

$d (c_{1}, c_{2}) = Ι (C_{b e f o r e}, X) - Ι (C_{a f t e r}, X) \geq 0 (8)$

此处I (Cbefore, X) 和I (Cafter, X) 是合并前后类和特征空间的互信息。标准信息理论处理表明:

$\begin{array}{l} d (c_{1}, c_{2}) = \sum_{x, i = 1, 2} p (c_{i}, x) \log \frac{p (c_{i}, x)}{p (c_{i}) p (x)} - \\ \sum_{x} p (c_{1} \cup c_{2}, x) \log \frac{p (c_{1} \cup c_{2}, x)}{p (c_{1} \cup c_{2}) p (x)} \\ = \sum_{x, i = 1, 2} p (c_{i}, x) \log \frac{p (x | c_{i})}{p (x | c_{1} \cup c_{2})} \\ = \sum_{x, i = 1, 2} p (c_{i}) D_{Κ L} (p (x | c_{i}) | | p (x | c_{1} \cup c_{2})) (9) \end{array}$

由此可以看出, 由IB方法得到类c1和c2的距离度量, 既考虑了p (x|c1) 和p (x|c2) 分布的不同, 也考虑了两个类的大小。

2.3 目标子区域聚类

给定视频图像序列Y和特征集X, 那么用来表示一幅图像中特征分布的混合高斯模型x就是条件密度函数f (x|y) , 假设观察一幅图像的先验概率统一是p (y) , 联合图像-特征分布即是p (x, y) ;假设c是图像的一个类, 其中对每一幅图像y∈c都是通过该类的混合高斯模型来表示:

$f (x | y) = \sum_{j = 1}^{k (y)} α_{y, j} Ν (μ_{y, j}, Σ_{y, j}) ‚ y \in c (10)$

式中:k (y) 就是f (x|y) 中高斯部分的数量。聚类中图像f (x|c) 的特征分布, 通过对类中所有图像模型进行平均而得到:

$\begin{array}{l} f (x | c) = \frac{1}{| c |} \sum_{y \in c} f (x | y) \\ = \frac{1}{| c |} \sum_{y \in c} \sum_{j = 1}^{k (y)} α_{y, j} Ν (μ_{y, j}, Σ_{y, j}) (11) \end{array}$

注意到f (x|y) 是GMM分布, 每一个类c的密度函数f (x|c) 就是多个GMM的混合, 因此也是GMM。

假设f (x|c1) , f (x|c2) 是与图像聚类c1, c2分别相联系的GMM。聚类c1∪c2合并后的GMM是:

$\begin{array}{l} f (x | c_{1} \cup c_{2}) = \frac{1}{| c_{1} \cup c_{2} |} \sum_{y \in c_{1} \cup c_{2}} f (x | y) \\ = \sum_{i = 1, 2} \frac{| c_{i} |}{| c_{1} \cup c_{2} |} f (x | c_{i}) (12) \end{array}$

由表达式 (9) 得到的两个图像聚类c1, c2的距离是:

$d (c_{1}, c_{2}) = \sum_{i = 1, 2} \frac{| c_{i} |}{| Y |} D_{Κ L} [f (x | c_{i}) ∥ f (x | c_{1} \cup c_{2})] (13)$

此处|Y|是图像序列数目的大小。因此, 为了计算两帧图像聚类c1, c2之间的距离, 需要计算两个GMM分布之间的KL散度。多个GMM之间的KL散度通过解析计算很困难, 因此通过蒙托卡罗方法进行近似, 用x1, x2, …, xn表示由属于类c1的图像提取出的特征集, KL散度DKL (f (x|c1) ‖ (x|c1∪c2) ) 可以近似如下:

$\begin{array}{l} D_{Κ L} (f (x | c_{1}) ∥ f (x | c_{1} \cup c_{2}) \\ ≅ \frac{1}{n} \sum_{t = 1}^{n} \log \frac{f (x_{t} | c_{1})}{f (x_{t} | c_{1} \cup c_{2})} (14) \end{array}$

另一个可用的近似是采用从混合高斯分布f (x|c1) 的采样来代替图像数据, 这就可以在不知道图像是由什么模型建立的情况下计算KL散度。图像分类实验表明, 两种对KL散度的近似[9]没有显著的区别。式DKL (f (x|c2) ‖ (x|c1∪c2) ) 可以通过类似方法近似。

IB算法进行图像目标子区域聚类的步骤如下 (本文采用由顶至下的聚类方式) :

(1) 初始聚类:划分每个跟踪目标自成一类。

(2) 在每一步中, 分割目标中两块子区域c1和c1, 使得信息损失d (c1, c2) (式 (13) ) 最小。

(3) 继续执行分割程序直到信息损失达到预设门限, 分割子区域将使信息损失增加而超过门限, 故停止分割。

3 实验结果

通过在视频中运动的人来验证IB方法聚类的性能。实验数据使用固定数码摄像机进行拍摄得到, 视频流中每帧图像大小为320×240, 拍摄速率为每秒30帧, 采样数据为100帧图像序列。图2 (a) 、图2 (b) 右图的椭圆区域即是用IB方法聚类得到的运动目标 (人) 区域, 显示的是第34, 42帧的结果。图2 (a) 、图2 (b) 左图是这两帧的原图。

用IB方法聚类可以基于直方图或基于概率密度分布进行聚类, 本文的实验是采用基于直方图的聚类, 分割时采用的是四叉树分割策略。由聚类的结果可以看出, 可以很容易区分人体的头部、上肢、上体、腿部。在第34帧中 (图2 (a) 右图) , 此时由于两条腿是重叠的, 所以聚类在一个椭圆区域里;上肢摆动幅度不大, 和上体聚类在一个椭圆区域里。在第42帧中 (图2 (b) 右图) , 由于两条腿距离明显, 聚类为两个椭圆区域;上肢小臂摆动明显, 单独聚为一类。

4 结语

用IB方法对运动目标进行聚类, 将各个可能的运动目标区域分别用一个椭圆, 以及该椭圆内的像素直方图来描述, 这样得到各区域的像素直方图相对更为单一, 这为运动目标下一步的跟踪等研究提供了比较小的搜索空间, 减小了计算量。

本文提出的方法仍有几个问题需要解决。在GMM有大量高斯模型的情况下, 用蒙托卡罗方法近似KL散度仍存在问题, 近似需要大量的采样, 这就增加了复杂度并可能引入采样噪声。需要继续研究以找到一种更简洁的聚类表示方法 (比如, 参数减少的GMM) ;需要一种解析算法, 或是更简单的估计来计算两个GMM的KL散度。

摘要：基于信息瓶颈理论实现了一种视频序列中运动目标区域的聚类方法。在介绍信息瓶颈方法聚类原理和特点的基础上, 对视频序列中的图像混合高斯建模形成各个子区域, 然后根据信息瓶颈法对各子区域聚类, 使得互信息损失最小。实验结果显示出了该聚类方法能够有效地实现运动目标区域的聚类。

关键词：信息瓶颈,混合高斯模型,运动目标,聚类

参考文献

[1] TISHBY N, PEREIRA F, BIALEK W. The information bottleneck method [C]//Proc. of the 37th Annual Allerton Conference on Communication, Control and Computing. [S.l.]: AACCCC, 1999: 368-377.

[2]SLONI M N, TISHBY N.Agglomerative information bot-tleneck[C]//Proc.of Neural Information Processing Sys-tems.[S.l.]:NIPS, 1999:617-623.

[3]SLONI M N, FRIEDMAN N, TISHBY N.Unsuperviseddocument classification using sequential information maxi-mization[C]//Proc.of the 25th Annual International ACMSIGIR Conference on Research and Development in Infor-mation Retrieval.[S.l.]:ACM, 2002:1151-1161.

[4]SHIRI Gordon, HAYIT Greenspan, JACOB Goldberger.Applying the information bottleneck principle to unsuper-vised clustering of discrete and continuous i mage represen-tations[C]//Proceedings of the Ninth IEEE InternationalConference on Computer Vision.USA:IEEE, 2003:120-128.

[5] GUEGUEN Lionel, DATCU Mihai. Image time series data mining based on the information bottleneck principle [J]. IEEE Transactions on Geoscience and Remote Sensin, 2007, 45 (4) : 827-838.

[6] COVER T M, THOMAS J A. Elements of information theory[M]. New York: John Wiley, 1991.

[7]SWAIN MJ, BALLARD D H.Color indexing[J].Inter-national Journal of Computer Vision, 1991, 7 (1) :11-32.

[8] CARSON C, BELONGIE S, GREENSPAN H, et al. Image segmentation using expectation-maximization and its application to image querying [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24 (8) : 1026-1038.

目标聚类篇3

电网需求侧用电特征挖掘、评价与控制近年来受到广泛关注[1]。单边市场模式下, 电力需求相对刚性, 对售电市场的细化研究显得非常重要[2,3,4,5,6]。文献[2]提出了用电市场结构对行业电量电价影响评价方法及量化因子。市场细分思想也被引入负荷预测领域[4]。文献[4,5]从电力营销的宏观层面上进行售电市场分析、预测、评估与综合测评。文献[6]阐述了已在欧洲试行的针对分布能源应用的用电水平及类型评价新方法。近年来, 数据挖掘为负荷特征识别提供了全新技术发展空间[7]。文献[8]应用主成分与曲元分析法对比层次聚类、k—均值、模糊C—均值等挖掘算法在负荷特性分析中的效率与价值, 对需求用电特征分析工具的选择具有指导意义。

从当前研究成果看, 缺少市场细分下的多指标综合测算方法。文献[5]提出的最优状态面积法取得较好效果, 但其仍针对传统分类方式, 缺乏对售电对象深入挖掘。本文提出用电集群概念, 对售电市场进行多目标聚类, 设计熵权改进的属性测度分析体系, 达到了售电对象特征属性精细分析的目的。

1 售电市场分析维度

1.1 用电集群定义

在需求常规分类中, 按电价分为农业、居民、工商业用电;按行业分为冶金、轻工、制造、化工用电等。但就同质性而言, 其划分依据不在于用电目的, 而应在于电压等级、容量、负荷形态、可靠性及电能质量要求等本质属性[1]。仅研究传统售电对象不足以精细挖掘用电特征分布, 容易造成市场评价、电价制定、需求侧管理等方面决策偏差, 参见附录A图A1。本文提出售电市场用电集群概念:用电集群是售电市场中以某种或多种分类准则划分的负荷样本群体。分类准则除传统口径外还可包括:典型形态或指标、需求响应程度与方式等。只有精细挖掘各典型集群综合特征, 才能在不同角度与精度上立体刻画售电市场特性细节。

图1展现了用电集群交叉属性。图1 (a) 说明设置单目标或多目标可将样本总体划分为不同集群;图1 (b) 表明对任意用户, 集群属性具有多样性。在负荷总体样本中形成集群的目标可以有多种, 为方便阐述, 将所用到的集群划分单目标列于表1。

1.2 基于用电集群的售电市场分析维度

不同目标形成的用电集群使售电市场分析对象范围大为扩展。对不同目标形成的用电集群对象从不同时间尺度进行多类事务分析构成了售电市场空间的分析维度, 如图2所示。

图2中分析事务可包括经济评价[2]、市场集中度[4]等, 实线三角空间代表以目标3划分售电市场后, 对集群进行短期电价响应评估。

2 售电市场用电集群精细划分

2.1 样本数据失真辨别与修正

可设短时段内数据纵向相似, 即连续3个数据无突变, 且附近同类日曲线横向相似。利用这2个特点通过样本统计指标及预设阈值判断失真数据。同类型日横向数据失真辨别与修正过程如下:

$\bar{x}_{n, i} = \frac{1}{Ν} \sum_{n = 1}^{Ν} x_{n, i} i = 1, 2, \dots, 96 (1)$

$σ_{i}^{2} = \frac{1}{Ν} \sum_{n = 1}^{Ν} (x_{n, i} - \bar{x}_{n, i})^{2} (2)$

$| x_{n, i} - \bar{x}_{n, i} | > 3 σ_{i} (3)$

$x_{n, i} = \frac{1}{2} (α_{1} \sum x_{n \pm 1, i} + β_{1} \sum x_{n, i}^{1, 2}) + γ_{1} \bar{x}_{n, i} (4)$

式中:xn, i为第n天第i点数据;xn±1, i为xn, i附近2个横向负荷;x $_{n, i}^{1, 2}$ 为最近2个相似日负荷点。

式 (3) 利用3σ原理进行失真判断。式 (4) 引入3个总和为1的权重修正数据。且有:

$x_{n, i} ´ = \frac{1}{5} \sum_{j = - 2}^{2} x_{n, i + j} i = 1, 2, \dots, 96 (5)$

|xn, i-xn, i′ |>δxn, i′ (6)

$x_{n, i} = \frac{1}{2} (α_{2} \sum x_{n, i \pm 1} + β_{2} \sum x_{n, i \pm 2}) (7)$

式中:xn, i′为平滑后序列;xn, -1, xn, 0, xn, 97, xn, 98分别为第n-1天、第n+1天最后及最前2个负荷;δ为失真阈值, 取0.08～0.15;α2, β2为参数, 满足α2+β2=1。

式 (5) 用于形成平滑序列。若满足式 (6) 失真条件, 则用式 (7) 修正数据。

2.2 指定目标下集群特征序列筛选

用电集群划分目标确定后, 计算样本各单元特征序列, 其计算目标由划分目标特征量筛选得到。首先定义归一化方法如下:

$\hat{x}_{i} = \frac{x_{i} - x_{i m i n}}{x_{i m a x} - x_{i m i n}} (8)$

式中: $\hat{x}_{i}$ 为归一化后i点数据;ximin和ximax分别为序列最小、最大值。

归一化方法将数据压缩在[0, 1]区间中。以下进行特征序列设定。

1) 以负荷形态相似为集群划分目标。

在此目标划分下, 成员特征量为各自典型负荷归一化曲线形态, TL={L1, L2, …, L24}, Li为负荷值。

2) 以指标集为目标。

指标集为:负荷率I1, 峰谷差率I2, 峰、平、谷期负载率I3, I4, I5, 最小负荷率I6, TI={I1, I2, I3, I4, I5, I6}。

3) 以电价响应类型为目标。

利用电价弹性矩阵[9]量化用户响应, 将其中衡量响应程度与方式的自弹性及交叉弹性系数作为特征序列:

${\begin{cases} e_{i i} = \frac{\partial Q_{i}}{Q_{i}} \frac{Ρ_{i}}{\partial Ρ_{i}} \\ e_{i j} = \frac{\partial Q_{i}}{Q_{i}} \frac{Ρ_{j}}{\partial Ρ_{j}} \end{cases} (9)$

式中:i, j∈{f, p, g};f, p, g代表峰、平、谷时段;Q和P分别为用户电量与电价。

特征序列TE={eff, epp, egg, efp, efg, epg, egp, egf, epf}。

4) 以行业为目标。

将行业编号作为特征量赋予各用户, TV={V1}, V1为用户所属行业编号。

2.3 可视化混合聚类算法与评判指标

通过指定目标下样本成员特征序列计算, 得到归一化M×NT阶 (M为成员数, NT为特征量个数) 特征矩阵, 利用各维划分集群。自组织映射神经网络 (self-organizing map, SOM) 可在保持拓扑特征下实现从n维空间到2维平面数据可视化降维[7,8], 2层节点由权重向量连接。聚类步骤[10]如下:

1) 对输出层各节点权重Wj进行初始化, 并定义神经网络训练结束条件;

2) 利用输入向量X和权值向量Wj的欧氏距离求距离最小的连接权重向量Wg:

$∥ X_{i} - W_{g} ∥ = \min ∥ X_{i} - W_{j} ∥ (10)$

3) 以竞争所得的获胜神经元g为中心取拓扑邻域Hg (t) , 其间单元为激活神经元, 以下式更新:

$W_{j} (t + 1) = W_{j} (t) + η (t) h_{g j} (t) (X_{i} (t) - W_{j} (t)) (11)$

式中:η (t) 为时刻t神经网络学习率;hgj (t) 为获胜神经元g的邻域函数。

4) 反复训练, 减小学习率, 至权值误差小于阈值或达到训练步数停止, 输出聚类结果。

利用SOM虽可直观判断用电集群类别但缺乏客观判别依据。为此选用k—均值算法对邻近点进行二次聚类。算法流程[7]为:①从n个对象中任选k个对象作为初始中心;②根据与中心相似度, 将其分配给与其最相似的类别;③以均值重新计算新类的聚类中心;④不断重复这一过程直到标准测度函数收敛。所取标准测度函数为:

$E = \sum_{i = 1}^{k} \sum_{p \in C_{i}} | p - m_{i} |^{2} (12)$

式中:E为样本与聚类中心均方差之和;p代表对象空间中的一个点;mi为聚类Ci均值。

假设聚类数为K, 各类包含序列集合为Ck, 其聚类中心代表曲线为xc, nk表示每个类中包含的序列单位数目, x1, j和x2, j为不同用户负荷序列, 其间的距离定义如下:

$D (x_{1, j}, x_{2, j}) = \sqrt{\frac{1}{24} \sum_{j = 1}^{24} (x_{1, j} - x_{2, j})^{2}} (13)$

采用MIA (mean index adequacy) 指标[8]IMIA进行聚类数与质量评判, IMIA可表征各聚类中心与对应类中所有单元的距离平均值, 越小表明聚类效果越好。

$Ι_{Μ Ι A} = \sqrt{\frac{1}{Κ} \sum_{k = 1}^{Κ} D^{2} (x_{c}, x_{k})} (14)$

式中:

$D (x_{c}, x_{k}) = \sqrt{\frac{1}{n_{k}} \sum_{n = 1}^{n_{k}} D^{2} (x_{c}, C_{k}^{n})} (15)$

xk为第k测试类数的样本子集;Cnk为第k测试类数子集中的第n个样本。

3 用电集群特征属性测度计算

3.1 多指标属性测度模型

属性测度[11]能有效规避层次法级差大、模糊评判过于依赖极值等缺点。设Ω为用电集群空间, 对集群x需测m个指标I1, I2, …, Im, 评价集为{C1, C2, …, CK}, Ck (1≤k≤K) 为评价类, 可有强弱优劣之分, 如C1={差}, C2={中}, C3={优}则可记为C3>C2>C1, 称为基于用电集群的售电空间的某种有序分割。评价集常以附录A表A1形式列出。

定义用电集群x具有级别Ck的大小用属性测度μxk=μ (x∈Ck) 表示, x的第j个指标 (其值为t) 具有Ck的大小用属性测度μ $_{x j}^{k}$ (t) 表示, 按属性测度理论[11]有:

$\sum_{k = 1}^{Κ} μ_{x}^{k} = 1 μ_{x}^{k} \geq 0 (16)$

$\sum_{k = 1}^{Κ} μ_{x j}^{k} (t) = 1 μ_{x j}^{k} (t) \geq 0 (17)$

由附录B表B2可确定单指标属性测度函数μkxj (t) , 假定ajk表示指标j的指标值范围 (见附录A表A1) , 且aj0<aj1<…<ajk, 令

$\begin{array}{l} b_{j k} = \frac{a_{j (k - 1)} + a_{j k}}{2} k = 1, 2, \dots, Κ (18) \\ d_{j k} = \min (| b_{j k} - a_{j k} |, | b_{j (k + 1)} - a_{j k} |) (19) \end{array}$

确定用电集群单指标属性测度函数μkxj (t) 如下:

$\begin{array}{l} μ_{x j}^{k} (t) = \\ {\begin{cases} 1 a_{j γ} + d_{j γ} < t < a_{j k} - d_{j k} \\ \frac{| t - a_{j γ} + d_{j γ} |}{2 d_{j γ}} a_{j γ} - d_{j γ} \leq t \leq a_{j γ} + d_{j γ} \\ \frac{| t - a_{j k} - d_{j k} |}{2 d_{j k}} a_{j k} - d_{j k} \leq t \leq a_{j k} + d_{j k} \\ 0 t < a_{j γ} - d_{j γ}, t > a_{j k} + d_{j k} \end{cases} (20) \end{array}$

式中:j=1, 2, …, m;k=2, 3, …, K;γ=k-1。

用电集群特征属性计算中, 各特征指标所起作用有差异, 设计权重wj计算多指标属性测度:

$μ_{x}^{k} = \sum_{j = 1}^{m} w_{j} μ_{x j}^{k} (t) \exists w_{j} \geq 0, \sum_{j = 1}^{m} w_{j} = 1 (21)$

用电集群的电力负荷特征属性集是负荷属性空间的有序分割, 可采用置信度准则。设λ为置信度, 0.5≤λ≤1, 如果有:

$k_{0} = \min {k | \sum_{l = 1}^{k} μ_{x}^{l} \geq λ, 1 \leq k \leq Κ} (22)$

则判定用电集群x属于Ck0级别, 其中置信度λ通常可取值为0.6～0.7。

3.2 引入熵权的综合属性测度加权系数改进

式 (22) 中测度主观权重易造成用电集群特征属性计算偏差, 熵权可有效弥补这一不足[12]。信息熵解决的是不确定系统信息量的量度问题, 设系统各状态出现概率为Pi (i=1, 2, …, n) , 其熵H定义为:

$Η = - \sum_{i = 1}^{n} Ρ_{i} \ln Ρ_{i} 0 \leq Ρ_{i} \leq 1, \sum_{i = 1}^{n} Ρ_{i} = 1 (23)$

设用m个指标构成的指标体系分析n个待计算用电集群, 第i个集群的第j个指标值为rij′ (i=1, 2, …, n;j=1, 2, …, m) , 形成用电集群原始指标矩阵R′= (rij′) m×n。根据指标类型对指标作无量纲化处理, 得到rij为样本指标rij′无量纲化后的值。

效益型指标为:

$r_{i j} = \frac{r_{i j} ´ - \min_{i} r_{i j} ´}{\max_{i} r_{i j} ´ - \min_{i} r_{i j} ´} (24)$

成本型指标为:

$r_{i j} = \frac{\max_{i} r_{i j} ´ - r_{i j} ´}{\max_{i} r_{i j} ´ - \min_{i} r_{i j} ´} (25)$

由式 (24) 、式 (25) 可得归一化矩阵R= (rij) m×n, rij∈[0, 1]。根据定义, 第j个指标的信息熵为:

$Η_{j} = - k \sum_{i = 1}^{n} Ρ_{i j} \ln Ρ_{i j} j = 1, 2, \dots, m (26)$

式中: $Ρ_{i j} = (1 + r_{i j}) / \sum_{i = 1}^{n} (1 + r_{i j})$ ;k=1/ln n。

则式 (21) 中用电集群第j个指标熵权wj为:

$w_{j} = \frac{1 - Η_{j}}{m - \sum_{j = 1}^{m} Η_{j}} \exists w_{j} \geq 0, \sum_{j = 1}^{m} w_{j} = 1 (27)$

3.3 用电集群特征属性评价指标

集群属性测度计算前需建立用电集群特征属性精细评价指标集。从电力电量与经济特性角度提出应用9个评价指标, 如图3所示。其中电价响应率用交叉与自弹性系数绝对值的算术平均表示。

4 算例分析

4.1 样本数据与综合特征属性分析流程

采集某电网2004年1月—2007年12月10个行业共计317个1 kV以上等级用户日负荷数据。容量、近年目录电价作为输入一并采集。用电集群特征属性分析流程包括特征序列计算、混合聚类、属性测度计算等主要模块, 均在MATLAB 7.0平台实现。算例样本信息、集群特征属性分析流程、指标测度划分标准分别参见附录B表B1、图B1、表B2。

4.2 基于混合可视化聚类的用电集群生成

SOM输入向量为317个用户特征序列, 4类目标维度为24维、6维、9维、1维。取18×18阶方阵神经元, 邻域函数取六边形函数, 最大训练步数2 500, 可得317个样本点的2维可视分布。采用收敛能力良好的k—均值计算可视平面各点邻域相似性, 较优类数利用MIA指标测试, 表1各目标不同聚类数下MIA值参见附录B图B2。当目标1～目标3划分超过6类、5类、5类时, 随类数增加而MIA减小趋势明显减弱, 可定义目标1～目标3分类数为6类、5类、5类, 目标4为既定的10类。基于SOM输出2维平面的k—均值计算收敛后, 可得附录B图B3中各目标下集群可视化聚类。

定义A (i, j) 为目标i下的第j个用电集群。附录B图B4展示了A (1, 1) , A (1, 6) , A (2, 2) , A (3, 4) 用电集群生成结果示例。

4.3 熵权改进后的用电集群特征属性测度计算

针对图3指标可得附录B表B3所列混合聚类后4类26个集群整体特征序列计算结果。用电集群整体特征直接影响其对售电市场的贡献水平。图3指标具有离散分布特点, 且成本与效益型指标共存, 无法精确定量判断各集群综合属性测度关键点。图4以雷达图展示了4类目标下的用电集群A (1, 1) , A (2, 3) , A (4, 7) 与A (1, 3) , A (2, 5) , A (3, 5) 特征属性序列。图中1～9为式 (24) 、式 (25) 归一化后的9个特征属性指标, 放射轴均为[0, 1]刻度, 闭环连接形成区域表示某集群特征属性指标序列。

图4虽能直观体现各用电集群单个特征指标相对高低, 但却无法客观评价集群综合整体特性相对优劣[5]。根据附录B表B2与式 (16) ～式 (22) 构造4级分段线性属性测度函数, 进行用电集群综合特征定量计算。图5为推导出的负荷率指标的4级分段线性测度函数, 其他指标推导参见附录C。结合属性测度函数与各集群特征序列计算出A (1, 6) 至A (4, 10) 共26个用电集群单指标属性测度, 完整结果列于附录B表B4。

信息熵可客观改进用电集群综合属性测度权重系数wj, 式 (23) ～式 (27) 更新结果列于表2。

定义评价因子Sx量化用电集群属性集优劣。设Ci分数ni, 对于C1>C2>…>CK, 取ni=K+1-i, 则集群x评价因子Sx分数定义为:

$S_{x} = \sum_{l = 1}^{Κ} n_{i} μ_{x}^{l} (28)$

利用式 (21) 、式 (28) 及表2熵权获取集群4级属性测度与综合测评因子, 计算结果列于表3, 完整结果详见附录B表B5。

评价因子量化了图3指标下集群综合测度, 值越大则属性相对越优。取置信度λ=0.6, 由表3可知, A (1, 1) , A (1, 2) , A (4, 9) 综合特性属于“较优”, A (4, 10) “较差”, 且A (4, 9) >A (1, 1) >A (1, 2) >A (4, 10) 。

4.4 算例结果分析

根据某地区售电市场10个行业317个用户用电集群特征属性算例计算结果, 可得以下结论:

1) SOM与k—均值混合聚类能针对既定目标精细挖掘用电集群。从MIA值和附录B图B3聚集程度可以看出, 目标2效果优于目标1, 3。图6为目标2, 3下各集群负荷率与电价响应率, 目标区分度明显。

2) 算法可基于图3指标计算用电集群综合特性, 进而分析各集群特征属性关键点。例如:图4中集群综合属性测度分别为2.540, 3.046, 2.877, 2.667, 2.802, 2.853, 6个集群综合特性高低排序为A (2, 3) >A (4, 7) >A (3, 5) >A (2, 5) >A (1, 3) >A (1, 1) 。定性来看, 雷达图所包围指标面积越大, 则集群综合特性越优, 与文献[5]结论一致。不同的是, 本文算法可精细分析特征属性差异关键点及其对集群综合测度的贡献。比较集群A (2, 3) 与A (1, 1) , 二者整体评价因子相差19.92%, 关键点在于前者的“优”、“较优”2个测度比后者高120.7%, 34.85%, 其本质在于A (2, 3) 在熵权系数最大的第5, 8, 3指标都明显高于A (1, 1) , 数据参见附录B表B3～表B5。

3) 用电集群特征属性计算的目的在于充分挖掘售电对象整体效应, 准确定位负控、需求管理或电价调整对象。例如:集群A (3, 4) 与A (3, 5) 指标9电价综合响应率为1.191, 1.374, 二者该指标测度属于较高的3级、4级 (参见附录B表B4) 。取售电量相当但指标9测度较低的集群A (1, 3) , A (4, 5) 与二者比较, 将分时价差同时拉大0.02元/ (kW·h) , 经弹性矩阵[9]测算四者削峰电量为21.4 MW·h, 39.5 MW·h, 2.03 MW·h, 1.7 MW·h, 对前2个集群调价效果明显, 市场影响力大。

5 结语

传统用电特性分析已不能满足对售电市场的深入研究要求。本文提出多目标聚类下用电集群特征属性分析新思路。通过基于划分目标的用电集群与分析维度概念, 极大地扩展了市场分析对象。采用混合聚类挖掘用电集群信息, 设计经熵权改进的集群分段属性测度分析流程, 以定量、精细计算售电市场中用电特征分布。实际算例证明所述算法效果明显, 能辅助电网公司深入分析特定售电空间。基于MATLAB平台设计的综合程序包已应用于某电网用电集群分析。用电集群的电网节点分布及其区域属性问题, 以及用电集群特征属性监测、动态识别应用与优化是未来的研究重点。

附录见本刊网络版 (http://www.aeps-info.com/aeps/ch/index.aspx) 。

摘要：提出售电市场中用电集群与分析维度概念。确定集群特征变量后, 采用自组织映射神经网络与k-均值混合可视化聚类技术对售电空间进行自定义目标划分。基于负荷与经济指标, 设计熵权改进的多指标属性测度算法对多目标划分下用电集群特性进行精细化定量综合计算, 以分析各对象属性整体相对优劣。采集某电网317个用户数据进行算例分析, 结果表明该算法能区别于传统负荷特性分析方法, 在扩大售电市场研究对象基础上实现更多有效信息挖掘与多目标售电对象特征精细分析。

关键词：多目标聚类,用电集群,自组织映射神经网络,属性测度,熵权

参考文献

[1]KIRSCHEN DS.Demand-side viewof electricity market.IEEETrans on Power Systems, 2003, 18 (2) :520-527.

[2]康重庆, 李顺福, 夏清, 等.用电市场的结构分析及其对市场营销的启示.电力系统自动化, 2003, 27 (14) :27-31.KANG Chongqing, LI Shunfu, XI A Qing, et al.Structureanalysis of electricity consumers and its instruction tomarketing.Automation of Electric Power Systems, 2003, 27 (14) :27-31.

[3]董继征, 何怡刚, 王薇, 等.基于电力细分市场的负荷分解预测方法.电网技术, 2005, 29 (17) :40-43.DONG Jizheng, HE Yigang, WANG Wei, et al.Loaddecomposition forecasting method based on electricity segmentmarket.Power System Technology, 2005, 29 (17) :40-43.

[4]胡江溢, 贾俊国, 林弘宇, 等.售电市场分析与预测指标体系.电力系统自动化, 2009, 33 (2) :10-14.HUJiangyi, JI AJunguo, LI N Hongyu, et al.Index systemofpower sale market analysis and forecasting.Automation ofElectric Power Systems, 2009, 33 (2) :10-14.

[5]庄彦, 康重庆, 胡江溢, 等.售电市场质量及其综合评价.电力系统自动化, 2009, 33 (3) :25-29.ZHUANG Yan, KANG Chongqing, HUJiangyi, et al.Qualityof power sale market and its comprehensive assessment.Automation of Electric Power Systems, 2009, 33 (3) :25-29.

[6]ENCI NAS N, ALFONSO D, I VAREZ C A, et al.Energymarket segmentation for distributed energy resourcesi mplementation purposes.IET Generation, TransmissionDistribution, 2007, 1 (2) :324-330.

[7]FIGUEIREDO V, RODRIGUES F, VALE Z, et al.An electricenergy consumer characterization framework based on datamining techniques.IEEE Trans on Power Systems, 2005, 20 (2) :596-602.

[8]CHICCO C, NAPOLI R, PIGLIONE F.Comparisons amongclustering techniques for electricity customer classification.IEEE Trans on Power Systems, 2006, 21 (2) :933-940.

[9]秦祯芳, 岳顺民, 余贻鑫, 等.零售端电力市场中的电量电价弹性矩阵.电力系统自动化, 2004, 28 (5) :16-19.QI N Zhenfang, YUE Shunmin, YU Yixing, et al.Priceelasticity matrix of demand current retail power market.Automation of Electric Power Systems, 2004, 28 (5) :16-19.

[10]KOHONEN T.Self-organized formation of topologicallycorrect feature maps.Biological Cybernetics, 1982, 43 (1) :59-69.

[11]程乾生.质量评价的属性数学模型和模糊数学模型.数理统计与管理, 1997, 16 (9) :18-23.CHENG Qiansheng.Attribute mathematical model and fuzzymathematical model for quality assessment.Application ofStatistics and Management, 1997, 16 (9) :18-23.

目标聚类篇4

基于K-means聚类思想，采用改进的形态学方法对红外图像进行预处理，然后采用基于二维梯度信息的K-means聚类算法，完成对红外图像中典型目标的检测。

1 Top-Hat算子预处理

形态学是一种非线性滤波，应用于图像和模式识别领域，其理论基础深，综合了多门学科知识，但其原理却比较简单，主要体现逻辑推理和严谨的数学演绎。设f(x,y)为输入图像；b(x,y)为结构元素；其中，(x,y)为图像平面空间的坐标点；f为(x,y)点的灰度值；b为(x,y)的结构函数值；Df和Db分别是f和b的定义域，则定义如下运算[11]

(1）膨胀

其中，[(s-x,t-y)]∈Df;(x,y)∈Db。

(2）腐蚀

其中，[(s+x,t+y)]∈Df;(x,y)∈Db。

(3）开运算

(4）闭运算

Top-Hat算子具有高通滤波的某些特性，开运算可以检测出图像中的峰，闭运算则能检测出图像中的谷。形态学Top-Hat算子能有效地识别出各种背景下的点目标，但是对于有较强背景噪声干扰的点目标图像，传统的Top-Hat算子的抑制效果不佳。为此，有学者提出修正的Top-Hat形态学滤波算子。修正Top-Hat形态学滤波器结构元由两部分组成：内部结构元C1（大小为n×n）和外部结构元C2（大小为m×m），即C1⊆C2。定义边缘结构元为A=C2-C1，在此基础上定义改进的Top-Hat算子为

改进的Top-Hat形态学滤波器能更好的抑制噪声影响。

2 改进的K-means聚类

K-means聚类是基于图像中目标和背景的灰度差异以及目标自身灰度的相似性进行分割检测，其聚类的基础是依据不同的属性进行分类，进而将具有相似属性的像素聚为同一类别。

2.1 二维梯度属性建立

经过预处理的红外图像，目标与背景的噪声得到抑制，对比度有了一定程度的增强，遍历图像中的每一像素点，分别计算图像行方向及列方向的梯度，得到每一像素点的二维梯度信息

其中，代表行方向上梯度信息；代表列方向上梯度信息；a,b代表梯度数值大小；（i,j）表征位置信息。将处于相同位置上的行向及列向梯度向量相加，即得到当前像素点的真实梯度特征为

这样得到梯度特征，表征当前点梯度信息，其模值代表梯度值大小。

2.2 梯度属性阈值预处理

二维梯度属性图中，梯度较大的像素点所在位置可认为是目标与背景的交界处，这些属性点组成了红外目标的边缘。而背景及目标内部，由于灰度值相差不大，其梯度属性要比边缘点小得多，为提高聚类效率，可选取合适的阈值TH，对梯度属性图进行处理，如下式

初始中心点的选择在K-means聚类算法中极其重要，为使各类像素点具有一定的区分度，通常寻找散布较大的点作为初始中心点。传统的K-means聚类算法是随机选取初始中心点，文中为了更好地进行红外目标分割，对在阈值和最大梯度模值之间的数值进行均分为

式中，将梯度属性图分成k类；μ（s）是第s类的中心值；max是最大梯度模值；TH为选定的阈值。

具体实现步骤如下：

(1）根据式（9）选取k个初始梯度模值均值

μ1(1）,μ2(2）,…,μk(k）。

(2）在第i次迭代时，根据如下准则将每个梯度模值都赋予k类之一（j=1,2，…，k,l=1,2，…，k,j≠l）；若

即将每个梯度模值赋予与它最相似的梯度模均值类。

(3）若对于j=1,2，…，k，有更新类梯度模均值

(4）如果对所有的j=1,2，…，k，有μ1(n+1）=μ1(n），则算法结束；否则进入步骤（2）继续下一次迭代。

3 实验结果与分析

为验证本算法对红外目标检测的效果，对实际拍摄得到的大视场红外图像进行处理，并与传统算法进行对比，结果如图1所示。其中，图1a为原始红外图像，图1b为K均值聚类处理结果，图1c为SUN-SAN算子处理结果[12]，图1d为文中算法处理结果。

原始红外图像中，主要是以天空、树木和路面为背景，以人为典型目标的图像。K均值聚类方法处理时，将部分树木和路面聚为一类，没有很好地突出树林中的目标。使用SUNSAN算子进行处理，虽然检测出目标，但处理结果中含有大量噪声点。文中算法的处理结果图中，很好地检测出目标，且较好地剔除了噪声点的影响。

为了对检测结果进行更好的评价，采用目标检测领域标准通用的几个评价指标进行客观评价，包括信噪比增益（ISNR)[13]，对比度增益（ISCR）和运行时间。ISNR和ISCR越大，说明算法抑制背景杂波和凸显目标的能力越强，各指标定义如下[1]

其中，SNRin、SNRout分别代表原始图像和处理后图像的信噪比；SCRin、SCRout分别代表原始图像和处理后图像的标准差。具体结果如表1所示。

可以看出，文中算法相较于其他两种算法，计算方便，运行时间短，并且对背景抑制作用明显，能更好的检测出目标。

4 结论

目标聚类篇5

关键词：减法聚类,目标定位,目标检测,模糊C均值聚类

0 引言

在智能监控场合,视频运动目标检测是一重要技术环节。在检测到视频运动目标区域后,需进一步定位视频运动目标,即获取视频运动目标的空间位置信息。多数研究人员在设计视频运动目标检测算法时,均假设所检测到的目标运动区域具有理想的空域连通性,然后再采用基于区域生长的方法对连通区域进行标记,以获得目标的空间位置信息。然而,在实际应用场合,所检测到的视频目标运动区域多数具有空域不连通性,即代表运动目标的区域存在分块或空洞。此时,若采用区域生长法对连通区域进行标记,则其所标记的代表视频运动目标的连通区域不可靠。目前,视频运动目标定位方法主要有基于区域生长的方法、水平垂直投影的方法及基于模式分类的方法。基于区域生长的定位方法不适用于待定位目标空域连通特性较差的应用场合。空域连通特性差的单目标定位可采用基于水平、垂直投影的定位方法,然而该方法不适用于水平、垂直方向存在重叠的多目标定位场合。基于模式分类的定位方法主要是基于数据聚类的方法,如K均值聚类、模糊C均值聚类(FCM)及减法聚类等。K均值或模糊C均值聚类算法在使用时需指定待定位目标的个数、初始位置及迭代次数等参数。孔万增和孙志海分别将减法聚类算法用于人脸和视频运动目标的定位[1,2],其实验结果表明减法聚类算法很适用于目标区域空域连通特性较差的目标定位场合。减法聚类算法是由Chiu[3]提出的一种基于密度值指标的聚类算法,该算法复杂度只与数据个数成简单的比例关系,适用于多数数据聚类场合,故逐渐得到研究人员的青睐。Sathit等[4]将减法聚类算法用于软件组件的分类。Eftekhari等[5]将减法聚类用于非线性系统建模时的紧凑模糊规则提取。Kim等[6]引入核函数距离测度替换了原减法聚类算法采用范数平方距离的度量。

视频运动目标定位是在对目标运动检测基础上的进一步处理,定位的效果直接影响着如目标跟踪、识别及编码等上层应用环节。因此,研究视频运动目标的定位问题很有意义。文献[1]虽然已给出了一种基于减法聚类的视频运动目标定位方法,然而在目标定位时采用单一尺度表示多个不同尺度的目标,并没有考虑目标尺度的不一致,且定位结果也无法获得目标的方向信息,定位结果不够合理。因此,为进一步提高减法聚类算法目标定位的准确度,本文针对文献[1]中目标定位的不足,进一步提出了一种尺度和方向自适应的减法聚类视频运动目标定位算法。

1 定位算法描述

为了能最终获得各个目标的尺度及方向信息,本文假设各个目标前景像素样本的二维空间坐标分量服从正态分布。在该假设条件下,如果能够获得各个目标前景像素的样本,则可根据数据样本多元正态分布的原则算得目标的尺度及方向信息。然而,基于减法聚类的目标定位方法只能获得视频运动目标的密度中心及目标个数,不能对所有前景像素进行归类。为了能够计算各个待定位目标尺度及方向信息,必须在减法聚类的基础上进一步对前景像素进行归类。由于减法聚类定位的结果提供了目标的位置及个数信息,所以本文选取模糊C均值聚类算法对前景像素做进一步归类。在获得各目标的样本数据后,即可算出待定位目标的二维尺度及方向。图1给出了本文尺度方向自适应减法聚类视频运动目标定位算法的流程图。现将本文所提出的目标定位算法分两部分进行阐述:1)减法聚类预定位及数据分类;2)尺度和方向参数计算。

1.1 减法聚类预定位及数据分类

设m维空间n个数据点(x1,x2,…,xn),xiT=(xi1xi2…xim)(i=1,...,n),减法聚类算法应结合具体问题考虑不同维度邻域半径。定义一对角阵Ma,其逆矩阵为Ma-1:

其中rai(i=,1,2,…,m)为数据点不同维度的邻域半径,邻域半径rai需根据不同的应用场合进行初始化。根据减法聚类算法的定义[3,7],数据点xi(i=1,...,n)处的密度值函数可表示为

在获得这n个数据点的密度值后,选择最大密度值点1x为第1个聚类中心,1P代表最大密度值。为找出新的聚类中心,需修正每个数据点的密度值,即在每个数据点xi的密度值iP上减去一定的密度值[3,7]:

其中Mb为另一对角阵,rbi(i=,1,2,…,m)为正常数,定义了一个密度值显著衰减的邻域,一般rbi=ηrai,η为大于1的正常数,η的经验值为1.25≤η≤.15,这样可避免出现相离很近的聚类中心。在修正了每个数据点密度值后,将具有最大密度的数据点选为聚类中心。该过程不断迭代,直到找出所有有效聚类中心,将式(3)简记为Pi⇐Pi'。减法聚类时可以Pk*<ε⋅P1*(0<ε≤)1作为迭代终止条件,其中1P*为第1个聚类中心密度,kP*为第k个聚类中心密度。

采用上述的减法聚类算法获得待定位目标的聚类密度值中心及目标个数后,根据模糊C均值聚类算法的思想[7],利用所有前景样本点到各个目标密度值中心的欧氏距离,计算各数据点隶属于各个密度值中心的隶属度,根据最大隶属度的模糊规则实现对前景像素样本的归类。假设减法聚类算法定位获得c个视频运动目标,目标记为Oj(j=1,...,c)。记c个视频运动目标密度值中心为yj(j=1,...,c),前景像素样本xi隶属于视频运动目标Oj的隶属度记为ωji,ωji计算公式见式(4)。利用式(5)可将所有前景样本点归到各个视频运动目标。其中dji=‖yj-xi‖,xj∈Oj,h∈1[,∞)为一加权指数,h的经验取值区间为[1.25,1.5]。

1.2 尺度和方向参数计算

设前景像素样本的二维空间坐标分量服从正态分布,则前景像素样本经减法聚类预定位及模糊C均值聚类算法归类后,各个目标均具有属于自己的前景像素样本。记第k个目标前景像素样本均值为µk,目标样本协方差矩阵为Mk,其中k=,1,2,…,c,协方差矩阵Mk为实对称阵。记协方差矩阵Mk所对应的特征向量及特征值矩阵分别为Vk和kD,则有MkVk=VkDk,即Mk=VkDkVk-1且Mk-1=Vk-1Dk-1Vk。又由于VkT=Vk-1,所以Mk-1=VkTDk-1Vk。将第k个目标某前景像素样本x偏离µk的距离度量表示为

式(6)对于二元正态分布为椭圆方程,对于三元正态分布则为椭球方程。若记z=Vk(x-µk),则式(6)可进一步表示为r2=zTDk-1z。由此可见,对于二元正态分布,式(6)所对应椭圆的两个主轴方向为协方差矩阵Mk特征向量的指向,椭圆半长轴和半短轴与协方差矩阵特征值的平方根成正比关系。利用该特点,视频运动目标可进一步用椭圆来表示,目标的方向为最大特征值相应特征向量的指向。这里第k个目标前景像素样本均值µk及样本协方差阵Mk采用一致最小方差无偏估计[8]:

设二元正态分布样本实对称协方差阵特征值λ1,λ2(λ1≥λ2),其对应的特征向量阵为V=[e 1e2],其中ei=[eixeiy]T(i=,12)。则视频运动目标的方向角θ,代表视频运动目标椭圆的半长轴ar和半短轴br可次表示为

为进一步说明目标尺度和方向参数的计算过程,本文将结合图2所示椭圆内的532组样本点,给出求取该组样本尺度及方向参数的数值计算示例。由式(7)可求得图2所示样本的均值µ=[57,72]。结合样本数据,由µ和式(8)可算得该组样本协方差矩阵M,由协方差矩阵M可进一步求得该矩阵的特征向量阵V和特征值阵D:

根据特征向量和特征值矩阵V和D,有1λ=448.5050,λ2=175.1945,对应的特征向量分别为1e=[-0.7433.0669]0T,e2=[-0.6690-.0743]3T。由式(9)可算得θ≈-0.286 5π(或0.713 5π),ra≈42.36,rb≈26.47,式(6)r值取2。最后,可得该组样本的定位结果如图2所示。

2 实验结果及分析

为进一步说明本文所提出的尺度方向自适应减法聚类视频运动目标定位算法的有效性。本文在CPU为Celeron 1.67 GHz,内存为512 MB,操作系统为Windows XP SP2的PC机上,采用VC++6.0开发环境(Debug模式),对不同视频序列的运动目标进行了定位实验。实验共用到3组视频测试序列:Highway(公共视频测试序列,下载地址http://cvrr.ucsd.edu/aton/shadow/,大小320×240,共500帧)、Viptraffic(Matlab7.1自带视频测试序列,大小160×120,共120帧)、Hand(自拍视频测试序列,大小320×240,共18帧)。

2.1 算法定位过程

图1已示意了本文尺度方向自适应减法聚类视频运动目标定位算法的定位流程。为更直观地说明本文算法的定位过程,图3给出了本文算法定位某二维数据样本的过程示意图。图3(a)~(d)共4张图依次对应于如下定位过程:二维待定位数据样本→减法聚类预定位→模糊C均值聚类→目标尺度及方向定位。采用减法聚类进行预定位时:ra1=45,ra2=15,η=1.25,ε=0.55。减法聚类预定位得到的目标密度中心坐标及密度值在图3(b)中标记。图3(d)标记了目标定位结果的半长轴、半短轴及方向角度参数。

2.2 定位效果比较实验

图4(a)为Highway第487帧运动检测的结果(未进行形态学滤波处理)。图4(b)、(c)和(d)分别示意了不同定位方法对图4(a)的定位效果。图5示意了本文方法与文献[1]的方法对图4(a)中6个目标定位的像素级偏差比较曲线,其中各个目标的偏差值由目标椭圆或正圆包含的总像素数减去对应目标前景像素点数算得。从图4和图5中可以看出:文献[1]的方法和本文方法比基于区域生长的定位方法具有更强的抗噪性能;与文献[1]的方法相比,本文方法可以进一步获得目标的尺度及方向参数,且本文定位方法的像素级平均偏差也低于文献[1]的定位方法。虽然图4给出的只是目标空域连通特性较差时的定位效果,但即使是空域特性连通性良好的情况,本文方法依然具有定位参数较丰富的优势。本文这里采用文献[9]方法对图4中的

Highway视频序列进行运动检测。基于本文实验环境,未对测试程序进行任何优化情况下,图4(b)算法耗时约328 ms,图4(c)算法耗时约32 ms,图4(d)算法耗时约598 ms。

2.3 不同视频序列定位实验

图6~图10示意了采用本文算法对Highway、Viptraffic和Hand三组视频序列视频运动目标的定位效果。对视频目标的运动检测采用文献[9]的方法,其中人手检测结合RGB空间肤色模型辅助检测。图6和图7的分别为Highway第486帧运动目标前景样本减法聚类预定位及尺度方向定位的效果。表1为对图8最左图所标记的视频运动目标进行定位后,最终所获得的各个目标的尺度及方向参数。从图6~图10的定位效果可以看出:本文的目标定位算法不但能更准确地定位视频运动目标,而且可以进一步提取出目标的尺度及方向参数,该参数特别有利于一些目标跟踪场合的应用,如Mean Shift算法做目标跟踪时初始目标模型的自动获取。

3 结论

基于减法聚类算法的视频运动目标定位方法很适用于待定位视频运动目标空域连通特性较差时的应用场合。本文针对原减法聚类定位法无法获取目标尺度和方向参数的问题,提出了一种解决该问题的定位算法,并通过大量实验辅助阐述本文方法的定位效果。本文方法与原减法聚类定位方法相比,虽然本文方法可获得更准确的目标定位结果,以及获得目标的尺度及方向参数,但由于模糊C均值聚类及协方差矩阵分析的引入,使算法耗时增加。因此,研究任何有利于提高定位算法处理效率的方法显得非常有意义。同时,减法聚类定位算法初始邻域半径的自学习也是研究重点之一。

参考文献

[1]孙志海,孔万增,朱善安.基于减法聚类算法的视频运动目标定位[J].光电工程,2008,35(7):12-16.SUN Zhi-hai,KONG Wan-zeng,ZHU Shan-an.Moving object location in video sequences based on subtractive clustering algorithm[J].Opto-Electronic Engineering,2008,35(7):12-16.

[2]KONG Wan-zeng,ZHU Shan-an.Multi-face detection based on downsampling and modified subtractive clustering for color images[J].Journal of Zhejiang University Science A(S1673-1581),2007,8(1):72-78.

[3]Chiu S L.Fuzzy model identification based on cluster estimation[J].Intelligent Fuzzy Systems(S1064-1246),1994,2:267-278.

[4]Sathit N,Peraphon S,William R.Fuzzy subtractive clustering based indexing approach for software components classification[J].Journal of Computer and Information Science(S0091-7036),2004,5(1):63-72.

[5]Eftekhari M,Katebi S D.Extracting compact fuzzy rules for nonlinear system modeling using subtractive clustering,GA and unscented filter[J].Applied Mathematical Modelling(S0307-904X),2008,32(12):2634-2651.

[6]Kim D,LEE K,LEE D,et al.A kernel-based subtractive clustering method[J].Pattern Recognition Letters(S0167-8655),2005,26(7):879-891.

[7]张智星.神经-模糊和软计算[M].西安:西安交通大学出版社,2000:305-309.ZHANG Zhi-xing.Neuro-fuzzy and soft computing[M].Xi’an:Xi’an Jiaotong University Press,2000:305-309.

[8]樊家琨.应用多元分析[M].开封:河南大学出版社,1993:23-30.FAN Jia-kun.Applied multivariate analysis[M].Kaifeng:He’nan University Press,1993:23-30.

目标聚类篇6

在果蔬种植业中,采摘作业所用的劳动力占整个生产过程所用劳动力的33% ~ 50% 。因此,研究和开发果蔬采摘智能机器人对于节省人工成本、降低果蔬损伤率、提高果农经济效益,以及促进现代农业装备朝着机械化、智能化方向发展均有重要意义[1,2,3]。

准确识别出成熟的果实是果实采摘机器人的首要任务,也是成功实现自动化采摘作业的关键技术。目前,国内外研究人员展开了大量研究工作。国外对于这方面的研究较早,Bulanon[4]等采用结合机器视觉系统和激光距离传感器的方式定位水果,采用机器视觉系统识别苹果,用激光距离传感器来测量距离。田间试验结果显示: 末端执行器能够在7. 1s的时间内采摘单果,采摘成功率达到90% 。Rakun[5]等通过整合目标颜色、纹理及三维形状信息来识别水果,利用多视几何方法来进行空间定位,较好地处理了光照不均匀、部分遮挡及相似背景等问题。我国在农业机器人领域的研究虽然起步晚,但发展速度快,近年来也取得了一定的成果。李昕[6]等利用了一种改进的类圆随机Hough变化算法,并在算法中添加了边缘预检测、快速定位圆心点等模块,成功将油茶果实从树枝、树叶等外界遮挡中分离出来。熊俊涛等[7]基于双边滤波的Retinex图像增强算法凸显图像中的荔枝果实与果梗,再利用Otsu自动阈值分割去除荔枝果实和果梗外的复杂背景,最后通过将双三次插值算法和传统的FCM算法融合,实现了不同光照下荔枝果实和果梗的识别。陈科尹等[8]针对模糊聚类分割方法在水果图像分割中的过分割现象和计算量大等问题,提出了一种基于多尺度视觉显著性改进的水果图像模糊聚类的分割算法,提高了果实分割率。吕小莲等[9]利用采摘西红柿图像中目标与背景的颜色差异建立了一种采摘西红柿识别方法,对非遮挡的采摘西红柿具有较高的识别效果。宋怀波[10]等基于凸壳理论对重叠苹果目标进行分割,并重建算法实现对遮挡苹果目标进行识别与定位。模糊聚类算法已有了很多的应用,但由于果实颜色饱和度的差异,部分果实目标会被聚类为其它目标。

本文以西红柿为研究对象,利用FCM算法对西红柿目标进行分割,对于在聚类过程中丢失的果实部分,采用超红图像进行处理分割出丢失的果实,与聚类得到的果实图像进行相加,以期得到较为完整的分割结果。

1 西红柿目标识别

1. 1 FCM 算法原理

FCM算法由Dunn[11]提出,Bezdek等[12]对其进行了完善。其用于图像分割的基本思想是使用隶属度来确定每个数据点属于某个聚类的程度,对目标函数进行迭代最小化,以确定其最佳类别[13]。其中,目标函数的定义为

同时满足式( 2) ,即

其中,X = { x1,x2,…,xn} 为聚类样本集合; n为聚类样本数量; V = { v1,v2,…,vc} 为c个聚类中心; c是聚类的类别数; uik表示第k个样本对i类的隶属度值,U围为1. 1 ~ 5。通过试验,选定对西红柿目标分割效果较好的m值为4。= [uik]是c×n维的矩阵; ‖xk- vi‖表示xk与vi之间的归一化距离。

FCM算法的实现步骤如下:

1) 设定聚类数目c和加权指数m,迭代截止误差ε> 0,随机数生成法产生满足约束条件的隶属度初始矩阵U( 1) 。

2) 代入公式( 3) ,计算聚类中心V,则

其中,i = 1,2,…,c; k = 1,2,…,n。

3) 代入公式( 4) ,更新隶属度值uik,则

其中,i = 1,2,…,c; k = 1,2,…,n。

4) 重复2 ) 和3 ) 步骤,直到满足公式( 5 ) 停止计算,则

1. 2基于FCM算法西红柿目标的识别

1. 2. 1 FCM 参数选择

西红柿目标分割目的是将西红柿果实与背景分离开来。利用FCM算法对其分割,首先要选择合适的参数,以便得到较好的分割结果。FCM的主要参数有3个[13]:

1) 样本数据的特征向量。通过对西红柿图像分析,果实目标与背景存在显著地颜色差异,因此将R、G、B这3个分量的灰度值作为样本数据的特征。

2) 最优聚类数c。最优聚类数c = 3,即将西红柿图像分割成果实、果梗和叶片3部分。

3) 模糊加权指数m。模糊加权指数m控制着模糊聚类中模糊程度的量级,对于参数m没有理论和经验性的公式[14]。Cannon等[15]认为: m有用的取值范

采用上述选定的参数对西红柿目标进行分割得到的分割结果如图1所示。图1( a) 为西红柿原始图像,图1( b) 、1( c) 、1( d) 分别是采用FCM算法分割出的果实图像、果梗图像和叶片图像。结合图1 ( b) 和图1( d) 可以发现: 由于果实颜色饱和度的差异,部分果实目标被聚类为叶片,使得目标分割不够完整。图1( d) 中的一部分果实图像恰巧是图1 ( b) 中丢失的果实部分,对图1( b) 和图1( d) 进行处理有望得到更好的果实目标。

1. 2. 2 FCM 分割效果的改进

图1( d) 中包含图1( b) 中丢失的果实目标。由于图1中果实目标与背景存在显著的颜色差异,西红柿目标的颜色主要为红色,采用超红图像去掉图1( d)中西红柿目标的背景,即通过公式( 6) 对图1( d) 进行处理,可以使丢失的西红柿目标更显著的同时去掉背景区域,则

其中,I为超红图像,R、G、B分别为图1( d) 图像的3个颜色分量。获取处理后图像的直方图,判断阈值,对其进行二值化处理。再与图1 ( b) 的二值化图像进行加法运算,得到较为完整的西红柿目标结果,如图2所示。其中,图2( a) 为图1( d) 采用超红图像处理后的结果。由图2可以看出: 西红柿目标更加显著且与背景区域对比明显,得到其直方图。利用Otsu算法对其二值化如图2( b) 所示,图2( c) 为图1( b) 的二值化图像,图2( d) 为图2( b) 与图2( c) 相加的结果。对比图2( c) 可以看出: 西红柿目标更为完整。

由图2( d) 可以看出: 采用所提出的方法得到的分割图像包含孔洞、毛刺等干扰,还需要进行去除噪声、孔洞填充及去除毛刺等处理工作,得到的分割结果如图3所示。

由图3可知: 经过处理后大部分毛刺干扰被去除,边缘变得更为平滑,得到较好的分割结果。

2 试验结果与分析

2. 1 试验条件与方法

为了验证FCM算法进行西红柿目标提取的有效性与准确性,选取20幅图像进行了试验。试验过程均在2. 6GHz处理器、4G内存的PC上完成,试验程序均在Mat Lab 2012a环境下编写、运行。

试验步骤如下:

1) 利用FCM算法进行西红柿目标的模糊聚类;

2) 利用所提出的方法对西红柿目标进行分割;

3) 对所得二值化聚类后的图像目标区域进行去噪、形态学处理等操作;

4) 分别采用K - means算法和Otsu算法对测试图像进行分割;

5) 对比3) 与4) 的分割结果,计算分割误差。

2. 2 试验结果

对测试图像采用上述步骤进行分割的结果如图4所示。其中,图4( a1) ~ ( a6) 为原始图像,图4( b1)~ ( b6) 为采用FCM算法得到的西红柿目标图像。由图4可以看出: 分割部分大多不完整。图4 ( c1) ~( c6) 为对FCM算法的改进结果。可以看出: 分割结果包含丢失的部分,得到较为完整的分割图像。图4( d1) ~ ( d6) 为采用K - means算法得到的分割结果。对比图4( c1) ~ ( c6) 可以看出: K - means算法对于有些原始图像的分割,仍存在不完整性。图4( e1) ~( e6) 为采用Otsu算法得到的分割结果。对比图4( c1) ~ ( c6) 发现: Otsu算法几乎得到正确的西红柿目标图像。因此采用文中算法对西红柿目标进行分割是可行的。

2. 3 试验结果分析

为了更为客观地判断所提方法的有效性和准确性,利用20幅测试图像进行试验,并将分割效果分别于K - means算法和Otsu算法的分割效果进行对比,引入分割效果的评判标准,即西红柿面积的分割错误率σ。其计算方法为

其中,S为原始图像中西红柿目标的真实面积,即西红柿区域包含的像素点数; Si( i = 1,2,3) 分别对应K - means算法、Otsu算法和本文方法分割出的西红柿面积包含的像素点数; σ为采用式( 7) 计算出的面积分割错误率。

所得的数据如表1所示。分析表1可知: K means算法的分割误差率最高为54. 35% ,平均分割错误率为20. 11% ; Otsu算法的分割误差率最高为62. 16% ,平均分割错误率为29. 35% ; 文中算法的分割误差率最高为46. 36%,平均分割错误率为16. 55%。文中所提算法的最高分割错误率在3者之中最低,比K - means算法的最高分割错误率低7. 99% ,比Otsu算法的最高分割错误率低了15. 80% 。文中算法平均分割错误率在3者之中也是最低的,比K - means算法的平均分割错误率低了3. 56% ,比Otsu算法的平均分割错误率低了12. 8% 。通过上述数据及结果分析可以发现: 利用本文所提出的算法可以有效地完成西红柿目标分割。

3 结论

目标聚类篇7

在渗透测试开始之前需要对目标进行侦察,目的是获取目标网络的IP地址、运行的操作系统以及应用程序列表[1]。目前渗透测试的侦察工作主要通过一些单一的工具进行,如nmap,nessus等[2,3]。然而,渗透测试是一个迂回迭代的过程,特别是在目标难以攻克的时候往往需要采用一些迂回的方式进行,这其中产生数据量是巨大的。对大量的数据进行分析并建立联系为渗透测试人员带来的不小的挑战。为了进一步提高测试人员获取信息的质量,提出了对检索到的数据集进行再挖掘、再组织的问题。其中的一项核心工作就是聚类,希望借助聚类技术对初步检索到的结果按照主题相似性划分成簇,这样目标的相关信息就可以以层次的形式展示给测试人员。

基于此,本文针对渗透测试中目标信息的获取方法进行研究,定了网络渗透测试数据集内容集合;在分析现有检索结果聚类算法存在的问题的基础上,提出了基于数据集相关性聚类的渗透测试目标信息获取模型,并以此模型为基础设计了原型系统。该模型以关键字抽取方式获取的检索结果集为基础,通过分析分词短语与查询关键字的关联程度选出与查询关键字最贴近的短语,以此为索引将相关报文建立备选簇,最后基于对备选簇和描述短语的评价对簇进行筛选和归并,得到聚类结果。实验结果表明,该模型优于相关工作,该种聚类算法在渗透测试中得到了很好的体现。

1 相关工作

目标信息的获取主要通过侦察的手段获取,侦察分为被动侦察与主动侦察。被动侦察从开放的数据源中收集信息,包括:公司网站、EDGAR数据库、用户组会议、商业伙伴。当要对一个目标进行渗透测试时,测试人员手中仅有的信息可能就是目标的网站,而地址范围需要再进一步去发现。这种情况下就必须做DNS和Whois的主动查询。

对数据的聚类首先在文献[4]中提出,已经成为近年来相关研究领域的热点问题之一。目前已有的方法可以分成两大类[5],第一类是基于文档(Document-based)的聚类方法,先对检索结果集进行聚类,再提取簇描述短语;第二类基于标签的聚类方法,先提取簇的描述短语作为标签,在根据标签聚类。基于文档的典型工作包括了[4,5,6,7,8,9],基于标签聚类的相关工作包括[9,10,11,12,13,14]。在现有的相关工作中只有文献[6,12,14]考虑了与查询词的关联信息,然而,文献[6]通过考察词与查询关键字的关联来提取文档特征,然后基于向量空间模型进行聚类,文中并未涉及描述短语的提取;文献[12]虽然考虑了与查询词的关联,但采用了基于概念格的层次聚类,不清楚与查询关键字的关联强弱对描述短语提取的作用;文献[14]虽然也考虑了关联,但需要Ontology、句法分析等的支撑。

2 渗透测试目标信息的获取模型

2.1 渗透测试数据集定义

本文首先做出如下概念的定义:

网络渗透测试数据集:能够从中分析得到网络渗透测试目标信息的数据类型的集合,称为网络渗透测试数据集。

2.1.1 获取目标网络上主机的IP地址

通过逆向分析IP的Whois信息、域名的Whois信息、反向DNS信息以及自治系统结构(Autonomous System,AS)可以获取目标的IP地址范围。限于篇幅这里就不一一列举对应的信息进行分析,本文仅指出内容。

2.1.2 目标系统运行的应用程序以及操作系统

通过域名历史信息以及IP的外网访问信息可以逆向获取目标的操作系统以及应用程序列表。

综上,数据集内容的定义,如表1所示。

2.2 数据集的相关性聚类算法

在网络渗透测试中涉及到的信息主要包括:IP、DNS、ASN、域名拥有者、邮箱、地址。因此现阶段本文采用关键字差异化抽取的方式对数据集进行处理。对数据进行关键抽取之后即可据此得到检索结果集,对于结果集的相关性聚类算法描述如下:

1)对检索结果集中的每个报文进行分词,抽取单词n-gram(n≤4),作为分词短语;

2)对分词短语与查询关键字进行相关性分析,选出与查询关键字最贴近的短语,以此为索引将相关报文建立备选簇;

3) 将短语与备选簇进行评价、筛选、归并;

4) 得到聚类结果及簇的主题描述词。

2.2.1 报文分词

本文采用基于词典的逆向最大匹配算法进行分词,将文本转化成单词序列,并删除其中的停用词等描述信息能力有限的单词,分词所使用的词典规模为30万。从单词序列中提取所以可能的单词n-gram(n≤4)作为描述簇的候选短语。

2.2.2 相关性分析

本文在提取簇内容描述的关键字时针对每一个n-gram评价其与查询关键字的相关性大小,以此来确定一个n-gram成为簇关键字的可能性。为此,本文采用基于距离的同现统计方法来进行,在同等条件下,n-gram与查询关键的距离越近,相关度越大。设Q = K1K2…KM为测试人员输入的查询,其中Ki为查询词项,m≥1;i = 1,…,m。该查询返回的结果集为R = {R1,R2,…,Rn},其中Rj为数据集报文,j= 1,n,Rj经过分词后被表示成单词序列,设该序列为mj1,mj2,…,mjLj,其中Lj为Rj的长度,对任意的单词N元组(n-gram);G=m1,m2,…,mn其与查询Q在R中的关联度Rele(G,Q,R)定义为:

$R e l e (G, Q, R) = {\begin{matrix} 1 ‚ & (Q \leq G) \\ \frac{1}{t} \sum_{j = 1}^{n} R e l e ‚ & (R_{j}, G, Q) \end{matrix} (1)$

式(1)中t为R中出现G的报文数量,ReleR(Rj,G,Q)为相关性大小的评价,其定义为:

$\begin{array}{l} R e l e_{R} (R_{j}, G, Q) = \\ {\begin{cases} 0 (G \notin R_{j}) \\ \frac{1}{| {G_{i} | G_{i} \in R_{j}} | | {Q_{k} | Q_{k} \in R_{j}} |} \times \\ \sum_{\forall G_{i} \in R_{j}} \sum_{\forall Q_{k} \in R_{j}} r e l e (R_{j}, Q_{i}, Q_{k}) \end{cases} (2) \end{array}$

式(2)中Gi属于Rj代表G在报文片段Rj的第i出现;Qk属于Rj代表Q在Rj中的第K次出现,|{Gi|Gi属于Rj}|w为G在Rj中出现的总次数,|{Qk|Qk属于Rj}|是Q在Rj中出现的总次数,Rele(Rj,Gi,Qk)为对于Rj中出现一对G和Q进行的基于距离的相关性度量,其定义为:

$\begin{array}{l} R e l e (R_{j}, G_{i}, Q_{k}) = \\ {\begin{cases} 1.0 - (D (G_{i}, Q_{k}, R_{j}) - 1.0) / 10; D (G_{i}, Q_{k}, R_{j}) < 10 \\ 0.1 \end{cases} (3) \end{array}$

式(3)中D(Gi,Qk,Rj)表示在Rj中第i次数显G与第K次出现的Q之间的距离,这种距离用间隔的单词数来表示。关联度Rele(G,Q,R)基于单词N元组G与查询Q在结果集中的共现频率及距离在R中对它们之间的相关度评价,共现频率越高,距离越近,则表明它们之间的关联度大。

2.2.3 质量判决

经过上述过程得到备选簇及索引后,需要对索引质量以及簇质量进行综合的评价,然后基于此进行备选簇的分裂、归并等处理,最后输出最优的簇及索引,这种优化方式的目标函数可以用式(4)来描述:

$\begin{array}{l} Q u a l i t y (C_{1} : L_{1}, C_{2} : L_{2}, \dots, C_{X} : L_{X}) = \\ Q_{L} (L_{1}, L_{2}, \dots, L_{X}) Q_{C} (C_{1} : L_{1}, C_{2} : L_{2}, \dots, C_{X} : L_{X}) (4) \end{array}$

式(4)中QL (L1,L2,…,LX)为索引的质量评价,QC为簇的质量评价,用簇间相似度和簇内相似度来衡量。

2.4 原型系统设计

原型系统由分析子系统(Eagle-eye)以及抓取引擎(Crawler-man)两部分组成,Crawler-man的主要功能是抓取基础数据集,基础数据集的本地化是进行分析的前提;Eagle-eye的主要功能是对基础数据集进行处理,同提供交互接口。原型系统的总体结构如图1所示:

3 实验与评价

3.1 实验设置

为了验证本文所提的模型的有效性,选取了如表1所示的2个歧义词、2个实体名、2个意义广泛的词作为查询词项关键字,对他们的检索结果进行聚类。

对上述6个查询结果集请一名资深渗透测试人员对检索结果的前50进行人工聚类,并对其中出现的短语进行打分,目的是描述这些短语是否适合作为簇的索引。具体的打分方法是:浏览前50条检索结果后从中选出10个满意的短语10个中等的短语,其余的默认为不满意的短语。分值如表3所示。

为了与文献[9]中的算法进行对比,本文在实验时用4个查询词项关键字的检索结果集作为文献[9]的训练数据集,剩下的两个查询词项的检索结果集作为本文算法和文献[9]中的测试数据集。需要说明的是,文献[9]采用的聚类方法是回归模型中线性核的支持向量回归模型(SV-L)。

3.2 评价方法

本文采用P@N来评价簇索引的质量,采用覆盖率和重叠率来评价簇的质量,这些指标的定义如下:

3.2.1 P@N

利用在前N个结果中的精确率(P)来评价簇索引的质量。

$Ρ @ Ν = \frac{| C \cap R |}{| R |} (5)$

式(5)中C表示人工标注的正确的短语集合,R表示产生的短语集合。

3.2.2 覆盖率(Coverage)

设结果集中互不相同的文档总数为D(T),前N个簇中的不同文档数为D(TopN),则覆盖率为D(TopN)/D(T)。

3.3 实验结果

从图2中可以看出,关键字“福特”的P@5、P@10、P@20均为1,表示排在前5、前10、前20的索引都是正确的。其中P@5结果的平均值为0.59,P@10结果的平均值为0.58,P@20结果的平均值为0.57。

图3给出了本文算法覆盖率的统计结果。

图4为本文算法( rele)与SV-L在索引平均准确率方面的对比。

从中可以看出两种方式的准确率相当,说明两种算法排在较前的簇索引质量相差不大,但SV-L需要人工标注大量训练数据,而rele无需训练过程,在保证质量的同时节省了人工成本。

图5为rele与SV-L在平均覆盖率方面的比较,从中可以看出rele覆盖率明显高于SV-L。

限于篇幅,下面利用原型系统以google为入口展开查询,如图6所示。

从上可知,在域名列表、DNS列表、ASN列表以及IP列表中原型系统均给出了良好的结果。

5 结论

本文提出了基于数据集相关性聚类的目标信息获取模型。实验结果表明,原型系统较好的满足了渗透测试的实际需求,在模型中使用的算法对提高聚类索引和簇的质量是有效的,覆盖率有明显改善。另外本文还存在改进的地方,目标系统无法识别成新词同时效率还有待进一步提高。

摘要：渗透测试中对目标进行侦察的目的是为了获取目标网络的IP地址、运行的操作系统以及应用程序列表。目前侦察主要通过一些单一的工具进行,这种方式侦察周期较长。结合目标信息内容,提出一种通过对数据集进行相关性聚类的方式来获取目标信息的模型,并设计了原型系统。实验结果表明,该模型优于相关工作,在较短的时间周期内获取了准确的目标信息。

【目标聚类】推荐阅读：

目标定位目标检测06-02

目标困惑：教学目标与学习目标应如何表述08-26

大目标小目标故事06-07

小学有关新年目标作文：新年，新目标08-17

小班第二学期各领域目标目标09-23

市年终目标目标考核汇报会主持词05-27

七上第一单元单元目标和分课目标06-27

价值目标07-04

目标融合07-17

目标调整07-19

>> 查看更多相关文档