Mach Learn(2009)74:1–22
DOI10.1007/s10994-008-5084-4
Semi-supervised graph clustering:a kernel approach
Brian Kulis·Sugato Basu·Inderjit Dhillon·
Raymond Mooney
Received:9March2007/Revised:17April2008/Accepted:8August2008/
Published online:24September2008
Springer Science+Business Media,LLC2008
Abstract Semi-supervised clustering algorithms aim to improve clustering results using limited supervision.The supervision is generally given as pairwise constraints;such con-straints are natural for graphs,yet most semi-supervised clustering algorithms are designed for data represented as vectors.In this paper,we unify vector-based and graph-based ap-proaches.We?rst show that a recently-proposed objective function for semi-supervised clustering based on Hidden Markov Random Fields,with squared Euclidean distance and a certain class of constraint penalty functions,can be expressed as a special case of the weighted kernel k-means objective(Dhillon et al.,in Proceedings of the10th International Conference on Knowledge Discovery and Data Mining,2004a).A recent theoretical con-nection between weighted kernel k-means and several graph clustering objectives enables us to perform semi-supervised clustering of data given either as vectors or as a graph.For graph data,this result leads to algorithms for optimizing several new semi-supervised graph clustering objectives.For vector data,the kernel approach also enables us to?nd clusters with non-linear boundaries in the input data space.Furthermore,we show that recent work on spectral learning(Kamvar et al.,in Proceedings of the17th International Joint Confer-ence on Arti?cial Intelligence,2003)may be viewed as a special case of our formulation. We empirically show that our algorithm is able to outperform current state-of-the-art semi-supervised algorithms on both vector-based and graph-based data sets.
Keywords Semi-supervised clustering·Kernel k-means·Graph clustering·Spectral learning
Editor:Jennifer Dy.
B.Kulis()·I.Dhillon·R.Mooney
Department of Computer Sciences,University of Texas,Austin,TX,USA
e-mail:kulis@https://www.doczj.com/doc/b31311243.html,
S.Basu
Google,Inc.,Mountain View,CA,USA
1Introduction
Semi-supervised clustering algorithms have recently received a signi?cant amount of atten-tion in the machine learning and data mining communities.In traditional clustering algo-rithms,only unlabeled data is used to generate clusterings;in semi-supervised clustering, the goal is to incorporate prior information about clusters into the algorithm in order to improve the clustering results.A related but different problem is semi-supervised classi-?cation(Chapelle et al.2006),which considers how unlabeled data can be used to im-prove the performance of classi?cation on labeled data.A number of recent papers have explored the problem of semi-supervised clustering.Research on semi-supervised cluster-ing has considered supervision in the form of both labeled points(Demiriz et al.1999; Sinkkonen and Kaski2002;Basu et al.2002)or constraints(Wagstaff et al.2001; Klein et al.2002;Xing et al.2003;Bar-Hillel et al.2003;Bie et al.2003;Kamvar et al.2003; Bilenko et al.2004;Basu et al.2004a,2004b;Chang and Yeung2004;Davidson and Ravi 2005a,2005b;Law et al.2005;Lu and Leen2005;Lange et al.2005).
As is common for most semi-supervised clustering algorithms,we assume in this paper that we have pairwise must-link constraints(pairs of points that should belong in the same cluster)and cannot-link constraints(pairs of points that should belong in different clus-ters)provided with the input.Pairwise constraints occur naturally in many domains,e.g., the Database of Interacting Proteins(DIP)data set in biology contains information about proteins co-occurring in processes,which can be viewed as must-link constraints during gene clustering.Constraints of this form are also natural in the context of the graph cluster-ing problem(a.k.a.graph partitioning or vertex partitioning),where edges in the graph en-code pairwise relationships.Different application areas of semi-supervised clustering with constraints have been studied recently,including(1)image segmentation for object iden-ti?cation in Aibo robots(Davidson and Ravi2005a),where cluster-level constraints are used to improve the pixel clustering;(2)object recognition in video sequences(Yan et al. 2004),where must-link constraints are used to group pixels belonging to the same object and cannot-link constraints are used to separate different objects;(3)clustering for lane?nding from GPS traces(Wagstaff et al.2001),where constraints are used to encode lane-contiguity and max-separation criteria;and(4)speaker identi?cation and categorization(Bar-Hillel et al.2003),where constraints are used to encode whether two speakers are similar or not.
Recently,a probabilistic framework for semi-supervised clustering with pairwise con-straints was proposed based on Hidden Markov Random Fields(Basu et al.2004b).The HMRF framework proposed a general semi-supervised clustering objective based on maxi-mizing the joint likelihood of data and constraints in the HMRF model,as well as a k-means-like iterative algorithm for optimizing the objective.However,HMRF-KMEANS can cluster input data only in the form of vectors.While much of the work on semi-supervised clus-tering has focused on vector-based inputs,very little work has gone into the study of semi-supervised graph clustering algorithms.In this paper,we unify vector-based and graph-based semi-supervised clustering using a kernel approach;in particular,our main contributions in this paper are as follows:
?We show that the HMRF semi-supervised clustering objective with squared Euclidean dis-tance and cluster-size weighted penalties is a special case of the weighted kernel k-means objective function(Dhillon et al.2004a).Given input data in the form of vectors and pair-wise constraints,we show how to construct a kernel such that running kernel k-means results in a monotonic decrease of this semi-supervised clustering objective function at every iteration of the kernel k-means algorithm.
?The weighted kernel k -means algorithm can be used to monotonically optimize a wide class of graph clustering objectives such as minimizing the normalized cut (Dhillon et al.2007).As a result,our approach can be generalized to optimize a number of differ-ent semi-supervised graph clustering objectives for which constraint-based supervision is more natural,including semi-supervised normalized cut,semi-supervised ratio cut,and semi-supervised ratio association objective functions.This equivalence gives us a new semi-supervised clustering algorithm SS-K ERNEL -KMEANS that can cluster data given either as vectors or a graph,along with supervision in the form of constraints.
?For vector-based data we have the ability to apply a kernel function,which allows SS-K ERNEL -KMEANS to discover clusters with non-linear boundaries in the input space.?We show how a previously proposed algorithm S PECTRAL -LEARNING (Kamvar et al.2003)can be viewed as a special case of our framework.The S PECTRAL -LEARNING al-gorithm can be viewed as optimizing an underlying semi-supervised clustering objective;speci?cally,it optimizes a relaxation of semi-supervised ratio cut.
?We empirically demonstrate that SS-K ERNEL -KMEANS outperforms HMRF-KMEANS (Basu et al.2004b )and S PECTRAL -LEARNING on several vector-based and graph-based data sets,including handwritten digits data,protein data,a gene network,and a data set of images.
We note that an earlier version of this paper appears as Kulis et al.(2005).This extended version further develops the mathematical connection between kernel k -means and graph clustering for semi-supervised clustering,and presents several new experimental results.2Background and related work
In this section,we provide the necessary background for our proposed kernel-based semi-supervised clustering algorithm SS-K ERNEL -KMEANS ,and also describe related research.
2.1Graph clustering and kernel k -means
In graph clustering,the input is assumed to be a graph G =(V ,E ,A),where V is the set of vertices,E is the set of edges,and A is the edge adjacency matrix.A ij represents the edge-weight between vertices i and j .Let links (A ,B )= i ∈A ,j ∈B A ij ,where A and B are subsets of vertices.Furthermore,let degree (A )=links (A ,V ).We seek to ?nd a k -way disjoint partitioning 1{V c }k c =1of V to minimize a particular objective.Table 1gives a list of some common graph clustering ob-jectives.Ratio association tries to maximize the af?nity/similarity of points within a cluster,Table 1Examples of graph
clustering objectives Name
Objective function Ratio association
maximize V 1,...,V k k c =1links (V c ,V c )|V c |Ratio cut
minimize V 1,...,V k k c =1links (V c ,V \V c )|V c |Normalized cut minimize V 1,...,V k k c =1links (V c ,V \V c )degree c 1k disjoint data subsets,whose union is the whole data.
normalizing each cluster’s contribution to the objective by the size of the cluster in order to balance the size of the clusters.Ratio cut(Chan et al.1994),on the other hand,tries to min-imize the total cost of the edges crossing the cluster boundaries—this is again normalized by the size of the clusters,to encourage balanced cluster sizes.The normalized cut crite-rion(Shi and Malik2000)uses the same objective as ratio cut but normalizes by the total degree of each cluster(the sum of the degrees of all nodes in the cluster)—this encourages the clusters to have similar degrees.
To make the connection between graph clustering and vector-based clustering,we in-troduce the weighted kernel k-means objective function(Dhillon et al.2004a).Given a set of data vectors X={x i}n i=1with x i∈R n,the goal of weighted kernel k-means is to?nd a k-way disjoint partitioning{πc}k c=1of the data(whereπc represents the c th cluster)such that
the following objective is minimized:
J({πc}k c=1)=
k
c=1
x i∈πc
αi φ(x i)?m c 2where m c=
x i∈πc
αiφ(x i)
x i∈πc
αi
.
Each vector x i has a pre-speci?ed non-negative weightαi associated with it,andφis a function mapping vectors in X to a(generally)higher-dimensional space.If all weights are set to one andφis the identity function,this reduces to standard k-means.
If we expand the distance computation φ(x i)?m c 2in the weighted kernel k-means objective function,we obtain the following:
φ(x i)·φ(x i)?2
x j∈πc
αjφ(x i)·φ(x j)
x j∈πc
αj
+
x j,x l∈πc
αjαlφ(x j)·φ(x l)
(
x j∈πc
αj)2
.
Notice that all computation involving data points is in the form of inner products.We can therefore use the kernel trick:if we can compute the inner product K ij=φ(x i)Tφ(x j)be-tweenφ(x i)andφ(x j)ef?ciently,we are able to compute distances between points in this mapped space without explicitly knowing the mapping of x i and x j toφ(x i)andφ(x j).We assume that the input is the kernel matrix K of inner products;it can easily be shown that any positive semide?nite matrix K can be thought of as a kernel matrix(Cristianini and Shawe-Taylor2000).
Using the kernel matrix K,the distance computation d(x i,m c)= φ(x i)?m c 2is rewritten as:
K ii?2
x j∈πc
αj K ij
x j∈πc
αj
+
x j,x l∈πc
αjαl K jl
(
x j∈πc
αj)2
.(1)
As a result,we may derive an algorithm analogous to k-means to monotonically decrease the weighted kernel k-means objective function without knowledge of the mapφ.Algo-rithm1shows the pseudo-code for the basic weighted kernel k-means algorithm,which is identical to standard k-means except for the fact that distances are computed using the kernel matrix.Note that as opposed to regular k-means,this algorithm does not update the cluster centroids m c explicitly.
Using the weighted form of the kernel k-means objective function is important because it is equivalent to a weighted graph-cut objective function,of which many existing graph clus-tering objectives are special cases(Dhillon et al.2007).For example,the normalized cut criterion for graph clustering can be written exactly as the weighted kernel k-means objec-tive function,where the kernel matrix K and weightsαare derived from the input adjacency
A LGORITHM 1:Basic weighted kernel k -means.K ERNEL -KMEANS (K ,k ,t max ,α,{π(0)c }k c =1)
Input:K :kernel matrix,k :number of clusters,t max :optional maximum number
of iterations,α:weight vector,{π(0)c }k c =1:optional initial clusters Output:{πc }k c =1:?nal partitioning of the points
1.Initialize the k clusters from {π(0)c }k c =1,if provided as input,else randomly.
2.Set t =0.
3.For each point x i and every cluster c ,compute d(x i ,m c )as in (1).
4.Find c ?(x i )=argmin c d(x i ,m c ),resolving ties arbitrarily.
https://www.doczj.com/doc/b31311243.html,pute the updated clusters as
π(t +1)c
={x i :c ?(x i )=c }.6.If not converged or t max >t ,set t =t +1and go to Step 3;Otherwise,stop and
output ?nal clusters {π(t +1)c
}k c =1.Table 2Popular graph
clustering objectives and
corresponding weights and
kernels given af?nity matrix A Objective Node weights Kernel Ratio association
1for all nodes K =σI +A Ratio cut
1for all nodes K =σI ?L Normalized cut Degree of the node K =σD ?1+D ?1AD ?1
matrix A .Other objective functions for graph clustering can similarly be expressed as spe-cial cases of the weighted kernel k -means objective functions.This allows us the ?exibility of having as input to the algorithm either a graph or data vectors that have been mapped to a kernel space.
Table 2shows how to set the weights and kernel for three popular graph clustering objec-tives to be equivalent to the weighted kernel k -means objective function.The node weights in this table are weights on the nodes in the graph that correspond to the weights of the data vectors in k -means,signifying the importance of the data vectors (i.e.,the degree of their contribution to the clustering objective function).Here,D is a diagonal matrix whose entries correspond to the sum of the rows of the input af?nity matrix A (which is the input similarity matrix or kernel matrix),L is the Laplacian matrix (D ?A ),and σis a positive real number chosen to be suf?ciently large such that K is positive de?https://www.doczj.com/doc/b31311243.html,ing simple eigenvalue bounds,one can appropriately compute σwithout resorting to expensive eigen-vector computation.We note that,in practice,one can typically set σ=0and still observe monotonic convergence despite the matrix K not being positive de?nite.See Dhillon et al.(2004b )for a more complete discussion on the choice and computation of σ.
While not equivalent,the kernels formed over these graphs bear resemblance to other graph kernels,such as those discussed by Smola and Kondor (2003);for example,the nor-malized cut criterion can be interpreted in terms of random walks.See Meila and Shi (2001)for a detailed analysis of this connection.
2.2Semi-supervised clustering
Often when clustering,we have some background knowledge about the cluster structure.As mentioned previously,in this work we assume that this knowledge comes in the form
of pairwise must-link or cannot-link constraints.Such constraints are natural for graphs,as pairwise relationships are explicitly captured via edges in a graph.However,most semi-supervised clustering with pairwise constraints assumes that the input is in the form of data vectors(Wagstaff et al.2001;Sinkkonen and Kaski2002;Klein et al.2002;Xing et al.2003; Bar-Hillel et al.2003;Basu et al.2004b;Bilenko et al.2004).In contrast,recent work by Bansal et al.(2002),Charikar et al.(2003),Demaine and Immorlica(2003)in semi-supervised clustering considers inputs only in the form of constraints,and does not consider an underlying distance function between the points.
2.2.1HMRF model
We now brie?y describe a recently proposed objective function for semi-supervised cluster-ing of data vectors,which we will use in our formulation.Basu et al.(2004b)proposed a framework for semi-supervised clustering based on Hidden Markov Random Fields(HM-RFs).Choosing squared Euclidean distance as the cluster distortion measure and the gener-alized Potts potential(Kleinberg and Tardos1999)as the constraint violation potential,the semi-supervised clustering objective can be expressed as:
J({πc}k c=1)=
k
c=1
x i∈πc
x i?m c 2+
x i,x j∈M
s.t.l i=l j
w ij+
x i,x j∈C
s.t.l i=l j
w ij,(2)
where M is the set of must-link constraints,C is the set of cannot-link constraints,w ij is the penalty cost for violating a constraint between x i and x j,and l i refers to the cluster label of x i.The?rst term in this objective function is the standard k-means objective function, the second term is a penalty function for violating must-link constraints,and the third term is a penalty function for violating cannot-link constraints.The algorithm HMRF-KM EANS developed for minimizing this objective(Basu et al.2004b)uses an iterative relocation ap-proach like k-means.One of the drawbacks to HMRF-KM EANS is that,in the E-step of the algorithm,given the current cluster centroids,the order in which points are greedily re-assigned to clusters determines the new clusters;that is,different orderings produce different clusterings.It is computationally intractable to solve for the optimal ordering.Several recent extensions of the HMRF-KM EANS model address this order-dependence issue and propose approximations that must be employed in the E-step,e.g.,loopy belief propagation(Bilenko and Basu2004;Law et al.2005),Gibbs sampling(Lu and Leen2005),and mean?eld ap-proximation(Lange et al.2005).As we will see in Sect.3,our proposed algorithm naturally avoids such an order-dependence problem.
2.2.2Spectral learning
Recently,spectral methods have become increasingly popular for clustering.These algo-rithms cluster data given in the form of a graph.One spectral approach to semi-supervised clustering is the S PECTRAL-LEARNING algorithm of Kamvar et al.(2003):
?Form the af?nity matrix A:the entries of A are assumed to be normalized between0and 1,where entry A ij is the similarity between points i and j.
?For all points i,j that have a must-link constraint,set A ij=1(maximum af?nity);for all points i,j that have a cannot-link constraint,set A ij=0(minimum af?nity).
?Re-normalize the matrix using additive normalization(Kamvar et al.2003):N= 1
max
(A+d max I?D).N now represents a normalized Markov transition process.
?Take the top k eigenvectors of A to be the columns of the matrix V,and cluster the rows of V.If N has k piecewise constant eigenvectors,then N has k strong cliques—so clustering the eigenvectors effectively tries to?nd these k strongly connected components or clusters.
In the above algorithm,d max is the maximum row-sum of A and D is the degree matrix.
Notice that the additive normalization is equal to I?1
d max L,which is equivalent to d max I?L
up to a scalar factor,where L=D?A is the graph Laplacian of A.Furthermore,the top eigenvectors of d max I?L are the same as the bottom eigenvectors of L.In the presentation of Kamvar et al.(2003),the S PECTRAL-LEARNING algorithm does not have an explicit underlying objective function.However in Sect.4.3,we will show that this algorithm can be viewed as a special case of our uni?ed semi-supervised clustering framework.Note that the S PECTRAL-L EARNING algorithm needs O(kn)memory to store the k eigenvectors for n points,which can be a substantial overhead for large graphs.
Another recent paper(Yu and Shi2004)considered a semi-supervised formulation of the normalized cut objective and had a spectral algorithm associated with it.The main dif-ferences between this work and our algorithm are:(1)only must-link constraints are con-sidered in their formulation,and there is no way to specify penalty weights for constraint violations:SS-K ERNEL-KMEANS considers both must-link and cannot-link constraints and allows constraint violation with an associated penalty,thereby making it more robust to constraint noise;(2)their formulation solves an expensive constrained eigen-decomposition problem while SS-K ERNEL-KMEANS uses an ef?cient iterative algorithm,making it easily scalable to large data sets.
3Kernel-based semi-supervised clustering for HMRF-KMEANS
This section demonstrates the connection between the semi-supervised clustering objective for the HMRF-KMEANS algorithm and the kernel k-means objective function.This leads to a kernel-based algorithm for optimizing the HMRF-KMEANS objective function with squared Euclidean distance and penalties weighted by the cluster size.
3.1Constructing the kernel
Recall the objective for semi-supervised clustering on a HMRF from(2),using squared Euclidean distance as the clustering distortion measure and the generalized Potts potential for constraint penalty.Let us alter this penalty function:instead of adding a penalty term for a must-link violation if the two points are in different clusters,we give a reward for constraint satisfaction if the points are in the same cluster,by subtracting the corresponding penalty term from the objective.If the sum of weights for all must-link constraints is a constant,then this is equivalent to the original objective function up to an additive constant. Therefore minimizing J({πc}k c=1)is equivalent to minimizing:
k c=1
x i∈πc
x i?m c 2?
x i,x j∈M
l i=l j
w ij+
x i,x j∈C
l i=l j
w ij.
We also introduce the notion of cluster-size weighted penalties:if there are two points that have a cannot-link constraint in the same cluster,we will penalize higher if the correspond-ing cluster is smaller.Similarly,we will reward higher if two points in a small cluster have
a must-link constraint.Thus,we divide each w ij by the size of the cluster that the points are in.This gives us:
J({πc}k c=1)=
k
c=1
x i∈πc
x i?m c 2?
x i,x j∈M
l i=l j
w ij
|πl
i
|
+
x i,x j∈C
l i=l j
w ij
|πl
i
|.(3)
Using the following simple result(see Duda and Hart1973):
k c=1
x i∈πc
2 x i?m c 2=
k
c=1
x i,x j∈πc
x i?x j 2
|πc|,
and re-writing the sums,minimizing the objective in(3)becomes equivalent to minimizing:
J({πc}k c=1)=
k
c=1
x i,x j∈πc
x i?x j 2
|πc|
?
x i,x j∈M
l i=l j
2w ij
|πl
i
|
+
x i,x j∈C
l i=l j
2w ij
|πl
i
|.(4)
Rewriting the sums yields the following:
J({πc}k c=1)=
k
c=1
x i,x j∈πc
x i?x j 2
|πc|
?
k
c=1
x i,x j∈πc
(x i,x j)∈M
2w ij
|πc| +
k
c=1
x i,x j∈πc
(x i,x j)∈C
2w ij
|πc|.
Let E be the matrix of pairwise squared Euclidean distances among the data points,such that E ij= x i?x j 2and W be the constraint matrix such that W ij is?w ij for a cannot link,w ij for a must link,and0otherwise.Furthermore,we introduce an indicator vector z c for cluster c.This vector is of length n and z c(i)=0if x i is not in cluster c,and1otherwise. We can now write the above objective in the following way:
J({πc}k c=1)=
k
c=1
z T
c
(E?2W)z c
z T
c
z c
,(5)
where z T
c z c is the size of clusterπc,an
d z T
c
(E?2W)z c gives the sum of E ij?2W ij over all
x i and x j inπc.
Now de?ne a matrix?Z such that?Z·c,the column c of?Z,is equal to z c/(z T c z c)1/2.?Z is an orthonormal matrix(?Z T?Z=I k),and the objective that we want to minimize can be re-written as:
k c=1?Z T
·c
(E?2W)?Z·c=trace(?Z T(E?2W)?Z).(6)
It has been shown that the kernel k-means objective function can also be expressed as a trace optimization problem(Dhillon et al.2004a).In particular,the kernel k-means objective is
A LGORITHM2:Semi-supervised kernel k-means for HMRF-KMEANS.
K ERNEL-HMRF-KMEANS(S,k,W,t max)
Input:S:input similarity matrix,k:number of clusters,W:constraint penalty matrix,t max:optional maximum number of iterations
Output:{πc}k c=1:?nal partitioning of the points
1.Form the matrix K=S+W.
2.Diagonal-shift K by addingσI to guarantee positive de?niteness.
3.Get initial clusters{π(0)
c }k c=1using constraints encode
d in W and farthest-?rst
initialization(see Algorithm3).
4.Return{πc}k c=1=K ERNEL-KMEANS(K,k,t max,1,{π(0)c}k c=1),where1is the vector of all ones.
A LGORITHM3:Farthest-?rst initialization.
F ARTHEST F IRST I NIT(A,k,W)
Input:A:input af?nity matrix,k:number of clusters,W:constraint penalty matrix
Output:{π(0)
c }k c=1:initial partitioning of the points
1.M=transitive closure of must-link constraints in W.
2.C M=connected components in M.
https://www.doczj.com/doc/b31311243.html,=components from C M disconnected across cannot-link boundaries.
4.Setπ(0)
1=largest connected component from CC;set i=1.
5.If k>i,go to Step
6.Else,go to Step8.
6.Find component CC j that is farthest from the current set of selected components {π(0)c}i c=1.
7.Setπ(0)
i+1=CC j;set i=i+1.Go to Step5.
8.Return{π(0)
c
}k c=1.
written as a maximization of trace(Y T KY),with Y analogous to?Z(an orthonormal indicator matrix).The only difference between these objectives is that our semi-supervised objective is expressed as a trace minimization,while kernel k-means is expressed as a trace maximiza-tion.To make our problem into a maximization problem,we note that for squared Euclidean distance, x i?x j 2=x T i x i+x T j x j?2x T i x j.Let S be the similarity matrix(S ij=x T i x j) and let?S be the matrix such that?S ij=S ii+S jj.Then,E=?S?2S.
By replacing E in the trace minimization,the problem is equivalent to the minimiza-tion of trace(?Z T(?S?2S?2W)?Z).We calculate trace(?Z T?S?Z)as2·trace(S),which is a constant and can be ignored in the optimization.This leads to a maximization of trace(?Z T(S+W)?Z).If we de?ne a matrix K=S+W,our problem is expressed as a maximization of trace(?Z T K?Z),and is mathematically equivalent to unweighted kernel k-means.
Note that this matrix K may not be positive semide?nite,a requirement for kernel k-means to converge.One can avoid this problem by performing diagonal shifting(Dhillon et al.2007)for kernelizing K,as shown in Step2of Algorithm2.This is done by addingσI to K.Note that
trace(?Z T(σI+K)?Z)=σ·trace(?Z T?Z)+trace(?Z T K?Z)
=σk+trace(?Z T K?Z).
A constant is added to the objective function,so the globally optimal solution is the same for both the shifted and unshifted matrices.Thus,shifting the diagonal allows one to con-struct a positive semi-de?nite matrix K(since addingσI to K increases the eigenvalues byσ),which guarantees monotonic convergence of the kernel k-means algorithm to a lo-cal optimum,while maintaining the globally optimal solution.As mentioned in Sect.2.1, one can run kernel k-means directly on K—even though there is no theoretical guarantee of convergence in this case,the algorithm generally monotonically converges in practice.
3.2The algorithm
Summarizing the result from the previous section,we have shown an equivalence be-tween unweighted kernel k-means and HMRF-KMEANS with squared Euclidean distance and cluster-size weighted penalties.We can now discuss a kernel-based algorithm for this HMRF-KMEANS objective by constructing the appropriate kernel matrix K(see Algo-rithm2).This algorithm simply constructs the kernel(as derived in the previous section), performs proper cluster initialization and runs kernel k-means.
A key advantage to this approach is that the algorithm assumes a similarity matrix as input.As given in the derivation,the similarity matrix is the matrix of vector inner products (i.e.the Gram matrix),but one can easily generalize this by applying a kernel function on the vector data to form the similarity matrix.Thus,unlike previous approaches to optimizing the HMRF-KMEANS objective function,our approach is easily generalized to handle non-linear cluster boundaries—for example,by applying a Gaussian kernel when forming the similarity matrix.
A step that we have not yet discussed is the initialization of the clusters prior to running kernel k-means.In standard k-means,many different initialization schemes are possible for generating starting clusters.However,in our case,the constraint information gives us im-portant clues about the cluster structure,and this information may be incorporated into the initialization step of the algorithm.For cluster initialization,we follow the approach of Basu et al.(2004b).We?rst take the transitive closure of the must-link constraints,assuming that all constraints are consistent.This gives us a set of connected components of must-link con-straints.
We then infer additional cannot-link constraints in the following way:if there exists a cannot-link constraint between two connected components,we add cannot-link constraints between all pairs of points a and b,where a belongs to the?rst connected component and b belongs to the second connected component.
After this step,we generate initial clusters by using a farthest-?rst algorithm.We com-pute the connected components and then choose k of these as the k initial clusters.The farthest?rst algorithm selects the largest connected component,then iteratively chooses the cluster farthest away from the currently chosen cluster,where the distance between clusters is measured by the total pairwise distance between the points in these clusters.Once these k initial clusters are chosen,we initialize all points by placing them in their closest cluster. Note that all the distance computations in this procedure can be performed ef?ciently in kernel space.
4Semi-supervised graph clustering
As discussed earlier,there is a direct mathematical connection between the weighted kernel k-means objective function and a wide class of graph clustering objectives.So far we have
considered the vector case while deriving the connection between HMRF-KMEANS and ker-nel k-means.In this section,we generalize this result for the case of several semi-supervised graph clustering objective functions.
4.1Objective functions
The HMRF-KM EANS objective function was motivated as a three-term objective function: one term for the clustering objective,one term for enforcing must-link constraints,and one term for enforcing cannot-link constraints.In the same vein,we now consider three semi-supervised graph clustering objectives,where the clustering objectives are graph-based in-stead of vector-based.
Semi-supervised normalized cut A semi-supervised version of the normalized graph cut objective seeks to minimize:
k c=1links(V c,V\V c)
degree(V c)
?
x i,x j∈M
l i=l j
w ij
deg(V l
i
)
+
x i,x j∈C
l i=l j
w ij
deg(V l
i
)
·(7)
Notice that,instead of cluster-size weighted penalties,we use degree-weighted penalties. Semi-supervised ratio cut Similarly,a semi-supervised ratio cut objective can be written as the minimization of:
k c=1links(V c,V\V c)
|V c|
?
x i,x j∈M
l i=l j
w ij
|V l
i
|
+
x i,x j∈C
l i=l j
w ij
|V l
i
|
·(8)
Semi-supervised ratio association Finally,the semi-supervised ratio association objective can be written as the maximization of:
k c=1links(V c,V c)
V c
+
x i,x j∈M
l i=l j
w ij
V l
i
?
x i,x j∈C
l i=l j
w ij
V l
i
·(9)
Note that the second and third terms in this objective function have opposite signs to the corresponding terms in the semi-supervised ratio cut and semi-supervised normalized cut objectives;this is because we aim to maximize the association.
4.2A kernel-based algorithm for semi-supervised graph clustering
We now provide a general algorithm for semi-supervised graph clustering that can optimize each of the three objectives given above.To do that,we must show that each of these objec-tives can be written as a special case of the weighted kernel k-means objective function.
First,consider minimizing semi-supervised normalized cut.Based on the analysis of Yu and Shi(2003),the?rst term in the semi-supervised normalized cut objective function can be expressed as k?trace(?Y T D?1/2AD?1/2?Y),where?Y is an orthonormal cluster in-dicator matrix,D is the diagonal matrix of node degrees,and A is the graph adjacency
Table 3Semi-supervised graph clustering objectives and corresponding weights and kernels given af?nity matrix A and constraint matrix W
Objective
Node weights Kernel SS ratio association
1for all nodes K =σI +A +W SS ratio cut
1for all nodes K =σI ?L +W SS normalized cut Degree of the node K =σD ?1+D ?1(A +W )D ?1
A LGORITHM 4:Semi-supervised graph clustering algorithm.SS-K ERNEL -KMEANS (A ,obj ,k ,W ,t max )
Input:A :input af?nity matrix,obj :clustering objective,k :number of clusters,W :constraint penalty matrix,t max :optional maximum number of iterations
Output:{πc }k c =1:?nal partitioning of the points
1.Generate a vector αof node weights based on obj using Table 3.
2.If obj is SS-ratio-cut,reset A as A ?D .
3.Form K =σ·diag (α)?1+diag (α)?1(A +W )diag (α)?1.
4.Get initial clusters {π(0)c }k c =1using the constraints encoded in W and weighted farthest-?rst initialization (see Algorithm 3).
5.Return {πc }k c =1=K ERNEL -KMEANS (K ,k ,t max ,α,{π(0)c }k c =1).
matrix.The second and third term of the objective function may be expressed concisely as ?trace (?Y
T D ?1/2W D ?1/2?Y ),using similar analysis as in the derivations of (5)and (6).Combining these two terms,we get that the semi-supervised normalized cut objective is equivalent to minimizing k ?trace (?Y
T D ?1/2(A +W )D ?1/2?Y )or,equivalently,maximizing trace (?Y T D ?1/2(A +W )D
?1/2?Y ).A generalization of the analysis of Dhillon et al.(2007)allows us to express this trace maximization exactly as weighted kernel k -means,as fol-lows.We set A =A +W as in the unweighted case,and run weighted kernel k -means on σD ?1+D ?1A D ?1with weights equal to the degree of the node.Running weighted kernel k -means with this kernel and weights will then monotonically decrease the objective in (7)for a graph with adjacency matrix A .
Analogous results may be obtained for semi-supervised ratio cut and semi-supervised ratio association,using similar analysis.For semi-supervised ratio cut,we run weighted kernel k -means on σI ?L +W (L is the Laplacian of A )with all weights equal to one.In ratio association,we run weighted kernel k -means on σI +A +W with all weights equal to one.In all cases,the addition of supervision to weighted kernel k -means simply requires adding a constraint matrix W appropriately to the kernel matrix.
Table 3summarizes the kernel and weight construction for each of these semi-supervised clustering objective functions to be equivalent to the weighted kernel k -means objective,and Algorithm 4describes the general kernel-based semi-supervised clustering algorithm.Note that further generalizations are possible;one could have a general,weighted semi-supervised graph clustering objective that is normalized by the sum of arbitrary weights instead of the degrees of a cluster or the cluster sizes.In this case αwould be an arbitrary weight vector.
Also note that the case of semi-supervised ratio association is identical to the earlier algorithm for HMRF-KM EANS ,with a graph adjacency matrix used as the input similarity matrix.
4.3Connections to spectral learning
We can view S PECTRAL-LEARNING(Kamvar et al.2003),described in Sect.2.2.2,in our framework as follows:for a must-link constraint,if A ij is the similarity between x i and x j,we set W ij=1?A ij(and hence the corresponding value in A+W is1).Similarly, for cannot-links,we set W ij=?A ij(and hence the corresponding value in A+W is0).
With this particular choice of constraint weights,the matrix A+W is identical to the matrix from S PECTRAL-LEARNING before additive normalization.This leaves just the additive normalization step,which is the same normalization required for semi-supervised ratio cut (up to a diagonal shift,which does not change the globally optimal solution).
A well-known relaxation to our trace maximization problem,trace(Y T KY),is achieved by taking the top k eigenvectors of K.The matrix formed by these eigenvectors is the opti-mal Y matrix,under the relaxation that Y is an arbitrary orthonormal matrix.Such a relax-ation leads to the S PECTRAL-LEARNING algorithm that was detailed in Sect.2.2.2.
Thus,the S PECTRAL-LEARNING algorithm may be viewed as solving a relaxed semi-supervised ratio cut objective.Moreover,our earlier analysis shows that the fast iterative kernel k-means algorithm can be used to optimize this objective,thus removing any require-ment for the expensive operation of eigen-decomposition(for large data sets).Alternatively, this analysis suggests other spectral algorithms based on semi-supervised normalized cut or semi-supervised ratio association.
One could analogously hope to employ kernel k-means to optimize the semi-supervised formulation of Yu and Shi(2004).However,because of the additional constraint introduced for must-link constraints into the formulation,it is not possible to apply kernel k-means directly.However,recent results have shown how to express kernel k-means as a continuous optimization problem(Kulis et al.2007).The extra must-link constraints may be added naturally in this setting,and the algorithm of Kulis et al.(2007)may then be applied to optimize the semi-supervised clustering objective introduced by Yu and Shi.As a result,no eigenvector decomposition would be required.We leave this as a potential area of future work.
5Experimental results
In this section,we present experimental results on both vector data and graph data.First, we compare SS-K ERNEL-KMEANS to HMRF-KMEANS on vector data,which optimizes an HMRF-based objective function using squared Euclidean distance as the distortion mea-sure.We present results on a synthetic data set,handwritten character recognition data sets, and a protein data set,demonstrating that SS-K ERNEL-KMEANS has better performance on these data sets with a proper choice of the kernel.We then present results of SS-K ERNEL-KMEANS on graph-based data—a gene network and an image data set,both of which can-not be clustered with HMRF-KMEANS.In this case,we compare results to S PECTRAL-L EARNING.
5.1Data sets
We performed experiments on the following vector-based datasets:
1.TwoCircles:A synthetic data set comprising of200data points in2dimensions—
100points in an inner circle are labeled to be in one class,and100data points in a surrounding outer circle are labeled to be in another class,as shown in Fig.1.
2.Digits:A subset of10%of the data points chosen randomly from three classes{3,8,9}
of the Pendigits handwritten digit recognition data set from the UCI Machine Learning Repository2—these three classes were chosen since distinguishing between sample hand-written digits from these classes visually is a dif?cult task.Each image is a black-and-white rectangular pixel display of a handwritten digit(either3,8or9).Using features like statistical moments and edge counts,each image was transformed to a16-dimensional vector.This dataset has317points,each in a16dimensional-space.Note that this data set has been used for testing other semi-supervised clustering algorithms,such as Bilenko et al.(2004),and that a subset of all the digits are used to make the clustering problem more challenging.
3.Letters:A subset of10%of the data points chosen randomly from three classes {I,J,L}of the Letters handwritten character recognition data set from the UCI Machine Learning Repository.This particular subset of227points in a16dimensional-space was chosen since it is a dif?cult visual problem to discriminate between these3types of handwritten characters.
4.Protein:This dataset contains20-dimensional feature vectors representing116pro-
teins from6functional classes(Xing et al.2003).
We also performed experiments on the following graph-based datasets:
1.GeneNetwork:An interaction network between216yeast genes,where each gene is
labeled with one of3KEGG(Ogata et al.1999)functional pathway labels.This data is
a subgraph of a high-quality probabilistic functional network of yeast genes(Lee et al.
2004):each edge weight in this network represents a probability of linkage between two genes,estimated by integrating diverse functional genomic data sources.The genes do not have an explicit vector representation in this data set.
2.Caltech Image Data:We experimented with the Caltech-4data set which contains
1155automobile,800airplane,435face,and798motorcycle images(http://www.robots.
https://www.doczj.com/doc/b31311243.html,/~vgg/data3.html).The pyramid match kernel(Grauman and Darrell2005),
a kernel function between images,was used to generate a kernel matrix on a subset 2https://www.doczj.com/doc/b31311243.html,/?mlearn/MLRepository.html.
Fig.2Example images from the Caltech-4data set
of300images in this data set.This kernel function takes as input sets of image features from two images(the sets may have different cardinality),and does an appropriate par-tial matching between these sets.As with the gene network,there is no explicit vector representation of this data set—the kernel function de?nes a matrix of kernel function evaluations,which is then viewed as a dense graph.Figure2contains examples from this data set.
Two different kernel matrices were constructed from this data set,generated using different methods.The?rst matrix,Caltech1,was generated using vocabulary-guided bins with SIFT descriptors from Harris and MSER detectors.The second,Caltech2, used uniform grid cells and SIFT descriptors extracted from a uniformly spaced grid on the image(Grauman and Darrell2005).
5.2Methodology
Figures3–9show learning curves with2-fold cross validation.These plots show the im-provement in clustering quality on the test set with increasing amount of pairwise constraints provided as supervision from the training set.These constraints are obtained by randomly selecting pairs of points from the training set,and creating must-link or cannot-link con-straints depending on whether the underlying classes of the two points are the same or different.Each point on the learning curve is an average of results over20runs.We generate constraints only using the training set,cluster the whole data without the labels,and evaluate the cluster quality only on the test set(Basu et al.2004b).We set each penalty weight w ij to be equal to n/(kC),where n is the number of data points,k is the number of clusters, and C is the total number of constraints–this was done to make the constraint penalty term approximately of the same scale as the distance penalty term between data points and the cluster centroids.
To evaluate clusters,we use Normalized Mutual Information(NMI):it is a standard tech-nique for determining the quality of clusters,by measuring the amount of statistical informa-tion shared by the random variables representing the cluster distribution and the underlying class distribution of the data points(Strehl et al.2000).If C is the random variable denoting the cluster assignments of the points,and K is the random variable denoting the underlying class labels on the points then the NMI measure is de?ned as:
NMI=
I(C;K)
(H(C)+H(K))/2
,(10)
where I(X;Y)=H(X)?H(X|Y)is the mutual information between the random variables X and Y,H(X)is the Shannon entropy of X,and H(X|Y)is the conditional entropy of X given Y(Cover and Thomas1991).The normalization by the average entropy of C and K makes the value of NMI stay between0and1.
5.3Results and discussion
Figure3shows the results on the TwoCircle data set.This synthetic dataset is used to demonstrate the effectiveness of SS-K ERNEL-KMEANS with the exponential kernel:this data set is not linearly separable in the original input space,but an exponential kernel K(x,y)=exp(? x?y 2/2ρ2)is able to linearly separate the2classes in the mapped space. Parameters such asρare typically chosen via cross-validation(for this simple example,an arbitrary value was chosen).SS-K ERNEL-KMEANS with the exponential kernel(SS-Kernel-KMeans-Exp)gives improved results with increasing number of pairwise constraints,until it reaches a NMI score of1.0on the test set.On the other hand,as expected,HMRF-KMEANS and SS-K ERNEL-KMEANS with a linear kernel(SS-Kernel-KMeans-Linear)are not able to get any improvement in performance on this dataset(NMI close to0),since both algorithms split the data linearly into two clusters and are completely unable to re-construct the non-linear class structure,even with as many as200constraints.For this?gure and the other ?gures,the NMI score with0constraints corresponds to the performance of the unsuper-vised clustering algorithm.
Figure4shows results on the Digits dataset.SS-K ERNEL-KMEANS gives the best performance when used with an exponential kernel,outperforming both HMRF-KMEANS with squared Euclidean distance and SS-K ERNEL-KMEANS with a linear kernel.Note that the SS-K ERNEL-KMEANS learning curves display a characteristic“dip”,where clustering accuracy decreases as a few initial constraints are provided,but after a certain point starts to increase and eventually rises above the initial point on the learning curve.We conjecture that this phenomenon is due to the fact that the kernel parameters learned using too few constraints are unreliable,and with higher number of constraints the parameter estimation becomes more accurate.
Since the GeneNetwork dataset is not vector-based,it cannot be clustered using HMRF-KMEANS.Three graph clustering objectives were used while clustering this dataset using SS-K ERNEL-KMEANS—normalized cut(SS-Kernel-KMeans-NormCut),ratio cut (SS-Kernel-KMeans-RatioCut)and ratio association(SS-Kernel-KMeans-RatioAssoc).The fourth plot in the?gure(Spectral-Learning)corresponds to the S PECTRAL-LEARNING al-gorithm(Kamvar et al.2003).As shown in Fig.5,all these algorithms have an improvement in performance with increasing supervision,but SS-K ERNEL-KMEANS with normalized cut has the best performance for this dataset.
Fig.5Results on
GeneNetwork data set
The bene?t of using SS-K ERNEL-KMEANS is clearly demonstrated in this experiment.
A closer look showed that the GeneNetwork data set has3clusters of different sizes and different edge densities,which explains why performing degree normalization in the normalized cut objective gives good results.While S PECTRAL-LEARNING can only use the ratio cut objective,SS-K ERNEL-KMEANS can work with other graph clustering objectives like normalized cut,therefore making it useful in domains where graph clustering objectives other than ratio cut are more effective.
Figures6and7show the results on the Letters and Protein data respectively. As expected,the NMI improves with increasing number of constraints,demonstrating that semi-supervised kernel KMeans performs better than the unsupervised version for these datasets too.The ratio association using an exponential kernel(SS-Kernel-Ratio-Association)outperforms normalized cut and ratio cut on these two datasets.For a detailed analysis of why different graph clustering objectives perform well on different datasets, please see Dhillon et al.(2007).Note that on these datasets,HMRF-KMEANS outperforms
Fig.7Results on Protein
data set
or matches the performance of our methods,implying that it is necessary to try different kernels for these particular datasets.
Figures8and9show the results on the Caltech1and Caltech2kernel matrices. Again,we see an increase in the NMI as the number of constraints increases.Moreover,we see that semi-supervised ratio cut performs much worse than the other methods;this may be due to the positive-de?nite shifting issues inherent in using kernel k-means for ratio cut.
For comparison,we also ran S PECTRAL-L EARNING on the Caltech image data sets. Surprisingly,we found that Spectral Learning demonstrates extremely poor clustering gen-eralization accuracy on this data.The NMI of the clustering results on all the data points improves with increasing supervision,but the NMI on the test data points(which is what is shown in the plots)actually decreases as the number of constraints increases.For example, on Caltech1,the NMI goes from0.11with50constraints to0.01with500constraints. Similar performance is achieved on the Caltech2data.Thus,spectral learning appears to be over?tting on this data.We hypothesize that the penalty weights inherent in spectral learning lead to perturbation in the kernel matrix,which ultimately degrades generalization performance.In our kernel-based algorithms,the penalties decrease as the number of con-
Fig.9Results on Caltech2
data set
straints increase,which empirically appears to be an effective strategy in the presence of many constraints.
Regarding run-time complexity,the different variants of the semi-supervised clustering algorithms took substantially less time than the S PECTRAL-L EARNING algorithm.This is because S PECTRAL-L EARNING requires expensive eigenvalue calculations,while the SS-K ERNEL-KMEANS algorithms are pseudo-linear in the size of the input(i.e.,linear in the size of the graph×the number of iterations until convergence).In particular,on the GeneNetwork data set,the SS-K ERNEL-KMEANS algorithm required0.307seconds on average to converge,while S PECTRAL-L EARNING cost4.787seconds on average(15.6 times longer).Given that this is a small data set,even more substantial gains will occur for larger data sets.For example,in Dhillon et al.(2007),it was shown that an implementa-tion of kernel k-means is hundreds to thousands of times faster than spectral methods for unsupervised large-scale graph clustering.
6Conclusions and future work
In this paper,a new algorithm SS-K ERNEL-KMEANS was developed to optimize a semi-supervised clustering objective that can cluster both vector-based and graph-based data. The analysis for this algorithm used kernel methods:by constructing an appropriate ker-nel,we were able to prove an equivalence between a special case of the HMRF-based semi-supervised clustering objective and the kernel k-means objective function.The result-ing algorithm provided a number of advantages over previously studied methods for semi-supervised clustering:(1)our analysis allows us to(locally)optimize the semi-supervised objective for both vector-based and graph-based inputs;(2)for vector-based inputs,the in-puts can be mapped to a higher-dimensional kernel space to get non-linear cluster bound-aries;(3)we can easily generalize the result to handle a number of semi-supervised graph clustering objectives;(4)the analysis allows us to link prior work on spectral learning to our semi-supervised clustering framework.
There are a number of interesting potential avenues for future research in kernel methods for semi-supervised clustering.Along with learning the kernel matrix before the clustering, one could additionally incorporate kernel matrix learning into the clustering iteration,as was done in Basu et al.(2004b).One way to incorporate learning into the clustering step is to de-vise a way to learn the weights in weighted kernel k-means,by using the constraints.Another possibility would be to explore the generalization of techniques in this paper beyond squared Euclidean distance,for unifying semi-supervised graph clustering with kernel-based clus-tering on an HMRF using other popular clustering distortion measures,e.g.,KL-divergence, or cosine distance(Basu et al.2004b).We would also like to extend the work of Basu et al.(2004a)to explore techniques of active learning and model selection in the context of semi-supervised kernel clustering.To speed up the algorithm further,the multi-level meth-ods of Dhillon et al.(2007)can be employed.
Acknowledgements This research was supported by NSF grant CCF-0431257,NSF-ITR award IIS-0325116,NSF Career Award ACI-0093404,and a Google Research Grant.We thank Kristen Grauman for the pyramid match data used for image clustering.We would also like to thank the anonymous reviewers for their detailed and very useful feedback.
References
Bansal,N.,Blum,A.,&Chawla,S.(2002).Correlation clustering.In Proceedings of the43rd IEEE sympo-sium on foundations of computer science(FOCS-02)(pp.238–247).
Bar-Hillel,A.,Hertz,T.,Shental,N.,&Weinshall,D.(2003).Learning distance functions using equivalence relations.In Proceedings20th international conference on machine learning(pp.11–18).
Basu,S.,Banerjee,A.,&Mooney,R.J.(2002).Semi-supervised clustering by seeding.In Proceedings of 19th international conference on machine learning(ICML-2002)(pp.19–26).
Basu,S.,Banerjee,A.,&Mooney,R.J.(2004a).Active semi-supervision for pairwise constrained clustering.
In Proceedings4th SIAM international conference on data mining.
Basu,S.,Bilenko,M.,&Mooney,R.J.(2004b).A probabilistic framework for semi-supervised clustering In Proceedings of10th ACM SIGKDD international conference on knowledge discovery and data mining (KDD-2004)(pp.59–68).
Bie,T.D.,Momma,M.,&Cristianini,N.(2003).Ef?ciently learning the metric using side-information.In Lecture notes in arti?cial intelligence:Vol.2842.Proceedings of the14th international conference on algorithmic learning theory(ALT2003)(pp.175–189).Berlin:Springer.
Bilenko,M.,&Basu,S.(2004).A comparison of inference techniques for semi-supervised clustering with hidden Markov random?elds.In Proceedings of the ICML-2004workshop on statistical relational learning and its connections to other?elds(SRL-2004),Banff,Canada.
Bilenko,M.,Basu,S.,&Mooney,R.(2004).Integrating constraints and metric learning in semi-supervised clustering.In Proceedings of the21st international conference on machine learning.
1.如何使用画图工具 想在电脑上画画吗？很简单，Windows 已经给你设计了一个简洁好用的画图工具，它在开始菜单的程序项里的附件中，名字就叫做“画图”。 启动它后，屏幕右边的这一大块白色就是你的画布了。左边是工具箱，下面是颜色板。 现在的画布已经超过了屏幕的可显示范围，如果你觉得它太大了，那么可以用鼠标拖曳角落的小方块，就可以改变大小了。 首先在工具箱中选中铅笔，然后在画布上拖曳鼠标，就可以画出线条了，还可以在颜色板上选择其它颜色画图，鼠标左键选择的是前景色，右键选择的是背景色，在画图的时候，左键拖曳画出的就是前景色，右键画的是背景色。
选择刷子工具，它不像铅笔只有一种粗细，而是可以选择笔尖的大小和形状，在这里单击任意一种笔尖，画出的线条就和原来不一样了。 图画错了就需要修改，这时可以使用橡皮工具。橡皮工具选定后，可以用左键或右键进行擦除，这两种擦除方法适用于不同的情况。左键擦除是把画面上的图像擦除，并用背景色填充经过的区域。试验一下就知道了，我们先用蓝色画上一些线条，再用红色画一些，然后选择橡皮，让前景色是黑色，背景色是白色，然后在线条上用左键拖曳，可以看见经过的区域变成了白色。现在把背景色变成绿色，再用左键擦除，可以看到擦过的区域变成绿色了。 现在我们看看右键擦除：将前景色变成蓝色，背景色还是绿色，在画面的蓝色线条和红色线条上用鼠标右键拖曳，可以看见蓝色的线条被替换成了绿色，而红色线条没有变化。这表示，右键擦除可以只擦除指定的颜色－－就是所选定的前景色，而对其它的颜色没有影响。这就是橡皮的分色擦除功能。 再来看看其它画图工具。 是“用颜料填充”，就是把一个封闭区域内都填上颜色。 是喷枪，它画出的是一些烟雾状的细点，可以用来画云或烟等。 是文字工具，在画面上拖曳出写字的范围，就可以输入文字了，而且还可以选择字体和字号。 是直线工具，用鼠标拖曳可以画出直线。
LAMMPS手册-中文解析 一、 欧阳家百（2021.03.07） 二、简介 本部分大至介绍了LAMMPS的一些功能和缺陷。 1．什么是LAMMPS? LAMMPS是一个经典的分子动力学代码，他可以模拟液体中的粒子，固体和汽体的系综。他可以采用不同的力场和边界条件来模拟全原子，聚合物，生物，金属，粒状和粗料化体系。LAMMPS可以计算的体系小至几个粒子，大到上百万甚至是上亿个粒子。 LAMMPS可以在单个处理器的台式机和笔记本本上运行且有较高的计算效率，但是它是专门为并行计算机设计的。他可以在任何一个按装了C++编译器和MPI的平台上运算，这其中当然包括分布式和共享式并行机和Beowulf型的集群机。 LAMMPS是一可以修改和扩展的计算程序，比如，可以加上一些新的力场，原子模型，边界条件和诊断功能等。 通常意义上来讲，LAMMPS是根据不同的边界条件和初始条件对通过短程和长程力相互作用的分子，原子和宏观粒子集合对它们的牛顿运动方程进行积分。高效率计算的LAMMPS通过采用相邻清单来跟踪他们邻近的粒子。这些清单是根据粒子间的短程互拆力的大小进行优化过的，目的是防止局部粒子密度过高。在
并行机上，LAMMPS采用的是空间分解技术来分配模拟的区域，把整个模拟空间分成较小的三维小空间，其中每一个小空间可以分配在一个处理器上。各个处理器之间相互通信并且存储每一个小空间边界上的”ghost”原子的信息。LAMMPS(并行情况)在模拟3维矩行盒子并且具有近均一密度的体系时效率最高。 2．LAMMPS的功能 总体功能： 可以串行和并行计算 分布式MPI策略 模拟空间的分解并行机制 开源 高移植性C++语言编写 MPI和单处理器串行FFT的可选性（自定义） 可以方便的为之扩展上新特征和功能 只需一个输入脚本就可运行 有定义和使用变量和方程完备语法规则 在运行过程中循环的控制都有严格的规则 只要一个输入脚本试就可以同时实现一个或多个模拟任务 粒子和模拟的类型： （atom style命令） 原子 粗粒化粒子 全原子聚合物，有机分子，蛋白质，DNA
细节决定成败 ——认识“画图”软件教学案例 【事件背景】 2014年9月29日按照学校教学安排，把精心准备的《认识“画图”软件》一课在学科组内做了认真的课堂展示。这节课是小学三年级的课，前节课学生初步认识了纸牌游戏软件，对在Windows中打开软件、认识窗口有了初步的了解。但是学生初学画图，鼠标拖动操作还不熟练，在技巧上还有待于逐步尝试掌握。根据学生原有的水平我提出了一个设计思路，即“作品欣赏，激发兴趣，互相讨论，任务驱动，指导点评”。 课堂中重难点的处理我主要是采用任务驱动教学法，设置了三个学习任务，分别以不同形式完成。对于第一个任务：启动“画图”软件，让学生自学教材P31，完成“画图”软件的启动。是为培养学生的自主学习能力，多数学生都能顺利启动后，找两个同学示范启动，锻炼了学生的动手操作和语言表达能力。第二个任务：认识“画图”软件的窗口组成我主要是用事先录制好的微课展示让学生记住。学生对这种形式感到很新奇，自然很快就记住了。第三个任务是这节课的重点也是难点：尝试用画图工具简单作画。 【事件描述】 根据教学设计，我全身心的投入到本节课的教学实践之中，课堂伊始效果良好，学生不仅对学习内容表现出了极大的兴趣，而且行为表现也很规范，学习状态认真。所以很顺畅的完成了第一个学习任务，紧接着便进入第二个环节的学习，即认识画图软件的窗口。为了很好的完成这一重要的学习任务，我对教学设计几经修改，最后决定采用‘微课’的形式，我便精心制作课件，录音合成，以图示加拟人风格的自述形式进行软件的自我介绍。当初我想这样做一定会收到事半功倍的效果，期待着在课堂上那称心一幕的出现。事实又是怎样的呢？
Pymol作图的实例 这是一个只是用鼠标操作的初步教程 Pdb文件3ODU.pdb 打开文件 pymol右侧 All指所有的对象，2ODU指刚才打开的文件，(sele)是选择的对象 按钮A:代表对这个对象的各种action， S：显示这个对象的某种样式， H：隐藏某种样式， L：显示某种label， C：显示的颜色 下面是操作过程： 点击all中的H，选择everything，隐藏所有 点击3ODU中的S，选择cartoon，以cartoon形式显示蛋白质 点击3ODU中的C，选择by ss，以二级结构分配颜色，选择 点击右下角的S，窗口上面出现蛋白质氨基酸序列，找到1164位ITD，是配体 点击选择ITD ，此时sele中就包含ITD这个残基，点击（sele）行的A，选 择rename selection，窗口中出现，更改sele 为IDT，点击（IDT）行的S选择sticks，点击C，选择by element，选择，，调 整窗口使此分子清楚显示。 寻找IDT与蛋白质相互作用的氢键： IDT行点击A 选择find，选择polar contacts，再根据需要选择，这里选择to other atoms in object ,分子显示窗口中出现几个黄色的虚线，IDT行下面出现了新的一行，这就是氢键的对象，点击这一行的C，选择 red red，把氢键显示为红色。 接着再显示跟IDT形成氢键的残基 点击3ODU行的S，选择lines，显示出所有残基的侧链，使用鼠标转动蛋白质寻找与IDT 以红色虚线相连的残基，分别点击选择这些残基。注意此时selecting要是
residures。选择的时候要细心。取消选择可以再次点击已选择的残基。使用上述的方法把选择的残基（sele）改名为s1。点击S1行的S选择sticks，C选择by elements,点击L选择residures显示出残基名称.在这个例子中发现其中有一个N含有3个氢键有两个可以找到与其连接的氨基酸残基，另一个找不到，这是因为这个氢键可能是与水分子形成的，水分子在pdb文件中只用一个O表示，sticks显示方式没有显示出来水分子，点击all行S选择nonbonded，此时就看到一个水与N形成氢键 ，点击分子空白处，然后点击选择这个水分子，更改它的名字为w。在all 行点击H，选择lines，在选择nonbonded，把这些显示方式去掉只留下cartoon。点击w行s 选择nb-spheres. 到目前为止已经差不多了 下面是一些细节的调整 残基名称位置的调整：点击右下角是3-button viewing 转变为3-button viewing editing，这样就可以编辑修改 pdb文件了，咱们修改的是label的位置。按住ctrl键点击窗口中的残基名称label，鼠标拖拽到适合的部位，是显示更清晰。 然后调整视角方向直到显示满意为止，这时就可以保存图片了，file>>save image as>>png
上篇用几何画板做数理实验 图1-0.1 我们主要认识一下工具箱和状态栏，其它的功能在今后的学习过程中将学会使用。 案例一四人分饼 有一块厚度均匀的三角形薄饼，现在要把它平 均分给四个人，应该如何分？ 图1-1.1 思路：这个问题在数学上就是如何把一个三角形分成面积相等的四部分。 方案一：画三角形的三条中位线，分三角形所成的四部 分面积相等，（其实四个三角形全等）。如图1-1.2。 图1-1.2
方案二：四等分三角形的任意一边，由等底等高的三角 形面积相等，可以得出四部分面积相等，如图1-1.3。 图1-1.3 用几何画板验证： 第一步：打开几何画板程序，这时出现一个新绘图文件。 说明：如果几何画板程序已经打开，只要由菜单“文件” “新绘图”，也可以新建一个绘图文件。第二步：(1)在工具箱中选取“画线段”工具； (2)在工作区中按住鼠标左键拖动，画出一条线段。如图 1-1.4。 注意：在几何画板中，点用一个空心的圈表示。 图1-1.4 第三步：(1)选取“文本”工具；(2)在画好的点上单击左 键，可以标出两点的标签，如图1-1.5： 注意：如果再点一次，又可以隐藏标签，如果想改标签 为其它字母，可以这样做： 用“文本”工具双击显示的标签，在弹出的对话框中进 行修改，(本例中我们不做修改)。如图1-1.6 图1-1.6 在后面的操作中，请观察图形，根据需要标出点或线的 标签，不再一一说明 B 图1-1.5 第四步：(1)再次选取“画线段”工具，移动鼠标与点A 重合，按左键拖动画出线段AC；(2)画线段BC，标出标 签C，如图1-1.7。 注意：在熟悉后，可以先画好首尾相接的三条线段后再 标上标签更方便。 B 图1-1.7
画图工具阶段教学指引如何使用画图工具 画图工具妙用文字工具 画图工具妙用圆形工具 画图工具妙用曲线工具 如何让画图工具存JPG格式 Win98 画图工具持JPG图片一法 Win98 画图工具持JPG图片二法 画图工具应用之屏幕拷贝 画图工具应用之双色汉字 画图工具应用之放大修改 画图工具应用之工具与颜色配置 画图工具应用之灵活编辑 画图工具操作技巧 画图工具应用技巧 画图工具另类技巧检测LCD的暗点
如何使用画图工具 想在电脑上画画吗？很简单，Windows 已经给你设计了一个简洁好用的画图工具，它在开始菜单的程序项里的附件中，名字就叫做“画图”。 启动它后，屏幕右边的这一大块白色就是你的画布了。左边是工具箱，下面是颜色板。 现在的画布已经超过了屏幕的可显示范围，如果你觉得它太大了，那么可以用鼠标拖曳角落的小方块，就可以改变大小了。 首先在工具箱中选中铅笔，然后在画布上拖曳鼠标，就可以画出线条了，还可以在颜色板上选择其它颜色画图，鼠标左键选择的是前景色，右键选择的是背景色，在画图的时候，左键拖曳画出的就是前景色，右键画的是背景色。
选择刷子工具，它不像铅笔只有一种粗细，而是可以选择笔尖的大小和形状，在这里单击任意一种笔尖，画出的线条就和原来不一样了。 图画错了就需要修改，这时可以使用橡皮工具。橡皮工具选定后，可以用左键或右键进行擦除，这两种擦除方法适用于不同的情况。左键擦除是把画面上的图像擦除，并用背景色填充经过的区域。试验一下就知道了，我们先用蓝色画上一些线条，再用红色画一些，然后选择橡皮，让前景色是黑色，背景色是白色，然后在线条上用左键拖曳，可以看见经过的区域变成了白色。现在把背景色变成绿色，再用左键擦除，可以看到擦过的区域变成绿色了。 现在我们看看右键擦除：将前景色变成蓝色，背景色还是绿色，在画面的蓝色线条和红色线条上用鼠标右键拖曳，可以看见蓝色的线条被替换成了绿色，而红色线条没有变化。这表示，右键擦除可以只擦除指定的颜色－－就是所选定的前景色，而对其它的颜色没有影响。这就是橡皮的分色擦除功能。 再来看看其它画图工具。 是“用颜料填充”，就是把一个封闭区域内都填上颜色。 是喷枪，它画出的是一些烟雾状的细点，可以用来画云或烟等。 是文字工具，在画面上拖曳出写字的范围，就可以输入文字了，而且还可以选择字体和字号。 是直线工具，用鼠标拖曳可以画出直线。 是曲线工具，它的用法是先拖曳画出一条线段，然后再在线段上拖曳，可以把线段上从拖曳的起点向一个方向弯曲，然后再拖曳另一处，可以反向弯曲，两次弯曲后曲线就确定了。 是矩形工具，是多边形工具，是椭圆工具，是圆角矩形，多边形工具的用法是先拖曳一条线段，然后就可以在画面任意处单击，画笔会自动将单击点连接
一、PPT模板与软件: 1、ScienceSlides: ScienceSlides就是一种PPT插件,可方便的画出各种细胞器化学结构,用来论文画图确实很好用。特别就是用这个与AI(illustrator)结合,画的图可以媲美老外的CNS哦。 2、科研医学美图PPT模板 3、200+套绝美PPT模板 二、代谢与信号分析软件: 1、CellNetAnalyzer: CellNetAnalyzer,就是一种细胞网络分析工具,前身就是FluxAnalyzer,就是基于MatLab的代谢网络与信号传导网络分析模块,。这就是一个典型的代谢流分析工具,可以进行代谢流的计算、预测、目标函数的优化,端途径分析、元素模式分析,以及代谢流之间的对比等。可以基本满足研究一个中型代谢网络的结构尤其就是计算流分配的要求,大部分论文中的代谢网络分析都就是或明或暗的用这个分析的。
2、信号通路图汇总 3、药理学思维导图 三、二维、三维构图软件: 1、DeepViewer _4、10_PC DeepViewer ,曾经也叫做Swiss-PdbViewer,就是一个可以同时分析几个蛋白的应用程序。为了结构比对并且比较活性位点或者任何别的相关部分,蛋白质被分成几个层次。氨基酸突变,氢键,原子间的角与距离在直观的图示与菜单界面上很容易获得。 2、pymol-0_99rc6-bin-win32 PyMOL就是一个开放源码,由使用者赞助的分子三维结构显示软件。PyMOL适用于创作高品质的小分子或就是生物大分子(特别就是蛋白质)的三维结构图像。PyMOL的源代码目前仍可以免费下载,供使用者编译。对于Linux、Unix以及Mac OS X等操作系统,非付费用户可以通过自行编译源代码来获得PyMOL执行程式;而对于Windows的使用者,如果不安装第三方软件,则无法编译源代码。 四、分子生物学软件
Pymol作图的实例 这就是一个只就是用鼠标操作的初步教程 Pdb文件3ODU、pdb 打开文件 pymol右侧 All指所有的对象,2ODU指刚才打开的文件,(sele)就是选择的对象 按钮A:代表对这个对象的各种action, S:显示这个对象的某种样式, H:隐藏某种样式, L:显示某种label, C:显示的颜色 下面就是操作过程: 点击all中的H,选择everything,隐藏所有 点击3ODU中的S,选择cartoon,以cartoon形式显示蛋白质 点击3ODU中的C,选择by ss,以二级结构分配颜色,选择 点击右下角的S,窗口上面出现蛋白质氨基酸序列,找到1164位ITD,就是配体 点击选择ITD ,此时sele中就包含ITD这个残基,点击(sele)行的A,选择rename selection,窗口中出现,更改sele为IDT,点击 (IDT)行的S选择sticks,点击C,选择by element,选择,,调整窗口使此分子清楚显示。 寻找IDT与蛋白质相互作用的氢键: IDT行点击A 选择find,选择polar contacts,再根据需要选择,这里选择to other atoms in object , 分子显示窗口中出现几个黄色的虚线,IDT行下面出现了新的一行 ,这就就是氢键的对象,点击这一行的C,选择red red,把氢键显示为红色。 接着再显示跟IDT形成氢键的残基 点击3ODU行的S,选择lines,显示出所有残基的侧链,使用鼠标转动蛋白质寻找与IDT以红色虚线相连的残基,分别点击选择这些残基。注意此时selecting要就是 residures。选择的时候要细心。取消选择可以再次点击已选择
《认识画图软件》教学设计 任教教师：苗丽娟 所在学校：复兴小学
《认识画图软件》教学设计 教学目标： 1、能熟练启动并退出画图软件； 2、认识画图软件的窗口并了解各种绘画工具的使用； 3、能绘制简单的图形。 重点难点： 了解各种绘画工具的使用。 教学时间：一课时 课前准备： 课件 教学过程： 一、导入 1、今天的天气真好,阳光明媚,老师和大家一起来欣赏一些作品(出示课件) 师：这些画漂不漂亮,它们不仅漂亮而且还很神奇。因为不是用笔和纸画出来的，而是用电脑上的画图软件画出来的。同学们想不想成为一名电脑绘画小高手。那就和老师一起来学习这一课：认识画图软件（课件出示） 二、新授 1、启动画图软件： 课件出示启动画图软件的方法，请同学们根据课件演示操作。 2、认识画图软件窗口： 课件出示画图软件窗口。 3、认识工具箱 （1）师问：工具箱中有多少个按钮？ 师：告诉大家一个方法，当我们把鼠标指针放到某个工具上时就会在它的旁边出现它的名字，而且下面任务栏中会出现对这个工具使用方法的介绍。 现在就请大家发挥你的小组合作能力，自主的探究一下这些工具： （2）课件出示：合作探究：工具箱中的各种工具有些什么作用？怎样使用？
（3）师说明活动要求：两人为一个小组进行合作，解决上述问题。 （4）学生操作。师和学生单独交流，了解学生学习情况，收集学生问题。（5）师问：谁愿意说说你对哪个工具最了解？它的名称是什么？怎样使用？（学生边说边演示，鼓励台下学生向台上演示的学生提出不懂的问题并寻求解决方法） 4、认识调色板： 课件出示选色框图：上面框中的颜色称为前景色，下面框中的颜色称为背景色 我们已经简单的认识了一些工具，现在我们画一个简单的图形并给它涂上颜色。 生画完后，师：在刚才的上色过程中为什么只有前景色会变化？背景色怎样改变？大家尝试一下。 师总结：单击左键拾取前景色，单击右键拾取背景色。 课件出示儿歌： 调色板儿真方便，多种颜色我来选。 单击左键前景色，单击右键背景色。 前景背景不一样，两键单击记心间。 三、退出画图软件 师：当图软件用完之后，怎样退出呢？聪明的你们能不能从课本上找到答案？有几种方法？ 第一种: 单击“文件(F)”菜单中的“退出(X)”命令，可以退出“画图”程序。 第二种:按一下右上角的× 师：如果还没有保存画好或修改过的图形，则在退出“画图”程序时，屏幕上会出现“画图”对话框，这时，如果单击“是(Y)”按钮，则保存图形后再退出；如果单击“否(N)”按钮，则不保存图形就退出；如果单击“取消”按钮，则不退出“画图”程序。 四、赛一赛
p y m o l作图的一个实 例
Pymol作图的实例 这是一个只是用鼠标操作的初步教程 Pdb文件3ODU.pdb 打开文件 pymol右侧 All指所有的对象，2ODU指刚才打开的文件，(sele)是选择的对象 按钮A:代表对这个对象的各种action， S：显示这个对象的某种样式， H：隐藏某种样式， L：显示某种label， C：显示的颜色 下面是操作过程： 点击all中的H，选择everything，隐藏所有 点击3ODU中的S，选择cartoon，以cartoon形式显示蛋白质 点击3ODU中的C，选择by ss，以二级结构分配颜色，选择 点击右下角的S，窗口上面出现蛋白质氨基酸序列，找到1164位ITD，是配体点击选择ITD ，此时sele中就包含ITD这个残基，点击（sele）行的A，选择rename selection，窗口中出现
，更改sele为IDT，点击（IDT）行的S选择sticks，点击C，选择by element，选择，，调整窗口使此分子清楚显示。 寻找IDT与蛋白质相互作用的氢键： IDT行点击A 选择find，选择polar contacts，再根据需要选择，这里选择to other atoms in object ,分子显示窗口中出现几个黄色的虚线 ，IDT行下面出现了新的一行 ，这就是氢键的对象，点击这一行的C，选择red red，把氢键显示为红色。 接着再显示跟IDT形成氢键的残基 点击3ODU行的S，选择lines，显示出所有残基的侧链，使用鼠标转动蛋白质寻找与IDT以红色虚线相连的残基，分别点击选择这些残基。注意此时selecting要是residures。选择的时候要细心。取消选择可以再次点击已选择的残基。使用上述的方法把选择的残基（sele）改名为s1。点击S1行的S选择sticks，C选择by elements,点击L选择residures显示出残基名称.在这个例子中发现其中有一个N含有3个氢键有两个可以找到与其连接的氨基酸残基，另一个找不到，这是因为这个氢键可能是与水分子形成的，水分子在pdb文件中只用一个O表示，sticks显示方式没有显示出来水分子，点击all行S选择nonbonded，此时就看到一个水与N形成氢键
如何使用画图工具 想在电脑上画画吗？很简单，Windows 已经给你设计了一个简洁好用的画图工具，它在开始菜单的程序项里的附件中，名字就叫做 “画图”。 启动它后，屏幕右边的这一大块白色就是你的画布了。左边是 工具箱，下面是颜色板。 现在的画布已经超过了屏幕的可显示范围，如果你觉得它太大了，那么可以用鼠标拖曳角落的小方块，就可以改变大小了。 首先在工具箱中选中铅笔，然后在画布上拖曳鼠标，就可以画出线条了，还可以在颜色板上选择其它颜色画图，鼠标左键选择的是
前景色，右键选择的是背景色，在画图的时候，左键拖曳画出的就是前 景色，右键画的是背景色。 选择刷子工具，它不像铅笔只有一种粗细，而是可以选择笔尖的大小和形状，在这里单击任意一种笔尖，画出的线条就和原来不一 样了。 图画错了就需要修改，这时可以使用橡皮工具。橡皮工具选定后，可以用左键或右键进行擦除，这两种擦除方法适用于不同的情况。左键擦除是把画面上的图像擦除，并用背景色填充经过的区域。试验一下就知道了，我们先用蓝色画上一些线条，再用红色画一些，然后选择橡皮，让前景色是黑色，背景色是白色，然后在线条上用左键拖曳，可以看见经过的区域变成了白色。现在把背景色变成绿色，再用左键擦除，可以看到擦过的区域变成绿色了。 现在我们看看右键擦除：将前景色变成蓝色，背景色还是绿色，在画面的蓝色线条和红色线条上用鼠标右键拖曳，可以看见蓝色的线条被替换成了绿色，而红色线条没有变化。这表示，右键擦除可以只擦除指定的颜色－－就是所选定的前景色，而对其它的颜色没有影响。 这就是橡皮的分色擦除功能。 再来看看其它画图工具。 是“用颜料填充”，就是把一个封闭区域内都填上颜色。 是喷枪，它画出的是一些烟雾状的细点，可以用来画云或烟 等。
CAD 绘制三维实体基础 AutoCAD除具有强大的二维绘图功能外，还具备基本的三维造型能力。若物体并无复杂的外表曲面及多变的空间结构关系，则使用AutoCAD可以很方便地建立物体的三维模型。本章我们将介绍AutoCAD 三维绘图的基本知识。 11.1 三维几何模型分类 在AutoCAD中，用户可以创建3种类型的三维模型：线框模型、表面模型及实体模型。这3种模型在计算机上的显示方式是相同的，即以线架结构显示出来，但用户可用特定命令使表面模型及实体模型的真实性表现出来。 11.1.1线框模型(Wireframe Model) 线框模型是一种轮廓模型，它是用线（3D空间的直线及曲线）表达三维立体，不包含面及体的信息。不能使该模型消隐或着色。又由于其不含有体的数据，用户也不能得到对象的质量、重心、体积、惯性矩等物理特性，不能进行布尔运算。图11-1显示了立体的线框模型，在消隐模式下也看到后面的线。但线框模型结构简单，易于绘制。 11.1.2 表面模型（Surface Model） 表面模型是用物体的表面表示物体。表面模型具有面及三维立体边界信息。表面不透明，能遮挡光线，因而表面模型可以被渲染及消隐。对于计算机辅助加工，用户还可以根据零件的表面模型形成完整的加工信息。但是不能进行布尔运算。如图11-2所示是两个表面模型的消隐效果，前面的薄片圆筒遮住了后面长方体的一部分。 11.1.3 实体模型 实体模型具有线、表面、体的全部信息。对于此类模型，可以区分对象的内部及外部，可以对它进行打孔、切槽和添加材料等布尔运算，对实体装配进行干涉检查，分析模型的质量特性，如质心、体积和惯性矩。对于计算机辅助加工，用户还可利用实体模型的数据生成数控加工代码，进行数控刀具轨迹仿真加工等。如图11-3所示是实体模型。 图11-1 线框模型 图11-2 表面模型 1、三维模型的分类及三维坐标系； 2、三维图形的观察方法； 3、创建基本三维实体； 4、由二维对象生成三维实体； 5、编辑实体、实体的面和边；
《画图软件画图忙》教学设计 ［教学目标］ (1)学习启动与退出“画图”程序。 (2)了解“画图”窗口的组成，特别是画图窗口独特的组成部分。 (3)学生通过自主探索初步认识绘图工具箱。 (4)通过对画图作品的欣赏和对画图程序的简单操作，培养学生对电脑画图的兴趣，从而进一步培养对信息技术的热爱。 ［教学重点与难点］ 重点：培养良好的画图习惯，能正确使用撤消和擦除。 难点：读懂对话框，学会保存作品。 ［课时安排］ 1课时。 [教学准备] 多媒体网络教室、多媒体课件 [教学过程] 一、激趣导入 师：今天，老师给大家带来了一位美术高手，但他不用纸笔，而是用电脑画画，想不想看他的精彩表演？ 播放《用“画图”画跑车》视频（2分钟）。
师：这位高手厉害不厉害？我们班有没有人能做到？想不想学？ 师：想成为高手可不是一朝一夕的事儿，我们要一点一滴地学习。首先，需要有敏锐的观察力。所以，我要考考大家，刚才视频中的高手是用哪个软件完成这幅图画的？ 师：看！这就是windows操作系统自带的“画图”程序。今天我们就来认识这个新朋友——“画图”。（板书课题） 二、教学新课 （一）启动“画图” 1．大家想认识这位新朋友吗？请你到电脑里把它找出来。 2.交流：你是如何找到这位新朋友的？ 3.是啊，联系以前学过的打开“写字板”的方法，同学们很快就找到了，这种知识迁移的方法是我们学习新知识的一种重要的方法。 （二）“画图”窗口 1.同学们都成功的启动了画图，看看这位新朋友，结合写字板，它窗口的哪些组成部分你认识呢？ 2.教师结合“写字板”引导小结。 常规部分：标题栏、菜单栏、状态栏 独特组成：工具箱、颜料盒、画图区 3.画图窗口中画图区就是我们用来画画的纸，我觉得这张纸太小了，你能帮我变大些吗？
一、PPT模板与软件： 1.ScienceSlides： ScienceSlides是一种PPT插件，可方便的画出各种细胞器化学结构，用来论文画图确实很好用。特别是用这个和AI（illustrator）结合，画的图可以媲美老外的CNS哦。 2.科研医学美图PPT模板 3.200+套绝美PPT模板 二、代谢与信号分析软件： 1.CellNetAnalyzer： CellNetAnalyzer，是一种细胞网络分析工具，前身是FluxAnalyzer，是基于MatLab的代谢网络和信号传导网络分析模块，。这是一个典型的代谢流分析工具，可以进行代谢流的计算、预测、目标函数的优化，端途径分析、元素模式分析，以及代谢流之间的对比等。可以基本满足研究一个中型代谢网络的结构尤其是计算流分配的要求，大部分论文中的代谢网络分析都是或明或暗的用这个分析的。
2. 信号通路图汇总 3. 药理学思维导图 三、二维、三维构图软件： 1.DeepViewer _4.10_PC DeepViewer ，曾经也叫做Swiss-PdbViewer，是一个可以同时分析几个蛋白的应用程序。为了结构比对并且比较活性位点或者任何别的相关部分，蛋白质被分成几个层次。氨基酸突变，氢键，原子间的角和距离在直观的图示和菜单界面上很容易获得。 2.pymol-0_99rc6-bin-win32 PyMOL是一个开放源码，由使用者赞助的分子三维结构显示软件。PyMOL适用于创作高品质的小分子或是生物大分子（特别是蛋白质）的三维结构图像。PyMOL的源代码目前仍可以免费下载，供使用者编译。对于Linux、Unix以及Mac OS X等操作系统，非付费用户可以通过自行编译源代码来获得PyMOL执行程式；而对于Windows的使用者，如果不安装第三方软件，则无法编译源代码。 四、分子生物学软件
MATLAB绘图
二维数据曲线图 p plot函数的基本调用格式为： x,y) ) plot( plot(x,y 其中x和y为长度相同的向量，分别用于存储x坐标和y坐标数据。 数据 例1 在0≤x2π区间内，绘制曲线y=2e-0.5x cos(4πx) 1≤区间内绘制曲线205x(4) 程序如下： x=0:pi/100:2*pi; cos(4*pi*x); 0.5*x).*cos (4*pi*x); y=2*exp(--0.5*x).* y=2*exp( x,y)) plot(x,y plot(x y plot( x y)
例2 绘制曲线。 绘制曲线 程序如下： t=0:0.1:2*pi; x=t.sin(3t); x=t*sin(3*t); y=t.*sin(t).*sin(t); plot( x,y);); plot(x,y
数最简单的调用格式是包含个输参数plot函数最简单的调用格式是只包含一个输入参数：p() plot(x) 在这种情况下，当x是实向量时，以该向量元素的下标为横坐标，元素值为纵坐标画出条连续曲线，标为横坐标，元素值为纵坐标画出一条连续曲线，这实际上是绘制折线图。
绘制多根二维曲线 1．plot函数的输入参数是矩阵形式时 数的输参数是矩阵形式时 (1) 当x是向量，y是有一维与x同维的矩阵时，则绘制出多根不同颜色的曲线。曲线条数等于y矩阵的另一维数，x被作为这些曲线共同的横坐标。 (2) 当x,y是同维矩阵时，则以x,y对应列元素为横、 纵坐标分别绘制曲线，曲线条数等于矩阵的列数。纵坐标分别绘制曲线曲线条数等于矩阵的列数
B2WS-6JGH-PV7G-PBKP 什么是结构生物学 结构生物学（Structural biology）是生物领域里面相对较新的一个分支。它主要以生物化学和生物物理学方法来研究生物大分子，特别是蛋白质和核酸，的三维结构，以及与结构相对应的功能。因为几乎所有的细胞内的生命活动都是通过生物大分子来完成的，并且这些大分子完成这些功能的前提是它们必须具有特定的三维结构，因此，对于生物化学家们，这是一个非常具有吸引力的领域。 该领域通常被认为开始于20世纪50年代，Max Perutzhe和Sir John Cowdery Kendrew于1959年各自利用X射线晶体学方法解析了肌红蛋白（Myoglobin）的三维结构，一种在肌肉中运输氧气的蛋白。他们因此分享了1962年的诺贝尔化学奖，并由此揭开了结构生物学的序幕。截止到2008年10月28日，已有53917个生物大分子结构在https://www.doczj.com/doc/b31311243.html, （蛋白质数据库）登记在案。 目前用于研究生物大分子结构的常用方法有X射线晶体学（X-ray crystallography）、核磁共振（NMR）、电子显微学（electron microscopy）、冷冻电子显微学（electron cryomicroscopy = cryo-EM）、超快激光光谱（ultra fast laser spectroscopy）、双偏振极化干涉（Dual Polarisation Interferometry）以及圆二色谱（circular dichroism）等。当中又以X射线晶体学和核磁共振最为常用。 图一：肌红蛋白（Myoglobin）的三维结构，世界上第一个由X射线晶体学解出的蛋白质结构，该蛋白在肌肉中传输氧气。
500mb高度场等直线图 .gs文件 * * Draw the COR.COEF SST and nhc000 * 'reinit' 'enable print h9601.31' 'clear' 'open hs.ctl' 'set dfile 1' 'set vpage 0.5 10. 0.2 8.5' 'set lon 0. 360.' 'set lat -90. 90.' 'set mproj latlon' 'set mpdset mres' 'set poli off' 'set ylint 10.' 'set xlint 20.' 'set csmooth on' 'set csmooth on' 'set csmooth on' 'set csmooth on' 'set csmooth on' 'set csmooth on' 'set csmooth on' 'set csmooth on' 'set clopts -1 -1 0.06' 'set clab forced' 'set cint 40.' 'set gxout contour' 'set cthick 4' 'set grads off' 'd rsst55' 'set string 3 c 5 0' 'set strsiz 0.14' 'draw string 4.5 7.5 1996.1.31 Global 500mb Geopotential Height Field' 'print' pull dummy .ctl文件 DSET h9601.31a TITLE height FORMAT yrev UNDEF -9999.00
LAMMPS手册-中文解析一、简介 本部分大至介绍了LAMMPS的一些功能和缺陷。 1．什么是LAMMPS? LAMMPS是一个经典的分子动力学代码，他可以模拟液体中的粒子，固体和汽体的系综。他可以采用不同的力场和边界条件来模拟全原子，聚合物，生物，金属，粒状和粗料化体系。LAMMPS可以计算的体系小至几个粒子，大到上百万甚至是上亿个粒子。 LAMMPS可以在单个处理器的台式机和笔记本本上运行且有较高的计算效率，但是它是专门为并行计算机设计的。他可以在任何一个按装了C++编译器和MPI 的平台上运算，这其中当然包括分布式和共享式并行机和Beowulf型的集群机。LAMMPS是一可以修改和扩展的计算程序，比如，可以加上一些新的力场，原子模型，边界条件和诊断功能等。 通常意义上来讲，LAMMPS是根据不同的边界条件和初始条件对通过短程和长程力相互作用的分子，原子和宏观粒子集合对它们的牛顿运动方程进行积分。高效率计算的LAMMPS通过采用相邻清单来跟踪他们邻近的粒子。这些清单是根据粒子间的短程互拆力的大小进行优化过的，目的是防止局部粒子密度过高。在并行机上，LAMMPS采用的是空间分解技术来分配模拟的区域，把整个模拟空间分成较小的三维小空间，其中每一个小空间可以分配在一个处理器上。各个处理器之间相互通信并且存储每一个小空间边界上的”ghost”原子的信息。LAMMPS(并行情况)在模拟3维矩行盒子并且具有近均一密度的体系时效率最高。 2．LAMMPS的功能 总体功能： 可以串行和并行计算 分布式MPI策略 模拟空间的分解并行机制 开源 高移植性C++语言编写 MPI和单处理器串行FFT的可选性（自定义） 可以方便的为之扩展上新特征和功能 只需一个输入脚本就可运行 有定义和使用变量和方程完备语法规则 在运行过程中循环的控制都有严格的规则 只要一个输入脚本试就可以同时实现一个或多个模拟任务 粒子和模拟的类型： （atom style命令）原子粗粒化粒子DNA 全原子聚合物，有机分子，蛋白质，联合原子聚合物或有机分子金属粒子材料粗粒化介观模型延伸球形与椭圆形粒子点偶极粒子刚性粒子所有上面的杂化类型力场：）（命令：pair style, bond style, angle style, dihedral style, improper style, kspace style, tabulated.
LAMMPS手册学习 一、简介 本部分大至介绍了LAMMPS的一些功能和缺陷。 1．什么时LAMMPS? LAMMPS是一个经典的分子动力学代码，他可以模拟液体中的粒子，固体和汽体的系综。他可以采用不同的力场和边界条件来模拟全原子，聚合物，生物，金属，粒状和粗料化体系。LAMMPS可以计算的体系小至几个粒子，大到上百万甚至是上亿个粒子。 LAMMPS可以在单个处理器的台式机和笔记本本上运行且有较高的计算效率，但是它是专门为并行计算机设计的。他可以在任何一个按装了C++编译器和MPI的平台上运算，这其中当然包括分布式和共享式并行机和Beowulf型的集群机。 LAMMPS是一可以修改和扩展的计算程序，比如，可以加上一些新的力场，原子模型，边界条件和诊断功能等。 通常意义上来讲，LAMMPS是根据不同的边界条件和初始条件对通过短程和长程力相互作用的分子，原子和宏观粒子集合对它们的牛顿运动方程进行积分。高效率计算的LAMMPS通过采用相邻清单来跟踪他们邻近的粒子。这些清单是根据粒子间的短程互拆力的大小进行优化过的，目的是防止局部粒子密度过高。在并行机上，LAMMPS采用的是空间分解技术来分配模拟的区域，把整个模拟空间分成较小的三维小空间，其中每一个小空间可以分配在一个处理器上。各个处理器之间相互通信并且存储每一个小空间边界上的”ghost”原子的信息。LAMMPS(并行情况)在模拟3维矩行盒子并且具有近均一密度的体系时效率最高。 2．LAMMPS的功能 总体功能： 可以串行和并行计算 分布式MPI策略 模拟空间的分解并行机制 开源 高移植性C++语言编写 MPI和单处理器串行FFT的可选性（自定义） 可以方便的为之扩展上新特征和功能 只需一个输入脚本就可运行 有定义和使用变量和方程完备语法规则 在运行过程中循环的控制都有严格的规则 只要一个输入脚本试就可以同时实现一个或多个模拟任务 粒子和模拟的类型：
画图教学案例 2009-05-18 14:39 一、教学目标： [认知目标] 1、复习“画图”中常用工具的使用方法。 2、继续提高电脑绘图的兴趣。 [能力目标] 1、通过复习，使学生进一步熟练地掌握电脑“画图”中常用绘画工具的使用方法。 2、能灵活运用“画图”中的各种工具进行创作型绘画，体现自己的个性。 [情景目标] 1、通过畅谈个人兴趣，来激发学生对生活的热爱，创作的欲望。 2、开发潜能，发散思维，提高学生创作热情和创作能力。 3、培养学生养成团结合作、相互交流评价的学习习惯。 二、教学重难点： 1、重点：通过复习进一步熟练掌握电脑“画图”中常用绘画工具的使用方法。 2、难点：灵活运用“画图”中多种绘画工具创作出体现自己个性的作品。 三、教学过程 （一）、品析作品，导入新课 1、每个人都有不同的兴趣和爱好，请同学们谈谈各自有哪些兴趣和爱好（教师和学生交流各人的兴趣） 2、同学们的兴趣很广泛，今天这堂课就和兴趣有关，叫《我的兴趣》（出示课题）。在同学们刚才说的兴趣当中，很多同学都喜欢玩电脑，老师想问一下，大家喜欢用电脑画画吗？（学生回答） 3、有些同学把自己的兴趣用电脑画了出来，让我们来欣赏一下，好不好？在欣赏这些作品的同时，我们可以相互讨论一下这些作品中用到了哪些画图工具。（学生欣赏并讨论） 4、教师出示一幅代表作品，请学生指出图中所用到的画图工具，并在黑板上找出相应的“工具”图标卡片。 5、教师评价：大家还记得这么多的画图工具，真是不错，但光记得名字还不够，我们还要熟练掌握它们的使用方法, 这样我们画起画来就能得心应手。 （二）任务驱动，巩固充实 有的同学喜欢体育运动，那你一定知道重大比赛之前都有“热身赛”，老师现在也想和同学们来个“热身赛”，大家敢不敢接受挑战？ 好，那么现在我们就开始“热身”，请看题（学生打开题目1：画一个蓝色的实心三角形）。 1、学生打开“画图”软件，教师交代比赛规则：本轮热身分2个阶段：首先我
C A D三维绘图教程与案例 很实用 Prepared on 21 November 2021
CAD 绘制三维实体基础 AutoCAD 除具有强大的二维绘图功能外，还具备基本的三维造型能力。若物体并无复杂的外表曲面及多变的空间结构关系，则使用AutoCAD 可以很方便地建立物体的 三维模型。本章我们将介绍AutoCAD 三维绘图的基本知识。 三维几何模型分类 在AutoCAD 中，用户可以创建3种类型的三维模型：线框模型、表面模型及实体模型。这3种模型在计算机上的显示方式是相同的，即以线架结构显示出来，但用户可用特定命令使表面模型及实体模型的真实性表现出来。 线框模型(Wireframe Model) 线框模型是一种轮廓模型，它是用线（3D 空间的直线及曲线）表达三维立体，不包含面及体的信息。不能使该模型消隐或着色。又由于其不含有体的数据，用户也不能得到对象的质量、重心、体积、惯性矩等物理特性，不能进行布尔运算。图11-1显示了立体的线框模型，在消隐模式下也看到后面的线。但线框模型结构简单，易于绘制。 表面模型（Surface Model ） 表面模型是用物体的表面表示物体。表面模型具有面及三维立体边界信息。表面不透明，能遮挡光线，因而表面模型可以被渲染及消隐。对于计算机辅助加工，用户还可以根据零件的表面模型形成完整的加工信息。但是不能进行布尔运算。如图11-2所示是两个表面模型的消隐效果，前面的薄片圆筒遮住了后面长方体的一部分。 实体模型 实体模型具有线、表面、体的全部信息。对于此类模型，可以区分对象的内部及外部，可以对它进行打孔、切槽和添加材料等布尔运算，对实体装配进行干涉检查，分析模型的质量特性，如质心、体积和惯性矩。对于计算机辅助加工，用户还可利用实体模型的数据生成数控加工代码，进行数控刀具轨迹仿真加工等。如图11-3所示是实体模型。 11．2 三维坐标系实例——三维坐标系、长方体、倒角、删除面 AutoCAD 的坐标系统是三维笛卡儿直角坐标系，分为世界坐标系（WCS ）和用户坐标系（UCS ）。图11-4表示的是两种坐标系下的图标。 图中“X ”或“Y ”的剪 头方向表示当前坐标轴X 轴或Y 轴的正方向，Z 轴正方向用右手定则判定。 图11-1 线框模型 图11-2 表面模型 图11-3 实体模型 1、三维模型的分类及三维坐标系； 2、三维图形的观察方法； 3、创建基本三维实体； 4、由二维对象生成三维实体； 5、编辑实体、实体的面和边；