nipsdlufl10-ProbabilisticModelSemanticWordVectors

Vol.48，No.6Jun. 202 1第48卷第6期2 0 2 1年6月湖南大学学报)自然科学版)Journal of Hunan University (Natural Sciences )文章编号：1674-2974(2021 )06-0058-09 DOI ： 10.16339/ki.hdxbzkb.2021.06.009深度优先局艺B 聚合哈希龙显忠g,程成李云12(1.南京邮电大学计算机学院，江苏南京210023；2.江苏省大数据安全与智能处理重点实验室，江苏南京210023)摘 要：已有的深度监督哈希方法不能有效地利用提取到的卷积特征，同时，也忽视了数据对之间相似性信息分布对于哈希网络的作用，最终导致学到的哈希编码之间的区分性不足.为了解决该问题，提出了一种新颖的深度监督哈希方法，称之为深度优先局部聚合哈希(DeepPriority Local Aggregated Hashing , DPLAH ). DPLAH 将局部聚合描述子向量嵌入到哈希网络 中，提高网络对同类数据的表达能力，并且通过在数据对之间施加不同权重，从而减少相似性 信息分布倾斜对哈希网络的影响.利用Pytorch 深度框架进行DPLAH 实验，使用NetVLAD 层 对Resnet18网络模型输出的卷积特征进行聚合，将聚合得到的特征进行哈希编码学习.在CI-FAR-10和NUS-WIDE 数据集上的图像检索实验表明，与使用手工特征和卷积神经网络特征的非深度哈希学习算法的最好结果相比,DPLAH 的平均准确率均值要高出11%，同时，DPLAH 的平均准确率均值比非对称深度监督哈希方法高出2%.关键词：深度哈希学习；卷积神经网络；图像检索；局部聚合描述子向量中图分类号:TP391.4文献标志码:ADeep Priority Local Aggregated HashingLONG Xianzhong 1，覮，CHENG Cheng1,2,LI Yun 1,2(1. School of Computer Science & Technology ,Nanjing University of Posts and Telecommunications ,Nanjing 210023, China ;2. Key Laboratory of Jiangsu Big Data Security and Intelligent Processing ,Nanjing 210023, China )Abstract : The existing deep supervised hashing methods cannot effectively utilize the extracted convolution fea ­tures, but also ignore the role of the similarity information distribution between data pairs on the hash network, result ­ing in insufficient discrimination between the learned hash codes. In order to solve this problem, a novel deep super ­vised hashing method called deep priority locally aggregated hashing (DPLAH) is proposed in this paper, which em ­beds the vector of locally aggregated descriptors (VLAD) into the hash network, so as to improve the ability of the hashnetwork to express the similar data, and reduce the impact of similarity distribution skew on the hash network by im ­posing different weights on the data pairs. DPLAH experiment is carried out by using the Pytorch deep framework. Theconvolution features of the Resnet18 network model output are aggregated by using the NetVLAD layer, and the hashcoding is learned by using the aggregated features. The image retrieval experiments on the CIFAR-10 and NUS - WIDE datasets show that the mean average precision (MAP) of DPLAH is11 percentage points higher than that of* 收稿日期：2020-04-26基金项目：国家自然科学基金资助项目(61906098,61772284),National Natural Science Foundation of China(61906098, 61772284);国家重 点研发计划项目(2018YFB 1003702) , National Key Research and Development Program of China (2018YFB1003702)作者简介:龙显忠(1985—),男，河南信阳人，南京邮电大学讲师，工学博士，硕士生导师覮 通信联系人,E-mail ： *************.cn第6期龙显忠等:深度优先局部聚合哈希59non-deep hash learning algorithms using manual features and convolution neural network features,and the MAP of DPLAH is2percentage points higher than that of asymmetric deep supervised hashing method.Key words:deep Hash learning;convolutional neural network;image retrieval;vector of locally aggregated de-scriptors(VLAD)随着信息检索技术的不断发展和完善，如今人们可以利用互联网轻易获取感兴趣的数据内容，然而，信息技术的发展同时导致了数据规模的迅猛增长.面对海量的数据以及超大规模的数据集，利用最近邻搜索［1(Nearest Neighbor Search,NN)的检索技术已经无法获得理想的检索效果与可接受的检索时间.因此,近年来,近似最近邻搜索［2(Approximate Near­est Neighbor Search,ANN)变得越来越流行,它通过搜索可能相似的几个数据而不再局限于返回最相似的数据，在牺牲可接受范围的精度下提高了检索效率.作为一种广泛使用的ANN搜索技术，哈希方法(Hashing)［3］将数据转换为紧凑的二进制编码(哈希编码)表示，同时保证相似的数据对生成相似的二进制编码.利用哈希编码来表示原始数据，显著减少了数据的存储和查询开销，从而可以应对大规模数据中的检索问题.因此，哈希方法吸引了越来越多学者的关注.当前哈希方法主要分为两类：数据独立的哈希方法和数据依赖的哈希方法，这两类哈希方法的区别在于哈希函数是否需要训练数据来定义.局部敏感哈希(Locality Sensitive Hashing,LSH)［4］作为数据独立的哈希代表，它利用独立于训练数据的随机投影作为哈希函数•相反，数据依赖哈希的哈希函数需要通过训练数据学习出来，因此，数据依赖的哈希也被称为哈希学习，数据依赖的哈希通常具有更好的性能.近年来，哈希方法的研究主要侧重于哈希学习方面.根据哈希学习过程中是否使用标签，哈希学习方法可以进一步分为：监督哈希学习和无监督哈希学习.典型的无监督哈希学习包括:谱哈希［5(Spectral Hashing,SH);迭代量化哈希［6］(Iterative Quantization, ITQ);离散图哈希［7(Discrete Graph Hashing,DGH);有序嵌入哈希［8］(Ordinal Embedding Hashing,OEH)等.无监督哈希学习方法仅使用无标签的数据来学习哈希函数，将输入的数据映射为哈希编码的形式.相反,监督哈希学习方法通过利用监督信息来学习哈希函数,由于利用了带有标签的数据,监督哈希方法往往比无监督哈希方法具有更好的准确性，本文的研究主要针对监督哈希学习方法.传统的监督哈希方法包括：核监督哈希［9］(Su­pervised Hashing with Kernels,KSH);潜在因子哈希［10］(Latent Factor Hashing,LFH);快速监督哈希［11］(Fast Supervised Hashing,FastH);监督离散哈希［1(Super-vised Discrete Hashing,SDH)等.随着深度学习技术的发展［13］,利用神经网络提取的特征已经逐渐替代手工特征，推动了深度监督哈希的进步.具有代表性的深度监督哈希方法包括:卷积神经网络哈希［1(Con­volutional Neural Networks Hashing,CNNH);深度语义排序哈希［15］(Deep Semantic Ranking Based Hash-ing,DSRH);深度成对监督哈希［16］(Deep Pairwise-Supervised Hashing,DPSH);深度监督离散哈希［17］(Deep Supervised Discrete Hashing,DSDH);深度优先哈希［18］(Deep Priority Hashing,DPH)等.通过将特征学习和哈希编码学习(或哈希函数学习)集成到一个端到端网络中，深度监督哈希方法可以显著优于非深度监督哈希方法.到目前为止，大多数现有的深度哈希方法都采用对称策略来学习查询数据和数据集的哈希编码以及深度哈希函数.相反，非对称深度监督哈希［19］(Asymmetric Deep Supervised Hashing,ADSH)以非对称的方式处理查询数据和整个数据库数据，解决了对称方式中训练开销较大的问题，仅仅通过查询数据就可以对神经网络进行训练来学习哈希函数，整个数据库的哈希编码可以通过优化直接得到.本文的模型同样利用了ADSH的非对称训练策略.然而，现有的非对称深度监督哈希方法并没有考虑到数据之间的相似性分布对于哈希网络的影响,可能导致结果是:容易在汉明空间中保持相似关系的数据对,往往会被训练得越来越好;相反,那些难以在汉明空间中保持相似关系的数据对，往往在训练后得到的提升并不显著.同时大部分现有的深度监督哈希方法在哈希网络中没有充分有效利用提60湖南大学学报(自然科学版)2021年取到的卷积特征.本文提出了一种新的深度监督哈希方法，称为深度优先局部聚合哈希(Deep Priority Local Aggre­gated Hashing,DPLAH).DPLAH的贡献主要有三个方面:1)DPLAH采用非对称的方式处理查询数据和数据库数据，同时DPLAH网络会优先学习查询数据和数据库数据之间困难的数据对，从而减轻相似性分布倾斜对哈希网络的影响.2)DPLAH设计了全新的深度哈希网络，具体来说,DPLAH将局部聚合表示融入到哈希网络中，提高了哈希网络对同类数据的表达能力.同时考虑到数据的局部聚合表示对于分类任务的有效性.3)在两个大型数据集上的实验结果表明，DPLAH在实际应用中性能优越.1相关工作本节分别对哈希学习［3］、NetVLAD［20］和Focal Loss［21］进行介绍.DPLAH分别利用NetVLAD和Fo­cal Loss提高哈希网络对同类数据的表达能力及减轻数据之间相似性分布倾斜对于哈希网络的影响. 1.1哈希学习哈希学习［3］的任务是学习查询数据和数据库数据的哈希编码表示，同时要满足原始数据之间的近邻关系与数据哈希编码之间的近邻关系相一致的条件.具体来说，利用机器学习方法将所有数据映射成{0,1}r形式的二进制编码(r表示哈希编码长度)，在原空间中不相似的数据点将被映射成不相似)即汉明距离较大)的两个二进制编码，而原空间中相似的两个数据点将被映射成相似(即汉明距离较小)的两个二进制编码.为了便于计算，大部分哈希方法学习{-1,1}r形式的哈希编码，这是因为{-1,1}r形式的哈希编码对之间的内积等于哈希编码的长度减去汉明距离的两倍，同时{-1,1}r形式的哈希编码可以容易转化为{0,1}r形式的二进制编码.图1是哈希学习的示意图.经过特征提取后的高维向量被用来表示原始图像，哈希函数h将每张图像映射成8bits的哈希编码,使原来相似的数据对(图中老虎1和老虎2)之间的哈希编码汉明距离尽可能小，原来不相似的数据对(图中大象和老虎1)之间的哈希编码汉明距离尽可能大.h（大象）=10001010h（老虎1）=01100001h（老虎2）=01100101相似度尽可能小相似度尽可能大图1哈希学习示意图Fig.1Hashing learning diagram1.2NetVLADNetVLAD的提出是用于解决端到端的场景识别问题［20(场景识别被当作一个实例检索任务),它将传统的局部聚合描述子向量(Vector of Locally Aggre­gated Descriptors,VLAD［22］)结构嵌入到CNN网络中，得到了一个新的VLAD层.可以容易地将NetVLAD 使用在任意CNN结构中，利用反向传播算法进行优化，它能够有效地提高对同类别图像的表达能力，并提高分类的性能.NetVLAD的编码步骤为：利用卷积神经网络提取图像的卷积特征;利用NetVLAD层对卷积特征进行聚合操作.图2为NetVLAD层的示意图.在特征提取阶段,NetVLAD会在最后一个卷积层上裁剪卷积特征，并将其视为密集的描述符提取器，最后一个卷积层的输出是H伊W伊D映射，可以将其视为在H伊W空间位置提取的一组D维特征,该方法在实例检索和纹理识别任务［23別中都表现出了很好的效果.NetVLAD layer（KxD）x lVLADvectorh------->图2NetVLAD层示意图⑷Fig.2NetVLAD layer diagram1201NetVLAD在特征聚合阶段，利用一个新的池化层对裁剪的CNN特征进行聚合，这个新的池化层被称为NetVLAD层.NetVLAD的聚合操作公式如下：NV((，k)二移a(x)(血⑺-C((j))(1)i=1式中:血(j)和C)(j)分别表示第i个特征的第j维和第k个聚类中心的第j维；恣&)表示特征您与第k个视觉单词之间的权.NetVLAD特征聚合的输入为：NetVLAD裁剪得到的N个D维的卷积特征,K个聚第6期龙显忠等:深度优先局部聚合哈希61类中心.VLAD的特征分配方式是硬分配,即每个特征只和对应的最近邻聚类中心相关联，这种分配方式会造成较大的量化误差，并且，这种分配方式嵌入到卷积神经网络中无法进行反向传播更新参数.因此,NetVLAD采用软分配的方式进行特征分配，软分配对应的公式如下：-琢II Xi-C*II 2=—e(2)-琢II X-Ck，II2k，如果琢寅+肄,那么对于最接近的聚类中心,龟&)的值为1,其他为0.aS)可以进一步重写为：w j X i+b ka(x i)=—e-)3)w J'X i+b kk，式中:W k=2琢C k；b k=-琢||C k||2.最终的NetVLAD的聚合表示可以写为：N w；x+b kv(j，k)=移—----(x(j)-Ck(j))(4)i=1w j.X i+b k移ek，1.3Focal Loss对于目标检测方法,一般可以分为两种类型:单阶段目标检测和两阶段目标检测,通常情况下，两阶段的目标检测效果要优于单阶段的目标检测.Lin等人［21］揭示了前景和背景的极度不平衡导致了单阶段目标检测的效果无法令人满意,具体而言，容易被分类的背景虽然对应的损失很低，但由于图像中背景的比重很大,对于损失依旧有很大的贡献,从而导致收敛到不够好的一个结果.Lin等人［21］提出了Fo­cal Loss应对这一问题，图3是对应的示意图.使用交叉爛作为目标检测中的分类损失，对于易分类的样本,它的损失虽然很低，但数据的不平衡导致大量易分类的损失之和压倒了难分类的样本损失,最终难分类的样本不能在神经网络中得到有效的训练.Focal Loss的本质是一种加权思想，权重可根据分类正确的概率p得到，利用酌可以对该权重的强度进行调整.针对非对称深度哈希方法，希望难以在汉明空间中保持相似关系的数据对优先训练,具体来说,对于DPLAH的整体训练损失，通过施加权重的方式,相对提高难以在汉明空间中保持相似关系的数据对之间的训练损失.然而深度哈希学习并不是一个分类任务,因此无法像Focal Loss一样根据分类正确的概率设计权重，哈希学习的目的是学到保相似性的哈希编码，本文最终利用数据对哈希编码的相似度作为权重的设计依据具体的权重形式将在模型部分详细介绍.正确分类的概率图3Focal Loss示意图［21】Fig.3Focal Loss diagram12112深度优先局部聚合哈希2.1基本定义DPLAH模型采用非对称的网络设计.Q={0},=1表示n张查询图像,X={X i}m1表示数据库有m张图像；查询图像和数据库图像的标签分别用Z={Z i},=1和Y ={川1表示；i=［Z i1，…,zj1,i=1，…,n;c表示类另数；如果查询图像0属于类别j,j=1，…,c;那么z”=1,否则=0.利用标签信息，可以构造图像对的相似性矩阵S沂{-1,1}"伊”,s”=1表示查询图像q,和数据库中的图像X j语义相似,S j=-1表示查询图像和数据库中的图像X j语义不相似.深度哈希方法的目标是学习查询图像和数据库中图像的哈希编码，查询图像的哈希编码用U沂{-1,1}""，表示,数据库中图像的哈希编码用B沂{-1,1}m伊r表示，其中r表示哈希编码的长度.对于DPLAH模型,它在特征提取部分采用预训练好的Resnet18网络［25］.图4为DPLAH网络的结构示意图，利用NetVLAD层聚合Resnet18网络提取到的卷积特征，哈希编码通过VLAD编码得到，由于VLAD编码在分类任务中被广泛使用，于是本文将NetVLAD层的输出作为分类任务的输入，利用图像的标签信息监督NetVLAD层对卷积特征的利用.事实上，任何一种CNN模型都能实现图像特征提取的功能，所以对于选用哪种网络进行特征学习并不是本文的重点.62湖南大学学报(自然科学版)2021年conv1图4DPLAH结构Fig.4DPLAH structure图像标签soft-max1,0,1,1,0□1,0,0,0,11,1,0,1,0---------*----------VLADVLAD core)c)l・>:i>数据库图像的哈希编码2.2DPLAH模型的目标函数为了学习可以保留查询图像与数据库图像之间相似性的哈希编码，一种常见的方法是利用相似性的监督信息S e{-1,1}n伊"、生成的哈希编码长度r,以及查询图像的哈希编码仏和数据库中图像的哈希编码b三者之间的关系[9],即最小化相似性的监督信息与哈希编码对内积之间的L损失.考虑到相似性分布的倾斜问题，本文通过施加权重来调节查询图像和数据库图像之间的损失，其公式可以表示为：min J=移移(1-w)(u T b j-rs)专,B i=1j=1s.t.U沂{-1,1}n伊r,B沂{-1,1}m伊r,W沂R n伊m(5)受FocalLoss启发,希望深度哈希网络优先训练相似性不容易保留图像对，然而Focal Loss利用图像的分类结果对损失进行调整，因此，需要重新进行设计，由于哈希学习的目的是为了保留图像在汉明空间中的相似性关系，本文利用哈希编码的余弦相似度来设计权重,其表达式为：1+。

VICTOR Nivo Multimode Plate ReaderMultimode DetectionDescriptionThe VICTOR ® Nivo ™ is a high-performance filter-based multimode plate reader system that can be equipped with all major detection technologies – absorbance, luminescence, fluorescence intensity, time-resolved fluorescence, fluorescence polarization, and Alpha. It is a compact, light-weight instrument designed for life science research laboratories performing routine low-throughput assays, or assay development work, and with diverse application requirements. The system’s software has a modern, workflow-oriented user interface that is easy to learn and includes pre-defined application protocols to get users productive quickly . In addition, MyAssays Desktop Standard software is provided for data analysis.Detection TechnologiesThe system incorporates a dynamic wheel system with space for storage of up to 32 filters, providing ready access to filters for a large number of dyes. Filters are exchanged between the inner and outer filter wheels, so any individual filter can serve either excitation or emission lightpaths. As a result, there’s no need to install new filters when switching between assays, and filters can be locked within the system so they can’t be mislaid in the lab – ideal for multi-user environments. When fully-loaded, the filter system provides the flexibility to detect many dyes with better sensitivityand greater cost-effectiveness compared to a monochromator. For absorbance measurements, there is a choice of either a filter- or a spectrometer-based system. Full spectrum absorbance measurements are ultra-fast – 230 to 1000 nm at selectable resolutions (2.0 nm, 5.0 nm, 10 nm) in less than one second per well. The spectrometer system also allows for the detection of a wide range of dyes or measurement of samples with unknown absorbance spectra. The system also features high-performance Alpha laser technology, validated for use with our proprietary AlphaScreen ® and AlphaLISA ® technologies.Key Features• Available in four configurations - standard models include absorbance, luminescence, and fluorescence; option to add time-resolved fluorescence, fluorescence polarization, and/or Alpha • T op and bottom reading of all standard technologies (with the exception of Alpha) for plate formats up to 1536-wells • Compact, lightweight instrument frees-up bench space and is easy to move • Internal dynamic filter wheel system with space for up to 32 filters • For absorbance, choice of filter-based detection for best sensitivity or spectrometer for wavelength flexibility • Time resolved fluorescence certified for use with proprietary LANCE ® and HTRF ® technologies • Enhanced Security software for regulated environments provides technological controls and features that support 21 CFR Part 11 compliance • Laser based Alpha detection capabilities for fast and sensitive Alpha measurements • Browser-based software enables control from a variety of devices – PC, laptop, or tablet • Controllable via network or Wi-Fi to facilitate remote working and data access • Optional dispenser for applications such as fast kinetics, flash luminescence, or dual addition assays • Integrated temperature control and optional gas control unit to keep cells healthy during long term kinetic assaysFor research purposes only. Not for use in diagnostic procedures.For a complete listing of our global offices, visit /ContactUsCopyright ©2020, PerkinElmer, Inc. All rights reserved. PerkinElmer ® is a registered trademark of PerkinElmer, Inc. All other trademarks are the property of their respective owners.58608 PKIPerkinElmer, Inc. 940 Winter StreetWaltham, MA 02451 USA P: (800) 762-4000 or (+1) 203-925-4602*ATP detected by VICTOR Nivo with dispenser。

Probabilistic Model Checking ofan Anonymity SystemVitaly ShmatikovSRI International333Ravenswood AvenueMenlo Park,CA94025U.S.A.shmat@AbstractWe use the probabilistic model checker PRISM to analyze the Crowds system for anonymous Web browsing.This case study demonstrates howprobabilistic model checking techniques can be used to formally analyze se-curity properties of a peer-to-peer group communication system based onrandom message routing among members.The behavior of group mem-bers and the adversary is modeled as a discrete-time Markov chain,and thedesired security properties are expressed as PCTL formulas.The PRISMmodel checker is used to perform automated analysis of the system and ver-ify anonymity guarantees it provides.Our main result is a demonstration ofhow certain forms of probabilistic anonymity degrade when group size in-creases or random routing paths are rebuilt,assuming that the corrupt groupmembers are able to identify and/or correlate multiple routing paths originat-ing from the same sender.1IntroductionFormal analysis of security protocols is a well-establishedfield.Model checking and theorem proving techniques[Low96,MMS97,Pau98,CJM00]have been ex-tensively used to analyze secrecy,authentication and other security properties ofprotocols and systems that employ cryptographic primitives such as public-key en-cryption,digital signatures,etc.Typically,the protocol is modeled at a highly ab-stract level and the underlying cryptographic primitives are treated as secure“black boxes”to simplify the model.This approach discovers attacks that would succeed even if all cryptographic functions were perfectly secure.Conventional formal analysis of security is mainly concerned with security against the so called Dolev-Yao attacks,following[DY83].A Dolev-Yao attacker is a non-deterministic process that has complete control over the communication net-work and can perform any combination of a given set of attacker operations,such as intercepting any message,splitting messages into parts,decrypting if it knows the correct decryption key,assembling fragments of messages into new messages and replaying them out of context,etc.Many proposed systems for anonymous communication aim to provide strong, non-probabilistic anonymity guarantees.This includes proxy-based approaches to anonymity such as the Anonymizer[Ano],which hide the sender’s identity for each message by forwarding all communication through a special server,and MIX-based anonymity systems[Cha81]that blend communication between dif-ferent senders and recipients,thus preventing a global eavesdropper from linking sender-recipient pairs.Non-probabilistic anonymity systems are amenable to for-mal analysis in the same non-deterministic Dolev-Yao model as used for verifica-tion of secrecy and authentication protocols.Existing techniques for the formal analysis of anonymity in the non-deterministic model include traditional process formalisms such as CSP[SS96]and a special-purpose logic of knowledge[SS99].In this paper,we use probabilistic model checking to analyze anonymity prop-erties of a gossip-based system.Such systems fundamentally rely on probabilistic message routing to guarantee anonymity.The main representative of this class of anonymity systems is Crowds[RR98].Instead of protecting the user’s identity against a global eavesdropper,Crowds provides protection against collaborating local eavesdroppers.All communication is routed randomly through a group of peers,so that even if some of the group members collaborate and share collected lo-cal information with the adversary,the latter is not likely to distinguish true senders of the observed messages from randomly selected forwarders.Conventional formal analysis techniques that assume a non-deterministic at-tacker in full control of the communication channels are not applicable in this case. Security properties of gossip-based systems depend solely on the probabilistic be-havior of protocol participants,and can be formally expressed only in terms of relative probabilities of certain observations by the adversary.The system must be modeled as a probabilistic process in order to capture its properties faithfully.Using the analysis technique developed in this paper—namely,formalization of the system as a discrete-time Markov chain and probabilistic model checking of2this chain with PRISM—we uncovered two subtle properties of Crowds that causedegradation of the level of anonymity provided by the system to the users.First,if corrupt group members are able to detect that messages along different routingpaths originate from the same(unknown)sender,the probability of identifyingthat sender increases as the number of observed paths grows(the number of pathsmust grow with time since paths are rebuilt when crowd membership changes).Second,the confidence of the corrupt members that they detected the correct senderincreases with the size of the group.Thefirstflaw was reported independently byMalkhi[Mal01]and Wright et al.[W ALS02],while the second,to the best ofour knowledge,was reported for thefirst time in the conference version of thispaper[Shm02].In contrast to the analysis by Wright et al.that relies on manualprobability calculations,we discovered both potential vulnerabilities of Crowds byautomated probabilistic model checking.Previous research on probabilistic formal models for security focused on(i)probabilistic characterization of non-interference[Gra92,SG95,VS98],and(ii)process formalisms that aim to faithfully model probabilistic properties of crypto-graphic primitives[LMMS99,Can00].This paper attempts to directly model andanalyze security properties based on discrete probabilities,as opposed to asymp-totic probabilities in the conventional cryptographic sense.Our analysis methodis applicable to other probabilistic anonymity systems such as Freenet[CSWH01]and onion routing[SGR97].Note that the potential vulnerabilities we discovered inthe formal model of Crowds may not manifest themselves in the implementationsof Crowds or other,similar systems that take measures to prevent corrupt routersfrom correlating multiple paths originating from the same sender.2Markov Chain Model CheckingWe model the probabilistic behavior of a peer-to-peer communication system as adiscrete-time Markov chain(DTMC),which is a standard approach in probabilisticverification[LS82,HS84,Var85,HJ94].Formally,a Markov chain can be definedas consisting in afinite set of states,the initial state,the transition relation such that,and a labeling functionfrom states to afinite set of propositions.In our model,the states of the Markov chain will represent different stages ofrouting path construction.As usual,a state is defined by the values of all systemvariables.For each state,the corresponding row of the transition matrix de-fines the probability distributions which govern the behavior of group members once the system reaches that state.32.1Overview of PCTLWe use the temporal probabilistic logic PCTL[HJ94]to formally specify properties of the system to be checked.PCTL can express properties of the form“under any scheduling of processes,the probability that event occurs is at least.”First,define state formulas inductively as follows:where atomic propositions are predicates over state variables.State formulas of the form are explained below.Define path formulas as follows:Unlike state formulas,which are simplyfirst-order propositions over a single state,path formulas represent properties of a chain of states(here path refers to a sequence of state space transitions rather than a routing path in the Crowds speci-fication).In particular,is true iff is true for every state in the chain;is true iff is true for all states in the chain until becomes true,and is true for all subsequent states;is true iff and there are no more than states before becomes true.For any state and path formula,is a state formula which is true iff state space paths starting from satisfy path formula with probability greater than.For the purposes of this paper,we will be interested in formulas of the form ,evaluated in the initial state.Here specifies a system con-figuration of interest,typically representing a particular observation by the adver-sary that satisfies the definition of a successful attack on the protocol.Property is a liveness property:it holds in iff will eventually hold with greater than probability.For instance,if is a state variable represent-ing the number of times one of the corrupt members received a message from the honest member no.,then holds in iff the prob-ability of corrupt members eventually observing member no.twice or more is greater than.Expressing properties of the system in PCTL allows us to reason formally about the probability of corrupt group members collecting enough evidence to success-fully attack anonymity.We use model checking techniques developed for verifica-tion of discrete-time Markov chains to compute this probability automatically.42.2PRISM model checkerThe automated analyses described in this paper were performed using PRISM,aprobabilistic model checker developed by Kwiatkowska et al.[KNP01].The toolsupports both discrete-and continuous-time Markov chains,and Markov decisionprocesses.As described in section4,we model probabilistic peer-to-peer com-munication systems such as Crowds simply as discrete-time Markov chains,andformalize their properties in PCTL.The behavior of the system processes is specified using a simple module-basedlanguage inspired by Reactive Modules[AH96].State variables are declared in thestandard way.For example,the following declarationdeliver:bool init false;declares a boolean state variable deliver,initialized to false,while the followingdeclarationconst TotalRuns=4;...observe1:[0..TotalRuns]init0;declares a constant TotalRuns equal to,and then an integer array of size,indexed from to TotalRuns,with all elements initialized to.State transition rules are specified using guarded commands of the form[]<guard>-><command>;where<guard>is a predicate over system variables,and<command>is the tran-sition executed by the system if the guard condition evaluates to mandoften has the form<expression>...<expression>, which means that in the next state(i.e.,that obtained after the transition has beenexecuted),state variable is assigned the result of evaluating arithmetic expres-sion<expression>If the transition must be chosen probabilistically,the discrete probability dis-tribution is specified as[]<guard>-><prob1>:<command1>+...+<probN>:<commandN>;Transition represented by command is executed with probability prob,and prob.Security properties to be checked are stated as PCTL formulas (see section2.1).5Given a formal system specification,PRISM constructs the Markov chain and determines the set of reachable states,using MTBDDs and BDDs,respectively. Model checking a PCTL formula reduces to a combination of reachability-based computation and solving a system of linear equations to determine the probability of satisfying the formula in each reachable state.The model checking algorithms employed by PRISM include[BdA95,BK98,Bai98].More details about the im-plementation and operation of PRISM can be found at http://www.cs.bham. /˜dxp/prism/and in[KNP01].Since PRISM only supports model checking offinite DTMC,in our case study of Crowds we only analyze anonymity properties offinite instances of the system. By changing parameters of the model,we demonstrate how anonymity properties evolve with changes in the system configuration.Wright et al.[W ALS02]investi-gated related properties of the Crowds system in the general case,but they do not rely on tool support and their analyses are manual rather than automated.3Crowds Anonymity SystemProviding an anonymous communication service on the Internet is a challenging task.While conventional security mechanisms such as encryption can be used to protect the content of messages and transactions,eavesdroppers can still observe the IP addresses of communicating computers,timing and frequency of communi-cation,etc.A Web server can trace the source of the incoming connection,further compromising anonymity.The Crowds system was developed by Reiter and Ru-bin[RR98]for protecting users’anonymity on the Web.The main idea behind gossip-based approaches to anonymity such as Crowds is to hide each user’s communications by routing them randomly within a crowd of similar users.Even if an eavesdropper observes a message being sent by a particular user,it can never be sure whether the user is the actual sender,or is simply routing another user’s message.3.1Path setup protocolA crowd is a collection of users,each of whom is running a special process called a jondo which acts as the user’s proxy.Some of the jondos may be corrupt and/or controlled by the adversary.Corrupt jondos may collaborate and share their obser-vations in an attempt to compromise the honest users’anonymity.Note,however, that all observations by corrupt group members are local.Each corrupt member may observe messages sent to it,but not messages transmitted on the links be-tween honest jondos.An honest crowd member has no way of determining whether6a particular jondo is honest or corrupt.The parameters of the system are the total number of members,the number of corrupt members,and the forwarding probability which is explained below.To participate in communication,all jondos must register with a special server which maintains membership information.Therefore,every member of the crowd knows identities of all other members.As part of the join procedure,the members establish pairwise encryption keys which are used to encrypt pairwise communi-cation,so the contents of the messages are secret from an external eavesdropper.Anonymity guarantees provided by Crowds are based on the path setup pro-tocol,which is described in the rest of this section.The path setup protocol is executed each time one of the crowd members wants to establish an anonymous connection to a Web server.Once a routing path through the crowd is established, all subsequent communication between the member and the Web server is routed along it.We will call one run of the path setup protocol a session.When crowd membership changes,the existing paths must be scrapped and a new protocol ses-sion must be executed in order to create a new random routing path through the crowd to the destination.Therefore,we’ll use terms path reformulation and proto-col session interchangeably.When a user wants to establish a connection with a Web server,its browser sends a request to the jondo running locally on her computer(we will call this jondo the initiator).Each request contains information about the intended desti-nation.Since the objective of Crowds is to protect the sender’s identity,it is not problematic that a corrupt router can learn the recipient’s identity.The initiator starts the process of creating a random path to the destination as follows: The initiator selects a crowd member at random(possibly itself),and for-wards the request to it,encrypted by the corresponding pairwise key.We’ll call the selected member the forwarder.The forwarderflips a biased coin.With probability,it delivers the request directly to the destination.With probability,it selects a crowd member at random(possibly itself)as the next forwarder in the path,and forwards the request to it,re-encrypted with the appropriate pairwise key.The next forwarder then repeats this step.Each forwarder maintains an identifier for the created path.If the same jondo appears in different positions on the same path,identifiers are different to avoid infinite loops.Each subsequent message from the initiator to the destination is routed along this path,i.e.,the paths are static—once established,they are not altered often.This is necessary to hinder corrupt members from linking multiple7paths originating from the same initiator,and using this information to compromise the initiator’s anonymity as described in section3.2.3.3.2Anonymity properties of CrowdsThe Crowds paper[RR98]describes several degrees of anonymity that may be provided by a communication system.Without using anonymizing techniques, none of the following properties are guaranteed on the Web since browser requests contain information about their source and destination in the clear.Beyond suspicion Even if the adversary can see evidence of a sent message,the real sender appears to be no more likely to have originated it than any other potential sender in the system.Probable innocence The real sender appears no more likely to be the originator of the message than to not be the originator,i.e.,the probability that the adversary observes the real sender as the source of the message is less thanupper bound on the probability of detection.If the sender is observed by the adversary,she can then plausibly argue that she has been routing someone else’s messages.The Crowds paper focuses on providing anonymity against local,possibly co-operating eavesdroppers,who can share their observations of communication in which they are involved as forwarders,but cannot observe communication involv-ing only honest members.We also limit our analysis to this case.3.2.1Anonymity for a single routeIt is proved in[RR98]that,for any given routing path,the path initiator in a crowd of members with forwarding probability has probable innocence against collaborating crowd members if the following inequality holds:(1)More formally,let be the event that at least one of the corrupt crowd members is selected for the path,and be the event that the path initiator appears in8the path immediately before a corrupt crowd member(i.e.,the adversary observes the real sender as the source of the messages routed along the path).Condition 1guarantees thatproving that,given multiple linked paths,the initiator appears more often as a sus-pect than a random crowd member.The automated analysis described in section6.1 confirms and quantifies this result.(The technical results of[Shm02]on which this paper is based had been developed independently of[Mal01]and[W ALS02],be-fore the latter was published).In general,[Mal01]and[W ALS02]conjecture that there can be no reliable anonymity method for peer-to-peer communication if in order to start a new communication session,the initiator must originate thefirst connection before any processing of the session commences.This implies that anonymity is impossible in a gossip-based system with corrupt routers in the ab-sence of decoy traffic.In section6.3,we show that,for any given number of observed paths,the adversary’s confidence in its observations increases with the size of the crowd.This result contradicts the intuitive notion that bigger crowds provide better anonymity guarantees.It was discovered by automated analysis.4Formal Model of CrowdsIn this section,we describe our probabilistic formal model of the Crowds system. Since there is no non-determinism in the protocol specification(see section3.1), the model is a simple discrete-time Markov chain as opposed to a Markov deci-sion process.In addition to modeling the behavior of the honest crowd members, we also formalize the adversary.The protocol does not aim to provide anonymity against global eavesdroppers.Therefore,it is sufficient to model the adversary as a coalition of corrupt crowd members who only have access to local communication channels,i.e.,they can only make observations about a path if one of them is se-lected as a forwarder.By the same token,it is not necessary to model cryptographic functions,since corrupt members know the keys used to encrypt peer-to-peer links in which they are one of the endpoints,and have no access to links that involve only honest members.The modeling technique presented in this section is applicable with minor mod-ifications to any probabilistic routing system.In each state of routing path construc-tion,the discrete probability distribution given by the protocol specification is used directly to define the probabilistic transition rule for choosing the next forwarder on the path,if any.If the protocol prescribes an upper bound on the length of the path(e.g.,Freenet[CSWH01]),the bound can be introduced as a system parameter as described in section4.2.3,with the corresponding increase in the size of the state space but no conceptual problems.Probabilistic model checking can then be used to check the validity of PCTL formulas representing properties of the system.In the general case,forwarder selection may be governed by non-deterministic10runCount goodbad lastSeen observelaunchnewstartrundeliver recordLast badObserve4.2Model of honest members4.2.1InitiationPath construction is initiated as follows(syntax of PRISM is described in section 2.2):[]launch->runCount’=TotalRuns&new’=true&launch’=false;[]new&(runCount>0)->(runCount’=runCount-1)&new’=false&start’=true;[]start->lastSeen’=0&deliver’=false&run’=true&start’=false;4.2.2Forwarder selectionThe initiator(i.e.,thefirst crowd member on the path,the one whose identity must be protected)randomly chooses thefirst forwarder from among all group mem-bers.We assume that all group members have an equal probability of being chosen, but the technique can support any discrete probability distribution for choosing for-warders.Forwarder selection is a single step of the protocol,but we model it as two probabilistic state transitions.Thefirst determines whether the selected forwarder is honest or corrupt,the second determines the forwarder’s identity.The randomly selected forwarder is corrupt with probability badCbe next on the path.Any of the honest crowd members can be selected as the forwarder with equal probability.To illustrate,for a crowd with10honest members,the following transition models the second step of forwarder selection: []recordLast&CrowdSize=10->0.1:lastSeen’=0&run’=true&recordLast’=false+0.1:lastSeen’=1&run’=true&recordLast’=false+...0.1:lastSeen’=9&run’=true&recordLast’=false;According to the protocol,each honest crowd member must decide whether to continue building the path byflipping a biased coin.With probability,the forwarder selection transition is enabled again and path construction continues, and with probability the path is terminated at the current forwarder,and all requests arriving from the initiator along the path will be delivered directly to the recipient.[](good&!deliver&run)->//Continue path constructionPF:good’=false+//Terminate path constructionnotPF:deliver’=true;The specification of the Crowds system imposes no upper bound on the length of the path.Moreover,the forwarders are not permitted to know their relative position on the path.Note,however,that the amount of information about the initiator that can be extracted by the adversary from any path,or anyfinite number of paths,isfinite(see sections4.3and4.5).In systems such as Freenet[CSWH01],requests have a hops-to-live counter to prevent infinite paths,except with very small probability.To model this counter,we may introduce an additional state variable pIndex that keeps track of the length of the path constructed so far.The path construction transition is then coded as follows://Example with Hops-To-Live//(NOT CROWDS)////Forward with prob.PF,else deliver13[](good&!deliver&run&pIndex<MaxPath)->PF:good’=false&pIndex’=pIndex+1+notPF:deliver’=true;//Terminate if reached MaxPath,//but sometimes not//(to confuse adversary)[](good&!deliver&run&pIndex=MaxPath)->smallP:good’=false+largeP:deliver’=true;Introduction of pIndex obviously results in exponential state space explosion, decreasing the maximum system size for which model checking is feasible.4.2.4Transition matrix for honest membersTo summarize the state space of the discrete-time Markov chain representing cor-rect behavior of protocol participants(i.e.,the state space induced by the abovetransitions),let be the state in which links of the th routing path from the initiator have already been constructed,and assume that are the honestforwarders selected for the path.Let be the state in which path constructionhas terminated with as thefinal path,and let be an auxiliary state. Then,given the set of honest crowd members s.t.,the transi-tion matrix is such that,,(see section4.2.2),i.e.,the probability of selecting the adversary is equal to the cumulative probability of selecting some corrupt member.14This abstraction does not limit the class of attacks that can be discovered using the approach proposed in this paper.Any attack found in the model where indi-vidual corrupt members are kept separate will be found in the model where their capabilities are combined in a single worst-case adversary.The reason for this is that every observation made by one of the corrupt members in the model with separate corrupt members will be made by the adversary in the model where their capabilities are combined.The amount of information available to the worst-case adversary and,consequently,the inferences that can be made from it are at least as large as those available to any individual corrupt member or a subset thereof.In the adversary model of[RR98],each corrupt member can only observe its local network.Therefore,it only learns the identity of the crowd member imme-diately preceding it on the path.We model this by having the corrupt member read the value of the lastSeen variable,and record its observations.This cor-responds to reading the source IP address of the messages arriving along the path. For example,for a crowd of size10,the transition is as follows:[]lastSeen=0&badObserve->observe0’=observe0+1&deliver’=true&run’=true&badObserve’=false;...[]lastSeen=9&badObserve->observe9’=observe9+1&deliver’=true&run’=true&badObserve’=false;The counters observe are persistent,i.e.,they are not reset for each session of the path setup protocol.This allows the adversary to accumulate observations over several path reformulations.We assume that the adversary can detect when two paths originate from the same member whose identity is unknown(see sec-tion3.2.2).The adversary is only interested in learning the identity of thefirst crowd mem-ber in the path.Continuing path construction after one of the corrupt members has been selected as a forwarder does not provide the adversary with any new infor-mation.This is a very important property since it helps keep the model of the adversaryfinite.Even though there is no bound on the length of the path,at most one observation per path is useful to the adversary.To simplify the model,we as-sume that the path terminates as soon as it reaches a corrupt member(modeled by deliver’=true in the transition above).This is done to shorten the average path length without decreasing the power of the adversary.15Each forwarder is supposed toflip a biased coin to decide whether to terminate the path,but the coinflips are local to the forwarder and cannot be observed by other members.Therefore,honest members cannot detect without cooperation that corrupt members always terminate paths.In any case,corrupt members can make their observable behavior indistinguishable from that of the honest members by continuing the path with probability as described in section4.2.3,even though this yields no additional information to the adversary.4.4Multiple pathsThe discrete-time Markov chain defined in sections4.2and4.3models construc-tion of a single path through the crowd.As explained in section3.2.2,paths have to be reformulated periodically.The decision to rebuild the path is typically made according to a pre-determined schedule,e.g.,hourly,daily,or once enough new members have asked to join the crowd.For the purposes of our analysis,we sim-ply assume that paths are reformulated somefinite number of times(determined by the system parameter=TotalRuns).We analyze anonymity properties provided by Crowds after successive path reformulations by considering the state space produced by successive execu-tions of the path construction protocol described in section4.2.As explained in section4.3,the adversary is permitted to combine its observations of some or all of the paths that have been constructed(the adversary only observes the paths for which some corrupt member was selected as one of the forwarders).The adversary may then use this information to infer the path initiator’s identity.Because for-warder selection is probabilistic,the adversary’s ability to collect enough informa-tion to successfully identify the initiator can only be characterized probabilistically, as explained in section5.4.5Finiteness of the adversary’s state spaceThe state space of the honest members defined by the transition matrix of sec-tion4.2.4is infinite since there is no a priori upper bound on the length of each path.Corrupt members,however,even if they collaborate,can make at most one observation per path,as explained in section4.3.As long as the number of path reformulations is bounded(see section4.4),only afinite number of paths will be constructed and the adversary will be able to make only afinite number of observa-tions.Therefore,the adversary only needsfinite memory and the adversary’s state space isfinite.In general,anonymity is violated if the adversary has a high probability of making a certain observation(see section5).Tofind out whether Crowds satisfies16。

dlib目标dlib（Deep Learning in C++）是一个用于机器学习和人脸检测等任务的C++工具包。

dlib是一个强大的开源库，提供了一些高效且易于使用的工具和算法，用于解决计算机视觉和机器学习问题。

dlib被广泛用于图像处理和计算机视觉中的目标检测任务。

它包含了一些经典的机器学习算法，如支持向量机（SVM）和随机森林（Random Forests），以及一些流行的卷积神经网络（CNN）的实现，如ResNet和AlexNet。

这些算法可以用于图像分类、物体检测和人脸识别等任务。

人脸检测是dlib最著名的功能之一。

dlib利用深度学习算法和计算机视觉技术，可以在图像中准确地检测到人脸，并标记出人脸的位置和特征点。

这些特征点包括眼睛、鼻子、嘴巴等重要的面部特征，可以用于人脸识别、表情分析和人脸变换等应用。

除了人脸检测，dlib还提供了一些其他有用的功能。

例如，它可以用于图像分类，将图像分为不同的类别。

它还可以用于目标跟踪，跟踪运动中的物体并预测其位置。

此外，dlib还提供了一些辅助工具，如图像增强和特征提取等。

在使用dlib时，我们通常需要加载预训练的模型。

这些模型已经在大规模数据集上进行了训练，并具备很强的泛化能力。

我们可以通过使用这些预训练模型来进行图像分类、目标检测和人脸识别等任务。

此外，我们还可以使用dlib的API来训练自己的模型，以满足特定的需求。

与其他一些深度学习框架相比，dlib的优点之一是其优秀的性能。

它是用C++编写的，可以在低端设备上运行，如嵌入式系统和移动设备。

此外，dlib提供了一些多线程的功能，可以充分利用多核处理器的并行计算能力，加快算法的速度。

在使用dlib时，我们还需要注意一些潜在的问题。

首先，由于dlib是基于C++的，因此它的学习曲线可能较陡峭，需要一定的编程经验和计算机视觉的知识。

其次，由于dlib的模型较大，因此在训练和部署模型时需要考虑存储空间和计算资源的限制。

dlib人脸识别原理人脸识别技术是一种日益普及的biomentric术，它在身份验证、安全保护和其他领域发挥着重要作用。

现代人脸识别技术大都基于计算机视觉和机器学习原理，其中最受欢迎的是DLib框架。

DLib是一种高级的开源机器学习软件库，它主要用于识别和分类人脸图像，以实现高精度的人脸识别。

本文将详细介绍DLib人脸识别的原理，并结合实例介绍其识别算法的具体流程。

1. DLib人脸识别原理DLib的人脸识别原理是借助机器学习训练一组模型，以实现高精度的人脸识别。

其中，DLib人脸识别模型通常使用一种叫做“支持向量机（SVM）”的机器学习算法，该算法可以自动找出一组数据中的模式，并使用它们来进行判断。

首先，DLib框架会对输入图像进行处理，该处理会将图像平均分割为一系列小块，并对每个小块进行提取特征。

提取的特征会被作为训练模型的输入，训练的模型被用来检测输入图像中是否存在人脸，以及识别出图像中的哪一个人。

DLib人脸识别模型支持不同的特征提取方式，其中最常用的是“局部二值模式（LBP）”特征提取方式。

LBP特征也称为局部纹理特征，它是指在一个给定的图像中，每个像素的值仅取决于它的邻域像素的值，而与其他远处的像素无关。

通过提取局部纹理特征，算法可以有效地减少噪声干扰，并精确地跟踪被识别的人的脸部特征，以便对其进行识别。

2. DLib人脸识别算法流程DLib人脸识别算法的具体流程如下：（1）获取待识别图像：首先，将待识别的人脸图像输入算法；（2）人脸检测：使用DLib框架中的相关算法，从输入图像中检测出人脸的位置；（3）特征提取以及预处理：将检测出的人脸图像使用LBP特征提取方法分割成小块，并对每个小块进行特征提取；（4）SVM训练：将每个块的特征向量输入SVM算法，进行训练，以生成一组用于人脸识别的模型；（5）计算相似度：计算每个待识别图像与训练生成的模型之间的相似度；（6）识别结果：根据计算出的相似度，识别出最匹配的人脸图像。

DPABI（Dublin Platform for Biomedical Imaging）是一个开源的生物医学成像平台，用于处理和分析医学影像数据。

DPABI的前缀可能是指该平台的缩写，或者某个特定的模块或工具的前缀。

DPABI平台提供了多种工具和库，用于处理医学影像数据，包括图像导入、格式转换、图像分割、标注、测量和分析等。

这些工具和库可能以DPABI作为前缀，以标识它们属于该平台的一部分。

例如，DPABI可能是一个用于医学影像分析的软件库，其中包含了一系列用于图像处理和分析的函数和工具。

该库可能以DPABI作为前缀，以便与其他库或工具进行区分。

需要注意的是，DPABI的具体含义和前缀的使用方式可能会因特定上下文而异。

如果您对DPABI的具体含义有疑问，建议参考相关文档或与相关开发人员进行联系以获取更准确的信息。

s Data mining and knowledge discovery in databases have been attracting a significant amount of research, industry, and media atten-tion of late. What is all the excitement about?This article provides an overview of this emerging field, clarifying how data mining and knowledge discovery in databases are related both to each other and to related fields, such as machine learning, statistics, and databases. The article mentions particular real-world applications, specific data-mining techniques, challenges in-volved in real-world applications of knowledge discovery, and current and future research direc-tions in the field.A cross a wide variety of fields, data arebeing collected and accumulated at adramatic pace. There is an urgent need for a new generation of computational theo-ries and tools to assist humans in extracting useful information (knowledge) from the rapidly growing volumes of digital data. These theories and tools are the subject of the emerging field of knowledge discovery in databases (KDD).At an abstract level, the KDD field is con-cerned with the development of methods and techniques for making sense of data. The basic problem addressed by the KDD process is one of mapping low-level data (which are typically too voluminous to understand and digest easi-ly) into other forms that might be more com-pact (for example, a short report), more ab-stract (for example, a descriptive approximation or model of the process that generated the data), or more useful (for exam-ple, a predictive model for estimating the val-ue of future cases). At the core of the process is the application of specific data-mining meth-ods for pattern discovery and extraction.1This article begins by discussing the histori-cal context of KDD and data mining and theirintersection with other related fields. A briefsummary of recent KDD real-world applica-tions is provided. Definitions of KDD and da-ta mining are provided, and the general mul-tistep KDD process is outlined. This multistepprocess has the application of data-mining al-gorithms as one particular step in the process.The data-mining step is discussed in more de-tail in the context of specific data-mining al-gorithms and their application. Real-worldpractical application issues are also outlined.Finally, the article enumerates challenges forfuture research and development and in par-ticular discusses potential opportunities for AItechnology in KDD systems.Why Do We Need KDD?The traditional method of turning data intoknowledge relies on manual analysis and in-terpretation. For example, in the health-careindustry, it is common for specialists to peri-odically analyze current trends and changesin health-care data, say, on a quarterly basis.The specialists then provide a report detailingthe analysis to the sponsoring health-care or-ganization; this report becomes the basis forfuture decision making and planning forhealth-care management. In a totally differ-ent type of application, planetary geologistssift through remotely sensed images of plan-ets and asteroids, carefully locating and cata-loging such geologic objects of interest as im-pact craters. Be it science, marketing, finance,health care, retail, or any other field, the clas-sical approach to data analysis relies funda-mentally on one or more analysts becomingArticlesFALL 1996 37From Data Mining to Knowledge Discovery inDatabasesUsama Fayyad, Gregory Piatetsky-Shapiro, and Padhraic Smyth Copyright © 1996, American Association for Artificial Intelligence. All rights reserved. 0738-4602-1996 / $2.00areas is astronomy. Here, a notable success was achieved by SKICAT ,a system used by as-tronomers to perform image analysis,classification, and cataloging of sky objects from sky-survey images (Fayyad, Djorgovski,and Weir 1996). In its first application, the system was used to process the 3 terabytes (1012bytes) of image data resulting from the Second Palomar Observatory Sky Survey,where it is estimated that on the order of 109sky objects are detectable. SKICAT can outper-form humans and traditional computational techniques in classifying faint sky objects. See Fayyad, Haussler, and Stolorz (1996) for a sur-vey of scientific applications.In business, main KDD application areas includes marketing, finance (especially in-vestment), fraud detection, manufacturing,telecommunications, and Internet agents.Marketing:In marketing, the primary ap-plication is database marketing systems,which analyze customer databases to identify different customer groups and forecast their behavior. Business Week (Berry 1994) estimat-ed that over half of all retailers are using or planning to use database marketing, and those who do use it have good results; for ex-ample, American Express reports a 10- to 15-percent increase in credit-card use. Another notable marketing application is market-bas-ket analysis (Agrawal et al. 1996) systems,which find patterns such as, “If customer bought X, he/she is also likely to buy Y and Z.” Such patterns are valuable to retailers.Investment: Numerous companies use da-ta mining for investment, but most do not describe their systems. One exception is LBS Capital Management. Its system uses expert systems, neural nets, and genetic algorithms to manage portfolios totaling $600 million;since its start in 1993, the system has outper-formed the broad stock market (Hall, Mani,and Barr 1996).Fraud detection: HNC Falcon and Nestor PRISM systems are used for monitoring credit-card fraud, watching over millions of ac-counts. The FAIS system (Senator et al. 1995),from the U.S. Treasury Financial Crimes En-forcement Network, is used to identify finan-cial transactions that might indicate money-laundering activity.Manufacturing: The CASSIOPEE trou-bleshooting system, developed as part of a joint venture between General Electric and SNECMA, was applied by three major Euro-pean airlines to diagnose and predict prob-lems for the Boeing 737. To derive families of faults, clustering methods are used. CASSIOPEE received the European first prize for innova-intimately familiar with the data and serving as an interface between the data and the users and products.For these (and many other) applications,this form of manual probing of a data set is slow, expensive, and highly subjective. In fact, as data volumes grow dramatically, this type of manual data analysis is becoming completely impractical in many domains.Databases are increasing in size in two ways:(1) the number N of records or objects in the database and (2) the number d of fields or at-tributes to an object. Databases containing on the order of N = 109objects are becoming in-creasingly common, for example, in the as-tronomical sciences. Similarly, the number of fields d can easily be on the order of 102or even 103, for example, in medical diagnostic applications. Who could be expected to di-gest millions of records, each having tens or hundreds of fields? We believe that this job is certainly not one for humans; hence, analysis work needs to be automated, at least partially.The need to scale up human analysis capa-bilities to handling the large number of bytes that we can collect is both economic and sci-entific. Businesses use data to gain competi-tive advantage, increase efficiency, and pro-vide more valuable services to customers.Data we capture about our environment are the basic evidence we use to build theories and models of the universe we live in. Be-cause computers have enabled humans to gather more data than we can digest, it is on-ly natural to turn to computational tech-niques to help us unearth meaningful pat-terns and structures from the massive volumes of data. Hence, KDD is an attempt to address a problem that the digital informa-tion era made a fact of life for all of us: data overload.Data Mining and Knowledge Discovery in the Real WorldA large degree of the current interest in KDD is the result of the media interest surrounding successful KDD applications, for example, the focus articles within the last two years in Business Week , Newsweek , Byte , PC Week , and other large-circulation periodicals. Unfortu-nately, it is not always easy to separate fact from media hype. Nonetheless, several well-documented examples of successful systems can rightly be referred to as KDD applications and have been deployed in operational use on large-scale real-world problems in science and in business.In science, one of the primary applicationThere is an urgent need for a new generation of computation-al theories and tools toassist humans in extractinguseful information (knowledge)from the rapidly growing volumes ofdigital data.Articles38AI MAGAZINEtive applications (Manago and Auriol 1996).Telecommunications: The telecommuni-cations alarm-sequence analyzer (TASA) wasbuilt in cooperation with a manufacturer oftelecommunications equipment and threetelephone networks (Mannila, Toivonen, andVerkamo 1995). The system uses a novelframework for locating frequently occurringalarm episodes from the alarm stream andpresenting them as rules. Large sets of discov-ered rules can be explored with flexible infor-mation-retrieval tools supporting interactivityand iteration. In this way, TASA offers pruning,grouping, and ordering tools to refine the re-sults of a basic brute-force search for rules.Data cleaning: The MERGE-PURGE systemwas applied to the identification of duplicatewelfare claims (Hernandez and Stolfo 1995).It was used successfully on data from the Wel-fare Department of the State of Washington.In other areas, a well-publicized system isIBM’s ADVANCED SCOUT,a specialized data-min-ing system that helps National Basketball As-sociation (NBA) coaches organize and inter-pret data from NBA games (U.S. News 1995). ADVANCED SCOUT was used by several of the NBA teams in 1996, including the Seattle Su-personics, which reached the NBA finals.Finally, a novel and increasingly importanttype of discovery is one based on the use of in-telligent agents to navigate through an infor-mation-rich environment. Although the ideaof active triggers has long been analyzed in thedatabase field, really successful applications ofthis idea appeared only with the advent of theInternet. These systems ask the user to specifya profile of interest and search for related in-formation among a wide variety of public-do-main and proprietary sources. For example, FIREFLY is a personal music-recommendation agent: It asks a user his/her opinion of several music pieces and then suggests other music that the user might like (<http:// www.ffl/>). CRAYON(/>) allows users to create their own free newspaper (supported by ads); NEWSHOUND(<http://www. /hound/>) from the San Jose Mercury News and FARCAST(</> automatically search information from a wide variety of sources, including newspapers and wire services, and e-mail rele-vant documents directly to the user.These are just a few of the numerous suchsystems that use KDD techniques to automat-ically produce useful information from largemasses of raw data. See Piatetsky-Shapiro etal. (1996) for an overview of issues in devel-oping industrial KDD applications.Data Mining and KDDHistorically, the notion of finding useful pat-terns in data has been given a variety ofnames, including data mining, knowledge ex-traction, information discovery, informationharvesting, data archaeology, and data patternprocessing. The term data mining has mostlybeen used by statisticians, data analysts, andthe management information systems (MIS)communities. It has also gained popularity inthe database field. The phrase knowledge dis-covery in databases was coined at the first KDDworkshop in 1989 (Piatetsky-Shapiro 1991) toemphasize that knowledge is the end productof a data-driven discovery. It has been popular-ized in the AI and machine-learning fields.In our view, KDD refers to the overall pro-cess of discovering useful knowledge from da-ta, and data mining refers to a particular stepin this process. Data mining is the applicationof specific algorithms for extracting patternsfrom data. The distinction between the KDDprocess and the data-mining step (within theprocess) is a central point of this article. Theadditional steps in the KDD process, such asdata preparation, data selection, data cleaning,incorporation of appropriate prior knowledge,and proper interpretation of the results ofmining, are essential to ensure that usefulknowledge is derived from the data. Blind ap-plication of data-mining methods (rightly crit-icized as data dredging in the statistical litera-ture) can be a dangerous activity, easilyleading to the discovery of meaningless andinvalid patterns.The Interdisciplinary Nature of KDDKDD has evolved, and continues to evolve,from the intersection of research fields such asmachine learning, pattern recognition,databases, statistics, AI, knowledge acquisitionfor expert systems, data visualization, andhigh-performance computing. The unifyinggoal is extracting high-level knowledge fromlow-level data in the context of large data sets.The data-mining component of KDD cur-rently relies heavily on known techniquesfrom machine learning, pattern recognition,and statistics to find patterns from data in thedata-mining step of the KDD process. A natu-ral question is, How is KDD different from pat-tern recognition or machine learning (and re-lated fields)? The answer is that these fieldsprovide some of the data-mining methodsthat are used in the data-mining step of theKDD process. KDD focuses on the overall pro-cess of knowledge discovery from data, includ-ing how the data are stored and accessed, howalgorithms can be scaled to massive data setsThe basicproblemaddressed bythe KDDprocess isone ofmappinglow-leveldata intoother formsthat might bemorecompact,moreabstract,or moreuseful.ArticlesFALL 1996 39A driving force behind KDD is the database field (the second D in KDD). Indeed, the problem of effective data manipulation when data cannot fit in the main memory is of fun-damental importance to KDD. Database tech-niques for gaining efficient data access,grouping and ordering operations when ac-cessing data, and optimizing queries consti-tute the basics for scaling algorithms to larger data sets. Most data-mining algorithms from statistics, pattern recognition, and machine learning assume data are in the main memo-ry and pay no attention to how the algorithm breaks down if only limited views of the data are possible.A related field evolving from databases is data warehousing,which refers to the popular business trend of collecting and cleaning transactional data to make them available for online analysis and decision support. Data warehousing helps set the stage for KDD in two important ways: (1) data cleaning and (2)data access.Data cleaning: As organizations are forced to think about a unified logical view of the wide variety of data and databases they pos-sess, they have to address the issues of map-ping data to a single naming convention,uniformly representing and handling missing data, and handling noise and errors when possible.Data access: Uniform and well-defined methods must be created for accessing the da-ta and providing access paths to data that were historically difficult to get to (for exam-ple, stored offline).Once organizations and individuals have solved the problem of how to store and ac-cess their data, the natural next step is the question, What else do we do with all the da-ta? This is where opportunities for KDD natu-rally arise.A popular approach for analysis of data warehouses is called online analytical processing (OLAP), named for a set of principles pro-posed by Codd (1993). OLAP tools focus on providing multidimensional data analysis,which is superior to SQL in computing sum-maries and breakdowns along many dimen-sions. OLAP tools are targeted toward simpli-fying and supporting interactive data analysis,but the goal of KDD tools is to automate as much of the process as possible. Thus, KDD is a step beyond what is currently supported by most standard database systems.Basic DefinitionsKDD is the nontrivial process of identifying valid, novel, potentially useful, and ultimate-and still run efficiently, how results can be in-terpreted and visualized, and how the overall man-machine interaction can usefully be modeled and supported. The KDD process can be viewed as a multidisciplinary activity that encompasses techniques beyond the scope of any one particular discipline such as machine learning. In this context, there are clear opportunities for other fields of AI (be-sides machine learning) to contribute to KDD. KDD places a special emphasis on find-ing understandable patterns that can be inter-preted as useful or interesting knowledge.Thus, for example, neural networks, although a powerful modeling tool, are relatively difficult to understand compared to decision trees. KDD also emphasizes scaling and ro-bustness properties of modeling algorithms for large noisy data sets.Related AI research fields include machine discovery, which targets the discovery of em-pirical laws from observation and experimen-tation (Shrager and Langley 1990) (see Kloes-gen and Zytkow [1996] for a glossary of terms common to KDD and machine discovery),and causal modeling for the inference of causal models from data (Spirtes, Glymour,and Scheines 1993). Statistics in particular has much in common with KDD (see Elder and Pregibon [1996] and Glymour et al.[1996] for a more detailed discussion of this synergy). Knowledge discovery from data is fundamentally a statistical endeavor. Statistics provides a language and framework for quan-tifying the uncertainty that results when one tries to infer general patterns from a particu-lar sample of an overall population. As men-tioned earlier, the term data mining has had negative connotations in statistics since the 1960s when computer-based data analysis techniques were first introduced. The concern arose because if one searches long enough in any data set (even randomly generated data),one can find patterns that appear to be statis-tically significant but, in fact, are not. Clearly,this issue is of fundamental importance to KDD. Substantial progress has been made in recent years in understanding such issues in statistics. Much of this work is of direct rele-vance to KDD. Thus, data mining is a legiti-mate activity as long as one understands how to do it correctly; data mining carried out poorly (without regard to the statistical as-pects of the problem) is to be avoided. KDD can also be viewed as encompassing a broader view of modeling than statistics. KDD aims to provide tools to automate (to the degree pos-sible) the entire process of data analysis and the statistician’s “art” of hypothesis selection.Data mining is a step in the KDD process that consists of ap-plying data analysis and discovery al-gorithms that produce a par-ticular enu-meration ofpatterns (or models)over the data.Articles40AI MAGAZINEly understandable patterns in data (Fayyad, Piatetsky-Shapiro, and Smyth 1996).Here, data are a set of facts (for example, cases in a database), and pattern is an expres-sion in some language describing a subset of the data or a model applicable to the subset. Hence, in our usage here, extracting a pattern also designates fitting a model to data; find-ing structure from data; or, in general, mak-ing any high-level description of a set of data. The term process implies that KDD comprises many steps, which involve data preparation, search for patterns, knowledge evaluation, and refinement, all repeated in multiple itera-tions. By nontrivial, we mean that some search or inference is involved; that is, it is not a straightforward computation of predefined quantities like computing the av-erage value of a set of numbers.The discovered patterns should be valid on new data with some degree of certainty. We also want patterns to be novel (at least to the system and preferably to the user) and poten-tially useful, that is, lead to some benefit to the user or task. Finally, the patterns should be understandable, if not immediately then after some postprocessing.The previous discussion implies that we can define quantitative measures for evaluating extracted patterns. In many cases, it is possi-ble to define measures of certainty (for exam-ple, estimated prediction accuracy on new data) or utility (for example, gain, perhaps indollars saved because of better predictions orspeedup in response time of a system). No-tions such as novelty and understandabilityare much more subjective. In certain contexts,understandability can be estimated by sim-plicity (for example, the number of bits to de-scribe a pattern). An important notion, calledinterestingness(for example, see Silberschatzand Tuzhilin [1995] and Piatetsky-Shapiro andMatheus [1994]), is usually taken as an overallmeasure of pattern value, combining validity,novelty, usefulness, and simplicity. Interest-ingness functions can be defined explicitly orcan be manifested implicitly through an or-dering placed by the KDD system on the dis-covered patterns or models.Given these notions, we can consider apattern to be knowledge if it exceeds some in-terestingness threshold, which is by nomeans an attempt to define knowledge in thephilosophical or even the popular view. As amatter of fact, knowledge in this definition ispurely user oriented and domain specific andis determined by whatever functions andthresholds the user chooses.Data mining is a step in the KDD processthat consists of applying data analysis anddiscovery algorithms that, under acceptablecomputational efficiency limitations, pro-duce a particular enumeration of patterns (ormodels) over the data. Note that the space ofArticlesFALL 1996 41Figure 1. An Overview of the Steps That Compose the KDD Process.methods, the effective number of variables under consideration can be reduced, or in-variant representations for the data can be found.Fifth is matching the goals of the KDD pro-cess (step 1) to a particular data-mining method. For example, summarization, clas-sification, regression, clustering, and so on,are described later as well as in Fayyad, Piatet-sky-Shapiro, and Smyth (1996).Sixth is exploratory analysis and model and hypothesis selection: choosing the data-mining algorithm(s) and selecting method(s)to be used for searching for data patterns.This process includes deciding which models and parameters might be appropriate (for ex-ample, models of categorical data are differ-ent than models of vectors over the reals) and matching a particular data-mining method with the overall criteria of the KDD process (for example, the end user might be more in-terested in understanding the model than its predictive capabilities).Seventh is data mining: searching for pat-terns of interest in a particular representa-tional form or a set of such representations,including classification rules or trees, regres-sion, and clustering. The user can significant-ly aid the data-mining method by correctly performing the preceding steps.Eighth is interpreting mined patterns, pos-sibly returning to any of steps 1 through 7 for further iteration. This step can also involve visualization of the extracted patterns and models or visualization of the data given the extracted models.Ninth is acting on the discovered knowl-edge: using the knowledge directly, incorpo-rating the knowledge into another system for further action, or simply documenting it and reporting it to interested parties. This process also includes checking for and resolving po-tential conflicts with previously believed (or extracted) knowledge.The KDD process can involve significant iteration and can contain loops between any two steps. The basic flow of steps (al-though not the potential multitude of itera-tions and loops) is illustrated in figure 1.Most previous work on KDD has focused on step 7, the data mining. However, the other steps are as important (and probably more so) for the successful application of KDD in practice. Having defined the basic notions and introduced the KDD process, we now focus on the data-mining component,which has, by far, received the most atten-tion in the literature.patterns is often infinite, and the enumera-tion of patterns involves some form of search in this space. Practical computational constraints place severe limits on the sub-space that can be explored by a data-mining algorithm.The KDD process involves using the database along with any required selection,preprocessing, subsampling, and transforma-tions of it; applying data-mining methods (algorithms) to enumerate patterns from it;and evaluating the products of data mining to identify the subset of the enumerated pat-terns deemed knowledge. The data-mining component of the KDD process is concerned with the algorithmic means by which pat-terns are extracted and enumerated from da-ta. The overall KDD process (figure 1) in-cludes the evaluation and possible interpretation of the mined patterns to de-termine which patterns can be considered new knowledge. The KDD process also in-cludes all the additional steps described in the next section.The notion of an overall user-driven pro-cess is not unique to KDD: analogous propos-als have been put forward both in statistics (Hand 1994) and in machine learning (Brod-ley and Smyth 1996).The KDD ProcessThe KDD process is interactive and iterative,involving numerous steps with many deci-sions made by the user. Brachman and Anand (1996) give a practical view of the KDD pro-cess, emphasizing the interactive nature of the process. Here, we broadly outline some of its basic steps:First is developing an understanding of the application domain and the relevant prior knowledge and identifying the goal of the KDD process from the customer’s viewpoint.Second is creating a target data set: select-ing a data set, or focusing on a subset of vari-ables or data samples, on which discovery is to be performed.Third is data cleaning and preprocessing.Basic operations include removing noise if appropriate, collecting the necessary informa-tion to model or account for noise, deciding on strategies for handling missing data fields,and accounting for time-sequence informa-tion and known changes.Fourth is data reduction and projection:finding useful features to represent the data depending on the goal of the task. With di-mensionality reduction or transformationArticles42AI MAGAZINEThe Data-Mining Stepof the KDD ProcessThe data-mining component of the KDD pro-cess often involves repeated iterative applica-tion of particular data-mining methods. This section presents an overview of the primary goals of data mining, a description of the methods used to address these goals, and a brief description of the data-mining algo-rithms that incorporate these methods.The knowledge discovery goals are defined by the intended use of the system. We can distinguish two types of goals: (1) verification and (2) discovery. With verification,the sys-tem is limited to verifying the user’s hypothe-sis. With discovery,the system autonomously finds new patterns. We further subdivide the discovery goal into prediction,where the sys-tem finds patterns for predicting the future behavior of some entities, and description, where the system finds patterns for presenta-tion to a user in a human-understandableform. In this article, we are primarily con-cerned with discovery-oriented data mining.Data mining involves fitting models to, or determining patterns from, observed data. The fitted models play the role of inferred knowledge: Whether the models reflect useful or interesting knowledge is part of the over-all, interactive KDD process where subjective human judgment is typically required. Two primary mathematical formalisms are used in model fitting: (1) statistical and (2) logical. The statistical approach allows for nondeter-ministic effects in the model, whereas a logi-cal model is purely deterministic. We focus primarily on the statistical approach to data mining, which tends to be the most widely used basis for practical data-mining applica-tions given the typical presence of uncertain-ty in real-world data-generating processes.Most data-mining methods are based on tried and tested techniques from machine learning, pattern recognition, and statistics: classification, clustering, regression, and so on. The array of different algorithms under each of these headings can often be bewilder-ing to both the novice and the experienced data analyst. It should be emphasized that of the many data-mining methods advertised in the literature, there are really only a few fun-damental techniques. The actual underlying model representation being used by a particu-lar method typically comes from a composi-tion of a small number of well-known op-tions: polynomials, splines, kernel and basis functions, threshold-Boolean functions, and so on. Thus, algorithms tend to differ primar-ily in the goodness-of-fit criterion used toevaluate model fit or in the search methodused to find a good fit.In our brief overview of data-mining meth-ods, we try in particular to convey the notionthat most (if not all) methods can be viewedas extensions or hybrids of a few basic tech-niques and principles. We first discuss the pri-mary methods of data mining and then showthat the data- mining methods can be viewedas consisting of three primary algorithmiccomponents: (1) model representation, (2)model evaluation, and (3) search. In the dis-cussion of KDD and data-mining methods,we use a simple example to make some of thenotions more concrete. Figure 2 shows a sim-ple two-dimensional artificial data set consist-ing of 23 cases. Each point on the graph rep-resents a person who has been given a loanby a particular bank at some time in the past.The horizontal axis represents the income ofthe person; the vertical axis represents the to-tal personal debt of the person (mortgage, carpayments, and so on). The data have beenclassified into two classes: (1) the x’s repre-sent persons who have defaulted on theirloans and (2) the o’s represent persons whoseloans are in good status with the bank. Thus,this simple artificial data set could represent ahistorical data set that can contain usefulknowledge from the point of view of thebank making the loans. Note that in actualKDD applications, there are typically manymore dimensions (as many as several hun-dreds) and many more data points (manythousands or even millions).ArticlesFALL 1996 43Figure 2. A Simple Data Set with Two Classes Used for Illustrative Purposes.。

A Survey of Clustering Data Mining TechniquesPavel BerkhinYahoo!,Inc.pberkhin@Summary.Clustering is the division of data into groups of similar objects.It dis-regards some details in exchange for data simplifirmally,clustering can be viewed as data modeling concisely summarizing the data,and,therefore,it re-lates to many disciplines from statistics to numerical analysis.Clustering plays an important role in a broad range of applications,from information retrieval to CRM. Such applications usually deal with large datasets and many attributes.Exploration of such data is a subject of data mining.This survey concentrates on clustering algorithms from a data mining perspective.1IntroductionThe goal of this survey is to provide a comprehensive review of different clus-tering techniques in data mining.Clustering is a division of data into groups of similar objects.Each group,called a cluster,consists of objects that are similar to one another and dissimilar to objects of other groups.When repre-senting data with fewer clusters necessarily loses certainfine details(akin to lossy data compression),but achieves simplification.It represents many data objects by few clusters,and hence,it models data by its clusters.Data mod-eling puts clustering in a historical perspective rooted in mathematics,sta-tistics,and numerical analysis.From a machine learning perspective clusters correspond to hidden patterns,the search for clusters is unsupervised learn-ing,and the resulting system represents a data concept.Therefore,clustering is unsupervised learning of a hidden data concept.Data mining applications add to a general picture three complications:(a)large databases,(b)many attributes,(c)attributes of different types.This imposes on a data analysis se-vere computational requirements.Data mining applications include scientific data exploration,information retrieval,text mining,spatial databases,Web analysis,CRM,marketing,medical diagnostics,computational biology,and many others.They present real challenges to classic clustering algorithms. These challenges led to the emergence of powerful broadly applicable data2Pavel Berkhinmining clustering methods developed on the foundation of classic techniques.They are subject of this survey.1.1NotationsTo fix the context and clarify terminology,consider a dataset X consisting of data points (i.e.,objects ,instances ,cases ,patterns ,tuples ,transactions )x i =(x i 1,···,x id ),i =1:N ,in attribute space A ,where each component x il ∈A l ,l =1:d ,is a numerical or nominal categorical attribute (i.e.,feature ,variable ,dimension ,component ,field ).For a discussion of attribute data types see [106].Such point-by-attribute data format conceptually corresponds to a N ×d matrix and is used by a majority of algorithms reviewed below.However,data of other formats,such as variable length sequences and heterogeneous data,are not uncommon.The simplest subset in an attribute space is a direct Cartesian product of sub-ranges C = C l ⊂A ,C l ⊂A l ,called a segment (i.e.,cube ,cell ,region ).A unit is an elementary segment whose sub-ranges consist of a single category value,or of a small numerical bin.Describing the numbers of data points per every unit represents an extreme case of clustering,a histogram .This is a very expensive representation,and not a very revealing er driven segmentation is another commonly used practice in data exploration that utilizes expert knowledge regarding the importance of certain sub-domains.Unlike segmentation,clustering is assumed to be automatic,and so it is a machine learning technique.The ultimate goal of clustering is to assign points to a finite system of k subsets (clusters).Usually (but not always)subsets do not intersect,and their union is equal to a full dataset with the possible exception of outliersX =C 1 ··· C k C outliers ,C i C j =0,i =j.1.2Clustering Bibliography at GlanceGeneral references regarding clustering include [110],[205],[116],[131],[63],[72],[165],[119],[75],[141],[107],[91].A very good introduction to contem-porary data mining clustering techniques can be found in the textbook [106].There is a close relationship between clustering and many other fields.Clustering has always been used in statistics [10]and science [158].The clas-sic introduction into pattern recognition framework is given in [64].Typical applications include speech and character recognition.Machine learning clus-tering algorithms were applied to image segmentation and computer vision[117].For statistical approaches to pattern recognition see [56]and [85].Clus-tering can be viewed as a density estimation problem.This is the subject of traditional multivariate statistical estimation [197].Clustering is also widelyA Survey of Clustering Data Mining Techniques3 used for data compression in image processing,which is also known as vec-tor quantization[89].Datafitting in numerical analysis provides still another venue in data modeling[53].This survey’s emphasis is on clustering in data mining.Such clustering is characterized by large datasets with many attributes of different types. Though we do not even try to review particular applications,many important ideas are related to the specificfields.Clustering in data mining was brought to life by intense developments in information retrieval and text mining[52], [206],[58],spatial database applications,for example,GIS or astronomical data,[223],[189],[68],sequence and heterogeneous data analysis[43],Web applications[48],[111],[81],DNA analysis in computational biology[23],and many others.They resulted in a large amount of application-specific devel-opments,but also in some general techniques.These techniques and classic clustering algorithms that relate to them are surveyed below.1.3Plan of Further PresentationClassification of clustering algorithms is neither straightforward,nor canoni-cal.In reality,different classes of algorithms overlap.Traditionally clustering techniques are broadly divided in hierarchical and partitioning.Hierarchical clustering is further subdivided into agglomerative and divisive.The basics of hierarchical clustering include Lance-Williams formula,idea of conceptual clustering,now classic algorithms SLINK,COBWEB,as well as newer algo-rithms CURE and CHAMELEON.We survey these algorithms in the section Hierarchical Clustering.While hierarchical algorithms gradually(dis)assemble points into clusters (as crystals grow),partitioning algorithms learn clusters directly.In doing so they try to discover clusters either by iteratively relocating points between subsets,or by identifying areas heavily populated with data.Algorithms of thefirst kind are called Partitioning Relocation Clustering. They are further classified into probabilistic clustering(EM framework,al-gorithms SNOB,AUTOCLASS,MCLUST),k-medoids methods(algorithms PAM,CLARA,CLARANS,and its extension),and k-means methods(differ-ent schemes,initialization,optimization,harmonic means,extensions).Such methods concentrate on how well pointsfit into their clusters and tend to build clusters of proper convex shapes.Partitioning algorithms of the second type are surveyed in the section Density-Based Partitioning.They attempt to discover dense connected com-ponents of data,which areflexible in terms of their shape.Density-based connectivity is used in the algorithms DBSCAN,OPTICS,DBCLASD,while the algorithm DENCLUE exploits space density functions.These algorithms are less sensitive to outliers and can discover clusters of irregular shape.They usually work with low-dimensional numerical data,known as spatial data. Spatial objects could include not only points,but also geometrically extended objects(algorithm GDBSCAN).4Pavel BerkhinSome algorithms work with data indirectly by constructing summaries of data over the attribute space subsets.They perform space segmentation and then aggregate appropriate segments.We discuss them in the section Grid-Based Methods.They frequently use hierarchical agglomeration as one phase of processing.Algorithms BANG,STING,WaveCluster,and FC are discussed in this section.Grid-based methods are fast and handle outliers well.Grid-based methodology is also used as an intermediate step in many other algorithms (for example,CLIQUE,MAFIA).Categorical data is intimately connected with transactional databases.The concept of a similarity alone is not sufficient for clustering such data.The idea of categorical data co-occurrence comes to the rescue.The algorithms ROCK,SNN,and CACTUS are surveyed in the section Co-Occurrence of Categorical Data.The situation gets even more aggravated with the growth of the number of items involved.To help with this problem the effort is shifted from data clustering to pre-clustering of items or categorical attribute values. Development based on hyper-graph partitioning and the algorithm STIRR exemplify this approach.Many other clustering techniques are developed,primarily in machine learning,that either have theoretical significance,are used traditionally out-side the data mining community,or do notfit in previously outlined categories. The boundary is blurred.In the section Other Developments we discuss the emerging direction of constraint-based clustering,the important researchfield of graph partitioning,and the relationship of clustering to supervised learning, gradient descent,artificial neural networks,and evolutionary methods.Data Mining primarily works with large databases.Clustering large datasets presents scalability problems reviewed in the section Scalability and VLDB Extensions.Here we talk about algorithms like DIGNET,about BIRCH and other data squashing techniques,and about Hoffding or Chernoffbounds.Another trait of real-life data is high dimensionality.Corresponding de-velopments are surveyed in the section Clustering High Dimensional Data. The trouble comes from a decrease in metric separation when the dimension grows.One approach to dimensionality reduction uses attributes transforma-tions(DFT,PCA,wavelets).Another way to address the problem is through subspace clustering(algorithms CLIQUE,MAFIA,ENCLUS,OPTIGRID, PROCLUS,ORCLUS).Still another approach clusters attributes in groups and uses their derived proxies to cluster objects.This double clustering is known as co-clustering.Issues common to different clustering methods are overviewed in the sec-tion General Algorithmic Issues.We talk about assessment of results,de-termination of appropriate number of clusters to build,data preprocessing, proximity measures,and handling of outliers.For reader’s convenience we provide a classification of clustering algorithms closely followed by this survey:•Hierarchical MethodsA Survey of Clustering Data Mining Techniques5Agglomerative AlgorithmsDivisive Algorithms•Partitioning Relocation MethodsProbabilistic ClusteringK-medoids MethodsK-means Methods•Density-Based Partitioning MethodsDensity-Based Connectivity ClusteringDensity Functions Clustering•Grid-Based Methods•Methods Based on Co-Occurrence of Categorical Data•Other Clustering TechniquesConstraint-Based ClusteringGraph PartitioningClustering Algorithms and Supervised LearningClustering Algorithms in Machine Learning•Scalable Clustering Algorithms•Algorithms For High Dimensional DataSubspace ClusteringCo-Clustering Techniques1.4Important IssuesThe properties of clustering algorithms we are primarily concerned with in data mining include:•Type of attributes algorithm can handle•Scalability to large datasets•Ability to work with high dimensional data•Ability tofind clusters of irregular shape•Handling outliers•Time complexity(we frequently simply use the term complexity)•Data order dependency•Labeling or assignment(hard or strict vs.soft or fuzzy)•Reliance on a priori knowledge and user defined parameters •Interpretability of resultsRealistically,with every algorithm we discuss only some of these properties. The list is in no way exhaustive.For example,as appropriate,we also discuss algorithms ability to work in pre-defined memory buffer,to restart,and to provide an intermediate solution.6Pavel Berkhin2Hierarchical ClusteringHierarchical clustering builds a cluster hierarchy or a tree of clusters,also known as a dendrogram.Every cluster node contains child clusters;sibling clusters partition the points covered by their common parent.Such an ap-proach allows exploring data on different levels of granularity.Hierarchical clustering methods are categorized into agglomerative(bottom-up)and divi-sive(top-down)[116],[131].An agglomerative clustering starts with one-point (singleton)clusters and recursively merges two or more of the most similar clusters.A divisive clustering starts with a single cluster containing all data points and recursively splits the most appropriate cluster.The process contin-ues until a stopping criterion(frequently,the requested number k of clusters) is achieved.Advantages of hierarchical clustering include:•Flexibility regarding the level of granularity•Ease of handling any form of similarity or distance•Applicability to any attribute typesDisadvantages of hierarchical clustering are related to:•Vagueness of termination criteria•Most hierarchical algorithms do not revisit(intermediate)clusters once constructed.The classic approaches to hierarchical clustering are presented in the sub-section Linkage Metrics.Hierarchical clustering based on linkage metrics re-sults in clusters of proper(convex)shapes.Active contemporary efforts to build cluster systems that incorporate our intuitive concept of clusters as con-nected components of arbitrary shape,including the algorithms CURE and CHAMELEON,are surveyed in the subsection Hierarchical Clusters of Arbi-trary Shapes.Divisive techniques based on binary taxonomies are presented in the subsection Binary Divisive Partitioning.The subsection Other Devel-opments contains information related to incremental learning,model-based clustering,and cluster refinement.In hierarchical clustering our regular point-by-attribute data representa-tion frequently is of secondary importance.Instead,hierarchical clustering frequently deals with the N×N matrix of distances(dissimilarities)or sim-ilarities between training points sometimes called a connectivity matrix.So-called linkage metrics are constructed from elements of this matrix.The re-quirement of keeping a connectivity matrix in memory is unrealistic.To relax this limitation different techniques are used to sparsify(introduce zeros into) the connectivity matrix.This can be done by omitting entries smaller than a certain threshold,by using only a certain subset of data representatives,or by keeping with each point only a certain number of its nearest neighbors(for nearest neighbor chains see[177]).Notice that the way we process the original (dis)similarity matrix and construct a linkage metric reflects our a priori ideas about the data model.A Survey of Clustering Data Mining Techniques7With the(sparsified)connectivity matrix we can associate the weighted connectivity graph G(X,E)whose vertices X are data points,and edges E and their weights are defined by the connectivity matrix.This establishes a connection between hierarchical clustering and graph partitioning.One of the most striking developments in hierarchical clustering is the algorithm BIRCH.It is discussed in the section Scalable VLDB Extensions.Hierarchical clustering initializes a cluster system as a set of singleton clusters(agglomerative case)or a single cluster of all points(divisive case) and proceeds iteratively merging or splitting the most appropriate cluster(s) until the stopping criterion is achieved.The appropriateness of a cluster(s) for merging or splitting depends on the(dis)similarity of cluster(s)elements. This reflects a general presumption that clusters consist of similar points.An important example of dissimilarity between two points is the distance between them.To merge or split subsets of points rather than individual points,the dis-tance between individual points has to be generalized to the distance between subsets.Such a derived proximity measure is called a linkage metric.The type of a linkage metric significantly affects hierarchical algorithms,because it re-flects a particular concept of closeness and connectivity.Major inter-cluster linkage metrics[171],[177]include single link,average link,and complete link. The underlying dissimilarity measure(usually,distance)is computed for every pair of nodes with one node in thefirst set and another node in the second set.A specific operation such as minimum(single link),average(average link),or maximum(complete link)is applied to pair-wise dissimilarity measures:d(C1,C2)=Op{d(x,y),x∈C1,y∈C2}Early examples include the algorithm SLINK[199],which implements single link(Op=min),Voorhees’method[215],which implements average link (Op=Avr),and the algorithm CLINK[55],which implements complete link (Op=max).It is related to the problem offinding the Euclidean minimal spanning tree[224]and has O(N2)complexity.The methods using inter-cluster distances defined in terms of pairs of nodes(one in each respective cluster)are called graph methods.They do not use any cluster representation other than a set of points.This name naturally relates to the connectivity graph G(X,E)introduced above,because every data partition corresponds to a graph partition.Such methods can be augmented by so-called geometric methods in which a cluster is represented by its central point.Under the assumption of numerical attributes,the center point is defined as a centroid or an average of two cluster centroids subject to agglomeration.It results in centroid,median,and minimum variance linkage metrics.All of the above linkage metrics can be derived from the Lance-Williams updating formula[145],d(C iC j,C k)=a(i)d(C i,C k)+a(j)d(C j,C k)+b·d(C i,C j)+c|d(C i,C k)−d(C j,C k)|.8Pavel BerkhinHere a,b,c are coefficients corresponding to a particular linkage.This formula expresses a linkage metric between a union of the two clusters and the third cluster in terms of underlying nodes.The Lance-Williams formula is crucial to making the dis(similarity)computations feasible.Surveys of linkage metrics can be found in [170][54].When distance is used as a base measure,linkage metrics capture inter-cluster proximity.However,a similarity-based view that results in intra-cluster connectivity considerations is also used,for example,in the original average link agglomeration (Group-Average Method)[116].Under reasonable assumptions,such as reducibility condition (graph meth-ods satisfy this condition),linkage metrics methods suffer from O N 2 time complexity [177].Despite the unfavorable time complexity,these algorithms are widely used.As an example,the algorithm AGNES (AGlomerative NESt-ing)[131]is used in S-Plus.When the connectivity N ×N matrix is sparsified,graph methods directly dealing with the connectivity graph G can be used.In particular,hierarchical divisive MST (Minimum Spanning Tree)algorithm is based on graph parti-tioning [116].2.1Hierarchical Clusters of Arbitrary ShapesFor spatial data,linkage metrics based on Euclidean distance naturally gener-ate clusters of convex shapes.Meanwhile,visual inspection of spatial images frequently discovers clusters with curvy appearance.Guha et al.[99]introduced the hierarchical agglomerative clustering algo-rithm CURE (Clustering Using REpresentatives).This algorithm has a num-ber of novel features of general importance.It takes special steps to handle outliers and to provide labeling in assignment stage.It also uses two techniques to achieve scalability:data sampling (section 8),and data partitioning.CURE creates p partitions,so that fine granularity clusters are constructed in parti-tions first.A major feature of CURE is that it represents a cluster by a fixed number,c ,of points scattered around it.The distance between two clusters used in the agglomerative process is the minimum of distances between two scattered representatives.Therefore,CURE takes a middle approach between the graph (all-points)methods and the geometric (one centroid)methods.Single and average link closeness are replaced by representatives’aggregate closeness.Selecting representatives scattered around a cluster makes it pos-sible to cover non-spherical shapes.As before,agglomeration continues until the requested number k of clusters is achieved.CURE employs one additional trick:originally selected scattered points are shrunk to the geometric centroid of the cluster by a user-specified factor α.Shrinkage suppresses the affect of outliers;outliers happen to be located further from the cluster centroid than the other scattered representatives.CURE is capable of finding clusters of different shapes and sizes,and it is insensitive to outliers.Because CURE uses sampling,estimation of its complexity is not straightforward.For low-dimensional data authors provide a complexity estimate of O (N 2sample )definedA Survey of Clustering Data Mining Techniques9 in terms of a sample size.More exact bounds depend on input parameters: shrink factorα,number of representative points c,number of partitions p,and a sample size.Figure1(a)illustrates agglomeration in CURE.Three clusters, each with three representatives,are shown before and after the merge and shrinkage.Two closest representatives are connected.While the algorithm CURE works with numerical attributes(particularly low dimensional spatial data),the algorithm ROCK developed by the same researchers[100]targets hierarchical agglomerative clustering for categorical attributes.It is reviewed in the section Co-Occurrence of Categorical Data.The hierarchical agglomerative algorithm CHAMELEON[127]uses the connectivity graph G corresponding to the K-nearest neighbor model spar-sification of the connectivity matrix:the edges of K most similar points to any given point are preserved,the rest are pruned.CHAMELEON has two stages.In thefirst stage small tight clusters are built to ignite the second stage.This involves a graph partitioning[129].In the second stage agglomer-ative process is performed.It utilizes measures of relative inter-connectivity RI(C i,C j)and relative closeness RC(C i,C j);both are locally normalized by internal interconnectivity and closeness of clusters C i and C j.In this sense the modeling is dynamic:it depends on data locally.Normalization involves certain non-obvious graph operations[129].CHAMELEON relies heavily on graph partitioning implemented in the library HMETIS(see the section6). Agglomerative process depends on user provided thresholds.A decision to merge is made based on the combinationRI(C i,C j)·RC(C i,C j)αof local measures.The algorithm does not depend on assumptions about the data model.It has been proven tofind clusters of different shapes,densities, and sizes in2D(two-dimensional)space.It has a complexity of O(Nm+ Nlog(N)+m2log(m),where m is the number of sub-clusters built during the first initialization phase.Figure1(b)(analogous to the one in[127])clarifies the difference with CURE.It presents a choice of four clusters(a)-(d)for a merge.While CURE would merge clusters(a)and(b),CHAMELEON makes intuitively better choice of merging(c)and(d).2.2Binary Divisive PartitioningIn linguistics,information retrieval,and document clustering applications bi-nary taxonomies are very useful.Linear algebra methods,based on singular value decomposition(SVD)are used for this purpose in collaborativefilter-ing and information retrieval[26].Application of SVD to hierarchical divisive clustering of document collections resulted in the PDDP(Principal Direction Divisive Partitioning)algorithm[31].In our notations,object x is a docu-ment,l th attribute corresponds to a word(index term),and a matrix X entry x il is a measure(e.g.TF-IDF)of l-term frequency in a document x.PDDP constructs SVD decomposition of the matrix10Pavel Berkhin(a)Algorithm CURE (b)Algorithm CHAMELEONFig.1.Agglomeration in Clusters of Arbitrary Shapes(X −e ¯x ),¯x =1Ni =1:N x i ,e =(1,...,1)T .This algorithm bisects data in Euclidean space by a hyperplane that passes through data centroid orthogonal to the eigenvector with the largest singular value.A k -way split is also possible if the k largest singular values are consid-ered.Bisecting is a good way to categorize documents and it yields a binary tree.When k -means (2-means)is used for bisecting,the dividing hyperplane is orthogonal to the line connecting the two centroids.The comparative study of SVD vs.k -means approaches [191]can be used for further references.Hier-archical divisive bisecting k -means was proven [206]to be preferable to PDDP for document clustering.While PDDP or 2-means are concerned with how to split a cluster,the problem of which cluster to split is also important.Simple strategies are:(1)split each node at a given level,(2)split the cluster with highest cardinality,and,(3)split the cluster with the largest intra-cluster variance.All three strategies have problems.For a more detailed analysis of this subject and better strategies,see [192].2.3Other DevelopmentsOne of early agglomerative clustering algorithms,Ward’s method [222],is based not on linkage metric,but on an objective function used in k -means.The merger decision is viewed in terms of its effect on the objective function.The popular hierarchical clustering algorithm for categorical data COB-WEB [77]has two very important qualities.First,it utilizes incremental learn-ing.Instead of following divisive or agglomerative approaches,it dynamically builds a dendrogram by processing one data point at a time.Second,COB-WEB is an example of conceptual or model-based learning.This means that each cluster is considered as a model that can be described intrinsically,rather than as a collection of points assigned to it.COBWEB’s dendrogram is calleda classification tree.Each tree node(cluster)C is associated with the condi-tional probabilities for categorical attribute-values pairs,P r(x l=νlp|C),l=1:d,p=1:|A l|.This easily can be recognized as a C-specific Na¨ıve Bayes classifier.During the classification tree construction,every new point is descended along the tree and the tree is potentially updated(by an insert/split/merge/create op-eration).Decisions are based on the category utility[49]CU{C1,...,C k}=1j=1:kCU(C j)CU(C j)=l,p(P r(x l=νlp|C j)2−(P r(x l=νlp)2.Category utility is similar to the GINI index.It rewards clusters C j for in-creases in predictability of the categorical attribute valuesνlp.Being incre-mental,COBWEB is fast with a complexity of O(tN),though it depends non-linearly on tree characteristics packed into a constant t.There is a similar incremental hierarchical algorithm for all numerical attributes called CLAS-SIT[88].CLASSIT associates normal distributions with cluster nodes.Both algorithms can result in highly unbalanced trees.Chiu et al.[47]proposed another conceptual or model-based approach to hierarchical clustering.This development contains several different use-ful features,such as the extension of scalability preprocessing to categori-cal attributes,outliers handling,and a two-step strategy for monitoring the number of clusters including BIC(defined below).A model associated with a cluster covers both numerical and categorical attributes and constitutes a blend of Gaussian and multinomial models.Denote corresponding multivari-ate parameters byθ.With every cluster C we associate a logarithm of its (classification)likelihoodl C=x i∈Clog(p(x i|θ))The algorithm uses maximum likelihood estimates for parameterθ.The dis-tance between two clusters is defined(instead of linkage metric)as a decrease in log-likelihoodd(C1,C2)=l C1+l C2−l C1∪C2caused by merging of the two clusters under consideration.The agglomerative process continues until the stopping criterion is satisfied.As such,determina-tion of the best k is automatic.This algorithm has the commercial implemen-tation(in SPSS Clementine).The complexity of the algorithm is linear in N for the summarization phase.Traditional hierarchical clustering does not change points membership in once assigned clusters due to its greedy approach:after a merge or a split is selected it is not refined.Though COBWEB does reconsider its decisions,its。

基于Log-Euclidean词袋模型与基于Stein核稀疏编码的人体行为识别算法的优化与改进随着人工智能和计算机视觉技术的发展，人体行为识别技术在智能监控、安全防范、智能交通等领域具有广泛的应用前景。

目前，基于Log-Euclidean词袋模型与基于Stein核稀疏编码的人体行为识别算法已经被广泛研究和应用。

这些算法在一些实际应用场景中还存在一些问题，如识别精度不高、运行效率低等。

本文将针对这些问题进行优化与改进，以提高人体行为识别算法的性能和实用性。

一、Log-Euclidean词袋模型的优化与改进Log-Euclidean词袋模型是一种常用于人体行为识别的特征提取方法，它可以将图像数据转化为向量形式，然后通过分类器进行训练和识别。

传统的Log-Euclidean词袋模型在处理大规模数据时存在计算复杂度高、识别精度不高等问题。

我们可以通过以下方式进行优化和改进：1. 采用分层词袋模型：在传统的词袋模型中，特征提取和词汇识别是分开进行的，这样会导致词袋模型对局部特征的捕获并不够充分。

我们可以采用分层词袋模型，将特征提取和词汇识别过程进行融合，从而提高对局部特征的表达能力。

2. 使用深度学习进行特征学习：深度学习在图像处理领域取得了很大的成功，可以通过深度学习网络进行特征学习，从而提高特征的抽取能力。

我们可以将深度学习网络与Log-Euclidean词袋模型进行结合，从而提高算法的识别精度和鲁棒性。

二、基于Stein核稀疏编码的优化与改进Stein核稀疏编码是一种基于核方法的特征提取和分类算法，它可以通过学习数据的稀疏表示来实现对数据的有效表达和识别。

传统的Stein核稀疏编码在处理高维数据和大规模数据时存在计算复杂度高、运行效率低等问题。

我们可以通过以下方式进行优化和改进：1. 使用快速算法进行训练和识别：传统的Stein核稀疏编码算法通常需要对整个数据集进行全局学习，这样会导致计算复杂度较高。

专利名称：基于多分辨率分形特征的神经树突棘图像分类方法专利类型：发明专利
发明人：张百灵,张云港
申请号：CN201210567451.4
申请日：20121224
公开号：CN103150573A
公开日：
20130612
专利内容由知识产权出版社提供
摘要：本发明公开了一种基于多分辨率分形特征的神经树突棘图像分类方法，包括以下步骤：（1）对神经树突棘图像进行特征提取获取神经树突棘图像的多分辨率分形特征；（2）采用线性判别分析（LDA）基于神经树突棘图像的多分辨率分形特征进行分类。

该方法分类精度高、分类结果稳定。

申请人：西交利物浦大学
地址：215123 江苏省苏州市工业园区独墅湖高等教育区仁爱路111号
国籍：CN
代理机构：苏州创元专利商标事务所有限公司
代理人：范晴
更多信息请下载全文后查看。

dlib 的用法-回复Dlib 是一个开源的C++ 库，提供了很多机器学习和图像处理的功能。

它具有简单易用的接口和高效的实现，广泛应用于计算机视觉、人脸识别、对象检测等领域。

在这篇文章中，我们将一步一步回答有关Dlib 的用法的问题，并探讨它的主要功能和应用。

1. 什么是Dlib？Dlib 是一个跨平台的C++ 库，由美国伊利诺伊大学厄巴纳-香槟分校的Davis King 开发。

它提供了包括线性代数、图像IO、机器学习、计算机视觉等功能的丰富工具集。

Dlib 的设计目标是简单易用且高效，以帮助开发人员快速构建机器学习和计算机视觉应用程序。

2. Dlib 的主要功能有哪些？Dlib 提供了许多功能强大的模块，包括但不限于以下几个方面：- 机器学习算法：Dlib 实现了各种常用的机器学习算法，如支持向量机(SVM)、随机森林、k-最近邻算法等。

这些算法可以用于分类、回归、聚类等任务。

- 计算机视觉：Dlib 提供了一系列计算机视觉算法，如人脸检测、关键点定位、姿态估计等。

它使用基于梯度的特征描述器和级联分类器来实现高效而准确的对象检测。

- 像素处理：Dlib 支持各种图像处理操作，如图像旋转、缩放、滤波等。

它还提供了灰度化、直方图均衡化等常见的像素操作。

- 图像IO：Dlib 能够读取和保存多种格式的图像文件，包括常见的JPEG、PNG 格式以及其它一些特殊格式。

这使得它很适合进行图像处理和计算机视觉任务。

- 并行计算：Dlib 支持多线程和多处理器计算，可以有效地利用多核处理器提高算法的运行速度。

3. 如何安装和配置Dlib？要安装和配置Dlib，可以按照以下步骤进行：- 下载Dlib：首先，我们需要从Dlib 的官方网站( 下载最新版本的Dlib 库。

- 安装依赖项：Dlib 依赖于一些第三方库，如Boost 和LAPACK，因此需要确保这些库已经安装在系统中。

- 编译和安装：将下载的Dlib 源代码解压缩到一个合适的目录，并使用C++ 编译器进行编译。

swisslog算法原理Swisslog算法原理Swisslog算法是一种常用于多目标优化问题的进化算法，它的核心思想是通过模拟自然界的“物竞天择、适者生存”的过程，以逐步寻找最佳解决方案。

在本文中，我们将一步一步地回答关于Swisslog算法的原理。

第一步：初始化种群为了开始Swisslog算法的优化过程，我们首先需要初始化一个种群。

种群是由一组候选解组成的集合，每个候选解代表问题的一个可能解决方案。

在Swisslog算法中，候选解通常是一个时间序列或向量。

我们可以通过随机生成的方法来产生初始种群。

第二步：计算适应度函数在Swisslog算法中，适应度函数用于评价每个候选解的质量。

适应度函数是根据问题的具体情况定义的，它可以是一个单目标函数，也可以是多个目标函数的组合。

适应度函数的计算结果越好，代表候选解越接近最优解。

第三步：选择优秀个体选择是Swisslog算法中的一个重要步骤。

在这一步中，我们将根据适应度函数的值来选择优秀个体，也就是具有较高适应度值的候选解。

选择的方式可以采用轮盘赌选择、锦标赛选择等多种方法。

第四步：运用局部搜索策略为了逐步优化种群中的个体，Swisslog算法引入了局部搜索策略。

局部搜索策略是对选定的个体进行近邻搜索，目的是通过微小的变异和搜索，进一步改进这些个体的质量。

局部搜索可以采用交换、插入、反转等操作，以及其他具体问题相关的搜索策略。

第五步：进行竞争与淘汰Swisslog算法仿照自然界的竞争与淘汰过程，通过一系列的竞争和淘汰，逐步将较差的个体替换为较优的个体。

具体来说，Swisslog算法会在局部搜索之后，将新生成的解与原个体进行比较，若新生成的解具有更好的适应度，就会替换掉原个体。

第六步：重复以上步骤直至收敛以上是Swisslog算法的一次迭代过程，从初始化种群到最后的竞争与淘汰，算法会不断重复以上步骤直至满足停止条件。

停止条件可以是达到一定的迭代次数，或者适应度值的变化不再显著。

第 62 卷第 6 期2023 年11 月Vol.62 No.6Nov.2023中山大学学报（自然科学版）（中英文）ACTA SCIENTIARUM NATURALIUM UNIVERSITATIS SUNYATSENI基于神经网络的多特征轻度认知功能障碍检测模型*王欣1，陈泽森21. 中山大学外国语学院，广东广州 5102752. 中山大学航空航天学院，广东深圳 518107摘要：轻度认知功能障是介于正常衰老和老年痴呆之间的一种中间状态，是老年痴呆诊疗的关键阶段。

因此，针对潜在MCI老年人群进行早期检测和干预，有望延缓语言认知障碍及老年痴呆的发生。

本文利用患者在语言学表现变化明显的特点，提出了一种基于神经网络的多特征轻度认知障碍检测模型。

在提取自然会话中的语言学特征的基础上，融合LDA模型的T-W矩阵与受试者资料等多特征信息，形成TextCNN网络的输入张量，构建基于语言学特征的神经网络检测模型。

该模型在DementiaBank数据集上达到了0.93的准确率、1.00的灵敏度、0.8的特异度和0.9的精度，有效提高了利用自然会话对老年语言认知障碍检测的准确率。

关键词：轻度认知功能障碍；自然会话；神经网络模型；多特征分析；会话分析中图分类号：H030 文献标志码：A 文章编号：2097 - 0137（2023）06 - 0107 - 09A neural network-based multi-feature detection model formild cognitive impairmentWANG Xin1， CHEN Zesen21. School of Foreign Languages， Sun Yat-sen University， Guangzhou 510275， China2. School of Aeronautics and Astronautics， Sun Yat-sen University， Shenzhen 518107， ChinaAbstract：Mild cognitive impairment （MCI） is both an intermediate state between normal aging and Alzheimer's disease and the key stage in the diagnosis of Alzheimer's disease. Therefore， early detec‐tion and treatment for potential elderly can delay the occurrence of dementia. In this study， a neural net‐work-based multi-feature detection model for mild cognitive impairment was proposed， which exploits the characteristics of patients with obvious changes in linguistic performance. The model is based on ex‐tracting the linguistic features in natural speech and integrating the T-W matrix of the LDA model with the subject data and other multi-feature information as the input tensor of the TextCNN network. It achieved an accuracy of 0.93， a sensitivity of 1.00， a specificity of 0.8， and a precision of 0.9 on the DementiaBank dataset， which effectively improved the accuracy of cognitive impairment detection in the elderly by using natural speech.Key words：mild cognitive impairment； natural speech； neural network model； multi-feature detec‐tion； speech analysisDOI：10.13471/ki.acta.snus.2023B049*收稿日期：2023 − 07 − 18 录用日期：2023 − 07 − 30 网络首发日期：2023 − 09 − 21基金项目：教育部人文社会科学基金（22YJCZH179）；中国科协科技智库青年人才计划（20220615ZZ07110400）；中央高校基本科研业务费重点培育项目（23ptpy32）作者简介：王欣（1991年生），女；研究方向：应用语言学；E-mail：******************第 62 卷中山大学学报（自然科学版）（中英文）轻度认知障碍（MCI，mild cognitive impair‐ment）是一种神经系统慢性退行性疾病，也是阿尔茨海默病（AD，Alzheimer's disease）的早期关键阶段。

2021⁃01⁃10计算机应用,Journal of Computer Applications 2021,41(1):43-47ISSN 1001⁃9081CODEN JYIIDU http ：//基于邻居信息聚合的子图同构匹配算法徐周波，李珍，刘华东*，李萍（广西可信软件重点实验室（桂林电子科技大学），广西桂林541004）（∗通信作者电子邮箱ldd@ ）摘要：图匹配在现实中被广泛运用，而子图同构匹配是其中的研究热点，具有重要的科学意义与实践价值。

现有子图同构匹配算法大多基于邻居关系来构建约束条件，而忽略了节点的局部邻域信息。

对此，提出了一种基于邻居信息聚合的子图同构匹配算法。

首先，将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习，从而得到聚合后的节点局部邻域信息；然后，根据图的标签、度等特征对匹配顺序进行优化，以提高算法的效率；最后，将得到的特征向量和优化的匹配顺序与搜索算法相结合，建立子图同构的约束满足问题（CSP ）模型，并结合CSP 回溯算法对模型进行求解。

实验结果表明，与经典的树搜索算法和约束求解算法相比，该算法可以有效地提高子图同构的求解效率。

关键词：子图同构；约束满足问题；图卷积神经网络；信息聚合；图匹配中图分类号：TP391文献标志码：ASubgraph isomorphism matching algorithm based on neighbor informationaggregationXU Zhoubo ，LI Zhen ，LIU Huadong *，LI Ping（Guangxi Key Laboratory of Trusted Software （Guilin University of Electronic Technology ），Guilin Guangxi 541004，China ）Abstract:Graph matching is widely used in reality ，of which subgraph isomorphic matching is a research hotspot and has important scientific significance and practical value.Most existing subgraph isomorphism algorithms build constraints based on neighbor relationships ，ignoring the local neighborhood information of nodes.In order to solve the problem ，a subgraph isomorphism matching algorithm based on neighbor information aggregation was proposed.Firstly ，the aggregated local neighborhood information of the nodes was obtained by importing the graph attributes and structure into the improved graph convolutional neural network to perform the representation learning of feature vector.Then ，the efficiency of the algorithm was improved by optimizing the matching order according to the characteristics such as the label and degree of the graph.Finally ，the Constraint Satisfaction Problem （CSP ）model of subgraph isomorphism was established by combining the obtained feature vector and the optimized matching order with the search algorithm ，and the model was solved by using the CSP backtracking algorithm.Experimental results show that the proposed algorithm significantly improves the solving efficiency of subgraph isomorphism compared with the traditional tree search algorithm and constraint solving algorithm.Key words:subgraph isomorphism;Constraint Satisfaction Problem (CSP);graph convolutional neural network;information aggregation;graph matching0引言图匹配技术被广泛地应用于社交网络、网络安全、计算生物学和化学等领域［1］中。

【系统发育】摘PAMl学习笔记-蜗牛PAML与 Branch model ——以灵长目动物溶菌酶编码基因适应性进化分析为例解读Branch Model1.什么是Branch model？Branch model是PAML软件CODEML程序过likelihood ratio test （LRT）进行不同支系间（lineages）适应性进化检测的一种模型。

该模型通过限制（constraint）系统发育树中不同分支上的omega(dN/dS)值的异同，并对不同的限制进行显著性分析（PAML 软件中的Chi2程序），进而得到较为可靠地分析结果。

在该法提出之前，不少学者通过简约法（parsimony method）或者似然法（likelihood method）先重建祖先序列（ancestral sequence），然后通过对构建的祖先序列的omega值估算进而预测不同支系的适应性进化特征。

诸如Prof. Messier等对于灵长目动物溶菌酶的分析便是如此。

Prof.Yang认为，从统计学的角度而言，这种将预测的数据当做真实观测数据的分析理念存在一定的随机误差（random errors）和系统误差(systematic errors), 本身并不是一种严谨的统计学方法。

Prof.Yang 所提出的Branch model巧妙地避开了直接利用ancestral sequence进行支系间适应性进化检测的流程，而是通过平均统计每一个节点（each node）中可能的ancestral sequence，根据其相对发生似然率（relative likelihoods of occurance）进行加权分析。

此外，Branch model还考虑到了（take into account）密码子转移/颠换速率偏差（transition/transversion rate bias）和非均匀密码子（nonuniform condon usage）这些与omega值计算有着显著关系的影响因素。

W ARNING: Amber lens versions not to be used as a visual public mode alarm notification appliance.NOTICE: This manual shall be left with the owner/user of this equipment.BEFORE INSTALLINGPlease read the System Sensor Audible Visible Application Reference Guide, which provides detailed information on notification devices, wiring and spe-cial applications. Copies of this manual are available from System Sensor. NFPA 72 and NEMA guidelines should be observed.I mportant: The notification appliance used must be tested and maintained following NFPA 72 requirements.GENERAL DESCRIPTIONThe L-Series Dual Strobe and Dual Strobe with Speaker Expander Plates for emergency communications use a single device plate to perform the functions of two to three devices on a back box. This combination of multiple devices on a single plate and back box lowers the overall cost of the installation and improves aesthetics by requiring fewer devices on the wall.The expander plate provides fast and easy installation: Mount the expander plate to a junction box and connect its field wiring to the terminals. Attach the mounting plate of a strobe or speaker strobe device and connect its field wiring. Then, hinge and attach the strobe or speaker strobe device with a captured mounting screw to complete the installation. This product is compa-rable to existing L-Series mounting plate installations.Dual Strobe and Dual Strobe with Speaker Expander Plates are designed to be used in 12 or 24 volt, DC or FWR (full wave rectified) systems. Clear lens ver-sion is listed to UL 1971 Listed and CAN/ULC S526-07 (Signaling Device for Hearing Impaired) for Public Mode Evacuation Signaling. Amber lens strobes are UL1638 Listed (Visual Signaling Appliances) for Private Mode General Utility Signaling. All L-Series products are suitable for use in synchronized systems. The System Sensor MDL3 module may be used to provide synchro-nization.The Dual Strobe and Dual Strobe wi th Speaker Expander Plates are designed for use in wall applications.LOOP DESIGN AND WIRINGThe system designer must make sure that the total current drawn by the de-vices on the loop does not exceed the current capability of the panel supply, and that the last device on the circuit is operated within its rated voltage. The current draw information for making these calculations can be found in the tables within this manual. For convenience and accuracy, use the voltage drop calculator on the System Sensor website (). See Figures 1-4 for wiring diagrams and shorting spring information.When calculating the voltage available to the last device, it is necessary to consider the voltage drop due to the resistance of the wire. The thicker the wire, the smaller the voltage drop. Wire resistance tables can be obtained from electrical handbooks. Note that if Class A wiring is installed, the wire length may be up to twice as long as it would be for circuits that are not fault tolerant.CANDELA SELECTIONThe product will be set at 15 candela from the factory. T o change the candela first remove the lower appliance from the expander plate by loosening the screw at the bottom of the appliance.Adjust the slide switch on the rear of the product to position the desired can-dela setting in the small window on the front of the unit. All products meet the light output profiles specified in the appropriate UL Standards. For amber lensed strobes used for full profile measurement, listed candela ratings must be reduced in accordance with T able 2. Use Table 1 to determine the current draw for each candela setting.NOTE: L-Series products set at 15 and 30 candela work on either 12V or 24V power supplies. The products are not listed for 12V operating voltages when set to any other candela settings.INSTALLATION AND MAINTENANCE INSTRUCTIONSDual Strobe andDual Strobe with SpeakerExpander Plates for Emergency CommunicationsFor use with the following models:SEP-SPWL, SEP-SPSWL-P – Strobe Expander Plate models and SPSEP-BBSWL Back Box Skirt model are compatible with SWL, SWL-P, SPSWL, SPSW-P, P2WL.PRODUCT SPECIFICATIONSSEP-SPSWL: Universal Expander Plate, Amber Lens, White, ALERT SEP-SPSWL-P: Universal Expander Plate, White, PlainSPSEP-BBSWL: Universal Expander Plate Back Box Skirt, WhiteOperating T emperature:Standard Products 32°F to 120°F (0°C to 49°C)Humidity Range:Standard Products 10 to 93% Non-condensing Strobe Flash Rate: 1 flash per secondNominal Voltage:Regulated 12VDC/FWR or regulated 24DC/FWROperating Voltage Range (includes fire alarm panels with built in sync):8 to 17.5V (12V nominal) or 16 to 33V (24V nominal)Operating Voltage with MDL3 Sync Module:8.5 to 17.5V (12V nominal) or 16.5 to 33V (24V nominal)Input terminal wire gauge:12 to 18 A WGNOTE : Strobes will operate at 12V nominal for 15 & 30 candela settings only. Switching between ranges is automatic.DIMENSIONS FOR PRODUCTS AND ACCESSORIESSEP-SPSWL (-P)SPSEP-BBSWLLength Width Depth Length Width Depth 13.05" (331.5 mm)5.39" (136.9 mm)2.41" (61.2 mm)13.75" (349.3 mm)6.10" (154.9 mm)2.5" (63.5 mm)MOUNTING BOX OPTIONSSEP-SPSWL, SEP-SPSWL-P: 4" x 4" x 21/8" or deeper SPSEP-BBSWL: 4" x 4" x 21/8"3825 Ohio Avenue, St. Charles, Illinois 60174800/736-7672, FAX: 630/377-6495I56-6569-000FIGURE 4. WIRING SEP-SPWL(-P): ATTACHING A HORN STROBE AS THE UPPER DEVICEINPUT FROM FACP OR PRIOR STROBE (-)(+)OUTPUT TO NEXT STROBE OR EOL(-)(+) A0564-00FIGURE 5. SHORTING SPRING ON HORN STROBE MOUNTING PLATE, STANDARD CANDELA, WHITEA0560-00NOTE: A shorting spring is provided between terminals 2 and 3 of the mount-ing plate to enable wiring checks after the system has been wired, but prior to installation of the final product. This spring will automatically disengage when the product is installed, to enable supervision of the final system.TABLE 1. STROBE CURRENT DRAW (mA) FOR SEP-SPWL (-P), SEP-SPSWL (-P)Candela Switch Setting 8-17.5 V olts 16-33 V olts DC DC FWR 15884360NOTE: Products set at 15 and 30 candela automatically work on ei-ther 12V or 24V power supplies. The products are not listed for 12V DC operation when set to any other candela settings.30143638375-10713695-121155110-148179135-172209185-222257TABLE 2: CANDELA DERATING FOR SEP-SPWL AND SEP-SPSWL AMBER LENS STROBE Cd Switch SettingPrivate ModeEmergency Warning15151230302475756095957511011085135135105185185145IMPORTANT: For more information on current draw, light output and sound output data, reference Speaker Strobe installation manuals I56-0002 and I56-0003 and Strobe only installation manual I56-5845 and I56-5847.FIGURE 1. WIRING SEP-SPWL(-P): CONNECTING THE UNIVERSAL EXPANDER PLATE'S LOWER STROBE OUTPUT TO NEXT STROBE OR EOL INPUT FROM POWER SUPPLY FOR STROBE OR PRIOR STROBE(+)(-)(+)(-)A0562-00FIGURE 2. WIRING SEP-SPWL(-P): ATTACHING A SPEAKER STROBE AS THE UPPER DEVICEINPUT FROM FACP OR PRIOR STROBE INPUT FROM AMPLIFIEROR PRIOR SPEAKER (-)(+)(-)(+)OUTPUT TO NEXT STROBE OR EOL OUTPUT TO NEXT SPEAKER OR EOL(-)(+)(-)(+)A0563-00NOTE: Loop resistance on a single NAC should not exceed 120 ohms for 24 volt and 30 ohms for 12 volt systems.FIGURE 3. SHORTING SPRING ON SPEAKER STROBE MOUNTING PLATE, STANDARD CANDELA,WHITEShorting SpringA0559-00NOTE: Shorting springs are provided between terminals 2 and 3 and terminals 5 and 6 of the mounting plate to enable wiring checks after the system has been wired, but prior to installation of the final product. These springs will automatically disengage when the product is installed, to enable supervision of the final system.MOUNTING THE UNIVERSAL EXPANDER PLATE AND SECOND DEVICE Junction Box Compatibility: The expander plate and back box skirt are com-patible with a 4" x 4" x 21/8" junction box.1a. F or flush mount appl i cat i ons: Attach the expander plate to a 4" x 4" x 21/8" junction box using the two screws provided with the expander plate.–Speaker Strobe as upper device: Figure 6.–Strobe as upper device: Figure 8.1b. F or surface-mount appli cati ons wi th a back box ski rt: Snap the ex-pander plate onto the skirt, and then attach the entire assembly to a 4" x 4" x 21/8" junction box using the two screws provided with the expander plate.–Speaker Strobe as upper device: Figure 7.–Strobe as upper device: Figure 9.2. C onnect the lower strobe's field wiring to the expander plate terminals.(See Figure 1.)3. A ttach the device mounting plate with the four screws provided with theexpander plate.4. C onnect the upper device's field wiring to the device mounting plateterminals. (See Figure 4.)5. A ttach upper device:a. H ook tabs at the top of the product housing into the grooves on devicemounting plate.b. S wing the device down into position to engage the terminals on thedevice with the terminals on the device mounting plate.c. M ake sure that the tabs on the back of the product housing fully en-gage with the device mounting plate.d. S ecure the device by tightening the single mounting screw in the frontof the device housing. For tamper resistance, the standard captivemounting screw may be replaced with the enclosed T orx screw. (Seeinstallation manual for upper device.)to flex.FIGURE 6. UNIVERSAL EXPANDER PLATE WITH SPEAKER STROBE FORFLUSH MOUNT APPLICATIONSA0568-00 Note: SEP-SPSWL expander plate shown.FIGURE 7. UNIVERSAL EXPANDER PLATE WITH SPEAKER STROBE SURFACE MOUNT APPLICATIONSA0565-00Note: SEP-SPSWL expander plate shown.Only mount on a wall and in the orientation shown.System Sensor ® is a registered trademark of Honeywell International, Inc.FIGURE 8. UNIVERSAL EXPANDER PLATE WITH HORN STROBE FORFLUSH MOUNT APPLICATIONS A0567-00Note: SEP-SPWL expander plate shown.FIGURE 9. UNIVERSAL EXPANDER PLATE WITH HORN STROBE FORSURFACE MOUNT APPLICATIONSA0566-00Note: SEP-SPWL expander plate shown.Only mount on a wall and in the orientation shown.The horn and/or strobe will not work without power. The horn/strobe gets its power from the fire/security panel monitoring the alarm system. If power is cut off for any rea-son, the horn/strobe will not provide the desired audio or visual warning.The horn may not be heard. The loudness of the horn meets (or exceeds) current Underwriters Laboratories’ standards. However, the horn may not alert a sound sleeper or one who has recently used drugs or has been drinking alcoholic beverages. The horn may not be heard if it is placed on a different floor from the person in hazard or if placed too far away to be heard over the ambient noise such as traffic, air conditioners, machinery or music appliances that may prevent alert persons from hearing the alarm. The horn may not be heard by persons who are hearing impaired.NOTE: Strobes must be powered continuously for horn operation.The signal strobe may not be seen. The electronic visual warning signal uses an ex-tremely reliable xenon flash tube. It flashes at least once every second. The strobe must not be installed in direct sunlight or areas of high light intensity (over 60 foot candles) where the visual flash might be disregarded or not seen. The strobe may not be seen by the visually impaired.The signal strobe may cause seizures. Individuals who have positive photoic response to visual stimuli with seizures, such as persons with epilepsy, should avoid prolonged exposure to environments in which strobe signals, including this strobe, are activated.The signal strobe cannot operate from coded power supplies. Coded power supplies produce interrupted power. The strobe must have an uninterrupted source of power in or-der to operate correctly. System Sensor recommends that the horn and signal strobe always be used in combination so that the risks from any of the above limitations are minimized.THREE-YEAR LIMITED WARRANTYSystem Sensor warrants its enclosed product to be free from defects in materials and workmanship under normal use and service for a period of three years from date of manufacture. System Sensor makes no other express warranty for this product. No agent, representative, dealer, or employee of the Company has the authority to increase or alter the obligations or limitations of this Warranty. The Company’s obligation of this Warranty shall be limited to the replacement of any part of the product which is found to be defective in materials or workmanship under normal use and service during the three year period commencing with the date of manufacture. After phoning System Sensor’s toll free number 800-SENSOR2 (736-7672) for a Return Authorization number, send defective units postage prepaid to: Honeywell, 12220 Rojas Drive, Suite 700, El Paso TX 79936, USA for US returns and 6581 Kitimat Road, Unit 6 Mississauga, ON L5N 3T5 forCanadian returns. Please include a note describing the malfunction and suspected cause of failure. The Company shall not be obligated to replace units which are found to be defective because of damage, unreasonable use, modifications, or alterations occurring after the date of manufacture. In no case shall the Company be liable for any consequen-tial or incidental damages for breach of this or any other Warranty, expressed or implied whatsoever, even if the loss or damage is caused by the Company’s negligence or fault. Some states do not allow the exclusion or limitation of incidental or consequential dam-ages, so the above limitation or exclusion may not apply to you. This Warranty gives you specific legal rights, and you may also have other rights which vary from state to state.FCC STATEMENTL-series Strobes and Horn/Strobes have been tested and found to comply with the lim-its for a Class B digital device, pursuant to part 15 of the FCC Rules. These limits are designed to provide reasonable protection against harmful interference when the equip-ment is operated in a commercial environment. This equipment generates, uses, and can radiate radio frequency energy and, if not installed and used in accordance with theinstruction manual, may cause harmful interference to radio communications. Operationof this equipment in a residential area is likely to cause harmful interference in which case the user will be required to correct the interference at his own expense. This ClassB digital apparatus complies with Canadian ICES-003.Please refer to insert for the Limitations of Fire Alarm SystemsTHE LIMITATIONS OF STROBE AND SPEAKER STROBE EXPANDER PLATE。