Vehicle type recognition at a checkpoint using PCA and BIC

1. A method for determining and recognizing types of vehicles passing a check point, which comprises:

up-loading an EM algorithm into a CPU;

collecting vehicle data as vehicles drive past a check point;

entering said data into said CPU said data being representative of essential characteristics of vehicles;

processing said data by said EM algorithm to produce an output model of the traffic volumes of the various types of vehicles; and

utilizing said output model to forecast future road maintenance costs and/or to plan and design future road networks, wherein

said EM algorithm is specially adapted to carry out the following steps:

1) standardize said data in sets;

2) when said data is standardized in sets, start with k 1;

3) set the initial value of μk to be the mean of the data set;

4) set the initial diagonal entries of Σk to be the variances of each variable;

5) set P(K)=1;

6) run clustering with the EM algorithm in this cluster;

7) obtain the new values for μk, Σk, (Pk) and the probability matrix P (k 1 xn);

8) define the BIC for this model as BICold=−(½)·Vold·log(N);

9) set k_prev= · k; and

10) repeat the following steps until k_prev=k;

a) set k_prev=k and a new variable called trace=1;

b) repeat the following steps until trace=k_prev;

(i) split the cluster at position trace into two clusters using PCA;

(ii) select data points to perform PCA from the data points that are most likely to come from cluster trace by checking the values in the probability marix P (k 1 xn);

(iii) run clustering with the EM algorithm for this new model;

(iv) obtain μk's, Σk's and (Pk)'s and the probability matrix P (k 1 xn)'s, and for the new model;

(v) define the BIC for this new model as BICnew=−λnew−(½)*Vnew*log(N);

(vi) if λnew−λold>a·(½)·(N)·(vnew−Vold), then replace the old model with the new model obtained in step (iii);

(vii) set K=+1;

(viii) if λnew−λold is not >a·(½)·(N)·(vnew−Vold), then keep the original model;

(ix) trace=trace+1; and

11) finally report the final model;

thereby determining and recognizing the types of vehicles passing the checkpoint to determine and recognize vehicle types in high volume traffic for monitoring traffic volumes of various types of vehicles, forecasting future road maintenance costs and planning and design of future road networks; wherein

in said steps:

N=number of data points;

V=number of variables;

K=number of clusters;

μk=the mean for kill cluster, each a vector of length V;

f° k:=the covariance matrices for kth cluster, each of size V*V;

xn · =the nth data point, which is a vector with length V;

P(k ! xn:)=the probability that xn comes from cluster k;

p(k)=: the probability that a data point chosen randomly comes from cluster k;

P(xn)=the probability of finding a data point at position xn;

λ=the value of log likelihood of the estimated parameter set;

PCA=Principal Component Analysis; and

BIC=Bayesian Information Criterion.

2. The method of claim 1 , wherein said vehicle data comprises length of said vehicle, distance between axles of said vehicle, and weights on said axles of said vehicle.

3. The method of claim 1 , including the additional step of obtaining the clustering results by checking the values in the final probability matrix.

4. The method of claim 1 including the additional step of using the final model, to cluster many data points where, if some data points are given, they can be assigned to their corresponding clusters, and obtaining a probability matrix whose entries are the values of P (k 1 x n ) for all values of cluster k's and x n 's, and from these values determining which cluster that each data point most likely comes from by checking the values in the probability matrix.

5. The method of claim 1 , for a vehicle that seldom appears, and it is desired to cluster it into a single cluster once it appears, by adding a new cluster to the final model, where the value of μ for the new cluster is the same as the variable values for this vehicle, where the covariance matrix Σ is a diagonal matrix, and setting diagonal entries of Σ to be very small numbers, where the variances for each variable are small numbers so that the values of P(k) for this cluster are set to be a small number since this vehicle is very rare to appear.

6. A method of determining and recognizing the types of vehicles passing a checkpoint which comprises the steps of:

uploading a computer program into a CPU, said computer program comprising an EM algorithm said EM algorithm including data representations of essential characteristics of vehicles

collecting vehicle data as said vehicles drive past a checkpoint to determine and recognize vehicle types for monitoring traffic volumes of various types of vehicles,

entering said data into said CPU; and

deriving an output from said CPU,

thereby monitoring traffic volumes of various types of vehicles for forecasting future road maintenance costs and planning and design of future road networks, wherein

the EM algorithm algorithm is specially adapted to carry out the following steps:

1) standardize said data in sets;

2) when said data is standardized in sets, start with k 1;

3) set the initial value of μk to be the mean of the data set;

4) set the initial diagonal entries of Σk to be the variances of each variable;

5) set P(K)=1;

6) run clustering with the EM algorithm in this cluster;

7) obtain the new values for μk, Σk, (Pk) and the probability matrix P (k 1 xn);

8) define the BIC for this model as BICold=−(½)·Vold·log (N);

9) set k_prev= · k; and

10) repeat the following steps until k_prev=k;

a) set k_prev=k and a new variable called trace=1;

b) repeat the following steps until trace=k_prev;

(i) split the cluster at position trace into two clusters using PCA;

(ii) select data points to perform PCA from the data points that are most likely to come from cluster trace by checking the values in the probability marix P (k 1 xn);

(iii) run clustering with the EM algorithm for this new model;

(iv) obtain μk's, Σk's and (Pk)'s and the probability matrix P (k 1 xn)'s, and for the new model;

(v) define the BIC for this new model as BICnew=−λnew−(½)*Vnew*log(N);

(vi) if λnew−λold>a·(½)·(N)·(vnew−Vold), then replace the old model with the new model obtained in step (iii);

(vii) set K=+1;

(viii) if λnew−λold is not >a·(½)·(N)·(vnew−Vold), then keep the original model;

(ix) trace=trace+1; and

11) finally report the final model;

thereby determining and recognizing the types of vehicles passing the checkpoint to determine and recognize vehicle types in high volume traffic for monitoring traffic volumes of various types of vehicles, forecasting future road maintenance costs and planning and design of future road networks;

wherein

in said steps:

N=number of data points;

V=number of variables;

K=number of clusters;

μk=the mean for kill cluster, each a vector of length V;

f° k:=the covariance matrices for kth cluster, each of size V*V;

xn · =the nth data point, which is a vector with length V;

P(k ! xn:)=the probability that xn comes from cluster k;

p(k)=: the probability that a data point chosen randomly comes from cluster k;

P(xn)=the probability of finding a data point at position xn;

λ=the value of log likelihood of the estimated parameter set;

PCA=Principal Component Analysis; and

BIC=Bayesian Information Criterion.

7. An apparatus comprising the combination of:

a CPU; and

a computer program which has been uploaded into said CPU, said computer program comprising an EM algorithm, said EM algorithm including data representations of essential characteristics of vehicles, wherein

the EM algorithm is specially adapted to carry out the following steps:

1) standardize said data in sets;

2) when said data is standardized in sets, start with k 1;

3) set the initial value of μk to be the mean of the data set;

4) set the initial diagonal entries of Σk to be the variances of each variable;

5) set P(K)=1;

6) run clustering with the EM algorithm in this cluster;

7) obtain the new values for μk, Σk, (Pk) and the probability matrix P (k 1 xn);

8) define the BIC for this model as BICold=−(½)·Vold·log(N);

9) set k_prev= · k; and

10) repeat the following steps until k_prev=k;

a) set k_prev=k and a new variable called trace=1;

b) repeat the following steps until trace=k_prev;

(i) split the cluster at position trace into two clusters using PCA;

(ii) select data points to perform PCA from the data points that are most likely to come from cluster trace by checking the values in the probability marix P (k 1 xn);

(iii) run clustering with the EM algorithm for this new model;

(iv) obtain μk's, Σk's and (Pk)'s and the probability matrix P (k 1 xn)'s, and for the new model;

(v) define the BIC for this new model as BICnew=−λnew−(½)*Vnew*log(N);

(vi) if λnew−λold>a·(½)·(N)·(vnew−Vold), then replace the old model with the new model obtained in step (iii);

(vii) set K=+1;

(viii) if λnew−λold is not >a·(½)·(N)·(vnew−Vold), then keep the original model;

(ix) trace=trace+1; and

11) finally report the final model;

thereby determining and recognizing the types of vehicles passing the checkpoint to determine and recognize vehicle types in high volume traffic for monitoring traffic volumes of various types of vehicles, forecasting future road maintenance costs and planning and design of future road networks; wherein

in said steps:

N=number of data points;

V=number of variables;

K=number of clusters;

μk=the mean for kill cluster, each a vector of length V;

f° k:=the covariance matrices for kth cluster, each of size V*V;

xn · =the nth data point, which is a vector with length V;

P(k ! xn:)=the probability that xn comes from cluster k;

p(k)=: the probability that a data point chosen randomly comes from cluster k;

P(xn)=the probability of finding a data point at position xn;

λ=the value of log likelihood of the estimated parameter set;

PCA=Principal Component Analysis; and

BIC=Bayesian Information Criterion.

8. The apparatus of claim 7 wherein said vehicle data comprises length of said vehicle, distance between axles of said vehicle and weights on said axles of said vehicle.

9. An apparatus for determining and recognizing types of vehicles passing a check point, which comprises:

a CPU;

an EM algorithm uploaded into said CPU;

structure operatively associated with said CPU for collecting vehicle data as vehicles drive past said check point;

means, operatively associated with said CPU for entering said data into said CPU said data being representative of essential characteristics of vehicles;

means for processing said data by said EM algorithm to produce an output model of the traffic volumes of the various types of vehicles; and

means for utilizing said output model to forecast future road maintenance costs and/or to plan and design future road networks, wherein

the EM algorithm is specially adapted to carry out the following steps:

1) standardize said data in sets;

2) when said data is standardized in sets, start with k 1;

3) set the initial value of μk to be the mean of the data set;

4) set the initial diagonal entries of Σk to be the variances of each variable;

5) set P(K)=1;

6) run clustering with the EM algorithm in this cluster;

7) obtain the new values for μk, Σk, (Pk) and the probability matrix P (k 1 xn);

8) define the BIC for this model as BICold=−(½)·Vold·log (N);

9) set k_prev= · k; and

10) repeat the following steps until k_prev=k;

a) set k_prev=k and a new variable called trace=1;

b) repeat the following steps until trace=k_prev;

(i) split the cluster at position trace into two clusters using PCA;

(ii) select data points to perform PCA from the data points that are most likely to come from cluster trace by checking the values in the probability marix P (k 1 xn);

(iii) run clustering with the EM algorithm for this new model;

(iv) obtain μk's, Σk's and (Pk)'s and the probability matrix P (k 1 xn)'s, and for the new model;

(v) define the BIC for this new model as BICnew=−λnew−(½)·Vnew·log(N);

(vi) if λnew−λold>a·(½)·(N)·(vnew−Vold), then replace the old model with the new model obtained in step (iii);

(vii) set K=+1;

(viii) if λnew−λold is not >a·(½)·(N)·(vnew−Vold), then keep the original model;

(ix) trace trace+1; and

11) finally report the final model;

thereby determining and recognizing the types of vehicles passing the checkpoint to determine and recognize vehicle types in high volume traffic for monitoring traffic volumes of various types of vehicles, forecasting future road maintenance costs and planning and design of future road networks; wherein

in said steps:

N=number of data points;

V=number of variables;

K=number of clusters;

μk=the mean for kill cluster, each a vector of length V;

f° k:=the covariance matrices for kth cluster, each of size V*V;

xn · =the nth data point, which is a vector with length V;

P(k ! xn:)=the probability that xn comes from cluster k;

p(k)=: the probability that a data point chosen randomly comes from cluster k;

P(xn)=the probability of finding a data point at position xn;

λ=the value of log likelihood of the estimated parameter set;

PCA=Principal Component Analysis; and

BIC=Bayesian Information Criterion.