初中化学实验的一般步骤范文1
一、实验原型及不足
教材中已经设计了4个实验来论证紫色小花变红的原因。先喷醋酸，发现小花变红，然后将紫色小花放入二氧化碳的集气瓶中，发现小花不变红；再将喷水的小花放入放入二氧化碳的集气瓶中，发现小花变红。这样的实验操作虽然能使学生知道小花变红的原因，但无法使学生体会探究的一般过程和方法。
二、实验改进及优点
教师在教学时，可以适当改变实验顺序，重新设计，从实验探究的一般步骤入手来探究这个问题。可以按照以下步骤进行：
演示：将教材中的实验IV前提，即先将喷水后的小花立即放入二氧化碳中，观察现象，发现小花变红。或者按照下面的方法进行：将干燥的小花放入底部有少量水二氧的化碳的集气瓶中，发现小花很快变红。
根据这个情境，引导学生提出问题、进行猜想、设计并进行实验，经过对现象的分析，得出了小花变红的原因。
提出问题：什么物质使紫色小花变成红色？
猜想与假设：小花变红了，为什么呢？因为小花不外乎与水、二氧化碳接触，所以学生很自然能够猜想到以下几点：1.水使紫色石蕊变成红色；2.二氧化碳使紫色石蕊变成红色；3.二氧化碳和水反应生成的物质使紫色小花变成红色。
设计并进行实验：根据上述的猜想，学生很快可以设计以下三个实验进行论证自己的猜想：1.将干燥的小花放入水中；2.将干燥的小花放入二氧化碳中；3.将干燥的小花放入底部有少量水的二氧化碳的集气瓶中（已经演示）。其中实验1和实验2的小花均不变色。
解释或结论：由上面3个实验，学生能够得出结论：二氧化碳和水反应生成的物质使紫色石蕊变成红色。
那么，学生自然会继续追寻原因：二氧化碳和水反应生成了什么物质呢？此时，教师再演示教材的第一个实验即醋酸使紫色小花变红的实验，且补充说明酸能使紫色石蕊变红的性质。这样，学生很快明白了二氧化碳和水反应生成了一种酸，老师再进一步说明这种酸为碳酸。
初中化学实验的一般步骤范文2
关键词：初中化学 实验活动 评价
化学新课程标准指出：科学素养的全面发展是学生在“知识与技能”“过程与方法”和“情感态度与价值观”等三个方面都得到和谐发展。三个维度目标之间应有机结合，融为一体。化学实验活动的开展就是全面考察落实三维目标的重要手段，通过开展化学实验活动能使学生在知识与技能、过程与方法、情感态度与价值观方面达到全面发展，有效实现三维目标。
化学实验活动表现评价是指评价者（可以是化学教师、家长、学生自己或同伴） 依据学生在解决问题的活动中表现出的行为，对学生化学实验学习的过程与结果进行的一种客观、综合的评价。
一、开展化学实验活动表现评价的步骤
第一步：提出要探究的问题。初中化学中值得探究的问题很多，有根据教材内容安排进行的探究，有对教学内容的自然延伸进行探究，有根据教材内容与现实生活的联系进行的探究，也有对化学实验进行改进进行的探究等。因此选择的范围非常广泛，但要解决的问题需具有较强的现实意义。
第二步：制定实验活动表现性评价量表。不同的活动类型需要设计不同的评价标准。化学活动按活动过程分为限制性活动和扩展性活动。限制性活动通常有明确的任务描述，活动步骤固定，评价标准确定，活动一般集中在专门技能上，而扩展性活动一般集中在问题的解决，它要求学生在活动本身所提供信息的基础上，从不同的渠道寻找信息，涉及多种技能和能力，综合解决某个问题。这种活动往往具有一定的开放性，没有任务的细节描述，只是给出最终的目标，活动的步骤不固定，评价的标准有更大的机动性。
第三步：学生设计实验探究方案。学生根据教师提出的问题设计实验方案。由于初中化学是化学的启蒙间段，学生知识比较缺乏，独立设计实验方案有一定的困难，因此，教师应作一定的提示或进行必要的指导。
这一活动探究既考察了学生对催化剂概念的理解，又关注学生设计化学实验方案和化学实验操作（称量、过滤、干燥） 技能。不是单纯地进行实验技能评价，而是与具体的实验探究活动相结合，对学生在实验探究活动中的表现进行评价，从促进学生科学素养的全面发展，实现三维目标。
根据这一问题学生设计实验方案并进行实验验证自己设计的实验满足要求的情况，我做了如下评价量表的设计。
初中化学实验的一般步骤范文3
【关键词】K-means算法；初始聚类中心；入侵检测
1.引言
聚类分析是源于许多研究领域，包括数据挖掘，统计学，生物学，以及机器学习[1]。设想要求对一个数据对象的集合进行分析，但与分类不同的是，它要求划分的类是未知的。那么我们就需要聚类分析中的基于多种不同思想的聚类算法，主要有基于划分的算法、基于层次的算法、基于密度的算法、基于网络的算法和基于模型的算法等。这些算法都能取得不错的聚类效果，其中应用最多且算法逻辑思维比较简单的就是基于K-means算法。
1967年，J.B.MacQueen提出了K-means算法，是一种基于质心的经典聚类算法。K-means算法以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而簇间的相似度较低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。K-means算法的处理流程如下：首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。
2.K-means算法的改进
无论是原始K-means算法还是使用了聚类准则函数的K-means算法，他们有一个共同的特点：在算法的初始阶段都需要随机的选取k个点作为初始聚类中心点，然后在此基础上进行迭代。
2.1 k-means算法初值选取的现有方法
针对初值选取的问题，目前主要有以下几种选取方法[3][4]：
①任意的选取k个样本数据作为初始聚类中心。
②把全部混合样本直观地分成k类，计算各类均值作为初始聚类中心。
③依据经验选取有代表性的点作为初始聚类中心。
④通过“密度法”选择代表点作为初始聚类中心。
⑤由(k-1)类聚类问题解出k类问题的代表点。
⑥采用遗传算法或者免疫规划方法进行混合聚类。
⑦进行多次初值选择、聚类，找出一组最优的聚类结果。
⑧按最大最小距离聚类法中寻找聚类中心的方法确定初始聚类中心。
⑨聚类中心由原来的点延伸到一条线段，这种选取方法可以避免类间有干扰点的情况。
2.2 新的初始聚类中心选取方法
直观上，类中心应处于所代表类的中心部分，所有属于该类的样本都在其周围某一邻域内。因而在空间上，类中心所处的位置样本点分布密度较大。同时，在样本点密度连续的范围内，应该只具有一个聚类中心，否则就会出现两个类交错在一起的情况。因此，初始类中心的选择应该满足两个条件：
①类中心所处位置样本点密度较高；
②类中心之间的距离应尽可能地大。
因此，在初始点的选择上，应考虑两个因素：密度因素和聚类因素。由于类中心所处位置总是在样本比较密集的地方，因而总是存在某些样本距离类中心比较近。如果能够找到这些样本并作为初始类中心，就能避免k-means算法因为初始化不合理而出现的种种问题。
①样本点密度的度量
对于一个数据集，当样本呈团状分布时，根据一般常识，某个样本点周围其它样本点越多时，则该样本点处的样本分布密度就越大，则该样本点对于分类的影响就越大。因此，每个样本点都存在一个分布密度，对于每个样本点xi，其点密度函数定义如下：
2.1
其中zi是一个关于样本点间距离的参数，其定义如下：
2.2
2.3
Pi表示第i个样本点xi对分类影响的程度，Pi越大，样本点xi周围的点越多，样本点xi的密度越大；反之Pi越小，样本点xi周围的点越少，样本点xi的密度越小。
②选择样本点作为初始类中心
通过pi的值可以轻易地找到密度较高的样本点，但还要保证所选择的样本点之间的距离尽可能的大，否则选择的类中心必然会聚集在样本密度最高的区域内。因此，除了第一个类中心可以根据密度的大小来选择外，选择其它类中心时还需要考虑距离的因素。本文使用密度和距离的乘积作为选择的度量。密度和距离的单位不同，直接相乘不具有可比性，因此需要进行归一化处理。对于给定的样本xi，将其到样本点xj（=1，2，…，N）的距离按式2.4进行变换：
2.4
设已选定多个类中心，则在新增类中心时要考虑使它到已有类中心的总的距离较大，同时该样本点的密度也较大。总的来说，就是在剩余的样本中选取xi，使得该样本点的分布密度乘以该样本点到已选聚类中心的归一化距离和wi最大：
2.5
其中（n1，…，nk）是已确定k(k≥1)个初类中心在样本中的序号。
③聚类中心初始化算法执行流程
结合以上两个小节的讨论结果，得到一种新的聚类中心选取算法，算法流程描述如下：
输入：待处理数据集wi，聚类个数K
输出：初始中心点集M
步骤：
步骤1：根据式㈠计算每一个样本的密度；
步骤2：初始中心点集M初始化为空集，即M=｛｝，初始累加参数wi为0，即：wi=0，（i=1，2，…，N）；
步骤3：令j=1，选择密度最大的样本点m1（第v1个点）作为第一个初始中心点，即：
Pv1=Max（Pi），（i=1，2，…，N）；
M=M∪｛m1｝；
步骤4：按㈣式计算已选初始中心点mj到所有样本的归一化距离，累加wi：
wi=wi+Pi，（i=1，2，…，N）；
步骤5：令j=j+1，选择使得wi取得最大值时所对应的样本点mj（第vj个点）（已选作中心点的样本除外）为第j个初始中心点，即：
=max{wi|i=（1，2，…，N），i≠（v1，…vj-1）}，
M=M∪｛mj｝；
步骤6：重复步骤4、步骤5直至找到k个中心点；
步骤7：输出中心点集M，算法结束。
从上述算法可以看出，由于初始中心点集的第一点为确定的（最大密度点），在基于距离最远的其他中心点搜索过程中，得到的中心点也基本上是确定的，消除了初始中心点选择的随机性，同时保证了获得较高质量的初始中心点。
2.3 算法的改进
改进后的k-means算法中，首先根据样本的每个属性在聚类过程中所起的作用的程度不同，利用变异系数赋权法给每一个属性赋一个相应的权值。然后通过一种简洁快速的初始聚类中心选取规则，变随机为有目的地确定了k-means算法的初始聚类中心，消除了初始中心点选择的随机性，同时保证了获得较高质量的初始中心点，解决了k-means算法对初始值敏感、易陷入局部最优的问题。改进的算法描述如下：
输入：待处理数据集，聚类个数K
输出：聚类结果
步骤1：对数据集执行加权处理程序，得到新的数据集；
步骤2：对加权后的数据集执行聚类中心初始化程序，得到K个初始聚类中心；
步骤3：调用跳过随机选取聚类中心的k-means算法进行聚类；
步骤4：输出聚类结果，算法终止。
3.实验设计与研究分析
入侵检测以探测入侵为中心，目的是为系统提供实时发现入侵行为并及时采取相应的防护手段。本章将介绍一种基于聚类的入侵检测系统模型以及数据预处理方法，并在入侵检测经典数据集KDD Cup 1999[5]上进行一系列的实验。
3.1 基于聚类的入侵检测系统模型
入侵检测分为两个阶段：训练阶段和检测阶段：
①训练阶段：输入训练数据，系统自动生成聚类，同时对这些聚类进行标类。
②检测阶段：收集到新的记录后进行标准化处理，计算标准化后的数据到各个
聚类中心的距离，取距离最近的聚类，若该聚类标记为正常类，则该数据为正常数据，否则则认为该数据为异常数据。
以下将介绍一种基于聚类分析的入侵检测系统模型，模型图如图1所示。
它由四个模块组成：数据预处理模块、聚类分析模块、标类模块、检测模块。各个模块的功能如下：
①网络数据收集
网络数据收集是入侵检测的基础，该模块主要是从网络上提取数据进行监视和检测，例如链路层的数据帧、通过网络层的IP包等。本文采用KDD Cup 1999数据集做实验。
②数据预处理模块
在数据预处理模块，主要是把收集到的网络数据进行标准化，转化为适合聚类算法运算的数据格式，同时对数据进行过滤、除噪等操作。
③聚类分析模块
数据经过预处理后，聚类分析模块利用聚类算法对这些数据（一般是连接记录）进行聚类和分类，区分哪些是正常连接记录，哪些是异常连接记录。本文采用第四章中介绍的改进k-means算法进行聚类分析。
④标类模块
数据经过聚类分析模块后，产生若干个簇，每个簇都包含一些连接记录；由于正常连接记录和异常连接记录的特性不同，不具有相似性，因此会被放入不同的簇中。这样就可以进行标记类（簇）的操作。那些包含较多数据的类是正常类，而包含较少数据类则是异常类。
⑤检测模块
在完成对聚类结果的标识后，我们就可以利用标类结果对新来数据进行检测，在不断完善和更新聚类结果的同时快速有效地检测各种入侵行为。计算标准化后的数据到各个聚类中心的距离，选取距离最近的聚类，若该聚类标记为正常类，则判定该数据为正常数据，否则认为该数据为异常数据。
3.2 实验结果与分析
在实验中，选用实验平台Win-
dowsXP，Matlab6.5语言编程环境，Intel Pentium3GHz CPU，1GB内存。评价入侵检测算法时采用两个性能指标其定义如下所示：
3.2
3.3
这两项性能指标充分反映了入侵检测系统的检测能力，能够对系统检测出多少入侵和做出多少不正确的分类做出评价。显然一个好的入侵检测系统应该使DR尽可能得大，而FR则尽可能的小。
在KDD Cup 1999训练数据集中的攻击数据有接近40万条，约占总数的80%，由于无监督入侵检测算法对于数据集中的入侵记录所占的比率十分敏感，如果入侵记录的数量太大，入侵在表现形式上就不会被看做入侵，所以必须首先对数据集进行过滤，选择合适的数据，然后才能进行实验，在现实中，入侵记录所占所有记录的比例在1%到1.5%之间。
试验中聚类数K的变化自由度比较大，具体取值和领域知识强相关，不同应用领域取不同的值才能得到理想的效果，因此不能直观的给出，只能通过实验进行估计。以下将进行K取值估计，改进k-means算法和传统k-means算法性能比较实验。
为了满足实验需要，我们从kdd-
cup.data_10_percent包选取了5个数据集作实验，其中一组训练数据集和四组测试数据集，训练数据集包含30300条数据，其中300条入侵数据，包含了DOS、PROBING、R2L、U2R所有四种类型的入侵数据类型。测试数据集包含10100条数据，100条入侵数据。
为了操作方便，在实验过程中我们只选取数据中的15关键属性进行聚类，其中12个连续属性，3个离散属性。利用以上数据集分别在传统k-means算法和本文改进k-means算法上进行实验，首先使用训练数据进行训练标类，然后依次输入其他四个测试数据集进行测试，对四次测试结果取平均，结果如表1所示。
由表3可知，改进k-means算法的检测率和误检率明显优于传统k-
means算法，同时随着聚类个数的增加，检测率和误检率也随之增大。因为当聚类数目很少时，系统训练之后的异常类也就很少，很多异常的记录被分到了正常的类中，而正常记录很少被分到异常的类中，这就导致系统对异常记录的低检测率，同时也获得了对正常记录的低误检率。而当聚类数增多时，系统训练之后的异常类也随之增多。此时，越来越多的异常记录被标记出来，但同时越来越多的正常记录也被分到了异常类中，系统获得高检测率的同时也不得不忍受高误检率的结果。
前面做了混合入侵类型的实验，系统在聚类数取25左右时获得了最佳检测结果，下面对指定攻击类型单独进行实验。选取8个是测试数据集，每个测试数据集包含5000条数据；而且训练数据集分别只包含50条DOS、U2R、R2L、PROBING入侵攻击数据。
聚类数取25，已知入侵指的是在测试集和训练集中都包含的入侵，未知入侵指的是测试集包含但训练集中没有的入侵。实验结果如表2所示。
由表2和表3可知，无论是已知的单一入侵类型还是未知的单一入侵类型，基于改进k-means算法的入侵检测效果都明显优于基于传统k-means算法的入侵检测效果，而且在对DOS、PROBING入侵攻击的检测都取得了比较高的检测率，但是对U2R和R2L入侵类型的检测效果不理想。出现这种结果的原因一方面是因为数据集中U2R和R2L入侵记录少，在训练时，对这两种类型的处理不太理想，导致后期的检测效果不理想，另一方面是因为U2R和R2L入侵一般通过伪装成合法用户身份进行入侵攻击，使得其表现出来的特征与正常网络数据包非常相似，造成较低的检测率。
在误检率方面，改进算法对单一攻击类型的检测优势。值得注意的是R2L攻击类型的误检率普遍较高。这是因为在训练时，很多R2L入侵记录都混进了正常聚类，而不少正常记录难免就被分到了异常聚类，致使检测阶段时很多正常记录被判定为异常。
在实际环境中，大多数入侵攻击类型都是DOS和PROBING。无论是已知入侵类型还是未知入侵类型，本文算法都取得了良好的检测效果。而对于实际环境中少见的R2L和U2R，本文算法也有检测能力。说明本文入侵检测能够比较有效的检测入侵行为。通过以上分析，基于本文改进的k-means算法应用于异常入侵检测中是可行而且有效的。
4.结论
本文详细介绍了k-means算法的思想原理、流程步骤，针对该算法的初值依赖性提出改进的聚类中心选取算法，获得较高质量的确定的初始聚类中心，消除了经典k-means初始中心选择的随机性，解决了该
（下转第18页）
（上接第14页）
算法对初始值敏感、易陷入局部最优的问题。阐述了基于聚类的入侵检测模型，并在此模型的基础上使用入侵检测数据集KDD Cup 1999对改进k-means算法和经典k-means算法作了对比仿真实验。实验结果表明：不管对存在单种攻击的网络连接记录集还是多种攻击同时存在的网络连接记录集，基于改进k-means算法的入侵检测系统都能够在保持较低的误报率的基础上，很好的检测出记录集中的攻击数据，包括未知类型的攻击数据。本文改进的k-means算法是一种有效的无监督入侵检测方法，根据此方法设计的入侵检测系统是有效可行的。
参考文献
[1]Jiawei Han,Micheline Kamber.数据挖掘概念与技术[M].北京：机械工业出版社,2001.8.
[2]MacQueen J.Some Methods for Classification and Analysis of Multivariate Observations[C].In:Proceedings of the 5thBerkeley Symposium on Mathematical Statistics and Probability.Berkeley,University of California Press,1967:281-297.
[3]U.M.Fayyad,C.Reina and P.S.Bradley.Initialization of iterative refinement clustering algorithms[A].In:Knowledge Discovery and Data Mining.1998:194-198.
[4]R.O.Duda,P.E.Hart.Pattern Classification and Scene Analysis[M].New York.John Wiley and Sons.1973.
[5]/kddcup/index.php.
作者简介：
薛京花（1984—），女，湖南益阳人，硕士研究生，现就读于中南林业科技大学计算机与信息工程学院，研究方向：网络与信息系统。
初中化学实验的一般步骤范文4
一、认真预习实验内容
实验前，要认真复习有关的实验原理和实验内容，明确实验目的，了解实验程序和操作方法。通过预习，应当对实验内容胸有成竹，以免盲目地“照方抓药”。要牢记实验装置与操作要点，对每个实验都要做到心中有数。还要熟悉实验内容及操作步骤，一个实验有几个步骤；验证和证明了物质的哪些化学性质，实验现象是什么，应在预习中根据已经学过的知识做好准备，以免实验时手忙脚乱。实验课上，实验教师一般要结合实验内容，对实验操作要点，实验中容易出现的问题，以及可能出现的意外事故和处理方法等，都要进行详细的讲解。因此，也应认真“听”，用心“记”，照着“做”。只有做到必要的预习，明确实验目的、原理、要求、方法、步骤和注意事项，在实验中，才能得心应手，顺利完成。
二、熟练基本操作
初中化学实验基本操作的主要内容有：试剂的取用、称量、溶解、搅拌、加热、过滤、蒸发、结晶、常用仪器的使用和气体发生器气密性的检查等。这些基本操作是进行各类化学实验的基础，是化学实验的“基本功”。要熟练基本功，既要仔细“看”，注意老师的示范操作，领会要领；又要认真“练”，结合具体实验训练操作，逐步形成实验技能。实验能力的形成是练会的，而不是看会和说会的。
三、严格操作规程
在实验时，必须严格按操作规程进行，不得凭兴趣，想当然，更不准违反实验操作规程。如：用排气法收集氧气，停止实验时，要先撤导气管然后撤酒精灯。点燃可燃性气体，要先做纯度检验。给试管里的液体加热时，切不可让试管口朝着自己和有人的方向等。不严格按照操作规程进行实验，则可能导致实验失败，甚至会发生事故，造成伤害后果。
四、细心观察、记录、分析实验
实验中，要细心观察实验现象，认真做好记录，仔细分析实验现象产生的原因。做实验时，要全神贯注，不但要动手，而且要动眼、动脑，注意观察实验中发生的现象。如：物质的状态；颜色、气味、溶解性等有无变化，是否有气体、沉淀生成等。如实记录实验现象，并按要求填写好实验报告，做好实验作业。
五、尊重实验事实
初中化学实验的一般步骤范文5
第一重境界：“入诗”
“入诗”就是让学生初步走近作者、走进文本。这需要完成前面的三个步骤：诵读感知、知人论世和文本解读。
步骤一：诵读感知
“诵读感知”就是先由老师范读或学生根据课本注释初步阅读文本，了解文本的基本内容。在本人的教学过程中，一般要求学生读准字音，查阅不理解的词语和典故的意思，然后找出诗歌中描写的主要意象。在此基础上自由朗读几遍。
步骤二：知人论世
“知人论世”就是介绍作者概况及和文本密切相关的文史知识、写作背景。现在的资料十分丰富，选择和甄别十分重要。资料介绍要力求贴近史实，从作者生活的大背景和大多数诗作中去感受作者的情怀，而不能“抓住一点，不及其余”，更不能在一首诗中顾头不顾尾地无限放大某个方面。要介绍作者生活的历史背景和诗作的创作背景。学生没有条件查找资料，需要老师进行筛选甄别后提供给学生参考。背景资料选择得好对学生理解古诗歌具有十分重要的意义。
步骤三：文本解读
“文本解读”就是引导学生理解诗歌的基本内容、初步感受作者的情怀。很多老师对古诗歌的文本解读或浮光掠影、蜻蜓点水，沉不下去，深入不了；或细微艰涩、旁征博引，贪多求全，找不到切入点。还有老师把古诗歌当古文来教，逐字解释、逐句翻译，弄得支离破碎，毫无美感，让一首韵味十足的古诗变得味同嚼蜡。因此，笔者认为，古诗歌的文本解读一定要贴近学生――要根据不同年级学生的知识文化积累提出不同的目标要求。对七年级的学生而言，他们只在小学的时候背诵过少量简易的古诗，对古诗的认知停留在浅层面上，因此文本解读的重点应该放在了解古代文化知识上，在老师的引导下初步感受炼字、修辞、诗歌的意境和作者的思想感情方面的内容。到了八年级，有了一定的积累，要多让学生自己体验古诗的语言美（如节奏、语调、修辞等），要开始引导学生通过想象体验逐步学会由“入诗”到“入境”、“入情”，感知作者的内心感受和作品的内涵。九年级，随着学生古代文化知识的积累和生活阅历的增加，古诗积累也逐步丰富起来，因此要在前面的基础上给学生适当增加古代文化素养的滋润，逐步学会通过古诗描绘的意境和作者进行心灵的沟通，逐步走进作者的内心世界，提高对古诗的欣赏品味和审美情趣，初步感受古诗歌的艺术表现力，为高中阶段进行古诗歌鉴赏打下较好的基础。
第二重境界：“入境”
“入境”就是通过对诗歌中的意象的联想想象再现诗中情景，让学生有“设身处地”之感。
步骤四：想象体验
在这个过程中，联想想象是十分重要的“入境”手段。在本人的教学实践中，经常使用联想想象的方式让学生把诗中的意象切分成若干个画面，再把若干个画面连接起来组成一个有变化的情节。这样，学生就有了一个具体可感的感知空间。
第三重境界：“入情”
“入情”是指了解作者的内心世界，和作者进行精神沟通。这需要做好两个准备。一是文本解读一定要到位，二是“入境”一定要到位。要引导学生通过对文本中重要词语和典故的理解，关键句子的把握来探究作者内心的丰富情感，这就在“入境”的基础上“入情”了。“入情”的过程是在想象的基础上深入体验的过程，这不是每个学生都可以达到的境界，但是能让少数学生体验与古人的心灵交流那也是一件功德无量的事情。
初中化学实验的一般步骤范文6
关键词：三维点集；凸包；极值点
中图分类号：TP212.12；O241.82
文献标志码：A
Improved algorithm on determining convex hull of 3D point set
ZHANG Fei，XIE Buying，YAN Xingyu，LIU Zheng
(College of Civil Eng.，Tongji Univ.，Shanghai 200092，China)
Abstract：To improve the computation efficiency of convex hull of 3D point set，an improved algorithm on determining convex hull of 3D point set is proposed by making full use of the extreme points and the character of the convex hull. Firstly，the extreme points in 3D point set are obtained to make up of the initial convex hull. Secondly，the internal points of the convex hull are eliminated according to the position relationship between the initial convex hull and the points. Finally，the external points are examined in turn，the point set，line set and face set that meet the requirements are acquired，and the convex hull is expanded to obtain the final point set，line set and face set of the convex hull. The comparison of time complexity analysis with normal algorithms and the experiments indicate that the algorithm has higher efficiency.
Key words：3D point set；convex hull；extreme point
0 引 言
点集凸包问题是计算几何学中基本、常见的问题，通常可以分为二维凸包和三维凸包.[1]二维凸包被广泛应用于模式识别、图像处理和设计自动化等领域[2]；三维凸包被广泛应用于计算机仿真、建筑体建模、卫星通信和无线电广播等领域[3].二维凸包算法相对比较简单、成熟，已有很多研究成果.随着计算机软件和硬件技术的发展，处理三维的问题越来越多，有必要进一步研究三维凸包算法.本文在现有二维和三维凸包算法的基础上，提出1种改进的三维点集凸包求取算法.
自20世纪70年代以来，不少学者提出有关点集凸包的算法，较为经典的有卷包裹法、格雷厄姆法、分治法、增量法以及周培德在文献[1]中提出的Z3―1和Z3―2算法.在这些算法中，卷包裹法、分治法、增量法以及Z3―2算法能够推广到三维.同样，也有很多二维算法不能推广到三维，比如格雷厄姆法和文献[4]提出的算法.
在绝大多数情况下，二维凸包和三维凸包由点集中的部分点构成，其余点则在凸包内部.所以，点集中的点可分为凸包顶点和内部点，因而可以考虑利用一些特殊点(如极值点)先构成凸包大体形状，再排除内部点中的部分点，以减少点的数目来提高算法效率，这就是快速凸包技术[5].这种思想显然也适用于三维点集凸包算法.
在快速凸包技术的基础上，本文给出1种改进的凸包求取算法.与传统快速凸包算法相比，本文算法考虑采用更多的极值点，更充分地利用极值点性质，缩小点的搜索范围，提高算法效率.
1 定义及性质
定义1 凸包.即凸包多面体，把多面体的任何1个面无限延展，其他面都在这个延伸面的同一侧.[1，6]文中的点集凸包是指包含点集中所有点的最小凸多面体.凸包的面均由三角形组成，即使真实的面由多边形组成，这些多边形也均被分割成三角形.
定义2 一维极值点.在三维点集中，若只考虑点的3个坐标中的1个坐标并求取其最大值或最小值，所求得的这些点称为一维极值点.如果最大极值点和最小极值点都不止1个，则所有最大极值点在同一平面，所有最小极值点也在同一平面内.
定义3 二维极值点.在三维点集中，如果把所有点都投影到1个坐标平面上(如xOy平面，yOz平面，zOx平面)，然后在平面上求取极值点，称这些点为二维极值点.现以投影到xOy平面为例定义二维极值点.在平面点集中，分别称具有最小和最大x坐标值的点构成的子集为Xmin子集和Xmax子集；分别称具有最小和最大y坐标值的点构成的子集为Ymin子集和Ymax子集.在Xmin子集中，称对应y坐标的最小的点为左下点，称对应y坐标最大的点为左上点；在Xmax子集中，称对应y坐标的最小的点为右下点，称对应x坐标最大的点为右上点；在Ymin子集中，称对应x坐标最小的点为下左点，称对应x坐标最大的点为下右点；在Ymax子集中，称对应x坐标的最小的点为上左点，称对应x坐标最大的点为上右点.
定义4 极值点.包括一维极值点和二维极值点.在现实情况下，某点可能既是一维极值点也是二维极值点.在算法应用的过程中并不严格区分.
性质1 空间中给定的若干个点的凸包是唯一的，且凸包的顶点必须是原给定点集中的点.[3]
性质2 极值点必为凸包的顶点中的点.
性质3 在三维点集中，必存在一维极值点，且至少有1个.如果只有1个一维极值点，则凸包为平面，这种情况将不形成凸包.所以，构成凸包的点集中，至少有2个一维极值点.
性质4 在三维点集中，必存在二维极值点，且至少有2个.当且仅当为2个极值点时，在投影平面内查找离由这2个点构成的直线最远的点作为极值点.如果不存在，则点集不构成凸包.这样，至少有3个极值点，最多8个极值点存在.即三维点集中，二维极值点可以构成1个平面或者空间凸环.文献[4]中给出的在二维情况下的证明，也适用于三维点集中二维极值点的情况.
推论 由性质3和性质4，在三维点集中，只要存在凸包，即所有点都不在同一平面上，由极值点可以构成1个初步凸包.
2 算法思路描述
求取三维点集的凸包，一般要求求出凸包的顶点集、棱边集以及面集.当然，在3个集合中，顶点集和面集是必需的，棱边集可以由面集直接推出.
算法的总体思路是：通过依次考察点集中的点，找出极值点，利用极值点快速形成初步凸包.初步凸包把原点集中的点分为初步凸包上点、外部点和内部点3个部分.外部点可能在凸包上，而内部点一定不在凸包上.算法的第2步则是删除内部点.第3步依次进行考察外部点，不断扩展初步凸包，最终形成所要得到的凸包.在扩展初步凸包的过程中，将待考察的点依次与上一步扩展凸包中的棱边构成面，并用极值点和上一步扩展凸包中的顶点集中的点判断该面是否应加入新的扩展凸包中，这样就可以找到所有应加入新扩展凸包中的面.再利用该待加入点和极值点验证原扩展凸包中的面，排除不满足新扩展凸包的所有的点、棱边和面.当考察完毕所有外部点时就可以得到最终所要求得凸包的点集、棱边集和面集.
2.1 算法主体流程
算法主体流程见图1.
图 1 算法主体流程
2.2 算法具体步骤
步骤1 求极值点并形成初步凸包，分为4个小步骤进行.
(1)依次考察点集中点的z坐标，分别求出1个最大和1个最小的一维极值点，并把点号保存在极值点集链表utdot中.
(2)依次考察点集中点的x坐标和y坐标，按照左下点、下左点、下右点、右下点、右上点、上右点、上左点和左上点的顺序依次求出所有存在的二维极值点，并将点号保存到极值点集链表utdot中.
(3)按照求取二维极值点的顺序，依次连接各点构成1个空间环；然后将z轴方向上的极值点分别与环中的点连接，构成基于三角形初步凸包.
(4)在步骤1的第(3)步中，把依次连接的边保存到棱边集链表llist中，把依次连接3点构成的面保存到面集链表alist中.同时，初始化顶点集链表endplist后，继续下一步.
步骤2 删除初步凸包内部点，又分为2个小步骤进行.
(1)依次考察点集中的点，从该点出发引1条平行于x轴的射线，如果该射线与初步凸包的面不相交或有2个交点，则该点在初步凸包的外部；如果只有1个交点，则该点在初步凸包的内部.如果与初步凸包的棱边、面或顶点相交，则改平行于y轴或z轴的射线，然后再按照前面的方法判定.如果3个方向的射线均与初步凸包的顶点或棱边相交，则该点在初步凸包的内部.[1]
(2)在步骤2的第(1)步中，把初步凸包外部点的点号保存到点集链表plist中.继续下一步.
步骤3 从点集链表plist中依次取出点pp，如果链表plist中点都取完，则执行步骤5，否则继续下一步.
步骤4 共有10个小步骤.依次从棱边集链表llist中取出棱边lp，如果链表llist中的棱边都取完，则执行步骤4中第(5)步，否则继续步骤4中第(1)步.
(1)由步骤3中的点pp和步骤4中的棱边lp构成1个面，依次用极值点集utdot中的点来判断该面的性质.如果所有极值点都在该面的同一侧，则继续下一步，否则退出本轮循环，执行步骤4.
(2)从顶点集链表endplist中依次取出点来判断该面的性质，如果所有点都在该面的同一侧，则继续下一步，否则退出本轮循环，执行步骤4.
(3)把步骤4的第(1)和(2)步中满足要求的面加入到面集链表alisttemp中，与该面相应的两条棱边加入到棱边集链表llisttemp中.
(4)继续步骤4.
(5)若alisttemp为空，执行步骤4中第(10)步，否则执行下一步.
(6)依次从扩展凸包面集alist中取出面a，用点pp和极值点集utdot中不为该面顶点的1点putdot进行判断，如果点pp和点putdot在面a的异侧，则把该面从alist中删除，并且加入到待删除面集链表alistdle中，否则不作任何处理，继续步骤4中第(6)步.当alist中的面都取完时，把alisttemp添加到alist中，执行下一步.
(7)依次考察面集alistdle中的面，如果有3个或者以上的面相交1点，则把该点加入到待处理点集链表plistdle中，否则继续步骤4中第(7)步.当面集alistdle中所有点面都考察完毕时，执行下一步.
(8)依次考察点集plistdle中的点，如果该点在面集alist的顶点中不存在，则从顶点集endplist中删除该点，否则不作任何处理.当plistdle中所有的点都考察完毕时，把点pp添加到endplist中，执行下一步.
(9)依次考察面集alistdle中的面，如果有2个面相交于1条棱边，则从棱边集llist中删除该棱边.当alistdle中的面全部考察完毕时，把llisttemp添加到llist中，执行下一步.
(10)继续步骤3.
步骤5 把极值点集链表utdot合并到链表plist中.最终凸包的点集为链表plist，棱边集为链表llist，面集为链表alist.算法完成.
2.3 算法改进方法
上述算法利用z轴方向的2个一维极值点和xy平面上最多8个二维极值点形成初步凸包.根据定义3，x，y和z轴方向的一维极值点均分别在2个平面上.根据极值点的性质，所有一维极值点均为凸包顶点.所以改进的方法是：求出所有一维极值点并由其构成1个新初步凸包，这个新初步凸包大于等于上述算法中的初步凸包.新凸包可以排除更多的内部点，从而减少步骤3和4中的判断次数，提高算法效率.
2.4 时间复杂度分析
文献[7]证明凸包算法的时间复杂度下限为o(n logn)，该结论也适用于三维凸包算法[1].常见的三维凸包算法中，卷包裹法和文献[1]中Z3―8算法的时间复杂度为o(n2)[1，6]；分治法和增量法为o(n log n)[1].经典的普通算法是利用定义1的性质，通过3点构成的面，然后用点集中的点是否都在该面同一侧的方法来判断该面是否为凸包的面.当考察完毕点集中任意3点所构成的面时，就可以得到凸包的所有面，进而求出凸包.其算法的复杂度为o(n3).
本文算法的时间复杂度分析如下：步骤1中，查找极值点耗时o(n)；步骤2中，删除内部点的复杂度为o(n)；步骤3和4构成1个用外部点扩展初步凸包的循环.外部点的数目与点集的数目相关，故循环外部的复杂度为o(n).循环内部中步骤4的第(1)～(4)步求顶点与棱边构成的面，并用扩展凸包顶点集中的点判断面的性质，其复杂度与扩展凸包中点的数目和棱边的数目相关.由于扩展凸包中点的数目相对于点集中点的数目和棱边的数目非常少，也可以认为是常数.所以，一般情况下其计算的复杂度为o(1).由性质和推理知，极值点可以构成初步凸包，进而可以排除内部点.所以，即使在最坏情况下，其时间复杂度也不会达到o(n)，可以认为其时间复杂度接近o(log n).步骤4的第(5)～(10)步的时间复杂度为o(1)，所以步骤3和4的最坏时间复杂度接近o(n log n).步骤5耗时可以忽略不计.所以，整个算法的最坏时间复杂度接近于o(n log n)，即接近于时间复杂度的下限.
3 实验分析
实验所用计算机的CPU为AMD 2500+，内存为512 MB.在VC++6.0中的MFC编程环境中，分别实现普通算法和改进算法.图2给出点集中点的数目为500个时的三维凸包计算结果.分别对普通算法和改进算法求三维点集凸包进行程序实验.对不同容量(小于104)的点集分别进行100次实验，然后求出平均消耗的时间列于表1和图3.同时，表1对普通算法和改进算法平均消耗时间的比值进行计算.图3中横轴表示点集中的数目，纵轴表示计算点集凸包运行所需要的平均消耗时间.
图 2 500个点的凸包计算结果
图 3 实验比较
从表1和图3可见，随着点集容量的增大，改进算法的优势越发明显.普通算法与改进算法的消耗时间比随着点集容量的增大而增大.在第2.4节中普通算法和改进算法的时间复杂度分别为o(n3)和o(n log n)，它们之间的比值为o(n2/log n)，与表1中的比值相符合，从而证明理论分析与实验分析一致.
4 结 论
从改进算法与普通算法的比较中可见，对于求102数量级的三维点集凸包，普通方法也能提供比较满意的求取时间，但当点集容量达到103时，普通算法就不能满足要求.改进算法可以快速求取大量三维点集的凸包，不仅在时间上取得较大突破，而且充分利用极值点在凸包上以及凸包的性质，为算法优化提供新的思路.
另外，改进算法效率高的原因还在于：(1)充分利用极值点，形成最大可能的初步凸包，排除初步凸包内部点，减少点的判断次数；(2)在判断面的性质中，优先用极值点进行判断，利用极值点的性质，可以很快得出该面的性质，减少判断的工作量；(3)在求取过程中，每次向扩展凸包中添加1个点，都构成1个新的扩展凸包，充分利用上一步中求取的成果，大大减少后面的计算工作量.
参考文献：
[1] 周培德. 计算几何――算法分析与设计[M]. 2版. 北京：清华大学出版社，2005：100-135.
[2] ROURKE O J. Computational geometry in C[M]. 2nd ed. Cambridge：Cambridge Univ Press，1998：73-78.
[3] 夏松，朱宜萱，杜志强. 一种新的空间凸多面体的生成算法[J]. 测绘通报，2006(1)：21-23.
[4] 余翔宇，孙洪，余志雄. 改进的二维点集凸包快速求取方法[J]. 武汉理工大学学报，2005，27(10)：81-83.
[5] 蒋红斐. 平面点集凸包快速构建算法的研究[J]. 计算机工程与应用，2002，38(20)：48-49.
