【《热点剪辑聚类技术概述》3000字】

热点剪辑聚类技术概述目录TOC\o"1-3"\h\u3536热点剪辑聚类技术概述 1222041.1.1使用机器学习方法的热点剪辑聚类技术 12221.1.2使用传统方法的热点剪辑聚类技术 3随着晶体管特征尺寸的缩小以及电路版图设计的日益复杂，热点问题日益成为了光刻工艺中一个不小的挑战。为了迎合工业界提出的修复方法，降低修复成本，热点剪辑聚类技术便应运而生了。热点剪辑聚类技术可以显著地减少制定修复策略的工作量，将大量的热点图像转化为少数几种特定模型，可以更加简洁地将有问题的热点图像聚类成组并用成熟的方法进行修复。在热点聚类成为可制造性流程设计基础的今天，热点剪辑聚类技术已发展出了多种方法。使用机器学习方法的热点剪辑聚类技术基于支持向量机的热点剪辑聚类算法支持向量机（SupportVectorMachine）是统计学领域中按监督学习的方法对数据进行二元分类的广义线分类器，其被CorinnaCortes等人[46]首次提出用于计算机机器学习中的手写字符识别问题。在此之后，支持向量机技术从统计学变成了机器学习中最为经典的算法之一。支持向量机的使用实例如图2.5所示，其非常善于在具有线性可分性的二维平面中找出最优的决策边界，形成更具鲁棒性的超平面。在不具有线性可分性的数据分类中，同样也可以通过设计损失函数的方法从而获得相对最优的最大间隔超平面。随着算法的发展，支持向量机算法不仅可以分类二维平面的数据，同样也可以扩展到三维空间进行数据分类。图STYLEREF1\s2.SEQ图\*ARABIC\s15支持向量机算法实例DuoDing等人[47]首次提出使用支持向量机方法设计热点剪辑聚类算法，并首次提出了一个分层细化的机器学习框架用于高性能热点检测流，提供完整的布局，以特征为中心的分析，而不会在运行时或通过滑动窗口或光栅扫描相关技术的覆盖范围受到惩罚。在这种分层细化的数据挖掘框架下，他们以一种基于片段的方式定义了新的分类特征度量。但显而易见的是，基于支持向量机方法的热点剪辑聚类算法具有迭代收敛慢、运行时间长、损失函数设计难度大、以及不具有明显线性可分性时分类效果差等缺陷。基于K-means的热点剪辑聚类算法K-means算法是聚类算法界的新锐，它近年来一跃成为最为常用的聚类算法之一。该算法是一种基于欧式距离并使用机器学习方法的聚类算法，其设计的核心理念是基于在同一个图中，两个元素的距离越近，其相似度就越高。作为一种无监督机器学习的聚类算法，K-means算法具有实现简单、聚类效果优秀等特点，因此近些年在聚类领域使用范围非常广泛，也衍生出了诸多分支算法如KernelK-means等等。在具体实现过程中，K-means算法会将给定的样本集按照其之间的相似程度定义为其相互之间的距离，并初始化K个点设为簇的质心，随后开始一步步的距离计算迭代，迭代过程中，会尽可能地去找能让簇内元素稠密的质心，同时让不同质心之间的距离尽可能大。如图2.6是K-means算法分类的一个实例，我们将K设置为3，则会生成红、绿、蓝三种颜色的质心，随后，再分别求所有样本到这3个质心的距离，并记录每个样本最邻近的质心。接着，一步步根据3种颜色的点互相的距离进行迭代计算质心新的位置，直至所有点的类别标记为距离最近的质心为止。图STYLEREF1\s2.SEQ图\*ARABIC\s16K-means算法实例NingMa[24]等人提出使用K-means方法进行热点剪辑聚类算法的设计。基于预先定义的聚类计数k，它首先随机选择k个聚类代表，然后将每个片段重新分配给一个类似的聚类代表，直到收敛产生热点剪辑聚类。其具有设计简单、收敛速度快、聚类效果好等特性，但其缺陷在于k值不好把控，需要多次迭代以尝试最适合聚类k值；其对噪音和异常点也比较敏感，对于不太好分的数据集难以收敛；并且，初始点的选择还会极大影响聚类结果，聚类中也非常容易陷入一种局部最优的状态从而无法达到全局最优。使用传统方法的热点剪辑聚类技术基于马尔可夫聚类的热点剪辑聚类算法马尔可夫聚类算法（TheMarkovClusterAlgorithm）是一种图算法，它的基本思想是：假设在一个元素稀疏分布的图G中，如果存在某个区域A，其中的元素聚合得较为紧密，那么在A中随机游走k步后仍然留在A区域中的概率就会很大。在算法中通常被定义为A内的k步路径（k-lengthpath）很多。换言之，如果在图中的某一区域内随机游走k步后仍然停留在该区域的概率很大，那么说明该区域内元素相互连通的概率同样很大，则该区域应被视为一个聚类。W.-C.Chang[26]等人提出一种基于马尔可夫聚类的方法，具体做法是先构建基于马尔可夫链的剪辑之间的相似关系图，然后再逐步迭代收敛，最后得到剪辑的自然分组结构。聚类过程如图2.7所示，图（a）是所有热点剪辑按照互相的相似程度进行连线产生的自然聚类关系示意，经由图（b）的马尔科夫随机游走过程逐步迭代收敛，最后得到图（c）的自然分组结构。图STYLEREF1\s2.SEQ图\*ARABIC\s17马尔可夫聚类算法的迭代过程在得到最终的热点剪辑自然分组结构后，该方法还会进行可行性修复。如图2.8所示，图（a）是代表剪辑之间相似程度的图，图（b）是马尔可夫收敛结果，但剪辑6与26的连接并不合理。经由可行性修复后，最终得到图（c）的聚类结果。图STYLEREF1\s2.SEQ图\*ARABIC\s18马尔可夫聚类算法的可行性修复基于马尔可夫聚类的热点剪辑聚类算法具有收敛快、聚类效果不错等优点，但其缺陷在于其收敛结果不能直接用于聚类结果，仍需要设计合理性分析与修复，即聚类结果不精确。除此之外，整个流程的运行速度也不出彩，而且聚类结果也不是最优的。基于整数规划的热点剪辑聚类算法整数规划（IntegerProgramming）问题描述的是要求一部分或全部决策变量取整数值的规划问题。R.R.Takkala[27]等人提出一种基于整数规划的热点剪辑聚类算法，其算法流程图如图2.9所示。图STYLEREF1\s2.SEQ图\*ARABIC\s19基于整数规划的热点剪辑聚类算法流程图在第一步预处理过程中，先提取了版图数据，将标记、剪辑以及版图多边形信息存放进内存中；随后第二步的距离计算中，通过旋转、翻转从而提取完全一样的热点剪辑，然后进行简化的成对距离计算，得到所有热点剪辑之间的相互距离；第三步聚类中，根据距离使用整数线性规划对所有热点剪辑进行聚类，然后再一一对剪辑形成代表性剪辑。该方法使用了整数线性规划并设计出一整套公式来解决聚类问题，同时也创造性地提出了一套能够生成代表性剪辑的方法，但其缺陷也很明显：时间开销太大，运行时间太长，使用ICCAD2016的基准测试集进行测试时，最大的测试样例运行时间达到100秒以上，远超所有同类型的论文结果，且得到的聚类结果也并不是最优的。基于贪婪随机自适应搜索的热点剪辑聚类算法贪婪随机自适应搜索（GreedyRandomizedAdaptiveSearch）算法被TAFeo和MGCResende[48]等人首次提出，是近几年提出的一种新兴且高效的算法框架。该算法善于解决NP难问题，且具有能够在可接受的运行时间中找到相对最优解的特性，能够满足大部分聚类实践需要，现今已广泛应用于医疗、经济、工业等领域的组合优化问题中。贪婪随机自适应搜索算法被设计为一种多步迭代的算法，它的设计思想类似于爬山法或模拟退火算法。贪婪随机自适应算法的每次迭代主要分为两个步骤：构造阶段与局部搜索阶段。其中，在构造阶段内，算法会先构建一个可行的初始解，即局部最优解Y，随后在第二个阶段中会对初始解的其它邻近分支进行局部搜索，并找出一个新的局部最优解X，并与第一步的最优解Y进行对比。如果新的解X比已经搜索到的最优解Y更好，那么就用X替代Y，反之则进行下一次迭代。M.Woo[25]等人提出使用基于贪婪随机自适应搜索算法来设计热点剪辑聚类算法，并提出了一整套版图信息的处理