Bayro-Corrochano E., Scheuermann G. Geometric Algebra Computing: in Engineering and Computer Science

Подождите немного. Документ загружается.

238 M.T. Pham et al.

where, w

ij ;k

= w

ij ;k

(



j;k

)

−

is the element of the matrix



which is the

matrix W

normalized so that the squared sum of all its elements becomes 1.

In addition, cluster structure embedded in the data distribution is evaluated as

alignment with identity matrix E,

A(W

,E)=

√



w

ii;k

∈(0, 1]. (18)

The alignment with E becomes 1 when similarity between any two different in-

stances is 0, i.e., no cluster structure is embedded.

On the other hand, when binary label y

∈{−1, 1} is given for each instance, if

instances with the same label are allocated near and those with the different label

are allocated far, then the clustering result of this feature agrees with the labels. This

is evaluated by the alignment between W

and Y =[Y

A(W

,Y)=





i,j|y

w

ij ;k

−



i,j|y

=y

w

ij ;k



∈[−1, 1]. (19)

A good combination of two feature extractions has a low A(W

) value. And,

if A(W

,E)is low and A(W

,Y)is high, f

induces a feature space with rich cluster

structure and agreement with the given labels.

Semi-supervised learning is a problem to infer labels for unlabeled data U =

{l +1,...,l +u = p} or unknown unlabeled data when the label y

∈{−1, 1} of a

part L ={1,...,l} of the instance set is known. In this paper, we solve a problem in

the case of labeling U . The goal is to ﬁnd a binary function γ :U →{−1, 1} such

that similar points have the same label.

Referring Zhu et al. [17], we decide a parameter σ of the kernel as follows. Dur-

ing making a minimum spanning tree over all data points with Kruskal’s Algorithm,

we label temporarily an unlabeled data a ∈U to the same label as the labeled datum

which connects with a for the ﬁrst time. Then we ﬁnd the median distance of tree

edges that connect two instances with different labels. We regard this distance d

a heuristic to the median distance between class regions. We arbitrarily set σ =

following the 3σ rule of Normal distribution, so that the weight of this edge is close

to 0.

Then, we construct a p × p symmetric weight matrix W =[w

]. The weight

matrix can be separated as

W =





(20)

at the lth row and lth column. For this purpose, Zhu et al. proposed to ﬁrst compute

a real-valued function g: U →[0, 1] which minimizes the energy

E(g) =



i,j



g(i) −g(j)



. (21)

Classiﬁcation and Clustering of Spatial Patterns with Geometric Algebra 239

Fig. 4 Algorithm to ﬁnd

latent willingness to buy.

From questionnaire data ξ

f ∈{f

} extracts

geometric features x

. Label

∗

is initially set to y

. After

calculating γ

(i), labels of

contradicted respondents are

excluded from {y

∗

}.The

algorithm ends when no more

contradictions occur

Restricting

g(i) =g

(i) ≡



0 (y

=−1),

1 (y

=1)

(22)

for the labeled data, g for the unlabeled data can be calculated by

=(D

−W

)

−1

, (23)

where D

=diag(d

) is the diagonal matrix with entries d



for the un-

labeled data. Then γ(i) is decided using the class mass normalization proposed by

Zhu et al.:

γ(i)=



1 (|{j |y

=1}|

(i)



(i)

> |{j |y

=−1}|

1−g

(i)



(1−g

(i))

−1 (otherwise).

(24)

Because either of three prices {ϕ

,ϕ

| ϕ

<ϕ

} is indicated to a re-

spondent when he/she indicates willingness to buy, we subdivide the respondents

into three groups according to the indicated price. Then, we calculate γ

for each

k ∈{1, 2, 3} regarding one group of respondents as labeled and the other groups as

unlabeled. After that, we check the consistency of respondent i, i.e., whether the

willingness decreases weakly monotonously with the price.

(i) ≥γ

(i). (25)

If respondent i contradicts to this condition then we clear the label y

and repeat the

semi-supervised learning regarding such respondents as unlabeled from this time

on. As shown in Fig. 4, we repeat this procedure until contradictions do not occur

any more.

3 Experimental Results and Discussion

This section shows experimental results of the proposed methods. Sects. 3.1 and 3.2

show applications of the multiclass classiﬁcation method proposed in Sect. 2.2 and

the semi-supervised learning method proposed in Sect. 2.3.

240 M.T. Pham et al.

3.1 Classiﬁcation of Handwritten Digits

3.1.1 Handwritten Digits

We used the Pen-Based Recognition of Handwritten Digits dataset of the UCI

Repository [15] as an example application for multiclass classiﬁcation because dig-

its have two-dimensional spatial features. The dataset consists of 10992 samples

written by 44 people. Among these samples, 7494 samples were written by 30 peo-

ple divided into learning data D

and validation data D

. The 3498 remaining sam-

ples were written by 14 other people and are used as test data D

. Eight points {r

}

dividing the orbit of the pen point into seven equally long segments were chosen. In

this study, we carry out the feature extraction with GA, after computing p

−

i.e., setting the origin

r at the center of the digit.

3.1.2 Classiﬁcation Result

For each feature extraction f ∈{f

}, the GMM learned from D

with four

values of α ∈{0.1, 0.01, 0.001, 0.0001}, and we then evaluated the correct classi-

ﬁcation rate for D

. Table 1 shows the results. In Table 1, the maximal classiﬁca-

tion rate is underlined. α = 0.01 was therefore chosen for all feature extractions

Table 2 shows the results of the identiﬁed models M with ¯q =



/M.The

numbers of misclassiﬁcations via coordinates f

, via outer products f

, and via

inner products f

were 100, 201, and 494, respectively. The correct classiﬁcation

rates were 97.14%, 94.25%, and 85.88%, respectively.

Tables 2 clearly show the differences in the misclassiﬁcations by different feature

extractions. Because the feature extraction f

keeps the coordinate information of

each point, it results in a smaller number of misclassiﬁcations. However, it has other

disadvantages. For example, because the ﬁrst point p

of most learning data of ‘0’

is in the top left area, some test data whose p

is in the top right area are misclas-

siﬁed. The feature extractions f

and f

, on the other hand, loose the coordinate

information of each point. However, they extract partial shape features not affected

by the position of the part of the digit under concern. Therefore, f

and f

correctly

classiﬁed the ‘0’ data with curves beginning in the top right area. Therefore, a mix-

ture of different f

expert feature extractions works best. The total number

Table 1 Correct

classiﬁcation rate for D

for

various α

αf

0.1 93.22% 95.09% 84.08%

0.01 99.36%

96.53% 90.13%

0.001 99.28% 96.43% 89.44%

0.0001 98.88% 96.45% 89.78%

Classiﬁcation and Clustering of Spatial Patterns with Geometric Algebra 241

Table 2 Identiﬁed models

for different features

‘0’ ‘1’ ‘2’ ‘3’ ‘4’ ‘5’ ‘6’ ‘7’ ‘8’ ‘9’

6755587689

2733343678

2894486655

¯qf

6 6.1 8.4 9.4 8.4 3 6.4 7.8 7.5 8.7

7 4.2 5.3 6 7 4.7 5.3 5.5 5.1 5.5

6.5 4.9 4.8 6.3 6 5.1 5.3 4.8 6.6 6.8

Fig. 5 Correct classiﬁcation rate with f

and mixture of experts

of misclassiﬁcations using a mixture of experts was 75, and the correct classiﬁcation

rate was 97.86%, better than the result of only using f

,orf

We assumed cases of different measurement environments from the one in which

both D

and D

have been measured. We generated a dataset D



={R(ξ, ϕ),ξ ∈

,ϕ ∼ U(ε)} that randomly rotated each digit of the test data D

. U(ε) is the

uniform distribution on [−ε, ε], and ϕ is a random variable. We generated 20 differ-

ent sets D



from the test dataset D

for each ε ∈{π/40,π/20,π/10} and classiﬁed

them. R(ξ,θ) rotates all the points of ξ by θ . Figure 5 shows the average and the

standard deviation of the correct classiﬁcation rate when using the feature extraction

and the mixture of experts.

The classiﬁcation precision using only feature extraction f

decreased remark-

ably with increasing ε. On the other hand, the classiﬁcation precision using the

mixture of expert did not decrease that much. The rotations had no inﬂuence in

the cases of f

and f

. Their classiﬁcation success rates were 94.25% and 85.88%,

respectively.

242 M.T. Pham et al.

3.2 Kernel Alignment and Web Questionnaire Analysis Results

3.2.1 Web Questionnaire Data

We analyzed a web questionnaire data for a new product by extracting features with

GA and ﬁnding the latent willingness to buy. Subjects answered ten questions about

each of six objects, i.e., scenes in which the product was used. Subjects were asked

to give an evaluation value to each question in ﬁve levels {1, 2, 3, 4, 5}, where “5”

means “I agree very much” and “1” means “I disagree very much.” Subjects an-

swered willingness to buy the product for a price randomly selected from three

prices.

We carried out the feature extractions with GA after subtracting 3 from all evalu-

ation values so that x

l,i

={−2, −1, 0, 1, 2}. For simplicity, the ﬁve level willingness

values were binarized: “5”, “4”→1 and “3”, “2”, “1”→−1.

3.2.2 Analysis Results

We calculated alignment of kernel matrix W

derived by feature f

,k= 0, 1, 2,

which extracted with GA. Table 3 shows kernel alignment with other feature kernels,

identity matrix E, and the latent willingness matrix Y . The binary label y

= 1

when the respondent had latent willingness as a result of three analyses via different

feature and y

=−1 otherwise, i.e., when the respondent was judged not having

latent willingness at least one analysis.

With kernel matrix W

, the kernel matrix W

had a smaller alignment (0.51) than

had (0.92). Therefore, the effect of combination with feature extraction f

was

better than with f

. Also, the result showed that because both feature extractions

and f

had alignment with E lower than f

, they have more abundant struc-

ture of cluster between respondents, and they contribute the total inference because

alignment with Y is higher than f

Table 4 shows the result without introducing GA to ﬁnd latent willingness to buy.

In the table, “C” shows the percentage of respondents whose γ contradicted to con-

dition (25) after the algorithm ended, and thus we ignore those respondents. “F–F”

shows the percentage of respondents whose y

=−1, where, for simplicity, we do

not mind what price was indicated to the respondent, and γ

(i) =−1, i.e., the re-

spondent did not have either apparent or latent willingness even if the price was the

Table 3 Kernel alignment

evaluation

1 0.92 0.63

0.92 1 0.51

0.63 0.51 1

E 0.71 0.82 0.36

Y 0.048 0.036 0.103

Classiﬁcation and Clustering of Spatial Patterns with Geometric Algebra 243

Table 4 Result without GA

C0.1%

F–F 39.9%

F–T 22.0%

T–F 6.7%

T–T 31.3%

lowest. “F–T” shows the percentage of respondents whose y

=−1butγ

(i) = 1,

i.e., the respondent answered not to have willingness, but he/she had latent willing-

ness at least for the lowest price. “T–F” shows the percentage of respondents whose

=1butγ

(i) =−1, i.e., the respondent showed apparent willingness, but from

the similarity of answering patterns he/she was not willing to buy. “T–T” shows the

percentage of respondents whose y

= 1 and γ

(i) = 1, i.e., the respondent had

both apparent and latent willingnesses. The analysis made the following clear:

• Out of 38.0% of respondents (“T–F” or “T–T”) who answered positively to the

direct question of willingness, 31.3% of all respondents were detected as “truly”

willing to buy (“T–T”).

• Out of 61.9% of respondents (“F–F” or “F–T”) who answered negatively to the

direct willingness question, 22.0% of all respondents were detected as latently

willing to buy (“F–T”).

As a conclusion, 53.3% of respondents had a latent willingness to buy (“F–T” or

“T–T”), and the other 46.7% respondents did not.

Next, we conducted a more detailed analysis introducing GA to deﬁne two more

feature spaces which are based on f

, respectively. Respondents were subdi-

vided into the ﬁve groups of “C”, “F–F”, “F–T”, “T–F”, and “T–T” for each fea-

ture aspect. Thus Table 5 shows four subtables each of which further divides the

corresponding respondents divided by f

to a matrix of judgements based on f

and f

. Though 52.1% of respondents had the same result by all analyses based

on f

(total of diagonal cells), the other 47.9% of respondents had different

result. Especially,

• The second table shows that out of 22.0% of respondents who did not have ap-

parent but had latent willingness according to analysis based on f

alone, only

1.3% of all respondents were judged as so according both to analyses based on

and f

• The bottom table shows that out of 31.3% of respondents who were judged as

“truly” willing to buy in the analysis based on f

alone, 17.6% of all respondents

were judged differently in at least one aspect of his/her answering pattern. On the

other hand, the remaining 13.7% of all respondents can be judged as willing to

buy with more conﬁdence supported by the judgements based on f

and f

As a conclusion, 15.0% of respondents were found to have latent willingness to buy

(“F–T” or “T–T” by all analyses) with more conﬁdence than in analysis without

introducing GA.

244 M.T. Pham et al.

Table 5 Detailed labeling

result

(F–F) f

39.9% F–F F–T

F–F 32.6% 0.2%

F–T 7.0% 0.1%

(F–T) f

22.0% F–F F–T

F–F 6.0% 0.3%

F–T 14.4% 1.3%

(T -F) f

6.7% T–F T–T

T–F 5.5% 0.1%

T–T 0.9% 0.2%

(T–T) f

31.3% T–F T–T

T–F 3.0% 0.9%

T–T 13.7% 13.7%

Finally, we utilize principal component analysis (PCA) to visualize the data given

by f

. Figure 6 shows apparent and latent willingnesses.

The top ﬁgure shows apparent willingness to buy. In top ﬁgure, blue ‘×’showsa

respondent who did not have willingness even price ϕ

, and red ‘◦’ shows a willing

respondent in the case of price ϕ

. The gray marks show apparent willingness in

other case of prices.

The bottom ﬁgure show latent willingness to buy. In the bottom ﬁgure, blue ‘×’

and red ‘◦’ show the result with feature extractions f

. Green ‘’ show respondents

who were judged as willing to buy with all feature extractions f

.FromFig.6

we can ﬁnd that green ‘’ in the bottom ﬁgure resembles distribution of blue ‘×’in

the top ﬁgure. This means that the proposed method can ﬁnd respondents who have

strong latent willingness.

4 Conclusions

In this study, we proposed systematic feature extraction methods by using GA.

Based on the extracted features, we solved two machine learning problems, i.e.,

Classiﬁcation and Clustering of Spatial Patterns with Geometric Algebra 245

Fig. 6 The visualization of latent willingness to buy the product by PCA. The top ﬁgure shows

apparent willingness, and the bottom ﬁgure shows latent willingness to buy. A respondent who

did not have willingness is shown by ‘×’. A willing respondent is shown by ‘◦’. Green ‘’inthe

bottom ﬁgure show respondents who were judged as willing to buy with all feature extractions

246 M.T. Pham et al.

the classiﬁcation of the handwritten digits by using GMMs and the discovery of

latent willingness to buy using semi-supervised learning.

We applied the proposed method to two-dimensional objects of handwritten dig-

its deriving three ways of feature extraction, via coordinates, outer products, and

inner products. When we assumed cases of different measurement environments,

the classiﬁcation success rate by pure coordinate value feature extraction dropped

substantially for rotated test data. In contrast to this, with the mixture of experts, the

classiﬁcation success rate was not only higher in the case of a constant measurement

environment; it was also much more stable in the case of large rotations of the test

data. Therefore, we can conﬁrm that the strategy to mix different GA feature extrac-

tions is superior in both classiﬁcation precision and robustness when compared with

pure coordinate value features, which is the most often used conventional method.

We also applied the proposed method of feature extraction to clustering of an-

swering patterns for a web questionnaire. We proposed the clustering algorithm by

using the result based on the similarity in each feature space. Then, we applied

the proposed method to the clustering of answering patterns for a web question-

naire, deriving three kinds of feature extraction i.e., coordinates, outer products,

and inner products. The result showed that feature extractions based on outer prod-

uct and inner product, respectively, had more abundant structure of cluster between

respondents and higher alignment with latent willingness to buy than in (m × n)-

dimensional vector space. Based on the extracted features, we found latent willing-

ness to buy from the questionnaire data. The results showed that semi-supervised

learning based on coordinates may detect respondents who had latent willingness to

buy and that introducing GA to the analysis may further ﬁnd respondents who have

strong latent willingness.

Acknowledgements This work was supported by Grant-in-Aid for the 21st century COE pro-

gram “Frontiers of Computational Science” (Nagoya University) and Grant-in-Aid for Young Sci-

entists (B) #19700218.

References

1. Hu, M.K.: Visual pattern recognition by moment invariants. IRE Trans. Inf. Theory 8(2), 179–

187 (1962)

2. Mukundan, R., Ramakrishman, K.R.: Moment Functions in Image Analysis, Theory and Ap-

plication. World Scientiﬁc, Singapore (1998)

3. Doran, C., Lasenby, A.: Geometric Algebra for Physicists. Cambridge University Press, Cam-

bridge (2003)

4. Hestenes, D.: New Foundations for Classical Mechanics. Springer, Dordrecht (1986)

5. Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science: An Object-

oriented Approach to Geometry. Morgan Kaufmann Series in Computer Graphics. Morgan

Kaufmann, San Mateo (2007)

6. Sekita, I., Kurita, T., Otsu, N.: Complex autoregressive model for shape recognition. IEEE

Trans. Pattern Anal. Mach. Intell. 14(4), 489–496 (1992)

7. Hirose, A.: Complex-Valued Neural Networks: Theories and Applications. Series on Innova-

tive Intelligence, vol. 5. World Scientiﬁc, Singapore (2006)

Classiﬁcation and Clustering of Spatial Patterns with Geometric Algebra 247

8. Matsui, N., Isokawa, T., Kusamichi, H., Peper, F., Nishimura, H.: Quaternion neural network

with geometrical operators. J. Intell. Fuzzy Syst. 15(3–4), 149–164 (2004)

9. Buchholz, S., Le Bihan, N.: Optimal separation of polarized signals by quaternionic neural

networks. In: 14th European Signal Processing Conference, EUSIPCO 2006, September 4–8,

Florence, Italy (2006)

10. Nitta, T.: An extension of the back-propagation algorithm to complex numbers. Neural Netw.

10(8), 1391–1415 (1997)

11. Hildenbrand, D., Hitzer, E.: Analysis of point clouds using conformal geometric algebra.

In: 3rd International Conference on Computer Graphics Theory and Applications, Funchal,

Madeira, Portugal (2008)

12. Hitzer, E.: Quaternion Fourier transform on quaternion ﬁelds and generalizations. Adv. Appl.

Clifford Algebr. 17(3), 497–517 (2007)

13. Sommer, G.: Geometric Computing with Clifford Algebras. Springer, Berlin (2001)

14. Dempster, A., Laird, N., Rubin, D.: Maximum likelihood from incomplete data via the EM

algorithm. J. R. Stat. Soc. Ser. B 39(1), 1–38 (1977)

15. Asuncion, A., Newman, D.J.: UCI Machine Learning Repository. University of California,

School of Information and Computer Science, Irvine (2007)

16. Tipping, M.E., Bishop, C.M.: Mixtures of probabilistic principal component analysers. Neural

Comput. 11, 443–482 (1999)

17. Zhu, X., Lafferty, J., Ghahramani, Z.: Combining active learning and semi-supervised learning

using Gaussian ﬁelds and harmonic functions. In: ICML 2003 Workshop on the Continuum

from Labeled to Unlabeled Data in Machine Learning and Data Mining (2003)

18. Cristianini, N., Kandola, J., Elisseeff, A., Shawe-Taylor, J.: On kernel target alignment.

J. Mach. Learn. Res. (2002)

19. Meinicke, P., Ritter, H.: Resolution-based complexity control for Gaussian mixture models.

Neural Comput. 13(2), 453–475 (2001)