Atmospheric Enuiromnf Vol. 12, pp. 23772382. Q Pergamon Press Ltd 1978. Printed in Great Britain.
PATTERN RECOGNITION METHODS IN AIR POLLUTION CONTROL SELMOTAUBER
Department of Mathematics, Portland State University, Portland, OR 97207, U.S.A. (First received 28 July 1977 and injinal form 4 July 1978)
Abstract-Pattern recognition methods are used to predict future developments in terms of historical data by comparing graphs of atmospheric pollution con~ntratjo~. The method is then applied to a practical example of crisis prediction for CO concentration.
Pattern recognition is a branch of applied mathematics which in recent times has greatly expanded. For the basic lines of this discipline and the rather substantial literature we refer to Fu (1968 ; 1974) and Fukanaga (1976). Many of the applied sciences use methods ofpattern recognition ; we mention in particular the case of meteorology since it is closely related to air pollution control. In our analysis we consider the graph of a given variable as function of time at a certain location and compare the segment of this graph to a contending segment of the same graph at a previous time interval. We may assume that a given time interval of say 24,48 or 72 hours is used for the comparison, and that the graph presents the graphical pattern of the concentration of one of several pollutants in the atmosphere. The computer compares this pattern with the patterns of graphs of the con~ntration of the same pollutant at different time periods of same length. If the computer recognizes a “similarity” which will be
mathematically defined then a forecast can be made on the basis of what happened in the previous case.
2. BASIC ONE-DIMENSIONAL
Consider a quantity x which is measured at irregular intervals according to a schedule determined by a computer and based on its past history of variation. We refer to Tauber (1976) for such a schedule. Let T be the basic interval we use for the comparison of patterns (cf: Section l), and let I(1) = [a(l), b(l)], I(2) = [a(2), b(2)], . . ., 1(n) = [u(n), b(n)] be adjoining intervals of length T, i.e. a(k) = b(k - 1). As stated, the measurements in f(k) are not performed at regular intervals. We call the instants of measurements for the basic interval I(j), a(j) = t(O,j), @J), Gj), *. . , t(a,,j), t(n, + l,j) = b(j), i.e. there are for I(j) n, + 2 measurements including the initial and final measurements, (cf: Fig. 1). The measur~ent at the instant t(m,j) is denoted as x[t(m,j)] =x(m,j), where m=O, 1,2,. . ., tri, nj + 1. The graph under consideration is the poiygoniai line
x(m-I, j) w(n,j)
Fig. 1. Measurements in I(j). 2317
j t t(n+l,j)=b(j)
joining the points [t(m,j), x(m,j)] in their order of succession. We recall that the equation of the line joining the two points [t(m - l,j), x(m - 1,j)] and [t(m,j), x(m,j)] is given by the equation x = Nm,j)t + B(m,j)
where a(m,j) =
x(m,j) - x(m - Lj) t(m,j) - t(m - 1,j) ’
If we associate to each point of x(t) as defined by (3) such a circle and construct the envelope of all these circles we obtain two curves (cJ Fig. 2) which define the R-region about the curve x(t). The analysis of pattern similarity using the R-region is scientifically very interesting but leads to rather difficult calculations due to the fact that limiting lines of the R-region are made of smooth line segments and arcs of circles instead of line segments only. If one tries to eliminate the circular arcs then the line segments of equations x(&j) = a(m,j)t + B(m,j) + R/Cl + [a(m,j)l*]
- LA - t(m - LAxhi) t(m,j) - t(m - 1,j)
would not intersect on the same verticals as the original graph. This would complicate greatly the basic inequalities.
the unit step function defined by
u(t - A) =
I 1 for
4. THE pREGlON
x(t) = f x(&j) = i “‘i j=o j=O a=1 u[t
1. CdmJN +/.RmN,
t(m - l,j)]
- u[t - t(m,j)]
the graph of the polygonial line. 3. THE R-REGION
Let At be the time interval necessary for performing the measurement x(m, j). This time interval may be far from negligible since we are dealing with gas analysis. Let Ax be the magnitude of the error committed in the measurement of x(m, j). Consider the quantity R = [At’ + Ax’]~/’ and the circle of radius R and center [t(m,j), x(m, j)]. Any point within this circle corresponds to a measurement “technically equal” to the measurement [t(m, j ), x(m, j )], i.e. equal within the maximum committed error. R is known under the name of quadratic error.
Let p be a positive number which we call the index of similarity. Consider the two quantities y(t)=(l -p) x(t), and z(t)=(l +p)x(t). y(t) amd z(T) represent under the given conditions the limits of the measurements of x(t) assuming a maximum relative error of p. In general p will be (hopefully) a small number, i.e. p < 1. This however need not be the case if the quantities measured are small. It could thus happen that p> 1 in which case y(t) would become negative. Since the measurements performed are all positive (except for temperatures) we replace y(t) by the horizontal axis (zero value) in this case. The p-region is the area between the two polygonial lines y(t) and z(t) being replaced by zero whenever y(t)
Consider two basic intervals of duration
Fig. 2. Definition of the R-region.
Pattern recognition methods in air pollution control
Fig. 3. Definition of the pregion.
x I --*__ 0
ci ttm,k) tC2.k) 1
Fig. 4. Comparison of graphs in i(k) and I(i).
= [a(i), b(i)], and Z(k)= [a(k), b(k)], where j < k. We consistently make use of the notation introduced in Section 2. Points Z(j) and Z(k) are said to be homologous or corresponding to homologous instants if the time interval between them is (k -j)T, thus clearly. a(j) an& u(k) as well as b(j) and b(k) are homologous. Subintervals of Z(i) and Z(k) are said to be homoIogous if their end points are. We compare (c$ Fig. 4) the portions of the graph of x(t) in Z(k) and Z(j), i.e. x(t, k) and x(t,j). Dejnition : If the graph of x(t, k) translated in time from Z(k) to Z(j) fits into the p-region of x(t, j) in Z(j) we say that them is p-similarity between x(r, k) and x(&j). As we shall see this leads to a two part set of formulae. Since in general according to the way the measurements of x(t) are monitored (see Section 1) the instants t(m,j), m = 1,2, . ., n,, and t(s, k), s = 1,2, . . ., n, are not homologous in general. We introduce the homologous
which expresses the fact (c$ Fig. 5) that the measured points of the graph x(&k) translated into the Z(j) interval atie within the p-region of the x&j) graph. This however is not enough, as can be seen in Fig. 5. The line joining the points [e(s - l,j), x(s - l,j] and [e(s,j), x(s, j)] is not within the p-region of Z(/)although the end points are. It is thus necessary to add another set of conditions to (6). Let Vt,j 1 = 4j
It + B(s,.i)
points O(S,j) = t(s, k) - (k - j) T
and can write the first condition of p-similarity in the form Fig. 5. Additional conditions for the translated graphs in the p-region.
2380 where A&j) = [x(s, k) - x(s - 4 k)]/[&,j), -4s
= [x(s, 4 - 4s - I, k)]lCr(s,k) - t(s - l,k)] = a(s, k) B&j)
= [O(s,j)x(s - Lk) - O(s - l,j)x(s,k)l/
[@(s,j) - e(s -
which after some manipulation be
using (5) turns out to
B(s,j) = /3(s,k) + (k - j) Ta(s, k).
The condition expressing that the line,segment [e(s - I, j), x(s - 1,j)], [f&j), k(s, j)] is withmthe p-region of 1(j) can be written J&j)CuCr - 6(s - Lj)] - u[r -
+y(m+ 1,j)[u[t 5 T(t,j)
@hi)~l - u[t -
e(s - l,j)]
- r4[t - t(m,j)]] + z(m + l,j)[u[t - a[r -
Equations (6) and (11) completely express the psimilarity of the portions of x(r) in I(k) and 1(j). Remark : Just as we defined the p-similarity based on the definition of the p-region we could define an Rsimilarity based on the definition of the R-region. As explained earlier it would be mathematically too complicated in the neighborhood of the endpoints of the subintervals considered.
The inequalities of (6) and (11) expressing p similarity are numerical land can be checked by a properly programmed computer., For a given p the computer can point out, that ‘x&f) is &imilar to x(r,ji), x(t,jr), . . ., as:far back as the.measurements are stored in the computer. Conversely the computer can determine p(k,j) the index of p-similarity between x(t, k) and x(t, j). Moreover by comparing x(t, k) to all thex(t,j),j=1,2 ,..., and by comparing the so obtained p(k, j) the computer can find that dk,j,,,) =min Cp(k,j)], j=l, 2, . . ., k- 1. We may then draw the logical conclusion that x(t, k) resembles most x(t, j,,,), and that, unless a drastic unforeseen change occur% what will follow x(t) in I(k), i.e. x(t, k) will resemble what had followed x(t) in I(&), i.e. x(t,jm). There is clearly a probabilistic aspect to the index p and the resemblance of x(t, j,,,) to x(t, k), and we intend to study this problem in the near future. 7. APPLICATION
diction, by defining p-similar weather condition as : “at most p-similarity for the temperature, the pressure, the wind vel&ity~(ntui&ically speaking) the wind direction (expressed as the angle the wind makes with the north, 058 52I-I rad) the, humidity, and some more meteorological factors, . . .“, we prefer to leave this definition to the professionals. It is preferable to accept the probability given by the meteorologists in their forecast and say that weather conditicns are considered similar if the prediction for the weather conditions is 75% certain to be the predicted ones, which are close to the ones in I(j + 1). In other words : the probability of similar weather conditions between I(k + 1) and 1(i+ 1) is at least 75%. Consider now a pollutant P and let C(t,P) be the concentration of P at the:instant C. The information concerns clearly a certain geographic region small enough to be determined by a single set of measurements. Using the same notation as before we let C(t, P, j), C(t, P,j + l), C(t, P, k) and C(t, P, k + 1) be the values of C(t, P) in the intervals I(j), I( j + l), I(k), I(k + 1). If the weather conditions for &):and I(k) are similar and the prediction for I(k + 1) is that it will be probably similar to Z(j+ 1) with a probability ofat least 75%, and if p(k, j) = p(k, j,,,), then C(t, P, k + 1) will be p-similar to C(t, P, j+ 1) with a p(k + 1, j + 1) of the same order of magnitude as p(k, j). This statement which is rather qualitative can be improved by two methods: (i) by improving, at least mathematically speaking, the weather prediction probability, and (ii) by establishing a mathematical theory connecting the parameter p to the probability of a p-similarity as explained in Section 6.
TO AIR POLLUTION:CONTRQL
Although we could apply the p-similarity method to meteorology or, more specifically to weather Ipre-
We have so far considered the case of one single ,pollutant P. For a given area there are usually several pollutants to be considered, say P(l), P(2), . . ., P(n). ;The best way to control the situation is to study each pollutant separately and consider the functions C[r, k, P(i)], i + 1,2,. . . , n. The problem can be somewhat simplified by taking the most significant of the pollutants, say P(a), and P(c) and studying some ‘linear combination of their concentration for a given location say Q(t, k) = aC[t, k, P(a)] +/KT[t, k, P(b)] + K[t, k, &)I, where usually a + /3+ 1= 1. Q(t, k) would be the significant pollution factor for the given location during the interval I(k). 9. EXAMPLE
The following measurements were recorded by the Department of Environmental,Quality (DEQ) of the State of Oregon, Air Quality Control Division, Portland, Oregon. The recording instrument is located at 718 W. Burnside Street in Portland. The tablegives the
Pattern rsognition methods in air polluti0nControl Tabk 1. The woQ-o100 01OO-Om 02OO-O3OO 03OO-OMB O4aMmO OMOJXOO O6OO-O7OO. 07OO-O8OO 08OOABOO O9OO-IOOO lOOO-1lOO llOO-1200 12OO-13OO 13aL14OO 14OO-15OO MO-164-m MO-1700 1700-1800 MOO-1900 19OOdOOO 2OOO-2100 21OO-2200 22OO-2300 2300~2400
19 Iwunbef 1972
19 Dam&a 1973
4.2 2.3 1.2 1.2 I.2 1.2
E 213 1.2 1.2 1.2
2.3 1.2 1.2 1.2 ::
::: 2.3 1.2 I.2 1.2
17.3 5.8 19.6 15.0 12.7 13.8 12.7 13.8 12.7 17.3 23.0 20.8 12.7 8.1 5.8 8.1 6.9 5.8
12.7 4.6 17.3 15.0 18.5 z:
5.8 8.1 5.8
;: lOI Il.5 12.7 15.0 IS.0 15.0 17.3 19.6 39.1 38.0 2O.8 15.0 12.7 10.4
2412 20.7 19.6 23.0 27.6 10.4 5.8 6.9 6.9 5.8 6.9
Fig. .6. Chcentrati0n gmphr.
21 8.1 1::: 10.4 17.3 18.4 12.7 8.1 ::: 5.8 3.5
average concentration of CO for every hour over a 24 hours interval, in mg rnd3. The meteorological indicators were as follows: Tuesday, December 19, 1972: High temperature, 59°F; Low temperature, 48°F; Precepitation, 0.25 in. rain ; Wind, S.W. av. 10.5 m h- i. Wednesday, December 20,1972 : High temp., 59°F; Low temp., 48°F; Precipitation, 0.71 in. rain; Wind, E. av. 11.4m h-‘. Wednesday, December 19, 1973: High temp., 50°F; Low temp., 40°F; Precipitation, 0.64 in. rain; Wind, E. av. 16.3 m h-‘. Thursday, December 20, 1973: High temp., 49°F; Low temp., 41°F; Pr~ipitation, 0.71 in. rain; Wind,S.E. av. 13.1 m h-i. Thefourdays can be classified as “cloudy”, typical Portland winter weather. In Fig. 6 we graph the average hourly concentrations. Since we are dealing with average hourly concentrations it seems logical to use a histogram type graph rather than a polygonial line. This does not change anything in the method used. In the left half of the figure we graph in plain line the concentrations for 19 December, 1972 and surround this graph with punctuated graphs of z(t) and y(t). The p selected is 0.66. On the same graph is the dot-dash graph of x(t) for 19 December, 1973. The largest p occurs for 0700 < t < 0800 h and is precisely p = 0.66, thus the choice of p. The climatic conditions between 19 December, 1972 and 1973 were close enough and so were the ones between 20 December, 1972 and 1973. Since the graph
showed a rather heavy CO concentration between 1600 and 1800 h for 20 December, 1972, and considering the p-similarity there was a good possibility of a high concentration of CO on 20 December, 1973. In fact there was a crisis since the concentration reached 39.1 mg rnw3. (The admissible level is 1Omg m-‘.) A crisis could thus have been predicted. By using a more systematic comparison scheme and by using a computer the value of p can be reduced and closer similarities can be obtained.
For a given location under the conditions given in Tauber (1976) a computer oriented analysis of the pollution conditions can be based on a method of pattern recognition. The method will be improved by the use of probability theory and can lead to signifi~t rest&s in the prediction of crises and determining measures to be taken to avoid such crises.
Fu K. S. (1968) Sequential ~eth~s in Pattern Rec#~t~o~. Academic Press, N.Y. Fu K. S. (1974) Syntactic Methods in Pattern Recognition. Academic Press, N.Y. Fukunaga K. (1972) Introduction to Statistical Pattern Recognition. Academic Press, N.Y. Tauber S. (1976) A systems approach to air pollution control. atmospheric ~nuiro~~~t 10, 633-636.