搜索
1/20/20201数据结构智能信息处理与算法IntelligentInformationProcessingandAlgorithm李勇明yongmingli@cqu.edu.cn重庆大学通信工程学院一、智能信息处理是一门综合性的交叉学科，是信息科学的前沿领域，主要研究利用智能技术对信息进行处理的理论、方法与技术。二、开设智能信息处理课程的必要性：国家信息化发展的需要；学科理论发展的需要；培养高素质信息处理人才的需要。国家《2006—2020年国家信息化发展战略》规划中指出，信息化是充分利用信息技术，开发利用信息资源，促进信息交流和共享，提高经济增长质量，推动经济社会发展转型的历史进程。20世纪90年代以来，信息技术不断创新，信息产业持续发展，信息网络广泛普及，信息化成为全球经济社会发展的显著特征，并逐步向一场全方位的社会变革演进。课程说明三、智能信息处理研究的主要内容——概述——具体主要智能信息处理方法——智能信息处理方法的实现及应用研究四、智能信息处理的特点（1）智能信息处理是人工智能与信号信息处理相结合的产物（2）智能信息处理的基础理论：数据融合、神经计算、模糊计算、进化计算，等（3）以智能信息处理为主要计算方法智能信息处理：是人工智能技术与信息技术结合的产物，广泛地模拟人的智能来处理各种复杂信息，包括非结构化信息、海量信息、不完全信息、不确定信息、模糊信息、多媒体信息、时间空间信息、认知信息等。主要技术与方法：数学统计、神经网络信息处理、模糊计算、进化计算，等。五、智能信息处理的应用智能通信、机器人、智能信号与信息处理、智能交通、智能医疗，等第1章概述•信息技术组成部分•主要历史发展•主要技术分类•目前研究现状和趋势信息技术组成部分信息获取信息传输信息处理信息应用信息源1.1智能计算及其主要发展历史•20世纪90年代，符号物理和连接机制结合•1992年，智能计算依靠数字材料•生物智能、人工智能、智能计算•人工神经网络为主导，与模糊逻辑系统、进化计算以及信号与信息学科的综合集成•人工神经网络特点：并行性、互连性、存储分布性、非线性、容错性、结构可变性、计算非精确性•模糊计算特点：非确定性•进化计算特点：并行性、随机性1.2智能信息处理的主要技术•神经计算技术•BP,RBF,Hopfield,随机型,自组织竞争型•权值计算，优化，软硬件实现，应用•模糊计算技术•模糊逻辑，粗糙集•应用•进化计算技术•GA,Tabu，PSO，ACO•软硬件实现，应用1.2.1神经计算技术•NAPAN的提出和简化•非线性（nonlinear），适应的（adaptive），并行的（parallel），模拟的（analogy），网络（network）•神经网络接近人脑的表现•与符号主义的区别•前者：认知的基本元素是神经细胞，认知过程是大量神经细胞的连接引起神经细胞的不同兴奋状态和系统表现出的总体行为。后者：认知的基本元素是符号，认知过程是对符号表示的运算。•PCA•SVM神经轴突与人工神经网络简图神经网络接近人脑的表现•能够处理连续的模拟信号（例如连续变换的图像信号）•能够处理不精确的、不完全的模糊信息。•冯.诺依曼计算机给出的是精确解，神经网络给出的是次最优的逼近解。•神经网络并行分布工作，各组成部分同时参与计算；单个神经元的动作速度不快，但网络总体的处理速度极快。•神经网络具有鲁棒性，即信息分布于整个网络各个权重变换之中，某些单元的障碍不会影响网络的整体信息处理功能。•神经网络具有较好的容错性，即在只有部分输入条件，甚至包含了错误输入条件的情况下，网络也能给出正确的解。•神经网络在处理自然语言理解、图像识别、智能机器人控制等疑难问题方面具有独特的优势。PCA（principalcomponentsanalysis）•一种简化数据集的技术。它是一个线性变换。这个变换把数据变换到一个新的坐标系统中，使得任何数据投影的第一大方差在第一个坐标（称为第一主成分）上，第二大方差在第二个坐标（第二主成分）上，依次类推。主成分分析经常用减少数据集的维数，同时保持数据集的对方差贡献最大的特征。•设法将原来变量重新组合成一组新的互相无关的几个综合变量，同时根据实际需要从中可以取出几个较少的综合变量尽可能多地反映原来变量的信息的统计方法叫做主成分分析或称主分量分析，也是数学上处理降维的一种方法。•与用全维观测空间相比，可以更好的推广到独立于训练集的数据•时间代价小SVM•支持向量机是将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。•对支持向量的分类等价于对整个样本集的分类•针对小样本情况1.2.2模糊计算技术•模糊理论的提出（不相容原理）•与其它方法的主要区别•无需提供数据之外的先验信息模糊逻辑•模仿人脑的不确定性概念判断、推理思维方式，对于模型未知或不能确定的描述系统，应用模糊集合和模糊规则进行推理，表达过渡性界限或定性知识经验，模拟人脑方式，实行模糊综合判断，推理解决常规方法难于对付的规则型模糊信息问题。模糊逻辑善于表达界限不清晰的定性知识与经验，它借助于隶属度函数概念，区分模糊集合，处理模糊关系，模拟人脑实施规则型推理，解决因“排中律”的逻辑破缺产生的种种不确定问题。•处理部分真实概念的布尔逻辑扩展。经典逻辑坚持所有事物(陈述)都可以用二元项(0或1，黑或白，是或否)来表达，而模糊逻辑用真实度替代了布尔真值。这些陈述表示实际上接近于日常人们的问题和语意陈述，因为“真实”和结果在多数时候是部分(非二元)的和/或不精确的(不准确的，不清晰的，模糊的)。•应用1.2.3粗糙集•它是一种刻划不完整性和不确定性的数学工具,能有效地分析不精确,不一致,不完整等各种不完备的信息,还可以对数据进行分析和推理,从中发现隐含的知识,揭示潜在的规律.•粗糙集理论是建立在分类机制的基础上的,它将分类理解为在特定空间上的等价关系,而等价关系构成了对该空间的划分.粗糙集理论将知识理解为对数据的划分,每一被划分的集合称为概念.粗糙集理论的主要思想是利用已知的知识库,将不精确或不确定的知识用已知的知识库中的知识来(近似)刻画.•该理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息,所以对问题的不确定性的描述或处理可以说是比较客观的应用举例1.2.4进化计算技术•为什么要研究？•遗传算法•蚁群算法•微粒群算法（粒子群算法）为什么？遗传算法（GeneticAlgorithm，GA）•在遗传算法里，优化问题的解被称为个体，它表示为一个变量序列，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，不过也有其他的依赖于特殊问题的表示方法适用，这一过程称为编码。首先，算法随机生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，以提高初始种群的质量。在每一代中，每一个个体都被评价，并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序，适应度高的在前面。这里的“高”是相对于初始的种群的低适应度来说的。算法主要流程•算法–选择初始生命种群–循环•评价种群中的个体适应度•以比例原则（分数高的挑中机率也较高）选择产生下一个种群（轮盘法roulettewheelselection、竞争法tournamentselection及等级轮盘法RankBasedWheelSelection）。不仅仅挑分数最高的的原因是这么做可能收敛到局部的最佳点，而非整体的。•改变该种群（交叉和变异）–直到停止循环的条件满足主要参数•种群规模(P,populationsize)：即种群中染色体个体的数目。•字串长度(l,stringlength)•交叉概率(pc,probabilityofperformingcrossover)：控制着交叉算子的使用频率。交叉操作可以加快收敛，使解达到最有希望的最优解区域，因此一般取较大的交叉概率，但交叉概率太高也可能导致过早收敛。•变异概率(pm,probabilityofmutation)：控制着变异算子的使用频率。•中止条件(terminationcriteria)应用•遗传计算、遗传编程、遗传学习•优化神经网络•数值优化、图像处理、仪器参数优化、工程设计，搜索，等蚁群算法（AntColonyOptimization，ACO）•是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值主要规则主要参数•最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。•错误概率：表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。•速度半径：表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。•记忆能力：表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。粒子群算法（ParticleSwarmOptimization，PSO）•PSO算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover)和“变异”(Mutation)操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。PSO的特点•实数编码•随机化•没有遗传操作如交叉(crossover)和变异(mutation).而是根据自己的速度来决定搜索。•粒子有记忆。PSO的应用•优化神经网络•连接权重，结构（拓扑结构，传递函数），学习算法•数值优化•图像处理、仪器参数优化、工程设计，搜索，等1.3智能技术的综合集成•模糊系统与神经网络结合•神经网络和遗传算法结合•模糊技术、神经网络和遗传算法综合集成•智能计算研究展望•神经网络与模糊系统和进化计算结合•神经网络与模糊及混沌三者结合•神经网络与近代信号处理方法小波、分形结合•专家系统与模糊逻辑、神经网络结合1.3.1模糊系统与神经网络结合1、各自优点：模糊技术以模糊逻辑为基础，抓住了人类思维中的模糊特点，以模仿人的模糊综合判断推理来处理常规方法难以解决的模糊信息处理难题。神经网络以生物神经网络为模拟基础，试图在模拟推理及自动学习等方面向前发展一步，使人工智能更接近人脑的自组织和并行处理等功能。2、互补性：将模糊技术引入神经网络可以使其处理不精确信息。3、相似点：都着眼于模拟人的思维；形式上有不少相似之处。1.3.2神经网络和遗传算法结合1、辅助式结合1）遗传算法对信息进行预处理，然后用神经网络求解问题；2）神经网络对信息进行预处理，然后用遗传算法求解问题。2、合作式结合1）利用遗传算法来优化神经网络连接权值；2）利用遗传算法来优化神经网络的结构。模糊技术、神经网络和遗传算法综合集成•模糊技术作为神经网络的隶属度函数•遗传算法可以优化模糊推理神经网络系统的参数•遗传算法可以优化模糊推理神经网络系统的结构•用神经网络调节和优化具有局部性的参数智能计算的展望•智能计算包括神经计算、模糊计算、进化计算三个主要方面，其积极意义在于促进了基于计算和物理符号结合的各种智能理论、模型，功能更强大，并能够实现更复杂系统的智能行为。•目前国际上智能计算研究正注意如下几个方面的结合：•1）神经网络与模糊