kc复杂度课件

复杂度分析,小组成员： 吴敏 贾添添 康孟飞 刘哲 徐兴哲,contents,复杂度简介,KC复杂度分析,粗粒化方法的研究和改进,总结,1,复杂度简介,KC复杂度,复杂度分析方法是一种非线性动力学的分析方法，非常适合对非线性、非平稳信号的分析处理。 Kolmogorov 在1965年提出了算法复杂度的概念，即：针对一字符串序列，在通用的图灵机上生成该序列的最短程序长度与该字符串大小之比。但是不存在一个函数能计算出所有字符串序列的算法复杂度。 目前，我们所使用的KC复杂度的概念实际上指的是Lempel-Ziv复杂度（LZC）。Lempel-Ziv复杂度是针对有限长序列提出的一种判别序列随机程度的手段，是由Abraham LempeI和Jacob Ziv于1976年发表在“IEEE Transactions On Information Theory”上的文章中首次提出的，首次从数学上将Kolmogorov复杂性的计算变为现实。 两者的区别在于：Kolmogorov复杂度以生成符号序列的最短的通用图灵机程序长度为复杂性的度量；Lempel-Ziv复杂度作为简化的模型以符号序列中出现的模式的多少为复杂性的度量。 KC复杂度分析是一种基于粗粒化的方法，根据粗粒化的程度不同称为N值化过程。经过粗粒化后，Lempel-Ziv复杂度对噪声不很敏感。这些特点很适合生物信号的处理。,KC复杂度的计算,1、时间序列的重构（N值化过程） 2、扫描重构序列，得到子序列的数目c(n) 3、归一化KC复杂度（0 C(n)1）,例如，序列0010的复杂性测度可以由以下步骤得到： “插入”符号* 得0*010 S=0，Q=0，SQ=00，SQv=0，Q(0)在SQv(0)中出现过0*010； S=0，Q=0l，SQ=001，SQv=00，Q(01)不在SQv(00)中出现过，Q是插入0*01*0 S=00l，Q=0，SQ=0010，SQv=00l，Q(0)在SQv(001)中出现过，Q是插入0*01*0 得到一个用 * 分成段的字符串，段的总数定义为“复杂度”c(n)。上例中c(n)=3,2,KC复杂度分析,1、不同类型信号的KC复杂度 2、信号长度对KC复杂度的影响 3、粗粒化的重数（N值化）对KC复杂度的影响 4、阶数对KC复杂度的影响,仿真信号：输入是采样率为1000、频率为1Hz的正弦信号，强度为1dbW的高斯白噪以及两者的线性叠加； 生理信号：正常年轻人静息闭眼、静息睁眼及工作记忆状态下的Fz和Pz导联的EEG，采样率为1000Hz，时长50s。,1、不同类型信号的KC复杂度,理论上，当取样点足够多的时候： 周期信号的KC复杂度趋于0； 理想白噪的KC复杂度趋于1； 观察结果： 正弦信号的KC复杂度趋于0； 混合信号的KC复杂度介于周期信号和高斯白噪之间； 高斯白噪的KC复杂度略高于1？,随机信号在混合信号中的占比不同对KC复杂度的影响,随着随机信号(高斯白噪)成分的增加，KC复杂度的值会逐渐增大并趋向于1， 不过几乎所有信号都在同样的取样长度处，KC复杂度的值趋于平稳。,静息态和工作记忆状态的EEG信号，其KC复杂度呈现明显不同的变化趋势；但由于是分析的全频段脑电信号，尚不能得出工作记忆的复杂度低于静息态复杂度的结论。 两种静息态的EEG信号的KC复杂度变化趋势基本一致，在细节上有不同之处。,2、信号长度对KC复杂度的影响,当取样点数较少的时候，复杂度值不能稳定； 只有当取样点数达到一定值，KC复杂度趋于稳定； 根据该测试结果，我们在随后对EEG数据进行处理时，采用了6000的窗宽，步长取1000。,3、粗粒化的重数（N值化）对KC复杂度的影响,对于周期序列，不同N值化的KC复杂度结果基本一致，均随着数据长度的增加趋于0。,与二值的粗粒化编码相比，四值的粗粒化编 码中包含了更多幅度跳动的信息。 粗粒化的程度会对复杂度产生显著影响；随着粗粒化精度的提高，复杂度的计算量增大，但其灵敏度也相应增加。,张连毅. 粗粒化编码对Lempel-Ziv复杂度的影响J. 上海电机学院学报, 2013, 16(4):193-197.,精神疲劳脑电信号数据，数据总长3000点，采样周期0.06。窗长1800、步长17，分别求Fp1、Fp2通道信号二值粗粒化的LZ复杂度2和四值粗粒化的LZ复杂度4。,张连毅. 粗粒化编码对Lempel-Ziv复杂度的影响J. 上海电机学院学报, 2013, 16(4):193-197.,全频段 波段 波段,4、阶数对KC复杂度的影响,高阶复杂度的概念： 对0-1序列的重构方法做一些改进：首先求原始信号的平均值；然后求信号与平均值的差值的绝对值，再求这一新得的绝对值序列的平均值，并以其为阈值构造0-1序列。该序列可以称之为原始信号的二阶符号序列，再计算其复杂度：称为二阶复杂度。如多次重复这一过程，可以得到信号的高阶复杂度。 二阶复杂度相对于一阶复杂度，可以反映出位于波幅绝对值较高位置处信号的变化，突出了原始信号中的细微变化和特征，增加对信号序列性质识别的区分度。 高阶复杂度的引入，可以减少粗粒化对原始信息的丢失。,4、阶数对KC复杂度的影响,高阶KC复杂度的值一般要大于低阶KC复杂度； 高阶KC复杂度的变化呈现出较大的波动性（差异性），对信号特征的反映更加精细。,通过比较右图，可发现： 对于同一导联，相同状态的KC复杂度，二阶复杂度的值要大于一阶复杂度的值； 对于工作记忆状态，二阶复杂度的变化趋势与一阶复杂度的变化趋势不同。,3,粗粒化方法研究和改进,1、不同粗粒化方法对KC复杂度的影响 2、粗粒化阈值对KC复杂度的影响,1、不同粗粒化方法对KC复杂度的影响,粗粒化即对时间序列的符号化，其目的是用尽量少的符号集提取尽可能多的有效信息，它提取有效信息的能力将直接影响到复杂度分析结果的好坏。常用的方法有以下几种： (1)静态法，即按照不同的阈值将原信号序列重构。前面的结果都是按照均值或均值加以变化作为粗粒化的阈值，除此之外还有等概率法和等区间法两种粗粒化的方法。 (2)动态法：也是最简单的一种粗粒化方法，只考虑两相邻点信号的关系。 (3)其他方法，如综合法等。,等概率法,复杂度计算的前提是不同字符s(j)在符号序列S(j)中出现的概率pj (j =1 , 2 , , k)应该相等, 而常规的粗粒化方法没有考虑这一因素。 粗粒化阈值选取原则：不同字符s(j)在重构后的符号序列S(i)中出现的频率尽可能相等;原序列中相等的数据在重构后的符号序列中必须对应于相同的字符。 对原序列x(i) ，i =1 , 2 , , n从小至大排序，进行k值化时阈值取,等区间法,对归一化的数据进行粗粒化，以10重粗粒化为例，原数据归一为0,1区间，并均等地分为10个区间，分别为：0, 0.1、0.1, 0.2、0.9, 1.0。 对应的阈值分别为：0.1、0.2 0.9,张佃中. Lempel-Ziv复杂度算法中粗粒化方法分析及改进J. 计算物理, 2008, 25(4):499-504.,肖毅, 陈善广, 韩东旭,等. 脑电信号多重粗粒化复杂度分析方法研究J. 电子科技大学学报, 2013, 42(3):469-474.,仿真信号2值化的三种粗粒化方法的结果对比： 对于二值化结果，三种方法KC复杂度基本保持一致，但等区间法的波动性更大。,仿真信号4值化的三种粗粒化方法的结果对比： 正弦信号无论采用几值化的粗粒化方法，结果基本保持一致，但在4值化时，等区间法的KC复杂度明显变小，且出现阶梯状变化，分析原因，可能与信号的个别位置出现较大幅值的脉冲有关。,通过上图1、2的比较可以发现，采用等区间法时，对数据做归一化处理可在一定程度上降低高幅值脉冲的影响,对于脑电信号，三种方法得到的复杂度结果变化趋势基本一致， 常规方法和等概率法的2值化复杂度结果几乎完全一致； 在3值化和4值化的时候，等区间法的复杂度值有明显减小，4值化尤为明显。 对于EEG信号，等区间法未出现阶梯状的改变，推测可能与脑电信号的高信噪比有关，没有附加较大的噪声干扰。,比较静息态闭眼和工作记忆的三值一阶KC复杂度可发现： 三种方法基本可以反映出两种不同状态脑电信号的复杂度变化趋势，但等区间法得到的复杂度变化呈现更大波动性。,其他改进的粗粒化方法介绍-避免过度粗粒化,a、多尺度二值化方法（动态法）,传统二值化方法（按照均值划分）得到重构序列为：11110000 多尺度二值化方法（第一个点按照均值划分，随后的点按照动态法划分）得到重构序列为：11010010 多尺度二值化方法刻画了一定程度范围内的变化过程，保留了更多的原始信号信息。,罗志增, 曹铭. 基于多尺度Lempel-Ziv复杂度的运动想象脑电信号特征分析J. 传感技术学报, 2011, 24(7):1033-1037.,其他改进的粗粒化方法介绍-避免过度粗粒化,b、以拟合曲线为界的二值化方法,和卫星, 陈晓平. LZ复杂度算法中的二值化方法分析及改进J. 江苏大学学报自然科学版, 2004, 25(3):261-264.,2、粗粒化阈值对KC复杂度的影响,三值化的阈值定义：,由于采用了x的最值作为阈值划分依据，所以依然存在受极端值影响的可能。取较大的m值可以减少这种影响。 另外，可以考虑采用均值均值/m的形式。,以二值粗粒化为例, 研究不同阈值对Lempel-Ziv 复杂度的影响.对已知的时间序列, 按 选取不同的阈值R , 进行二值粗粒化, 计算出相应的复杂度.,不同的二值粗粒化阈值, 对复杂度C 和Ch 大小的影响非常明显,为了得到能反映出序列动力学特性而又相对稳定的复杂度值, 粗粒化阈值选取是一个比较关键的因素. 图中“ + ”号和“ O” 分别表示的是以序列的平均值为阈值和等概率粗粒化方法确定的阈值算得的复杂度的相应位置, 二者差异不大, 且均接近复杂度峰值位置。,张佃中. Lempel-Ziv复杂度算法中粗粒化方法分析及改进J. 计算物理, 2008, 25(4):499-504.,4,总结,KC复杂度算法简单，便于实现，是分析脑电等信号非线性变化特征的有效手段； 通过仿真，验证了随机序列的复杂度趋于1，周期信号的复杂度趋于0，其余信号的复杂度介于0,1之间； 复杂度c(n)的稳定性与计算所选取的信号长度n（即计算窗口的大小）有关，需选择合适的n值