聚类识别（精选8篇）
聚类识别 篇1
1 前言
面向对象内容识别过程中以单词为单位的常规检索方式, 缺乏内容时间序列上的关联, 检索效果大打折扣, 尤其是对音视频、图片等非结构数据的内容识别, 效果非常差。而由于K-MEANS聚类算法在处理大数据环境下内容中的数据流方面存在着算法敏感, 以及内容识别效率和速度上的缺陷, 因此, 从网络内容格式类型的序列关系进行K-MEANS聚类算法的改进, 使其能够保持可接受的检索速度和识别能力是本文重点研究方向。
2 非结构化内容识别方法
随着宽带流量的提高, 互联网内容日益丰富, 非结构化内容如:音视频、图形图像的文件越来越多。对于非结构化内容的识别方法主要包括以下几个步骤:
2.1 分割
分割是是实现非结构化内容识别的第一步, 根据内容的转换边界进行分割, 分割方法包括模板匹配法、直方图法、边缘检测法、模型法、颜色柱状图法、运动矢量法以及基于多维空间仿生信息学理论的方法等。镜头边界检测作为视频检索的第一步具有重要意义, 其结果将对整个视频检索结果产生直接的影响。
2.2 特征提取
提取非结构化对象基本信息及动态信息, 得到一个尽可能充分反映内容的特征空间, 这个特征空间将作为内容识别依据, 内容特征分为静态特征和动态特征。静态特征的提取主通常采用图像特征提取方法, 如提取颜色特征、纹理特征、形状和边缘特征等。动态特征是获取动态特征的方法是运动估计, 通过匹配算法估计出每个像素或区域的运动矢量, 作为非结构化数据的运动特征。
2.3 聚类
高效的索引技术是基于内容的检索在大型数据库中发挥优势的保证。索引技术随着数据库的发展而发展, 提高索引效率有缩减特征向量的维度和聚类索引算法两种方法, 针对非结构化内容检索需要3个步骤: (1) 进行维度缩减; (2) 对存在的索引方法进行评价; (3) 根据评价定制自己的索引方式。为了保证内容识别的效率和准确性, 内容识别的聚类算法尤为重要。
3 基于K均值聚类的内容识别均值算法
基于K均值聚类的内容识别算法模型如下:
(1) 选取K个聚类中心作为服务器内容样本的K均值聚类算法迭代的聚类中心v11, v21, ⋯, vk1。
(2) 对于服务器内容样本X (设进行到第K次迭代) , 如果|X-vjk|<|X-vik|, 则X∈Sjk, 其中Sjk是以vjk为集类中心的样本集。
(3) 计算服务器内容样本各聚类中心的新向量值:
式中nj为Sj所包含的样本数。
(4) 如果vjk+1≠vjk, (j=1, 2, ⋯, k) , 则回到第2步, 将全部服务器内容样本重新分类, 重新迭代计算;如果vjk+1=vjk, (j=1, 2, ⋯, k) , 则结束。
K均值伪代码如下:
设定聚类数目K, 最大执行步骤tmax, 一个很小的容忍误差ε>0
决定聚类中心起始位置Cj (0) , 0<j≤K
4 基于K-MEANS聚类算法改进的内容识别
4.1 K-MEANS聚类改进算法的数据处理
现有的网络内容检索方式逐渐从关键词检索转向对象检索, 也就是以内容片段为输入, 从大量数据中找出接近的内容。现行的互联网基于关键词的敏感内容规避业务的选择结果模式主要是采用双向选择模式, 因此基于关键词的敏感内容规避业务挖掘也要遵循这样的模式原则, 选取服务器中基于关键词的敏感内容进行规避, 选择结果意向数据作为主要数据挖掘内容。网站敏感内容选择内容处理的数据类型包括:文本、图像、音频、视频等。处理方法首先要采用绝对偏差法进行数据标准化;其次采用简单匹配系数方式对互联网内容进行检测, 通过为0, 不通过为1;最后采用对数变换将数据转换为[0, 1]区间内数据, 再进行区间标度变量相同的标准化。数学公式表示:
首先, 计算平均的绝对偏差sf
x变量代表度量值, m代表平均值。
其次, 计算m:1
最后, 计算标准化量度值:
4.2 基于K-MEANS聚类算法改进的设计
针对现有的K-MEANS算法在内容识别中的聚类结果往往趋于孤立点的问题以及时间复杂度为O (n2) 不利于对互联网中大数据量的挖掘问题, 本文采用的是基于排列组合思想的K-MEANS剪枝改进算法。算法描述如下:
4.3 内容识别
互联网内容检索方法不仅仅局限于全文检索, 在很大程度上也不同于关键字检索。非结构化内容本身的层次化结构则要求内容检索必须层次化进行。因此, 内容的特征决定了内容检索必须是层次化的, 且用户接口是多表现模式的, 下面提出几种常用的检索方法:
(1) 基于框架的方法:该方法通过知识辅助对内容建立框架, 并进行层次化检索。
(2) 基于浏览的方法:基于浏览的方法始终是内容检索中一个不可缺少的方法。如果用户没有明确的查询主题或用户的主题在框架中没有被定义等, 用户可以通过浏览来确定其大概目的。
(3) 基于描述特征的检索:该检索针对内容的局部特征检索, 描述特征包括说明性特征和手绘特征。
(4) 内容的检索反馈在检索的实现中除利用内容特征进行检索外, 还应根据用户的反馈信息不断学习改变阈值重新检索, 实现人机交互, 直到达到用户的检索要求。
5 结语
论文提出了一种基于排列组合的K-MEANS聚类算法, 该算法在互联网海量数据挖掘过程中, 可以满足内容识别的检索速度和识别能力, 尤其是对非结构化数据, 如:图形、图像、视频等, 具有很好的识别能力, 在面向对象的内容识别趋势下, 该算法具有较好的先进性和实用性。
参考文献
[1]侯泽民, 巨筱.一种改进的基于潜在语义索引的文本聚类算法[J].计算机与现代化, 2014 (7) :24-27.
[2]王友卫, 刘元宁, 凤丽洲, 等.基于用户兴趣度的垃圾邮件在线识别新方法[J].华南理工大学学报 (自然科学版) , 2014 (7) :21-27.
[3]江雪, 孙乐.用户查询意图切分的研究[J].计算机学报, 2013, 36 (3) :664-670.
[4]杨陟卓, 黄河燕.基于词语距离的网络图词义消歧[J].软件学报, 2012, 23 (4) :776-785.
[5]皋军, 孙长银, 王士同.具有模糊聚类功能的双向二维无监督特征提取方法[J].自动化学报, 2012, 38 (4) :549-562.
[6]黄学沛, 张燕, 项炬, 等.基于云架构的自适应聚类图像识别技术的研究与实现[J].电脑与电信, 2016 (5) :30-32.
聚类识别 篇2
关键词：说话人识别；模式匹配；FCM
中图分类号：TP18 文献标识码：A文章编号：1009-3044(2007)16-31104-02
A Ameliorated Method Of Speaker Recognition With Fuzzy C-meansClustering
SUN De-yi, CUI Lian-yan
(Information Science & Engineering College,Liaoning Institute of Technology, Jinzhou 121001，China)
Abstract:Pattern matching plays a very important role in the speaker recognition system, whose method can affect the system recognition rate directly. This article presents a method about fuzzy vector quantization(FVQ) and a method of the speaker recognition with subtractive clustering and fuzzy c-means clustering arithmetic by analyzing the arithmetic to fuzzy c-means. The experiment indicated that this method enhanced the recognition rate and is a effective speaker recognition method.
Key words:the speaker recognition; pattern matching; FCM
1 引言
随着社会的发展,安全问题日趋重要,用生物特征并结合计算机技术进行安全验证是当今的热门课题,说话人识别技术是生物识别技术的一种,与其它生物识别技术相比, 说话人识别具有更为简便、准确、经济及可扩展性良好等众多优势,可广泛应用于安全验证、控制等方面。说话人识别是一项根据语音波形中反映说话人生理和行为特征的语音参数,自动识别说话人身份的技术。它的基本原理是通过分析人的发声和听觉,为每个人构造一个独一无二的数学模型,由计算机对模型和实际输入的语音进行精确匹配,根据匹配结果辨认出说话人是谁。在声纹识别过程中最主要的两部分内容是特征提取和模式匹配。特征提取,就是从声音中选取唯一表现说话人身份的有效且稳定可靠的特征；模式匹配就是对训练和鉴别时的特征模式做相似性匹配。
2 模式匹配
本文所研究的说话人识别系统主要以美尔倒谱系数MFCC和差分美尔倒谱系数ΔMFCC作为说话人的特征参数，采用模糊矢量量化的识别方法。在分析了模糊C均值（FCM）聚类和改进的FCM聚类算法的性能的基础上，引入减法聚类算法，对改进的FCM算法的初始聚类中心进行初始化，从而避免改进的FCM聚类算法仍然对聚类中心的初值十分敏感，收敛结果易陷入局部极小的弊端，保证获得的改进的FCM聚类结果为全局最优解。
2.1 模糊C-均值（FCM）聚类算法
FCM聚类是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。它把n个数据向量xk（k= 1，2，…，n）分为c个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。并且使得每个给定数据点用值在（0，1）间的隶属函数确定其属于各个组的程度。FCM的目标函数定义为：
2.2 改进的FCM算法
2.2.1 放松隶属度
在FCM算法中，因引入了各个聚类的隶属度之和为1的归一化条件，在样本集不理想的情况下可能导致结果不好。如当存在某个野点样本远离各类的聚类中心时，它严格属于各类的隶属度都很小，但由于各个聚类的隶属度之和为1这个条件的要求，将会使它对各类都有较大的隶属度，这种野点的存在将影响迭代的最终结果。对于此缺点，采用一种放松的归一化条件，使所有样本对各类的隶属度总和为N，即：
这样，在有野点存在的情况下得到较好的聚类结果。
2.2.2 加权模糊C-均值聚类
在解决实际问题的过程中,我们经常发现利用经典的模糊C-均值聚类所得到的结果与主成分分析的结果有较大的差异，本文将模糊C-均值聚类进一步加以改进，使得聚类的结果与主成分分析基本一致。我们的方法将模糊C-均值聚类的迭代公式中的欧氏距离改为加权欧氏距离，其中的权向量采取主成分分析的方法计算。
加权模糊C-均值聚类表示如下：
其中，ωj通过以下方法计算得到：
(1)将原始数据矩阵统一趋势化，得到无量纲矩阵Y；
(2)计算矩阵Y的相关系数矩阵R；
(3)计算相关系数矩阵R的特征值λj；
经过改进的加权模糊C-均值聚类的结果与主成分分析基本一致，特别适用于大样本的聚类。
2.3 减法聚类算法
与传统的FCM聚类算法一样，改进的FCM聚类算法仍然对聚类中心的初值十分敏感，收敛结果易陷入局部极小。为了得到较好的结果，在使用改进的FCM聚类之前先用减法聚类算法进行初始化聚类中心，以保证获得的改进的FCM聚类结果为全局最优解。
减法聚类算法是把所有的数据点作为聚类中心的候选点，它是一种快速而独立的近似聚类方法，计算量与数据点的数目成简单的线性关系，而且与所考虑问题的维数无关。
考虑M维空间的n个数据点xi(i=1,2,…,n)，其减法聚类过程分为下面几步：
（1）计算每个数据点xi的密度指标：
这里ra是一个正数，选择具有最高密度指标的数据点xc1为第一个聚类中心，Dc1为其密度指标。
（2）假定xck为第k次选出的聚类中心，相应密度指标为Dck，对于每个数据点的密度指标按式（5.19）修正：
是否成立。若不成立，则转到（2）；若成立则退出。其中δ<1是事先给定的参数，此参数决定了最终产生的初始化聚类中心数目，δ越小，则产生的聚类数越多。
本系统将减法聚类与改进的FCM聚类相结合，以减法聚类的聚类中心作为改进的FCM聚类算法的初始聚类中心，以保证改进的FCM聚类结果为全局最优解。
3 系统仿真及结果
将减法聚类与改进的FCM聚类相结合的算法应用于说话人识别，为评价识别方法的性能，使用Matlab 6.5 软件进行仿真实验。
3.1 系统设定
本系统语音采样频率为8kHz，量化位数为16bit，采集到的语音用PCM编码的wav格式文件保存。取帧长为30ms，帧移10ms，加海明窗。这里使用短时能量和过零率的端点检测方法，提取语音信号的有声段。
本系统特征参数提取采用从语音信号的有声段提取12维MFCC参数及其12维一阶差分MFCC参数并进行组合，作为说话人的特征参数。说话人码本的建立与识别采用减法聚类与改进的FCM聚类算法相结合的方法对每一个说话人的特征参数进行聚类分析，在Matlab模糊逻辑工具箱中，提供了subclust函数来完成减法聚类的功能，该函数的调用格式如下：
[C，S]=subclust（X，radii，XBounds，options）
其中X为输入数据，radii取为0.5，XBounds、options参数取缺省值。
3.2 仿真结果及分析
在实验中，语音数据是10名说话人相隔3个月在实验室的两组录音，每组录音中每个人录10次音，得到每个人的20次录音。对于每个人的录音，从两组中分别取出3次（共6次）录音进行训练，得到这个人语音的6个码本，其余14次录音用于识别测试。测试结果的总平均量化误差见表3.1，其中，第 行数据代表第 个人的语音分别用第1～10个人的码本进行模糊量化产生的总平均量化误差；从每行的最小值可以看出，每个人的语音用自己的码本进行模糊量化时产生的总平均量化误差最小，即可以代表正确的说话人。
表1 总平均量化误差表
图1 总平均量化误差对比
4 结束语
测试的结果表明：本方法的识别率较高，达到百分之九十以上。该方法以减法聚类的聚类中心作为改进的FCM聚类的初始聚类中心，避免了收敛结果陷入局部极小的问题，识别性能有了明显的改善，是一种行之有效的说话人识别方法。
参考文献：
[1]张军英.说话人识别的现代方法与技术[M].贵州:西北大学出版社,1994.
[2]何英，何强.扩展编程[M].北京:清华大学出版社,2002.
[3]杨彦、赵力.一种改进的模糊C-均值聚类算法在说话人识别中的应用[J].电声技术,2006.01.
[4]LiH. Fuzzy clustering method based on perturbation.Fuzzy Sets and Systems[J] ,1989,33:291-302.
基于聚类集成的用户负荷模式识别 篇3
近几年来, 广东省经济飞速发展, 用电负荷持续攀升, 但是电网侧由于受到气候、能源与自身建设周期等诸多因素的影响, 经常处于电源性电力供应不足的状态。在未来相当长一段时间内, 电力短缺的形势不会改变, 单纯寄希望于扩大电源和电网规模并不能缓解长期的电力短缺, 必须从用电侧入手, 采取各种节能技术和措施, 逐步改变客户的用电行为。错峰作为需求侧的管理方法之一, 可以有效地缓解供需紧张的矛盾, 但错峰也会给地区的工业生产和经济发展带来不利的影响, 对用户用电负荷进行分析, 可以主动掌握负荷变化规律, 改进错峰方案, 缓解电源紧张对生产的影响, 将有限的能源资源投入到对社会和市场贡献最大的领域。
用户用电负荷模式特点的主流研究方式是对用户负荷模式进行分群。依据用户日用电负荷曲线的形态变化, 使用聚类分析方法对用户用电负荷数据进行分群[1,2,3]。目前, 已有许多学者和专家为此作了大量的分析和研究工作, 如双向夹逼的多层次聚类法[4,5]、基于支持向量机的聚类分析[6]、模糊C均值[7,8]等。然而, 用户用电负荷数据是不平衡[9]的时间序列[10]数据, 以上各方式最大缺陷是数据集自身的特性会严重影响传统聚类方法的分群效果。并且, 单一的算法较难获得高的聚类准确率, 甚至对于特定的数据集也很难找出最佳的聚类算法方法进行分析[11]。更重要的是, 单一的聚类算法泛化能力差, 只适用于特定的数据集, 对其他数据集的分群效果不理想。为解决以上问题, 设想对经遴选的聚类算法得到的聚类结果进行对比或融合, 以得到最佳者。因此, 集成技术被引入到负荷数据的聚类分析中。
聚类集成[12]是将传统的聚类算法与集成技术结合起来对数据进行“二次聚类”, 其基本思想是通过对一组对象集采用不同的算法或使用不同的初始条件来进行多次聚类, 将所得到的聚类结果用一种融合方法进行合并, 从而得到比单一算法更优的最终聚类结果。聚类集成已经被证明是可以提高无监督数据分析的鲁棒性、适用性、稳定性、并行性和可扩展性的方法, 并从统计学、计算能力、解释能力三个基本方面解释了集成方法能优越于任何的单个成员[13,14]。
本文提出基于用户用电负荷数据的聚类集成方案, 如图1所示, 以用户用电负荷数据作为研究对象, 挑选适合该类数据特征的聚类算法。通过多种标准化方法, 形成多个同源数据集。再分别运行备选聚类算法, 得到多样化的分群结果, 每个结果称为一个聚类成员。将所有聚类成员构造共识矩阵, 对共识矩阵使用CSPA算法, 得到每一个用户属于每一类的概率, 最后根据概率值对用户的负荷模式进行归簇。
1 用电负荷模式聚类分析
1.1 数据预处理
用电负荷模式聚类分析的数据取自计量自动化系统, 计量自动化系统在运行过程中难免遭受软硬件故障、信号异常、线路检修等因素影响, 存在读数出现异常或缺失的情况, 因此需要对数据进行规范性校验, 甄别出数据集中不符合分析要求的数据, 将其剔除或修正, 从而保证数据的正确性、一致性、完整性和最小性[15]。常见的负荷数据异常类型如表1所示, 表中所列各类型的异常数据均为规范性校验要解决的数据质量问题。
规范性校验首先根据数据共线性删除冗余数据。其次, 查找负荷读数数据中的缺失值, 用平滑修正公式的计算结果将其替代;若同一用户的数据缺失量达到该用户数据采集量的20%或以上, 则将该用户剔除分析对象。再次, 通过直接评价法[16]查找不符合用电业务特性的异常数据, 用平滑修正函数的计算结果将其替代。异常数据主要包括读数骤降、暴增或为负等。其中, 平滑修正公式的表达式为:
其中, k为向前采集的点数, l为向后采集的点数。
数据规范性校验完成后, 还需进行标准化处理。以去除数据的基荷, 让数据的值域都落入同一指定区间中, 从而消除各个用户由于生产规模等因素的影响造成负荷量级的差异, 凸显用户间用电负荷模式间的差异。标准化公式集合如下:
其中, T为天数, Pij为第i个用户在j时刻的用电负荷。通过不同的标准化手段, 更能从数据上显现用户的负荷模式特点。并将所有用户的负荷曲线都投影到指定区间中, 达到仅保留用户用电负荷曲线的用电习惯和特点的效果。
1.2 遴选聚类算法
用户用电负荷数据是不平衡的时间序列数据。不平衡数据是指数据集中不同用电类型的数据量差异显著, 这将影响聚类算法分群效果;同时, 时间序列数据在平方以上的高次方运算中会出现显著的截断误差, 这将导致时间序列数据经过聚类算法得到的结果不稳定。数据量越大, 聚类结果愈来愈趋向不理想。
为了将数据不平衡性和时序特性的影响降到最小, 需要从通用的聚类分析算法集合中找到对负荷数据不平衡性和时序特性敏感度较低的算法, 并且寻找到的算法适用于用电负荷分析。因此, 在数据集中分别抽取不同数量级的样本, 样本数量分别为50、200、800、3 200。选取50种不同类型的聚类分析算法作为备选集, 考察各个聚类算法在不同数量级下的用户用电负荷数据集的聚类效果, 聚类算法优劣可以从聚类运行结果的主成分展示图中各簇的分离程度和聚类算法的运行时间两个方面进行评判。
以clara聚类分析算法为例, 利用主成分方法对用户负荷模式聚类分析效果进行可视化。在不同的样本容量下, 考察clara算法的稳健性。随着样本数目的增加, 各簇的重复面积越来越大, 这说明数据的不平衡性以及时序特性严重影响clara聚类算法的稳定性。如图2所示。
经过抽样实验, 选定共轭凸函数K均值算法、模糊C均值算法和多球面K均值算法作为聚类集成算法集合的备选算法。当重新抽样或进一步增大抽样量时, 上述算法的分簇效果仍然较其他算法优秀。如表2所示。但是聚类效果仍有较大的改善空间, 仅通过选优和调整算法参数, 用电负荷模式分群的效果提升是有瓶颈的, 而且, 在聚类分析过程中, 需要大量的人工参与其中。
1.3 聚类集成
为进一步克服用户用电负荷数据不平衡性以及时序特性对聚类分析算法的影响, 得到分簇结果更佳、更稳健的聚类模型, 使用聚类集成方法, 可得到优越于单个聚类分析算法的集成结果, 以及更加稳定的聚类分析模型。
根据聚类集成算法要求, 当聚类成员间的差异度应维持在50%左右时, 得到的聚类集成模型是稳健的。采用不同的标准化手段, 用同一种聚类算法设置不同参数可得到相似度不完全一致的多样化聚类成员。根据先验知识分别为聚类算法集合分别设定多组运行参数, 运行聚类算法集, 得到聚类成员。结构示例如图3所示。在得到的聚类成员后, 对聚类成员进行合并, 得到矩阵H。矩阵H组织形式如下图所示。其中, x1, x2, …, xn表示n个用户;H1, H2, …, Hn表示n个聚类成员;h1, h2, …, hn表示一个簇, 数值“1”代表该用户的用电负荷模式特点数据该簇, 数值“0”表示该用户不属于该簇。
通过矩阵H可构建共识矩阵S。共识矩阵S表达式如下:
其中, 共识矩阵S中元素sij是用户i与用户j属于同簇的概率。
对共识矩阵S使用CSPA超图分割算法进行重构。首先随机选取t个用户作为典型用户, 计算用户i与t个典型用户属于同一簇的概率prij, 依据公式:
其中, sij是共识矩阵S中用户i与用户j属于同簇的概率, σ1为惩罚因子。i个用户与t个典型用户构成概率关系矩阵Pr, prij为Pr中元素, 表示第i个用户与第j个典型用户属于同簇的概率。再计算两两用户间的相异距离Dij, 依据公式:
其中, d () 为距离公式, σ2为惩罚因子。根据Dij计算距离准则函数LH, 依据公式:
其中, wb为权重。此时, 已形成一次的聚类集成结果。由于t个典型用户是随机选取的, 所以需寻找最优的集成结果。因此, 再随机选取t个用户作为典型用户, 重新计算典型用户与其他用户属于同簇的概率矩阵Pr, 相异距离Dij以及距离准则函数LH, 直至遍历所有典型用户组合, 得到距离准则函数值集{LH1, LH2, …, LHn}。获取距离准则函数的最小值min{LH1, LH2, …, LHn}, 输出对应的Pr, 形成最优的聚类集成结果。
2 聚类集成效果对比分析
将基于聚类集成的用户负荷模式识别应用于广东省中山市6 500家专变用户的负荷模式识别中, 随机抽取200条用户负荷曲线, 如图4所示。并将该部分负荷曲线根据业务专家意见进行分群, 得到具有业务意义的标识u0。
匹配正确度定义为对比u0与聚类结果的标识ui进行匹配, 匹配准确度计算公式如下:
其中为用户数, i为在第i个聚类算法得到的分群结果。
本方案将用户负荷曲线数通过标准化公式及遴选的聚类算法得到的聚类成员进行集成并得到最终分群结果。现对比聚类集成与产生聚类成员所用的FCM、CCFK-means、SK-means算法分别在聚类数目3、4、5、6的匹配正确度, 对比结果如图5所示。
从图5可以看出, 聚类集成的平均匹配正确度较三种算法的平均匹配正确度提高7.6%, 充分印证了聚类集成的性能和稳定性优于单一的聚类算法。一般而言, 聚类的分簇数越少, 匹配正确度越高。当分簇数为3时, 三种单一的聚类算法性能较好, 集成算法也随之有较好的分簇效果。当簇数目为4时, 匹配正确度较分簇数为3时有提升, 很可能是该数据集划分为4个簇更为恰当, 此时集成算法的匹配正确度比三种单一的聚类更高。随着分簇数增多, 各个聚类算法的匹配正确度均有下降, 但是聚类集成的匹配正确度仍较其他单一聚类算法优异。
分簇数目为4时, 集成聚类以及各类单一聚类算法都有最佳表现, 可以认为该数据集划分为四类时是合适的。现比较在分簇数为4时, 各个分簇的匹配正确度。对比结果如图6所示, 单一聚类算法均存在部分分簇匹配正确度较低的情况, 即单一的聚类算法仅善于识别某种类型的数据而对其他类型数据辨识能力较差。相较之下, 聚类集成的分簇匹配正确度更为均衡, 体现出聚类集成的分簇稳定性的优势。
3 典型用电负荷模式识别
根据聚类集成模型所得分析结果, 中山市用户用电负荷模式可划分为四个典型模式, 分别为三峰型、双峰型、平稳型、避峰型。如图7所示。
三峰型用户用电负荷模式的特征是三个用电高峰, 分别出现在早上10点、下午4点以及晚上8点, 而在正午、晚上6点以及深夜是用电低谷, 三峰型的用户用电曲线呈现波浪形状, 几乎不存在平稳用电的时间。这类型用户大多是大工厂、劳动密集型企业, 如制造业、代加工业, 其表现为用电负荷大, 且用电负荷模式规律, 用电因工作人员的作息而定, 较少受到其他因素影响。三峰型负荷用户约占总体用户的40%。
双峰型的负荷曲线形状与三峰型十分相似, 其用户用电负荷模式的特征是两个用电高峰, 分别出现在早上10点、下午4点, 用电低谷是正午、晚上6点以及深夜。从晚间7点到清晨, 大部分用户几乎没有用电, 仅有小部分用户有用电迹象, 随之产生用电小高峰, 但是夜间用电峰值不足白天用电高峰的50%。这类型用户大多是政府、企业办事机构、网点等。双峰型负荷用户约占总体用户的30%。
避峰型用户的用电负荷模式展现出用电晚上高白天低的特点, 深夜其用电高峰, 并显现出7、8小时以上的较长时间的高峰用电;在早晨用电负荷开始下滑, 并在白天几乎不用电。避峰型用户在本身的用电负荷模式中已经采用错峰的形式, 即在白天用电高峰时用电负荷少, 晚上用电较高。形成该用电负荷模式可能是由于行业本身特点决定的, 如制冰厂、面包厂等;也有可能是由于电网实施峰谷电价有效引导用户错峰用电形成的。该类型用户占总体不足10%, 并且, 大部分用户的用电高峰负荷相对不高, 避峰型用户平均用电负荷仅为三峰型用户负荷的70%。
平稳型用户的用电负荷模式特点是用电负荷持续且平稳, 几乎没有明显的用电高峰与用电低谷。而且, 这类用户的另一特点是用户间的用电负荷差异较大。这是由于对用户用电负荷数据进行标准化造成的, 因为使用标准化收到去除了用户用电负荷上的差距, 导致平稳用电的用电大户与几乎不用电的小户被划归同一类别。这类型用户的特点是生产持续, 可能断电所带来的损失比要求员工上夜班所导致的用工成本更高。因此, 在实行错峰用电时, 该部分用户的用电应受到相应保证的, 尽量减少因断电造成的经济损失。
4 结语
本文在用户负荷模式识别中引入聚类集成技术, 构建了基于用户用电行为特点的聚类集成模型。从通用算法集中, 选择适合负荷数据集的聚类分析算法, 并结合标准化手段, 生成多样化的聚类成员, 将所有聚类成员合并成共识矩阵, 再运用CSPA超图分割算法对共识矩阵重构, 得到了集成所有聚类成员特性的分群结果。该模型具有很强的泛化能力, 并可获得优越于单一聚类分析算法的分群结果。
将该聚类集成模型应用于中山市6 500家专变用户, 得到了三峰型、双峰型、平稳型以及避峰型四类用户典型负荷模式。通过分析四类负荷模式的用户特性, 主动掌握负荷变化规律, 做到早认识、早布局, 针对错峰重点关注对象, 综合考虑经济、环境、安全等影响因素, 优化错峰方法, 缓解电源紧张对生产的影响, 从而将有限的能源资源投入到对社会和市场贡献最大的领域。
摘要：为提高错峰管理中用户负荷模式识别的可靠性与普适性, 针对目前单一聚类算法难以解决用电负荷数据的不平衡性以及时序特性等问题, 提出一种基于聚类集成技术的用户负荷模型识别方案。利用多种标准化方法以及经遴选的聚类算法生成多样化的聚类成员, 通过将所有聚类成员合并构造共识矩阵并进行重构, 得到较单一聚类算法更为优越的分群结果。该方案比采用单一的聚类分析得到的用户用电负荷数据分簇结果更稳健可靠, 且对数据结构变化的敏感度低、分簇效果更好、泛化能力更强, 并在中山市6 500家专变用户的用电负荷模式识别中取得了良好的应用效果。
聚类识别 篇4
在计算机辅助测量中, 为了实现从不同空间坐标拍摄的场景图片来实现物体三维信息重构, 需要对场景中的标志点进行识别和定位, 解决摄像机初始定向问题的常用方法是在被测物体上粘贴编码标志点, 利用图像中的编码标志和结合对极几何约束解算出相邻图像间的基本矩阵。基本矩阵是摄像机内外参数的综合表象, 利用基本矩阵可得到相机的在世界坐标中初始位置姿态, 作为摄像机的初始定向。聚类分析是数理统计中的一种分析方法,它是用数学方法定量地确定样本的相似关系[1]。把不同的形状标志点作为聚类中不同的样本, 通过模糊划分矩阵把不同的样本区分开来, 达到同编码标志点的一样的区分功能[2]。本文提出一种可以应用于物体表面三维数据提取的标志点提取方法并叙述其原理。
2 识别原理
在三维测量中通常使用的标志点是数位环形编码标志, 编码标志中心的圆是定位圆, 用于提取编码标志的位置信息, 周围的环形为编码段, 用来提取编码标志的编码值信息。每个编码标志均对应唯一一个编码值, 在测量中可以通过编码值实现同值编码标志的匹配[3]。现在对环形编码标志点进行改动, 形状区域分别变成圆形、方形和十字形, 如图1 所示, 以圆形、方形和十字形代替编码值, 但这种以形状代替编码值方式缺点是可作为编码值的形状较少, 但对于编码标志点数量需求少的场合是可以满足要求。
在此对选用的圆形、方形或十字形三种标志点区域划分成7×7 等份, 每个小区域再划分为16×16 等分,每个标识点占据的像素区域为7×7×16×16 图像点,标志点图形分成49 个区域后, 每个区域中标识点图形占据的像素为n ≤ 16×16,n/7×7×16×16 作为区域的特征值xi, 计算7×7 等分中每一个等分黑像素所占比例作为为特征值, 可得到每个标志点有49 个特征值[4]。实际应用中图像内标志点的大小是受多种因素影响, 只要占据的区域不过于太小对识别结果影响不大。理想的标志点图形可以构成具有三个理想样本的一个聚类, 对应的模糊划分矩阵是3×3 的矩阵。对三种待识别标志点分类的标准是三个标志点图像与聚类中心的距离平方和最小或。因为一个样本是按不同的隶属度属于聚类中的标准样品的, 所以应同时考虑每个标志点与的聚类中心的距离。如果与聚类中心较远可以认为是伪特征点应以排除。将三种样本逐个输入去计算与聚类中心的距离,与聚类中心较近应属于同一类, 再加以判别。
对于应用于标识点识别的模糊聚类分析主要包括3个模块: 标识及特征提取模块, 模糊矩阵计算模块, 模糊聚类模块。标识及特征提取模块负责完成对图像的标识点特征的提取。通过相应的准则进行连通性的判断,并把标识出标志点添加标号。利用像素占据每块区域的比例的方法得到每个标识点的特征值, 以用来计算模糊距离[5]。模糊距离计算模块根据特征值计算三个样品间的初始模糊距离, 构建模糊矩阵。模糊聚类模块根据采集的图像质量输入聚类阈值对样本进行分类输出结果,总体系统结构流程图如图2 所示。
3 图像预处理
COMS图像传感器在时序控制下读取每个像素点的灰度值, 在图像采集过程中调整相机距离物体的距离使标志点所占据的像素区域尽可能占据7×7×16×16 个像素区域大小附近, 由于定向反光标志点可使传感器局部过饱和, 所以可以通过控制镜头的光阑大小和CMOS的增益来减小图像传感器对背景光的响应, 但在单色光照射下获得的背景光和定向标志点数据并不是理想的二值化数据, 从灰度直方图上可以知道数据分布趋向两个值, 背景光对应低灰度值, 定向标志点对应高的灰度值,对图像进行二值化时对于8bits灰度阈值可以取大于220, 这样很好的突出标志点的像, 把灰度大于220 的像素直接替换成255, 否则替换成0。对预处理后的图像中的对各个标志点进行标号, 首先检测缓冲区, 从左到右,从上到下, 依次检测每个像素, 如果某像素点像素灰度值为255, 则依次检测该点像素(x,y) 相连通的邻域点集合{(x±1,y±1)} 共8 个点的像素值[6], 根据连通性判断标志点区域, 一幅图像内可能存在多个连通成分, 每个连通成分都对应一个待识别的目标图像区, 给各目标图像区分配相应标号的工作做为标记, 图像标识及特征提取的算法流程图如图3 所示。
4 标志点的识别
经过上述图像预处理后, 可以认为得到N个标志点, 首先计算N个标志点之间的模糊距离, 然后构造等价类, 设其中两个标志点的特征值分别为Xi,Xj,Xi=(xi1,xi2,…,xi49)T,Xi=(xj1,xj2,…,xj49)T, 在此采用欧式距离算法,
得到模糊系数矩阵Dij, 记录下模糊系数矩阵中的不同系数并对其大小进行排序, 其中标志点图像必然存在质量差的, 通过设定阈值使得在分类中去除图像质量差的标志点作为模糊聚类的阈值, 去掉系数矩阵中较小系数的所对应的标志点。设 ω 为代表三种标准的标志点聚类, 设通过采集的标志点和类内标准标志点分别为,Xi=(xi1,xi2,…,xi49)T,,计算归为一类的标志点与类内标准标志点的距离, 与三个标准标志点距离最小的标志点可以认为是一种形状的标志点, 达到了判别标志点的形状和归类, 整个模糊聚类算法如图4 所示。
5 结束语
本文主要讨论了基于模糊聚类对标志点的识别方法, 在合理选择标志点形状和数量情况下, 通过计算标志点特征值及标志点之间相互距离, 通过设定阈值去除伪标志点, 通过模糊聚类识别方法分出标志点种类, 此方法可以满足三维测量中对标志点识别的需要。
摘要：提出模糊聚类应用于三维测量中标识点的识别方法 ,通过计算标志点间的欧式距离和模糊矩阵系数可以去除具有成像缺陷的标志点图形,根据标志点与标识样品间的欧式距离可以判断出标志点的形状,此方法应用于三维测量可以提高标志点识别能力和质量。
关键词：模糊聚类,标志点,识别方法
参考文献
[1]李士勇.工程模糊数学及应用[M].哈尔滨:哈尔滨工业大学出版社,2004.
[2]杨淑莹.图像模式识别[M].北京:清华大学出版社,2005.
[3]邾继贵,于之靖.视觉测量原理与方法[M].机械工业出版社,2012.
[4]邾继贵,叶声华.工业现场近景数字摄影视觉精密测量[J].地理空间信息,2004,(6):11-14.
[5]冯伟兴,梁洪,王臣业.Visual C++数字图像模式识别技术详解[M].北京:机械工业出版社,2012.
聚类识别 篇5
关键词：车牌识别,车牌定位,K-均值,聚类,字符识别
机动车号牌识别系统主要功能是通过图像采集和图像识别的手段识别机动车的身份。对车牌识别领域的研究最初起源于二十世纪九十年代的发达国家, 而国内的研究起源于二十世纪末。号牌识别的最主要的步骤是:车牌定位、字符分割和字符识别。而后两者现在基本已经达成共识, 字符分割采用对二值化图片进行垂直投影和水平投影, 字符识别使用模板匹配方法或者SVM方式。最重要而且方案最多样化的步骤还是在车牌定位上。
车牌定位基本可以分为三种大的研究方向:对灰度图像进行边缘检测、对灰度图像进行角点检测和对彩色图像进行颜色模型处理。边缘特征是人类视觉感知的重要来源, 文献将边缘检测理论、形态学填充、腐蚀开运算后得到车牌待选区域, 最后分析获取车牌位置, 边缘检测作为研究范围最广和目前大多数产品使用的技术, 的确具有速度快、准确率较高的特点, 尽管现有的边缘检测算子十分成熟, 但是没有一种适应于任何图像质量、任何图形环境的边缘提取方法, 而且为了得到高识别率, 对于每幅图像要选用合适的边缘检测算子。文献将彩色图像转换到HSV颜色空间中对色彩进行分层处理是车牌定位彩色图像处理方向较新颖的方法, 但是这类方法的缺点也是很明显的, 当车身颜色与牌照颜色相近时, 辨识就变的几乎不可能了。文献提出了角点检测法, 因为角点代表的特征像素点占图像像素总数的百分之一, 却构成物体大部分的外形要素, 由于牌照的字符部分角点数较多, 所以作者使用Harris算法获取整幅图像的所有角点, 然后使用一个固定大小的滑窗去遍历图中的角点以得到牌照待选区域。通过角点获取牌照区域受干扰小, 识别的效率也比较高, 是应该深入研究的方向。
1 车牌标准分析
现行的《中华人民共和国公共安全行业标准——中华人民共和国机动车号牌》 (GA36-2007) , 于2007年9月28日发布, 同年11月1日实施, 用来代替原来的国标GA36-1992。按照GA36-2007的标准, 为了我们计算机识别的方便, 我重新整理从号牌行数和号牌特征着手归纳, 见表1。
经过归类并简化后, 很大程度上避免了排列方式对识别算法的干扰, 在字符分割阶段对车牌进行横向投影分析号牌分类是单行牌照还是双行牌照, 并根据上表优化算法, 可以达到快速准确的目的, 见图1。
下面从典型的单行牌照, 分析其字符规律。牌照中的字符分为三段:第一个字符是省、自治区或者直辖市的简称, 确定为汉字字符;第二个字符是发牌机关代号, 是大写的英文字母;第三至第七个字符为序号, 通常为大写英文字符和阿拉伯数字字符的排列, 对于特别号段的车辆会在末位字符出现“警”“领”“学”“临”“试”“港”“澳”等汉字字符。
典型的双行牌照, 见图2。双行牌照第一行就是单行牌照分割点前的两个字符, 第二行是单行牌照的第三位到第七位。双行牌照和单行牌照相比, 长宽比更小。
从颜色方面看, 无论是单行的牌照还是双行的牌照, 都有多种颜色的排列组合。但是归纳来说, 牌照背景颜色和牌照字体颜色的组合一共是四种, 分别是:黄底黑字、蓝底白字、黑底白字、白底黑字。特殊分类的字符颜色为红色, 而且特殊字符不会出现在蓝底背景的牌照上面。
2 原始K-均值算法
用Harris角点检测算法运算后的图像, 通过观察可以发现“牌照区域肯定是角点聚集的区域, 但是角点聚集的区域不一定是牌照所在区域”, 需要使用一个聚类分析方法来找到若干个角点聚集区域, 然后通过对区域特征的筛选, 最终决定牌照位置。K-均值算法是一种得到了广泛使用的基于划分的聚类算法, 算法把n个数据点按照目标函数分为k个簇, 以使簇内数据点具有较高的相似度, 而这个目标函数可以是欧氏距离。K-均值算法满足了希望把n个角点以欧氏距离分为k个号牌待选区域的思想, 而且它的时间复杂度是O (tkn) , t是迭代次数, 所以对图3 (a) 上由Harris算法得到的角点执行K-均值算法, 经t次迭代得到k个簇, 见图3。
3 改进K-均值算法
使用原始K-均值算法并不能在每次收敛后都得到牌照正确的区域 (见图4) , 因为其算法本身是用于数据挖掘的, 算法中初始点是随机决定的, 目标函数使用的是欧氏距离, 为适应号牌识别的效率和识别率双重的要求, 需要对其修改。在这个过程中, 参考了文献, 但是考虑到文中AP算法的时间复杂度高, 所以还是用K-均值算法。
首先从算法的随机取初始点着手, 通过实验发现初始随机点选择的结果不同, 收敛后的簇是可能不一致的, 所以尽量要选择一种既能接近最终收敛簇的形心, 又能是一种快速稳定的初始点提取算法。研究后决定用分冶思想把图像分成若干个矩形区域, 算法1的步骤如下:
步骤2, 遍历Ci, 2这张存放了角点的二维表, , 1/ij=C×M W, k Ci, 2N/H=×, Aj, kAj, k1=+。
步骤3, 设值max, 遍历Aj, k, 当Aj-1, k, Aj+1, k, Aj, k-1, Aj, k+1均未被访问过时, max=Aj, k, 并标记Aj, k为已访问过。
步骤4, 循环到步骤3, 所有的初始点都选出为止。
第二点的改进是传统的K-均值聚类时使用的欧氏距离, 而牌照的规格不是圆, 需要使用标准化的欧氏距离公式。两个n维向量a (x11, x12, ..., x1n) 与
b (x21, x22, ..., x2n) 间的标准化欧氏距离公式为:
其中ks是分量的标准差, 对于最常见的440mm×140mm的机动车牌照上二维的角点数据, 公式可以推导为
于是整个号牌定位的算法可以这样描述:
步骤1, 使用FAST角点算法获取图中角点。
步骤2, 使用算法1提取K-均值的初始点。
步骤3, 以计算出的中心点执行K-均值算法。
步骤4, 修改K-均值算法使用公式1。
步骤5, 在聚类后获取的簇所组成的矩形中, 根据车牌标准, 删除以下情况:高要比宽大;宽大于高的3.5倍;宽小于高的2倍;号牌颜色面积小于总面积50%。
执行上述算法后得到图5, 其中左边一张是通过上述算法得到的初始点, 右图是通过初始点再调用K-均值算法得到最终的角点分类后各个区域的中心, 从中可以发现初始点已经很接近最终的收敛结果, 所以这种算法可以大大的加快K-均值算法迭代的速度, 而且使得K-均值算法的执行速度是快速的, 结果是稳定的。
4 算法效率实验
测试数据集的描述:本文采用从网上随机选取的二十七张车辆正面图片作为样本来验证改进后的算法的效率。通过FAST角点检测, 其中每张图产生一千个以下的角点。
算法对比:分别用传统K-均值算法、滑窗定位法和改进过的K-均值算法分别对样本图片的角点进行聚类, 分别从平均识别速度和平均识别率两个方面进行对比, 见表2。
表2是对三种不同聚类算法的实验结果的汇总, 给出了具体量化的数据, 通过表2可看出传统K-均值算法由于迭代次数多而收敛速度慢, 并且识别率低。而改进后的K-均值算法虽然算法复杂但是由于迭代过程的改进使得识别速度和平均识别率都得到了很好的平衡。
5 车牌字符分割算法研究
本章节将讨论车牌字符分割问题。车牌字符的分割是车辆号牌识别流程中承上启下的环节, 主要是继续前章车牌定位的工作结果, 主要任务是从一张车牌图像中准确可靠的分割得到各个字符并完成归一化的工作, 提供给下面字符识别环节来进行分析。
由于机动车牌照存在单行车牌和双行车牌, 所以进行列分割之前要首先进行判断。通过分析车牌区域的水平投影图的形态就可以知道, 见图7。
因为车牌尺寸不同, 必须对它进行归一操作:将牌照灰度图缩放到100×50像素, 计算各行中段约25%~75%的区域, 在这个区域中搜索灰度值最小点, 若该点在接近1/3处, 该号牌就是双行车牌, 否则是单行车牌。下面介绍用列分割方法把单行车牌进行字符分割。首先对车牌定位后的图像进行二值化操作 (临界灰度值是160) , 这样得到的二值化图像减少了光照不均的影响。然后对单行车牌区域的二值化图像做垂直投影, 见图8。
然后通过下列的步骤实现字符分割, 其中投影图为P。
步骤1:令max P=MAX (P) , 得到投影图中的最值。
步骤2:寻找N中的0值点, 以0值点将N分为若干块:recti, i=1, 2, 3, ...。
步骤4:各块宽度为width=imax (recti) -min (recti) 。宽度中值为media Width。将widthi<media Width×1.2的块就近合并。
步骤5:若recti的宽度大于两倍中值宽度, 按中点将其分拆成两块。
步骤6:重复步骤4和5, 直到无合并或拆分操作为止。
步骤7:如果块宽度小于各块平均宽度, 以该块中心左右往外media Width2作为分割点;否则以该块左右边界为分割点。
步骤8:按照分割点分割图像, 按照各分割块的左右次序对其编号。
步骤9:分析各块底色 (二值化图像为0的点) 的平均色度值, 将其和车牌区域底色比较, 删除误差超过50%的块。
这样就把字符从定位好的牌照图像中分离出来了, 见图9。
6 车牌字符分割识别研究
支持向量机来识别号牌字符, 利用其良好的分类能力, 可以用来对字符进行分类, 有很高的字符识别率。
1992年开始在统计学习理论领域发展了一种称为支持向量机 (Support Vector Machine, SVM) 的新的模式识别方法, 在解决小样本、非线性及高维模式识别的问题中表现出很好的性能。由于同时神经网络遇到了网络结构固定、过学习和欠学习问题, 所以支持向量机方法成了机器学习领域内新的热点。
SVM方法从线性可分的最优分类面 (Optimal Hyper-plane) 提出了二类分类技术。它通过构造最优超平面使得不同样本类的距离最大化。
yi[ (wixi) +b]-1≥0, i=1, 2, ..., n就得到了最优的分类面。表述成约束优化问题就是在 (l) d的条件下, 求方程
对w和b偏微分并使之等于0, 得到对偶问题
在线性不可分情况下, 增加了松弛项ξi≥0, 分类条件方程变成:
所谓SVM的训练, 就是通过已有的样本, 求得支撑最优分类面的样本向量。由于SVM自身的特点, 相对于识别的样本, 只需要少量样本进行训练。这一点就满足车牌字符识别系统的要求。同时, 如果把整个字符作为输入数据, 输入样本就具有高维度的特征, 这要求分类器能够进行高效的高维度数据分类能力, 这也是SVM的优势所在。鉴于以上这些原因, 构造了用于车牌字符识别的支持向量机, 并使用大量实际数据效验所设计方法的有效性。训练中从100多张尺寸为800×600的各类机动车照片中分割出700多张字符照片, 其中某种字符的照片数是大于1的, 按照字符分类, 每种字符抽取一张, 一共71张字符照片, 手动选定字符系统自动对其进行缩放操作, 统一成32×16像素的图片, 然后再进行灰度化操作和二值化操作 (通过实验二值化的阀值定为灰度值160) , 这样每个字符照片所包含的信息量是相同的。实验中使用的支持向量机是由台湾林智仁教授开发的libsvm, 由于Objective-C是向下支持C语言的, 所以libsvm (C语言版) 是可以直接用于Objective-C开发的, 见图10。使用svm_train来进行训练。
识别的步骤和训练的步骤是相似的。对于从字符分割后的字母/数字图片, 首先进行灰度化和二值化处理 (二值化的阀值定为灰度值160) , 这样把产生的二进制数值作为一个svm节点, 加载SVM自识别系统在磁盘上的识别模型, 返回识别的结果。
7 号牌识别应用
最后在一台联想Think Pad T430上, 安装了Mac OS Mountain Lion (10.8.5) X64位操作系统和Xcode编程开发软件, 并把APP运行在一台i Phone 4 (操作系统IOS7.1.2) 上实现了号牌识别的全部功能, 见图11。
经过号牌定位、字符分割和字符识别三大步骤后, 实验在真机上的运行效果如图10所示。
8 结语
针对车牌定位这个难点问题, 本文将K-均值算法用于号牌识别的算法并进行了优化, 首先提出用分冶思想用于K-均值算法的初始点选取;然后对K-均值算法得到的结果, 也就是号牌候选区域进行筛选, 结合形状和颜色等因素来最后精确定位车牌, 这样既提高了算法的收敛速度, 又增加了算法的准确性。经IOS平台上实现的整个号牌识别程序实验结果, 证明改进后的号牌定位算法提高了识别率, 成效显著。
参考文献
[1]王晓雪, 苏杏丽.数字图像处理在车牌识别中的应用[J].自动化仪表, 2010, 31 (7) :22.
[2]迟晓君.一种基于支持向量机的车牌字符识别方法[J].信息技术与信息化, 2007, (6) :
聚类识别 篇6
关键词：股权结构,利润操纵,层次聚类分析,Logistic模型
一、引言
证券市场成立至今,国内外的利润操纵案件接连不断,严重影响了证券市场的健康发展。虽然我国对利润操纵行为加大了处罚力度同时也实行了更加严苛的审计程序,但利润操纵行为并没有明显减弱的趋势,反而是上市公司为了获取非法利益,使得利润操纵手段越来越复杂和隐蔽,外部信息使用者很难了解公司的真实经营状况。因此,对利润操纵行为识别的研究具有非常重要的意义。关于利润操纵的概念会计界存在两种观点:第一种观点是将利润操纵等同于西方会计文献中的盈余管理,即公司管理层为实现自身效用或公司市场价值最大化等目的进行会计政策选择,从而调节公司盈余的一种行为。第二种观点是将公司管理层出于某种动机,利用法规政策的空白或灵活性,甚至违法违规等各种手段对公司利润或获利能力进行操纵的行为称为利润操纵。结合Healy和Wahlen(1999)提出的盈余操纵是管理当局运用职业判断编制财务报告和通过规划交易以变更财务报告,旨在误导那些以公司经营业绩为基础的利益关系人的决策或影响那些以会计报告数字为基础的契约后果,本文拟采用第二种观点,即将利润操纵理解为为达到自身目的虚增利润的恶性行为。恶性的利润操纵行为严重影响财务报表的信息披露的真实性及资本市场的运行,而改进利润操纵识别模型有助于报表利益相关者更好的识别企业报表的真实性。本文研究的主要目的是建立相对简单的模型有效改善现有模型提高利润操纵识别率。
二、文献综述
(一)国外研究
Scott L.Summers和John T.Sweeney(1998)利用内部交易活动作为模型识别指标,运用分层Logistic回归建立了内部人交易因素的识别模型,较早的建立了利润操作的识别模型,为利润操纵识别研究的发展奠定了基础。Charalambos T.Spathis(2002)利用单变量和多变量统计技术建立了包含Z计分值以及不包含Z计分值的模型来识别利润操纵行为,选取10个用来检验虚假报告的财务指标,用该模型检验了希腊上市公司的财务数据,达到了较高的准确率。Demski(2008)回顾了利润操纵的各种实证研究,研究了利润操纵的各种模型,利润操纵研究趋于定量化。前期的识别指标均局限于财务指标,但Igan和Pinheio(2010)对公司治理与利润操纵的关联性进行了研究,认为利润操作行为与企业管理人员的行为显著相关,应加强内部管理及内部审计委员会与外部审计师的监督。
(二)国内研究
闫达伍、王建英(2001)利用选取的8个财务指标对样本进行配对检验,发现利润操纵公司普遍存在通过非营业活动、增加投资收益及采用关联交易来虚增利润的做法。李延喜、姚宏等(2006)设计17组会计指标,通过对利润操纵公司与其配对样本进行显著检验,构建指标的“安全区域”和“警戒区域”,初步建立了利润操纵识别模型,使得利润操纵由定性研究转为定量研究。姜金玲、李延喜(2008)运用Logistic回归模型构建上市公司利润操纵模型,这些模型的识别率均在70%-80%,识别率均不是很高。此外,部分学者也研究了非财务指标与利润操纵之间的关系,将影响因素进行了有效扩展、完善,有效提高了模型的识别率。林长泉、张跃进和李殿富(2000)从产权背景、会计准则因素以及外部审计监督等方面分析了国有股权背景下的利润操纵行为,揭示了股权背景对利润操纵的影响。郭太平、姜素萍和李明(2007)分析了上市公司利润操纵与股权结构的关系,得出利润操纵和公司股权结构存在显著的相关性。国有控股、第一大股东持股比例、第二大股东持股比例、第一大流通股股东持股比例和第二大流通股股东持股比例与利润操纵存在显著负相关关系。针对此前建立的基础识别模型,部分学者开始着手对利润操作识别模型进行改进。李双杰、陈星星(2013)利用粗糙集简化利润操纵的识别指标,通过蒙特卡洛模拟,提出基于BP神经网络的中国上市公司利润操纵的识别模型,进一步引入DEA效率指标,将非财务指标与财务指标相结合,有效提高了模型的判别率。梁鸿旭(2013)认为利润操纵是盈余管理超过了一定的范围所形成的连续行为,将模糊数学理论与线性规划有机结合,在一定程度上改善了将润操纵行为人的划分为{0,1}所带来的界限不清问题。
国外学者对于利润操纵行为的研究主要集中于利润操纵的原因、方法手段以及模型的建立和实证分析上。国内学者则集中于会计准则变化下利润操纵的原因、手段等理论研究,研究利润操纵识别的模型较少。且从现有文献来看,大部分学者的识别指标体系均局限于财务指标。但利润操纵企业与无利润操纵企业的股权结构存在显著差异,股东尤其是大股东对企业报表的真实性产生至关重要的影响,而且股权集中度对企业管理层产生的制约程度有一定差异,进而会对企业的利润操纵产生一定的影响,股权结构与利润操纵行为具有显著的关联性。同时,利润操纵是盈余管理超过了一定的范围所形成的连续行为,利润操纵行为的严重程度有较大的差异,简单的分为{0,1}使得分析结果不够严谨。因此,本文在前人研究的基础上改善现有模型,力求有效提升利润操纵行为的识别率。
三、研究设计
(一)样本选取与数据来源
本文从CSMAR数据库的上市公司违法违规数据库中选取2000~2013年间有利润操纵行为的77家上市公司作为研究样本,并对样本进行筛选和配对。样本筛选原则为:金融业与其他行业经营差异较大,剔除金融业企业;由于对利润操纵行为的识别需要利用企业前期的指标数据,因此剔除三年内有连续舞弊的企业;剔除已经退市和数据严重缺失的企业。为了消除行业类型及会计政策差异等因素造成的影响,本文按照1:1的比例选取与利润操纵组相互匹配的对照组,配对原则如下:按照证监会行业分类,对照组与利润操纵组所属行业相同;对照组与利润操纵组总资产规模差距不超过20%;对照组经营状况正常,治理结构合理,上市信息披露及时;对照组在利润操纵组舞弊期间,没有受到证监会的违规处罚。经过筛选,最终剩余56家样本企业,剔除不能配对的3家公司,得到53组配对样本。
(二)利润操纵识别指标的选取
徐浩萍(2005)认为控股股东为了保持上市公司的融资资格或是为了获取最大收益,会选择利润操纵,控股股东持股比例对利润操纵有一定的影响;于鹏(2007)研究得出分散化的股权结构以及国有股权对公司管理层的制约性相对较差,从而使得公司进行盈余操纵的可能性更大。因此,本文在已有研究的基础上,考虑识别指标所含信息的准确性和完备性,并综合考虑利润操纵的成因、手段、表现方式等因素引入股权结构指标优化了指标体系。本文选取了22个财务指标和6个体现股权结构的指标如表1所示。
四、实证结果与分析
(一)描述性统计
本文最终选取了利润操纵组及对照组共106家上市公司的指标数据作为研究对象。搜集了这106家上市公司以利润操纵当年为时点的t-1、t-2、t-3三个时期的指标数据(由于上市公司被证监会披露为利润操纵企业的时点具有滞后性,部分上市公司的财务指标在披露的前三年便有利润操纵迹象)。同时对这三个时期的指标数据分别进行配对样本T检验与Wilcoxon符号秩检验,T检验与Wilcoxon符号秩检验结果(两个检验结果只需其中一个显著即可,由于篇幅所限,本文未将检验结果列出)显示,在0.05的显著水平下,选取的指标中X1、X2、X3、X4、X9、X10、X11、X13、X14、X15、X16、X17、X18、X19、X20共15个财务指标指标,X24、X25、X26、X274个股权结构指标在53组双样本中具有显著差异。确定显著性指标后,对选取的指标进行相关性分析。通过对各时期样本指标的相关性分析可知,去掉显著相关的变量X1、X4、X15、X16、X19、X20、X25、X26,其他变量在显著水平0.05下不相关。本文选取的识别指标如表2所示。
(二)回归分析
(1)基于财务指标的Logistic实证结果。Logistic回归是处理定性因变量的常用统计分析方法,相比于多元回归分析,其不要求变量服从正态分布,因此模型相对稳健。本文将利润操纵行为作为虚拟变量引入模型,其中有利润操纵行为的取值为1,无利润操作行为的取值为0,运用SPSS17.0统计分析软件将上述配对检验中的9个显著的财务指标及相应的样本数据带入Logistic回归模型,预测结果如表3所示。由表3可知,共106个样本,其中有利润操纵行为的上市公司与无利润操纵行为的上市公司各53家,模型能正确识别的上市公司为78家,模型的正判率为73.6%,超过了70%。因此,本文构建的上市公司利润操纵模型具有较好的预测效果。但模型整体的识别率不高,后文将进一步完善。
(2)加入股权指标后Logistic实证结果。将上述配对样本检验中的9个显著的财务指标和2个显著的股权指标及相应的样本数据带入Logistic回归模型,估计及预测结果如表4和表5所示。
由表5可知,加入股权结构指标后,模型对于无利润操纵公司的识别的正确率提高到75.5%,对利润操纵公司的识别正确率提高到81.1%,总体的正判率有一定程度的改善,达到78.3%。这表明股权结构指标对于识别利润操纵行为十分有效。更为详细地,本文对两个体现股权结构的指标呈现出的显著性作出如下解释:第一,第一大股东股权性质对利润操纵行为影响显著。可以解释为第一大股东为国有背景时,相关政府部门能为企业投入资金、政策支持,能够更加有效地改善企业自身的经营,而且国有产权背景的上市公司的上市盈利压力相对较小,且公司管理效率较低,对利润操纵的能力有所欠缺,一定程度上反而能够维护报表利益相关者的切身利益,能有效抑制利润操纵行为。相比而言,民营企业大股东为改善公司形象、获取非法利益、避免行政处罚,会选择进行利润操纵。第二,第一大流通股东持股比例与利润操纵之间呈现显著的负相关关系。流通股股东大部分为自然人股东,其持股比例越高,表明其对公司的经营状况看好,不会短期抛售股票,公司盈利能力相对较强,同时反过来能够加强对上市公司的监督,能有效抑制利润操纵对自身带来的巨额损失。
(三)层次聚类分析
现有的利润操纵行为识别模型均将利润操纵行为分为有利润操纵行为和无利润操纵行为,对结果进行了离散化处理。而实际上利润操纵是盈余管理超过了一定的范围,是操纵程度上的连续行为,利润操纵有程度上的差异,有些操作行为可能非常轻微,有些可能非常严重。梁红旭(2013)通过将模糊数学的相关理论与线性规划结合建立一个全新的利润操纵模型,该模型在一定程度上克服了将利润操纵行为人为的划分为{0,1}所带来的界限不清问题。上述利润操纵模型在一定程度上能够识别利润操纵行为,但整体识别正确率不高,主要是因为利润操纵企业舞弊程度、舞弊手法具有一定的差异,笼统的将所有样本分为一类,可能会影响识别的准确性。层次聚类分析是对样品或指标进行分类的一种多元统计分析方法,其讨论的对象是大量的样品,要求能合理地按各自的特性将数据分类到不同的类或者簇,同一个簇中的对象有很大的相似性,而不同簇间的对象有很大的相异性。鲍新中(2013)通过层次聚类方法将财务状况分为5类,更符合实际状况,同时验证了该方法的有效性。
上述模型中显著的指标对具有严重利润操纵行为的识别效果较好,但对某些利润操纵手段复杂或行为轻微的企业却无法有效识别。为了有效克服将利润操纵行为人为的划分为{0,1}所带来的界限不清问题。本文利用表4中回归显著的指标X2、X3、X24、X27对初始样本进行层次聚类分析。层次聚类划分为两层,识别率较高的43家样本划分为一层,即大样本组;识别率低的10家企业划分为一层,称为小样本组。对两个样本组数据指标重新进行配对检验。
(1)大样本组利润操纵识别。对大样本组中的43家样本中各个指标重新进行配对样本T检验与Wilcoxon秩检验,结果显示,X2、X3、X9、X10、X11、X13、X14、X17、X18、X24、X27在0.05的显著水平下具有显著差异,对这11个指标进行相关性检验,剔除相关性水平较高的变量X9,余下的变量在显著水平0.05下不相关。对不相关的变量运用Logistic模型进行回归,结果如表6所示。由表6可知,检验的样本共有86个,采用层次聚类后的Logistic模型回归,模型能正确识别出的上市公司数量为71个,模型的总体正判率达到82.6%。相比前文的模型,该模型在去除舞弊轻微或操纵手法高明的企业后,识别率提高,进一步验证层次聚类的有效性,需要对剩余的样本进行单独识别。
(2)小样本组利润操纵识别。对该样本组中的10家企业的指标数据单独进行配对样本T检验与Wilcoxon符号秩检验,由于其自身利润操纵行为程度较为轻微或是手段越来越复杂、高明,其与正常的配对企业之间的显著性差异不大,结果显示在显著水平0.1下,X1、X2、X4、X6、X11、X14、X15、X19、X20、X21具有显著差异,而对于股权结构来说却没有明显的差异,由于该组样本量较小,本文运用Logistic回归模型时,采用Forward:Wald变量进入方法,可以在一定程度上自动克服变量之间共线性问题,其中变量进入标准是:P≤0.05进入,p≥0.1移出。模型预测结果如表7所示。检验的样本共有20个,采用层次聚类后的Logistic回归模型,模型能正确识别的上市公司数量为18个,模型的总体正判率达到了90%。
对于两个利润操纵程度不同的样本组,层次聚类后识别率显著提高,说明利润操纵公司的严重程度有一定的差异,且部分上市公司手段越来越高明,针对不同的利润操纵程度及手段,研究者应运用不同的方法来识别,对于一些利润操纵程度较轻,手段隐晦且与正常公司在财务指标与股权结构指标无较大差异的公司,传统的识别指标无法进行有效识别进行识别,对这类配对样本组重新进行显著性检验后,从回归结果中可以看出,主要通过X6经营活动中产生的现金流出小计/营业成本、X20息税前利润/平均总资产两个指标来识别。X6值越大,利润操纵的可能性越大,即所有的营业成本支出中用经营活动现金支付的比例较大,企业经营能力较差,现金流动水平较低,企业进行利润操纵的可能性越大。X20值越小,表明企业的投入产出水平较差经营效率较低,企业进行利润操纵的动机越强。对于这类利润操纵公司而言,其股权结构不存在显著的差异,且较难通过利用某些操纵手段修改数据形成的异常指标来进行识别,这类企业的一般财务指标较正常但是企业经营效率指标却相对较差,可结合其他因素增强对该类利润操纵企业的识别。
五、结论
上市公司的利润操纵行为严重损害了广大的利益相关者的权益,严重影响证券市场的良好的运行,随着中国证券市场的繁荣发展,市场规范与监管力度逐渐加大。建立高效、简洁的利润操纵识别模型是亟待解决的问题。本文研究发现上市公司利润操纵程度、造假手段具有显著差异,实际上利润操纵行为是盈余管理超过了一定的范围,是操纵程度上的连续行为。因此本文通过运用层次聚类方法,对不同程度的利润操纵上市公司分别进行识别,有效改善了笼统识别的弊端,对不同利润操纵程度上市公司运用不同的识别指标,对于两组样本的识别率分别达到了82.6%、90%,大大提升了模型的识别准确率。
层次聚类后的模型利润操纵公司识别正确率提高,主要是由于某些公司利润操纵程度比较微弱或是手段比较隐蔽,与正常经营的企业进行一定幅度的盈余管理水平相差不多,降低了对操纵企业的有效识别。层次聚类后,针对不同的类别,运用不同的指标,能够更加切实准确的识别。
参考文献
[1]阎达五、王建英:《上市公司利润操纵行为的财务指标特征研究,《财务与会计》2001年第10期。
[2]李延喜、姚宏、高锐:《上市公司利润操纵行为识别模型研究》,《管理评论》2006年第1期。
[3]姜金玲、李延喜、高锐:《基于Logistic的上市公司利润操纵行为识别模型研究》,《经济管理》2008年第9期。
[4]林长泉、张跃进、李殿富:《我国国有企业及上市公司的利润操纵行为分析》,《管理世界》2000年第3期。
[5]郭太平、姜素萍、李明:《上市公司利润操纵与股权结构关系探讨—基于我国制造业的分析》,《证券经纬》2008年第3期。
[6]徐浩萍:《控制股东利润操纵的动机及其监管研究》,《财经研究》2005年第2期。
[7]Healy M,Wahlen M.A Review of the Earnings Management Literature and Its Implications for Standard Settings.Accounting Horizons,1999.
[8]Charalambos T.Spathis.Detecting False Financial Statements Using Published Data:Some Evidence from Greece.Auditing Journal,2002.
聚类识别 篇7
随着信息技术的不断发展，计算机的系统安全越来越受到人们的关注，进行用户身份认也成为保护系统安全的一个重要手段。而传统的密码认证已经远远不能达到安全要求，因此基于生物特征的识别认证方法得到了广泛应用，例如指纹识别、虹膜识别、人脸识别等，但上述几种识别方法在应用过程中需要硬件设备的支持，并且成本较高，不利于推广。20世纪80年代，Gaines等人首先提出了击键特征用于用户身份认证[1]，随后出现了大量研究成果，如使用统计分析理论、模糊数学、人工神经网络等方法进行实现。其中统计分析理论是在假设样本为正态分布的前提下，将测试样本与训练样本进行比较，不过目前尚不清楚击键特征是否符合正态分布，模糊数学方法的精确度不高，而人工神经网络虽然效果比较好，但是实现难度较高并且训练时间比较长。
在此提出将聚类分析的方法用于击键特征识别，采用谱系聚类法对提取的用户击键特征进行分类，相比于前面提到的几种识别算法而言，谱系聚类法在实现时比较容易，并且其识别准确度达到了一定的要求，比较适合用于击键识别。
2 击键特征
用户击键特征体现为击键延迟时间和击键间隔时间[1]，不同人的这两种击键特征的不同性已经得到证实，所以在进行识别时既可以以其中之一为主要对象，也可以使用二者结合，在此主要针对击键间隔时间进行识别。
简单介绍一下用户击键特征的提取过程。用户在击键时，键盘会向系统发送击键消息，每按下一个键，便会有两个消息产生：一个是按下键的消息，一个是弹起键的消息。通过设置键盘钩，可以捕获键盘消息。在键盘钩函数中，可以对这消息进行识别需要的处理。在该函数中，通过测时函数对两个消息之间的间隔进行测量，从而得到一组击键序列之间的时间间隔向量，即用户击键特征矢量。
3 击键特征识别算法
3.1 类及类间距离测度方法
在研究聚类算法之前，要了解类的定义，这里将模式的特征矢量作为集合中的元素，并且以距离作为模式间的相似性测度。定义如下：
若集合S中任一元素xi、xj的距离dij有
式中，h为给定的阈值，则称S相对于阈值h组成一类。
距离测度的种类比较多，常用的有欧氏距离、绝对值距离、明氏距离、马氏距离等，这里使用的是最常用的欧氏距离，其计算方法如下：
设x=(x1,x2,...,xn),y=(y1,y2,...,yn)T。向量x,y欧氏距离为：
识别算法除了类及所用的相似性测度之外，还要用到类间距，类间距离的定义式有很多，下面主要介绍两种距离的定义。
(1)最近距离法
两个聚类ωk和ωl之间的最近距离定义为
式中，dij表示xi∈ωk与xj∈ωl之间的距离。
(2)最远距离法
两个聚类ωk和ωl之间的最远距离定义为
式中，dij表示xi∈ωk与xj∈ωl之间的距离。
3.2 谱系聚类法
谱系聚类法又称系统聚类法、层次聚类法，是效果较好、经常使用的方法之一，国内外研究得较为深入，有不少成果[2]。其基本思想为：首先定义类与类之间的距离，这里采用的是最近距离，再有类与类之间最短距离的递推公式，其中ωr为由ωp和ωq合并所得。
在此基础上，先将n个变量视为n个类，计算两两之间的距离，然后找到距离最小的两个变量，将其合为一类，再找到与此类距离最小的变量加入该类，最后得到所有变量间的谱系关系。
具体的算法步骤为：
(1)初始分类。令k=0，每个模式自成一体。
(2)计算各类间的距离，从而生成一个对称的距离矩阵。
(3)找出步骤(2)中距离矩阵中的最小元素，将其对应的两个类合并成一类，产生新的聚类。
(4)检查类的个数，如果大于2转至步骤(2);否则，停止。
对于给定的N个n维模式，要分成c类，在采用最近距离或最远距离的情况下的计算复杂度为O(cN2n2)。
在实现击键识别过程中，可以采用最近距离、最远距离或者平均距离中任意一种，但每种距离的适用范围不同，需根据具体要求进行选择。
3.3 识别方法
在完成数据的采集之后，要对采集到的用户击键特征矢量进行聚类分析，按上述谱系聚类法完成聚类后，可以得到一个类似图1的谱系关系图。根据图1中所示各矢量关系可以清楚地看到，矢量x6距离类的中心最远，因此在进行识别时类似于x6的这种待检测矢量就可以被拒绝。
在完成采样、聚类、识别之后，即结束整个用户击键特征识别。
4 测试
4.1 测试数据采集
本次测试数据采集在Microsoft Visual Studio 2008环境使用C++语言编程实现，获得的击键时间间隔精度为毫秒(ms)。共设置口令4个，长度分别为6、8、10和12。采集合法用户击键特征样本20个，合法待测样本和非法待测样本各50个。
4.2 测试结果
测试结果如表1所示。
从表1中数据及文献[3]可以看出，尽管使用谱系聚类法对用户击键特征的识别准确度不如神经网络等方法，但是其实现难度较小，花费较多资源，因此还是用一定应用价值的。
5 结语
提出使用统计学中常用的谱系聚类法对用户击键特征进行分析识别，从测试结果中可以看出该方法达到了较好的效果。虽然无法达到人工神经网络等方法的识别精度，但是该方法比较容易实现，并且可以满足一定的安全要求，具有一定的使用价值。
摘要：以用户击键特征为依据,提出了一种基于谱系聚类法的识别算法。该算法通过谱系聚类法对用户击键特征向量进行聚类分析,并形成各向量之间的谱系关系,从而由谱系关系来对击键特征向量进行识别。该算法的主要特点是使用欧氏距离进行分类,算法实现简单并且识别速度快。由于采用的聚类算法的简单性,其识别精度尚有待提高,因此该算法适用于击键识别的简单应用。
关键词：谱系聚类法,击键特征,身份认证
参考文献
[1]Gaines R,Lisowski W,Press S.Authentication by Keystroke Timing:Some Preliminary Results[R].Rand Corporation:Rand Report R-2560-NSF,1980.
[2]孙即祥.现代模式识别[M].北京:高等教育出版社,2008.
聚类识别 篇8
星座图重构中最常用的聚类算法是均值聚类算法及其改进算法。由于均值聚类算法需要预先知道初始聚类中心位置及其数目的缺点，因此文献[3]提出用基于信噪比估计的自适应减法聚类算法得到初始聚类中心。在信噪比较大时，由减法聚类算法得出的聚类中心和实际调制星座图很接近。但当信噪比较小时，聚类结果和实际调制星座图的误差较大，因此本文拟用半监督聚类法对自适应减法聚类得到的初始星座图进行二次聚类[4]。本文首先用基于“密度”思想的自适应减法聚类给出初始聚类中心，然后再用半监督聚类方法重构星座图，最后对重构的星座图提取特征参数R进行调制阶数判别。半监督重构星座图过程中，在每个聚类中心周围标记部分样本点，用标记的样本点指导隶属度及聚类中心的更新，很大程度上减少了算法的迭代次数，缩短了运算时间，降低了复杂度。
1 基于信噪比的自适应减法聚类
针对任何一种调制方式，在合适的“密度”半径下，基于“密度”指标的减法聚类算法[5,6]能够高效地找到初始聚类中心。对不同阶数的调制信号，根据信噪比估计值设定不同大小的“密度”半径值，就可以完成星座图的初始聚类。下面给出基于信噪比估计的减法聚类算法。
考虑N个码元同步复信号(r1,r2，…，rN),k=1,2，…，N，不失一般性，对其进行幅度归一化得rn,k。由于每个数据都是聚类中心的候选者，因此rn,k处密度指标Dk定义为
式中:SNR表示信噪比值;θɑ(SNR)定义了基于信噪比的密度指标领域，是平均功率意义上的平均噪声幅度值，表明了信号点的聚合程度;Kɑ表示性能调整系数，通过改变Kɑ的值找到聚类密度与平均噪声幅度的比例关系。实际应用中，Kɑ的值通过多次实验得到。将式(2)代入式(1)可得
式中:Pn代表了平均每个符号的噪声功率。每个数据点的密度指标都计算完之后，选择密度最大的点作为第一个聚类中心，令rnc,1为选中的点，Dnc,1为其密度。每个数据点rn,k的密度将用式(4)重新修正
式中:Kb是个常数，物理意义是密度减小的领域半径的调整系数。常数Kb通常大于Ka，为了避免出现相距很近的聚类中心，一般取Kb=1.5×Ka。该过程不断重复，直至将所有的数据点都包含在聚类中心辐射的范围内，找到所有的初始聚类中心。
2 改进的半监督模糊聚类算法
传统的半监督模糊聚类算法[7,8]是通过标记部分样本点来指导聚类中心的更新，将密度较大的点及其周围的点作为标记的样本点，并给这部分标记的样本点赋予初始的隶属度值进而指导隶属度及聚类中心的更新。设N个码元同步复信号组成的样本集合R=(r1,r2，…，rN),k=1,2，…，N。用式(5)选择密度较大点的周围的部分点作为标记样本点。
式中:mi为聚类中心;C表示聚类中心的数目;uik是第k个样本对于第i个聚类中心的隶属度;Ku是常数，用来调整密度较大点周围点数的选择[9];Pn*是归一化后的信号噪声功率。由式(6)计算标记样本点的初始隶属度值fik和uik为
式中:h是标记样本点的数目;C是聚类中心的数目;b是控制模糊程度的常数[10]，实验中取值2.3。更新隶属度值为
同时隶属uik度满足式(8)，即每个样本对各个聚类中心的隶属度之和为1[11]。
更新完隶属度之后按式(9)更新聚类中心为
隶属度和聚类中心都更新完之后代入式(10)计算误差平方和函数[12]，计算公式为
由式(7)可知，α与标记的样本点数成反比，在此可将α值理解为对标记样本点的可信度。标记的样本点占样本总数的比例越小，说明标记的点离密度最大点越近，从而标记的点成为聚类中心的可能性越大、可信度越高，相应的α值就越大;相反标记的点越多，可信度就越低，α值就越小。在隶属度更新和误差平方和函数的求解中，α的引入体现了标记样本点的监督和指导作用，是半监督思想的具体体现。通过迭代使代价函数逐渐收敛，收敛的判决条件为
Jc(k+1)≈Jc(k)(11)
传统的半监督聚类算法，用式(5)选择标记点，利用标记点监督指导聚类中心和Je的更新，在更新过程中所有的样本点都参与运算。这里存在2个问题:1)标记点的选择;2)更新过程中是否全部的样本点都要参与运算。针对第1个问题，在噪声功率一定的情况下，Ku的大小决定着标记样本点的多少。Ku值越大标记的样本点越多，最终的聚类中心越精确、误差平方和越小，但相应会增加一定的运算量。在低信噪比情况下样本点数据受噪声影响，Ku过大将不可避免地选择部分受噪声影响大的样本点作为标记点来监督聚类过程，严重影响聚类的最终结果。所以选择合适的Ku标记部分有代表意义的点作为标记点来指导聚类过程是关键。经过多次实验，选取Ku=1.5时，聚类中心周围标记的点分布均匀，能够较好地指导聚类中心的更新。针对第2个问题，在噪声功率和Ku一定的情况下，参与运算的样本点数目决定了算法的时间复杂度。参与运算的样本点数越多，算法花费的时间就越多，所以如何减少参与运算的点数才是降低算法复杂度的关键。基于此本文在传统半监督算法的基础上提出如下改进:在初始样本点数N一定、初始聚类中心确定的情况下，按式(5)在每个聚类中心周围标记出大部分样本点并按距初始聚类中心的距离远近排序，然后对排过序的这部分点每隔一个点取一个点与各个初始中心一起作为最终标记点，最后仅用这部分标记的样本点参与隶属度和聚类中心的更新运算，这在很大程度上减少了参与运算的样本点数，缩短了运算时间，提高了运算效率。本文用等间隔法取标记点，一方面保证了标记样本点的覆盖范围，确保最终聚类结果的精度不下降;另一方面也在一定程度上避免了相距过近的两个点重复参与运算，降低了算法的时间复杂度。
文中N表示样本总数，C表示聚类中心数目，h表示标记样本点数目。改进前的聚类算法在计算初始聚类中心时的时间复杂度为O(N+C)，隶属度更新时的时间复杂度为O(NC)，聚类中心更新时的时间复杂度为O(C)。即算法总的时间复杂度为O(N+C)+O(NC)+O(C)。改进之后算法总的时间复杂度为O(N+C)+O(hC)+O(C)，而Nh，通过仿真表明改进之后算法的运算时间减少为原来的1/3。
3 基于星座图圆半径的MQAM信号识别算法
通过对MQAM方形星座图的研究，星座图上的每个点可以按照到原点的距离不同划分到半径不同的圆上。为了实现对不同调制阶数的比较，定义一个相对的判别标准，即定义变量R使其等于星座图的圆中最大半径与最小半径之比
首先由标准星座图计算出参数R的标准值Rs。然后在得到C个聚类中心之后，计算每个中心所在圆的半径值并排序，取最大的4个半径值的均值作为最大半径rmax，取最小的4个半径值的均值作为最小半径rmin，从而求得参数R。将R和Rs相比较实现不同调制阶数的识别。基于半径的调制方式的识别方法，重构星座图的特征值提取简单，调制方式判决方便;能胜任星座图出现偏移的情形，星座图中部分中心偏移不影响正确判决;最大优点是当出现聚类的中心数比实际的星座图的中心数多或者少时，不需要进行中心的合并和分裂。
4 仿真结果
本文在高斯白噪声、误码率15%的情况下，对4阶到256阶MQAM信号分别进行100次实验。其中对4QAM,8QAM,16QAM,32QAM使用2 000点样本数据进行实验，对64QAM,128QAM信号使用4 000点样本数据进行实验，256QAM使用8 000点样本数据进行实验。
4.1 聚类准确性和聚类时间
本文对传统的半监督聚类算法和改进后的算法分别进行100次的实验仿真，并统计了算法改进前后的运算点数、聚类中心数和运行时间如表1。表1中斜杠前后分别表示传统的半监督聚类算法和改进后算法的参数。从表1可以看出，传统的半监督算法对4QAM,16QAM，…，256QAM分别用2 000,4 000,8 000样本点进行运算更新，而改进后算法参与运算的样本点数近似为传统算法的1/3。从聚类中心数目来看，改进后的算法在减少了大量参与运算的样本点数的情况下，并没有降低聚类中心的准确性。从算法的运算时间来看，传统的半监督算法的运算所花费的时间近似是改进后算法的3倍。
4.2 误差平方和函数曲线
图1和图2分别是16QAM信号迭代50次的误差平方和函数曲线，其中误码率为15%,Eb/Nb=5 dB。由图1看出改进前的算法要迭代8次时才逐渐收敛，而改进后算法迭代4次就趋于收敛。迭代次数减少一半，算法的运行所花费时间大大缩短。针对128QAM,256QAM等更高阶信号，参与运算的样本点更多，时间复杂度更高，运用改进后的算法优势会更加明显。因此通过改进的半监督聚类算法，对高阶调制信号来说，时间缩短更明显、效率更高。
4.3 基于半径的MQAM信号识别
根据标准的Rs值将不同阶数的调制信号的R值划分不同的范围如表2所示。对于不同阶数的调制信号将R落在相应范围内时即将信号的调制方式判别为相应的调制阶数。结合表1和表2可以看出对于低阶调制信号聚类中心数目准确，识别率达到100%，对于高阶信号尽管聚类中心数目不太准确，但是用本文提出的基于半径的调制识别算法识别率仍然在95%左右。因此，重构星座图基于半径的识别算法在聚类中心数目不准确时能够正确识别，不需要聚类中心的合并和分裂，算法简单高效。
5 总结
本文用改进的半监督聚类算法，由减法聚类得到初始聚类中心，用半监督思想标记每个聚类中心周围部分样本点参与隶属度和聚类中心的更新，与之前的半监督聚类算法的所有样本点都参与运算相比，在很大程度上减少了参与运算的样本点，降低了算法的时间复杂度，提高了运算效率。但是参与更新的样本点数减少，聚类中心的更新尺度减小，即初始聚类中心的权重变大，对初始聚类中心的依赖性大。因此聚类中心的准确性和算法的复杂度需要折中处理，找到合适的分界点。
参考文献
[1]刘爱声.数字通信信号调制识别研究[D].南京:南京邮电大学,2012.
[2]王建新,张路平.MQAM信号调制方式盲识别[J].电子与信息学报,2011,33(2):332-336.
[3]孙刚灿.非协作数字通信信号调制方式识别算法研究[D].北京:北京理工大学,2008.
[4]GU L.Two semi-supervised locality sensitive K-means clustering[C]//Proc.IEEE Fifth International Conference on Advanced Computational Intelligence.Nanjing,China:IEEE Press,2012:296-299.
[5]YANG Q,ZHANG D,TIAN F.An initialization method for fuzzy cmeans algorithm using subtractive clustering[C]//Proc.Third International Conference on Intelligent Networks and Intelligent Systems.Shenyang,China:IEEE Press,2010:393-396.
[6]LI Yanling,LI Bingbing,YIN Changyi.Modulation classification of MQAM signals using particle swarm optimization and subtractive clustering[C]//Proc.International Conference on Signal Processing.Beijing,China:IEEE Press,2010:1537-1540.
[7]GU Lei,LU Xianling.Semi-supervised locality-weight fuzzy c-means clustering[C]//Proc.International Conference on System Science,Engineering Design and Manufacturing Information.Wuxi,China:IEEE Press,2012:88-91.
[8]曾山.模糊聚类算法研究[D].武汉:华中科技大学,2012.
[9]CHEN C.A semi-supervised feature selection method using a non-parametric technique with pairwise instance constraints[J].Journal of Information Science,2013,39(3):359-371.
[10]COVES T F,HRUSCHKA E R,GHOSH J.A study of k-means-based algorithms for constrained clustering[J].Intelligent Data Analysis,2013,17(3):485-505.
[11]HASHEMI H,JAVAHERIAN A,BABUSKA R.A semi-supervised method to detect seismic random noise with fuzzy GK clustering[J].Journal of Geophysics and Engineering,2008,5(4):457.