helpfn

180 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

A Mechanics-Based Similarity Measure for Text Classification in Machine Learning Paradigm

Venkatanareshbabu Kuppili , Mainak Biswas , Damodar Reddy Edla , K. J. Ravi Prasad, and Jasjit S. Suri

Abstract—Document classification and clustering is emerging as a new challenge in the Big Data era where terabytes of data are generated every second through billions of mobile phones, desk- tops, servers, and mobile devices such as cameras and watches. The effectiveness of classification and clustering algorithms de- pends on the similarity measure used between two text documents in the corpus. We have applied Maxwell–Boltzmann distribution to find the similarity between the two documents within a doc- ument corpus. In this paper, the document corpus is treated as a large system, individual documents as containers, attributes as subcontainers, and each term as a particle. The proposed simi- larity measure is named Maxwell–Boltzmann Similarity Measure (MBSM). MBSM is derived from the overall distribution of fea- ture values and total number of nonzero features among the doc- uments. We demonstrate that MBSM satisfies all properties of a document similarity measure. The MBSM is incorporated in sin- gle label K -nearest neighbors classification (SLKNN), multi label K -nearest neighbors classification (MLKNN) and K -means clus- tering. We benchmark MBSM against other similarity measures like Euclidian, Cosine, Jaccard, Pairwise, ITSim, and SMTP. The comparative performance shows that MBSM outperformed all ex- isting similarity measures and increased classification accuracy of SLKNN and MLKNN and clustering accuracy and entropy of K -means algorithm while making them more robust. The high- est accuracy obtained from tenfold cross validation for SLKNN is 0.9531 and MLKNN is 0.9373. The MBSM achieved maximum accuracy of 0.6592 and minimum entropy of 0.2426 amongst all similarity measures in the scale of unity for K -means clustering.

Index Terms—Text classification, text clustering, Maxwell– Boltzmann distribution, multi-label learning.

I. INTRODUCTION

W ITH the advent of Big Data there is an increasing need toassess the source, nature and significance of data. The underlying principle of assessment lies with developing new mathematical and physical paradigms to study the data. One such mathematical paradigm is the similarity measure which has been used for classification and clustering of data. In the follow- ing subsection, a general study of prevalent similarity measures

Manuscript received February 8, 2018; revised May 28, 2018 and July 5, 2018; accepted July 28, 2018. Date of publication August 24, 2018; date of current version March 25, 2020. (Corresponding author: Jasjit S. Suri.)

V. Kuppili, M. Biswas, and D. R. Edla are with the Department of Computer Science and Engineering, National Institute of Technology, Far- magudi 403401, India (e-mail:, [email protected]; mainak.biswas@ nitgoa.ac.in; [email protected]).

K. J. Ravi Prasad is with the Department of Humanities and Sciences, National Institute of Technology, Farmagudi 403401, India (e-mail:, k.j.raviprasad@ nitgoa.ac.in).

J. S. Suri is with the Global Biomedical Technologies, Inc., Roseville, CA 95661 USA (e-mail:, [email protected]).

Digital Object Identifier 10.1109/TETCI.2018.2863728

is given. Similarity measures such as Euclidean distance [18], Jaccard [8], Extended Jaccard [19] and Cosine [20] compute the distance or angle between vectors. Similarity measures can be broadly classified as topological measures and feature con- tent measures. In topological measures, features are arranged in a hierarchical structure and a suitable path length between these features is needed to be computed. Feature content mea- sures are based on the evidence of presence, where features with higher frequency are considered to be more specific with high information content, whereas, features with lower frequency are considered more general with low information content. ITSim, PairWise measures belong to the category of feature content measures. The information content measure of giving higher priority to high valued features with little difference among the two documents may yield no significant results. Euclidean and Cosine belong to the category of topological measures. Eu- clidean and Cosine measure are prone to information loss as two similar documents may have their similarity margin offset by the presence of a single feature with large weight.

Hence, statistical measures are needed to be included to opti- mize the similarity between two documents. Similarity measures have recently become an emerging topic of interest among data mining and Big Data research communities. Similarity measures have been widely used in various domains of research, such as for reconstructing phylogenetic trees [17]. Similarity measure is also used to calculate the similarity between two ordered trees. The objective is to find evolutionary relationship among various biological species or other entities based on the similarity and differences among their physical or genetic features [24]. Sim- ilarity measure has also been used in distance based indexing for string proximity to improve database search [16]. Further, similarity metrics have also been adapted for comparing graphs [2] and attributed trees [21]. Similarity measures have also been used for evaluating the importance of features in data mining [4], [15] and comparing information content [10].

Documents are represented as sparse vectors with large num- ber of features which in turn are used to compute similarity. The document space is highly homogeneous i.e., there exists large commonality between classes of documents. In a large corpus, classes of documents with large number of features generally overlap with each other. It is a hard problem to ascertain classes of documents based on their differences. A new similarity mea- sure based on Statistical Mechanics (SM) is proposed to address the issue.

Statistical mechanics deals with statistics of large number of particles or atoms with respect to energy distribution among

2471-285X © 2018 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

KUPPILI et al.: MECHANICS-BASED SIMILARITY MEASURE FOR TEXT CLASSIFICATION IN MACHINE LEARNING PARADIGM 181

them. In the year 1859, Maxwell developed the kinetic theory of gases where he determined the distribution of velocities among molecules of gas. Later, Boltzmann generalized and postulated his idea about the distribution of energy among the gaseous molecules. It is in this context that Maxwell and Boltzmann postulated that the most probable state of gaseous molecules in the system. It is observed that the properties mentioned are almost similar to the properties of a large document corpus, where the corpus can be treated as a large system, individual documents as containers, attributes as sub-containers and each term as a particle/molecule.

In pursuit of the objective, the following hypothesis is pro- posed “It is stated that the behavior similarity of gaseous molecules in a system and words in a document corpus can be used to find similarity between text documents”. In the next subsection, a discussion on the approach taken is given.

In this paper, we adopt the concept of Maxwell-Boltzmann distribution Law1 [14], [23] of a large number gaseous molecules for designing a new similarity measure. It is known that Maxwell-Boltzmann distribution can be used to calculate the energy difference between two containers with similar sub components.2 This principle can be most effectively used as the first application of statistical mechanics for document classifi- cation and clustering. An analogy has been made between gas molecules in a container and words in a document. It is seen that the enormous number of gas molecules in a container resem- bles huge number of words distributed throughout a document corpus. In contrast to the existing measures, the statistical prop- erties of features (molecules) present in documents (container) are taken into account while computing the similarity measure. The new similarity measure is derived by considering the over- all distribution of feature values and total number of non-zero features among the documents. The similarity measure is devel- oped from the concept of Maxwell- Boltzmann Distribution. It is named as Maxwell-Boltzmann Similarity Measure (MBSM). The MBSM is described as the inverse of the energy difference or dissimilarity between two documents. The energy difference is described as the logarithm of the ratio of the overall distri- bution of feature values and total number of non-zero features among the documents. The MBSM when applied to Single Label K-Nearest Neighbor (SLKNN) classification and Multi-Label K-Nearest Neighbor (MLKNN) algorithms gives better accu- racy(Acc). The MBSM is also applied to K-Means Clustering (KMC) algorithm which gives increased accuracy (Acc) and decreased entropy (En) than prevalent similarity measures. The reliablity analysis shows that MBSM has better reliability than other similarity measures.

The rest of the paper is organized as follows. An overview of existing measures is given in section II. Maxwell-Boltzmann Similarity Measure (MBSM) is derived and explained in section III. Experimental results are provided in section IV and performance evaluation is given in section V. Discussion is given in section VI. Finally, conclusion is given in section VII.

1Online. Fitzpatrick, “http://tinyurl.com/jc5xs8f” 2Online. Hill, “http://tinyurl.com/7qt9dcu”

II. OVERVIEW OF EXISTING METHODS

This section discusses existing similarity measures. It is divided into four subsections, II-A, II-B, II-C and II-D. In subsection II-A, a discussion on properties of similarity mea- sure is given. In subsection II-B, the different types of similarity measures are described. In subsection II-C, a brief introduction on Maxwell-Boltzmann Distribution is made. In the subsection II-D, the behavior similarity between gaseous molecules and words in text documents is discussed in detail.

A. Six Properties of Similarity Measure

Most document similarity measures are derived from seman- tic [22] metric. The similarity between two documents is based on the mathematical strength of semantic relationship. It is cal- culated as the distance between terms or features of two or more documents.

To resolve the problem, Dekang Lin [11] provided three in- tuitions for document classification, which are:

� Intuition 1: The similarity between documents d1 and d2

is related to their commonality. The more commonality they share, the more similar they are.

� Intuition 2: The similarity between d1 and d2 is related to the differences between them. The more differences they have, the less similar they are.

� Intuition 3: The maximum similarity between d1 and d2

is reached when d1 and d2 are identical, no matter how much commonality they share.

Let’s say that I(a) is the information content of message a and is measured by the negative logarithm of the probability of statement a. Then, given two statements X and Y, their description is defined as I(description(X, Y)), commonality is denoted as I(common(X, Y)), difference is represented as [I(description(X, Y)) − I(common(X, Y))] and similarity S(X, Y) is embodied as the function of commonality and dif- ference which is given by f(common(X, Y),difference(X, Y)). The similarity reaches highest at unity (S(X, Y) = 1) when both X and Y are identical or I(common(X, Y)) = I(description(X, Y)).

From the above intuitions regarding similarities and differ- ences between d1 and d2 , Lin stated six important properties [12] for the similarity measure. These are:

Property 1: The presence or absence of a feature is more essential than the difference between the two values associated with a present feature.

Consider two attributes fi and fj and two documents d1 and d2 . Suppose fi does not appear in d1 but it appears in d2 , then fi is considered to have no relationship with d1 while it has some with d2 . In this case, d1 and d2 are dissimilar in terms of fi. If fj appears in both d1 and d2 , then fj has some relationship with d1 and d2 simultaneously. In this case, d1

and d2 are similar to some degree in terms of fj . In the above two cases, it is reasonable to say that fi carries more weight than fj in determining the similarity degree between d1 and d2 . For example, assume that fi is absent in d1 , i.e., d1i = 0, but appears in d2 , e.g., d2i = 2, and fj appears both in d

1 and d2 , e.g., d1j = 3 and d

2 j = 5. Then fi is considered to be more

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

182 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

essential than fj in determining the similarity between d1 and d2 , although the differences of feature values in both cases are the same.

Property 2: The similarity degree should increase when the difference between two non-zero feature values decreases. For example if k1 and k2 are two features. Then, for the two docu- ments d1 and d2 , the similarity degree between d1

k1 = 100 and

d2 k1

= 5, will be far lesser than the similarity between d1 k2

= 2 and d2

k2 = 5.

Property 3: The similarity degree should decrease when the number of presence-absence features increases.

If there are three features k1 , k2 and k3 , and their sim- ilarity degree for values with respect to documents d1 and d2 are d1 = <0k

1 , 1k

2 , 0k

3 > and d2 = <1k

1 , 0k

2 , 0k

3 > is

lesser than documents d3 and d4 , d3 = <0k 1 , 1k

2 , 0k

3 > and

d4 = <0k 1 , 1k

2 , 1k

3 >, since, # of present-absent pairs w.r.t d1

and d2 is (two) is greater w.r.t d3 and d4 (one). Property 4: Two documents are least similar to each other if

none of the features have non-zero values in both documents. If d1 and d2 are two documents such that for each k of the n

features:

d1k.d 2 k = 0 and d

1 k + d

2 k > 0

where, 0 < k ≤ n. Then both documents are least similar to each other. Property 5: The similarity measure should be symmetric.

The similarity degree between d1 and d2 should be equal to similarity degree between d2 and d1 .

Property 6: A value for distribution offers more contribution to the similarity between d1 and d2 .

The standard deviation of the feature is taken into account, for its contribution to the similarity between two documents. A feature with a larger spread offers more contribution to the similarity between d1 and d2 .

B. Types of Similarity Measures

The most common similarity measure is Euclidean Distance [18]. It has been most widely used to calculate the similarity between objects in multidimensional space. Documents are rep- resented as high dimensional feature vectors. Since documents are high dimensional vectors, this method captures the summa- tion of the root squared difference between each feature of a document vector. The Euclidean similarity is given by:

SEuc(d 1, d2 ) =

√ (d1 − d2 )(d1 − d2 )T (1)

The Cosine similarity measure calculates the angle between two document vectors [20]. It is the second most widely used method for document classification and clustering. Euclidean distance and cosine similarity measure are the most widely used methods for machine learning and pattern recognition. However, cosine similarity measure is insensitive towards term weight between two documents [9] where the product of terms in both documents sometimes gets affected by the differences. The

Cosine Similarity is given by:

Scos(d 1, d2 ) =

d1 (d2 )T√ d1 (d1 )T

√ d2 (d2 )T

(2)

Jaccard Coefficient is another popular measure for document classification [8]. Since documents are represented as vectors, it measures similarity as the ratio of the size of the intersection to the size of union of the two document vectors. The Jaccard Similarity is given by:

SJaccard(d 1, d2 ) =

a a + b + c

(3)

where, a denotes the number of terms common to d1 and d2 , b denotes the number of terms unique to d1 and c denotes the num- ber of terms unique to d2 . The Tanimoto Distance also known as Extended Jaccard is another popular similarity measure [19]. It is based on Jaccard Distance and is given by:

SEJ (d 1, d2 ) =

d1.d2

d1.d1 + d2.d2 − d1.d2 (4)

Joris D’hondt proposed Pair Wise Adaptive Dissimilarity mea- sure. It is based on the Cosine Distance for high dimensional feature space [5]. This measure takes into account minimum necessary non zero feature values and finds their cosine similar- ity. The Pairwise similarity measure is given by:

SP airW ise(d 1 K , d

2 K ) =

d1K .d 2 K√

d1K .d 1 K .

√ d2K .d

2 K

(5)

where, diK is a small subset of i = 1, 2, . . . ,n consisting of the union of the K largest values of d1 and d2 . Aslam et al. provided Information Theoretic document Similarity Measure (ITSim) based on the six axioms of document similarity [1] [12] [11] [13] which is given by:

SIT Sim (d 1, d2 ) =

2. ∑

s�d1 υd2 log π(s)∑ s�d1 log π(s) +

∑ s�d2 log π(s)

(6)

where, π(s) denotes the fraction of document corpus. Another similarity measure was proposed by Lin which takes into ac- count three cases[12], which are:

(a) The feature is present in both documents (b) The feature appears in both documents and (c) The feature is absent in both documents It is given by:

FLin (d 1, d2 ) =

∑ N∗(d1i , d

2 i )∑

Nu (d1i , d 2 i )

(7)

where,

N∗ =

⎧ ⎪⎨ ⎪⎩

0.5 ∗ {1 + exp − d1i −d2i σ2

} if d1i .d2i > 0 0 if d1i = 0 and d

2 i = 0

−λ otherwise; and

Nu =

{ 0 if d1i = 0 and d

2 i = 0

1 otherwise;

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

KUPPILI et al.: MECHANICS-BASED SIMILARITY MEASURE FOR TEXT CLASSIFICATION IN MACHINE LEARNING PARADIGM 183

Fig. 1. Figure depicting movement of gaseous particles in random directions within a container.

From the above Eq. (7), Lin derived a similarity measure which is given by:

SLin (d 1, d2 ) =

FLin (d1, d2 ) + λ 1 + λ

(8)

where, λ is a constant, σ denotes the standard distribution of all non-zero values. In the next subsection 2.3, Maxwell-Boltzmann Distribution is discussed in detail.

C. Introduction on Maxwell-Boltzmann Distribution

In the year 1859, the kinetic theory of gases was developed. It discusses about distribution of velocities among molecules of gases was determined.3 Later, it was generalized to express the distribution of energies among molecules. It is assumed that the gas container consists of billions of molecules moving rapidly at random while colliding with each other and the walls of the container as shown in Fig. 1. This is qualitatively consistent with the physical properties of gases, if the notion that raising the temperature causes the molecules to move faster and collide with the walls of the container more frequently. Four assumptions were made from this behavior of gaseous molecules.

1) The diameter of molecules is much smaller than the dis- tance between them.

2) The collisions between particles conserve energy. 3) The molecules move with constant speed in a straight line

without collision. 4) The positions and velocities of molecules are initially ran-

dom. From these assumptions, the probability of the velocities of

different molecules at a particular temperature is predicted. The plot for probable velocities of molecules at different tempera- tures is shown in Fig. 2. Raising the temperature makes the curve skew to the right, increasing the most probable velocity. There exists a degree of uncertainty with respect to the fact that the motion of every single particle at all times cannot be determined in practice in any large system. Maxwell’s theory is based on statistical averages to see if the macro states could be predicted from the micro states. The number of micro states within any given configuration has to be determined, i.e. the number of ways in which N objects can be arranged into n distinct groups, also called the Multiplicity Function. This Multiplicity Function is discussed in the next section in detail.

3Online. Hill, “http://tinyurl.com/7qt9dcu”

Fig. 2. Maxwell-Boltzmann Distribution of velocities of molecules at a par- ticular temperature. Most probable velocity distribution is increased when tem- perature increases (T2 > T1 ).

Fig. 3. (a) Subfigure showing distribution of gaseous molecules within Gi sub-containers among Nn containers in a system. (b) Subfigure showing distri- bution of number of terms within each document for a document corpus.

D. Molecules and Words: An Analogy

Consider a text corpus consisting of millions of documents. In each text document there are thousands of terms whose order of arrangement unknown. The text corpus can be considered similar to a large container of gaseous molecules moving at ran- dom velocities. In our text corpus, we take the random order of arrangement of words to replicate the velocity of each molecule.

In the document corpus, we have N tokens distributed among n documents which are N1,N2, . . . ,Nn . Therefore, the total number of combinations that are formed can be represented by the multiplicity function ω which is given as:

ω = N

( ∏n

i= 1 Ni!) (9)

However, there can be multiple arrangements wherein the Ni tokens can be arranged in the ith document. It is noted that the tokens are distinguishable and are segregated into different types. Let the total number of token types for the ith docu- ment be expressed as Gi as shown in Fig. 3. Since, the previous combinations are unknown, therefore for all possible number of combinations within each document is put as GNii . There- fore, when GNii is multiplied with Eq. (9), we obtain the total multiplicity function θ which is given by:

θ = N!∏n i= 1 Ni!

.

n∏ i= 1

GNii (10)

Now, we draw our analogy from the second law of thermody- namics which states that the internal energy of an isolated sys- tem tries to reach an equilibrium. The equilibrium configuration

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

184 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

corresponds to the most probable configuration which is the state with maximum multiplicity, i.e., θ.

In the classical system, there are two constraints based on the assumptions of Maxwell Distribution Law. The first constraint is that total number of particles in a container must be conserved as shown in Eq. (11)

φ = ∑

Ni = N(constant) (11)

and total energy of the system must be conserved which is given by:

ψ = ∑

Ei.Ni = U(constant) (12)

where, Ei denotes the energy of the ith sub-container. After applying the logarithm function to Eq. (10):

log(θ) = log N! − n∑ Ni! + log

n∑ i= 1

Gi.Ni (13)

After applying Stirling’s Approximation4 to Eq. (13):

log(θ) = N log N − N − n∑ i= 1

NilogNi

+ n∑ i= 1

Ni + log n∑ i= 1

Gi.Ni (14)

The Lagrange’s multiplier is applied to Eq. (14) using con- straints shown in Eq. (11) and (12). New parameters α and β are introduced for implementing Lagrange’s multiplier which is given by:

log(θ) + αφ − βψ = 0 (15) Differentiating Eq. (15) with respect to Nj :

δ{log(θ) + αθ − βψ = 0} δNj

= 0 (16)

Expanding, Eq. (16):

δ

{ log

( N log N − N −

n∑ i= 1

Ni log Ni + n∑ i= 1

Ni

+ log n∑ i= 1

Gi.Ni

) + α

( ∑ Ni

)

− β ( ∑

Ei.Ni

)}/ δNj = 0

Since N is constant and the only terms which are non-zero when i = j are:

log Gj − log Nj + α − βEj = 0 (17) α − βEj is derived from Eq. (17):

α − βEj = log Nj Gj

(18)

where, Nj denotes number of particles in the j th document and

Gj denotes number of sub compartments in the j th document.

4logx! = xlogx − x.

Widom derived variables α and β [23]. The total energy of the system is given by:

Ej − Ef kBT

= log Nj Gj

(19)

where, Ej denotes energy of each particle (term) and Ef denotes Fermi Energy. Replacing left side of the equation with EC = Ej −Ef kB T

, we get:

EC = log Nj Gj

(20)

where, EC denotes overall energy, Nj denotes number of parti- cles (terms) in the jth document and Gj denotes number of sub containers (features) in jth document. It is observed that energy of a container (document) is directly proportional to number of particles (terms) in containers (documents) and inversely pro- portional to number of sub containers (features). In the next section, Maxwell-Boltzmann Similarity Measure (MBSM) for text classification and clustering is derived from this study on the behavior of gaseous molecules. The corresponding theorem and proof is also discussed in detail.

III. MAXWELL-BOLTZMANN SIMILARITY MEASURE

It is learnt from Eq. (20) that the energy of a document is derived from the overall distribution of feature values and total number of non-zero features among the documents. It inspired to develop a new similarity measure named Maxwell-Boltzmann Similarity Measure (MBSM) for document classification and clustering. The MBSM consists of the sum of squared difference of all feature values and total number of non-zero features among the documents. The energy difference of dissimilarity between two documents is used to define the MBSM. The dissimilarity between two documents is given by:

D(d1, d2 ) ≈ log ND GD

(21)

where,

ND =

⎧ ⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎩

0.5 ∗ ∑(d1k − d2k )2 if d1k and d2k > 0 λq ∗ 0.5 ∗ ∑(d1k )2 if d1k > 0, d2k = 0 λq ∗ 0.5 ∗ ∑(d2k )2 if d2k > 0, d1k = 0 0 otherwise;

and

GD =

⎧ ⎪⎪⎪⎪⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎪⎪⎪⎪⎩

total number of nonzero attributes if d1k, d

2 k > 0

total number of features of d1

having nonzero terms if d1k > 0, d 2 k = 0

total number of features of d2

having nonzero terms if d2k > 0, d 1 k = 0

0 otherwise ;

where, 0 < λ < 1, k denotes features and q denotes number of present-absent pairs. λ and q are incorporated to satisfy Lin’s property 1 which states that the presence or absence of a feature is more essential than the difference between the two values associated with a present feature. d1k and d

2 k refer to the total

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

KUPPILI et al.: MECHANICS-BASED SIMILARITY MEASURE FOR TEXT CLASSIFICATION IN MACHINE LEARNING PARADIGM 185

number of terms present in the kth feature of the 1st and 2nd

document. Now expanding ND in Eq. (21), we get:

D(d1, d2 ) = c.

log 0.5 ∗ ∑(d1k −d2k )2 +λq ∗ 0.5 ∗

∑ d1k

2 +λq ∗ 0.5 ∗ ∑ d1k 2

GD (22)

where, c is constant. Substituting c = 1 in the Eq. (22):

D(d1, d2 ) = log ND GD

(23)

As log(0) is undefined, numerical term 1 is added to the loga- rithm Eq. (23). In order to make Eq. (23) satisfy property 6, a smoothing parameter σ is introduced in Eq. (23), which is given by:

D(d1, d2 ) = log (

1 + ND σ.GD

) (24)

where,

σ =

{ 1 if (∃k)(d1k.d2k ) > 0 0 if (∀k)(d1k.d2k ) = 0

The following theory is presented with respect to the measure. Theorem 1: If similarity between two documents is

SM BSM = 11+D(d1 ,d2 ) then it lies between 0 and 1.

0 < SM BSM ≤ 1 Proof: It is known that

D(d1, d2 ) > 0 (25)

Adding 1 to both sides such that,

1 + D(d1, d2 ) ≥ 1 > 0 (26) Dividing each side by 1 + D(d1, d2 ), the equation obtained is

1 ≥ 1 1 + D(d1, d2 )

> 0 (27)

Therefore, our similarity measure is

1 ≥ SM BSM (d1, d2 ) > 0 (28) �

Therefore,

SM BSM = 1

1 + D(d1, d2 ) (29)

The Eq. (29) denotes proposed MBSM which is used to find similarity between two documents. The section is further di- vided into two subsection III-A and III-B. Subsection III-A discusses about the similarity between two documents and subsection III-B shows how MBSM can be applied to find sim- ilarity between two document sets.

A. Similarity Between Two Documents

In this section, it is shown through various examples that MBSM satisfies Lin’s properties when it is applied between two documents.

Remark 1: The presence or absence of a feature is more essential than the difference between the two values associated with a present feature.

In determining the similarity of two documents the similarity degree for a feature present in both documents would have relevance with respect to a feature absent in one document. The D(d1, d2 ) function is calculated with more weightage given to documents having both features rather than being present in one and absent in another. A variable λ is used to accomplish this. Assuming λ = 0.99 the following cases were considered.

Case 1: Two documents with both present-present and present-absent features

Example 1: d1 = <2, 3, 1, 0> and d2 = <0, 1, 3, 2>, So σ = 1, then MBSM is computed as

1

(1 + log(1 + 0.5∗((3−1) 2 + (1−3)2 )+ 0.5∗(0.99)2 ∗((2−0)2 + (0−2)2 )

1∗(4+ 2) )

= 0.54

Case 2: Two documents having same number of terms as the above example, with only present-present and absent-absent feature pairs.

Example 2: d1 = <2, 3, 1, 0> and d2 = <2, 1, 3, 0>, σ = 1 then MBSM is computed as

1

(1 + log(1 + 0.5∗((2−1) 2 + (3−1)2 + (1−3)2 )

1∗6 ) = 0.66

It is seen that two documents with present-absent pairs miss- ing has greater similarity degree than documents with present- absent pairs existing.

Remark 2: The similarity degree should increase when the difference between two non-zero values of a specific feature decreases.

Case 1: When the difference between two documents is low. Example 3: Let two documents be d1 = <2, 1, 2> and d2 =

<1, 2, 1>, then their similarity degree is:

1

(1 + log(1 + 0.5∗((2−1) 2 + (1−2)2 + (2−1)2 )

1∗6 ) = 0.82

Case 2: When the difference between two documents is high.

Example 4: Let two documents be d1 = <20, 10, 20 > and d2 = <10, 20, 10>, then σ = 1, therefore, their similarity de- gree is:

1

(1 + log(1 + 0.5∗((20−10) 2 + (10−20)2 + (20−10)2 )

1∗6 ) = 0.20

As the differences between two documents are raised by a factor of ten, similarity degree reduces significantly.

Remark 3: The similarity degree should decrease when the number of present-absent feature pairs increases.

There are two cases Case 1: When the number of present-absent pairs is low

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

186 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

Example 5: Let two documents be d1 = <2, 0, 2, 1> and d2 = <3, 1, 1, 0>, then their similarity degree is:

1

(1 + log(1 + 0.5∗((2−3) 2 + (2−1)2 ]+ 0.5∗0.992 ∗[(0−1)2 + (1−0)2 )

1∗(4+ 2) )

= 0.78

Case 2: When the number of present-absent feature pairs increases

Example 6: Let two documents be d1 = <2, 0, 1, 1>and d2 = <3, 1, 0, 0>, with equal number of terms is:

1

(1 + log(1 + 0.5∗((2−3) 2 ]+ 0.5∗0.993 [(0−1)2 + (1−0)2 + (1−0)2 )

1∗(2+ 3) )

= 0.751

It is seen that if the number of present-absent feature pairs is increased, their similarity degree decreases.

Remark 4: Two documents are least similar to each other if none of the features have non-zero values in both documents.

Here all the features are present-absent pairs. Therefore, σ = 0 in the denominator of the D function making it infin- ity and reducing the similarity to zero.

Example 7: Let two documents be d1 = <2, 1, 0, 0> and d2 = <0, 0, 1, 3>, then their similarity degree is:

1

(1 + log(1 + 0.5∗0.99 2 ∗((2−0)2 + (1−0)2 + (2−0)2 + (1−0)2 )

0∗(4) )

= 1 ∞ = 0

Therefore, making the two documents least similar with all present-absence feature pairs in them.

Remark 5: The similarity measure values should be between one and zero.

Since the difference between two same documents is zero making similarity degree equal to one and thus achieving highest similarity. In the second case, if all features are present-absent pairs, σ = 0 making value of D function infinity, and inversely making similarity degree zero.

Remark 6: The similarity measure should be symmetric. Since the differences between two documents are squared,

the similarity measure is symmetric between two documents. Remark 7: A value for distribution offers more contribution

to the similarity between d1 and d2 . In this paper, σ represents ths value of distribution which is:

σ =

{ 1 if (∃k)(d1k.d2k ) > 0 0 if (∀k)(d1k.d2k ) = 0

B. Similarity Between Two Document Sets

In this section, it is shown that MBSM can be applied to find similarity between two document sets. Let A1 and A2 be our two document sets containing p and q documents each with n features respectively i.e, A1 = (d11, d

2 1, ....., d

p 1 ) and A2 =

(d12, d 2 2, ....., d

q 2 ) where, d

l s denotes a document with s�(1, 2)

representing document set and 1 ≤ l ≤ p or 1 ≤ l ≤ q. ND is

given by:

ND (A1, A2 ) =

⎧ ⎪⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎪⎩

∑ ∑ ∑ (di1 k −dj2 k )2 2 if d

i 1k > 0, d

j 2k > 0

∑ ∑ (di1 k )2 2 if d

i 1k > 0, d

j 2k = 0

∑ ∑ (dj2 k )2 2 if d

j 2k, d

i 1k = 0

0 otherwise;

and

GD (A1, A2 ) =

{ Sum of all non zero features σ = 1

0 σ = 0

where,

σ =

{ 1 if (∃kdi1k.dj2k ) > 0 0 if (∀kdi1k.dj2k ) = 0

Therefore,

D(A1, A2 ) = log (

1 + D1 + D2 + D3

GD

) (30)

where,

D1 = 0.5 ∗ ∑ ∑ ∑

(di1k − dj2k )2

D2 = λ q ∗ 0.5 ∗

∑ ∑ (di1k )

2

D3 = λ q ∗ 0.5 ∗

∑ ∑ (dj2k )

2 )

SM BSM (A1, A2 ) = 1

1 + D(A1, A2 ) (31)

Eq. (30) gives us the dissimilarity between the given document sets and Eq. (31) gives the similarity between them.

Example 8: Let documents set be

A1 =

⎧ ⎪⎨ ⎪⎩

d11 = <6, 3, 5, 0>

d21 = <2, 1, 2, 0>

d31 = <5, 3, 7, 0>

and

A2 =

⎧ ⎪⎨ ⎪⎩

d12 = <0, 1, 9, 2>

d22 = <0, 4, 6, 3>

d32 = <0, 3, 8, 7>

Then ND (A1, A2 ) = 0.5 ∗ ((3 − 1)2 + (3 − 4)2 + (3 − 3)2 + (5 − 9)2 +(5 − 6)2 +(5 − 8)2 +(1 − 1)2 +(1 − 4)2 +(1 − 3)2 + (2 − 9)2 + (2 − 6)2 + (2 − 8)2 + (3 − 1)2 + (3 − 4)2 + (3 − 3)2 + (7 − 9)2 +(7 − 6)2 + (7 − 8)2 )+0.5 ∗ 0.9918 ∗ (3 ∗ 62 +3 ∗ 22 +3 ∗ 52 +3 ∗ 22 + 3 ∗ 32 + 3 ∗ 72 ) = 236.97

and GD (A1, A2 ) = 36 + 18 = 54. Thus D(A1, A2 ) = 1.6842. Therefore, SM BSM (A1, A2 ) = 11+D(A 1 ,A 2 ) = 0.3725.

IV. EXPERIMENTAL RESULTS

This section describes experimental results obtained using the proposed MBSM when applied to various machine learn- ing algorithms. The proposed MBSM is compared with various

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

KUPPILI et al.: MECHANICS-BASED SIMILARITY MEASURE FOR TEXT CLASSIFICATION IN MACHINE LEARNING PARADIGM 187

TABLE I SPLITTING OF DOCUMENTS AMONG FOUR CLASSES IN WEB KB DATASET

similarity measures such as Euclidean [18], Jaccard [8], Ex- tended Jaccard [19], Cosine [20], PairWise [5], ITSim [1] and SMTP [12] using K-Nearest Neighbors Document Classifica- tion and K-Means Clustering [7], [25]. Three algorithms have been used for performance evaluation. These are Single Label K-Nearest Neighbors (SLKNN) and Multi-Label K-Nearest Neighbors (MLKNN) for classification and K-Means cluster- ing (KMC) for clustering. This section is divided into four sub- sections, IV-A, IV-B, IV-C and IV-D. In subsection IV-A, de- scription of datasets is given. In subsection IV-B, results from the implementation of SLKNN is provided. In subsection IV-C, details of implementation of the MLKNN and corresponding results are given. In the last subsection IV-D, implementation details and results for KMC are discussed.

A. Description of Datasets

Three datasets have been used, namely, Web KB, 20 News- groups and Reuters Dataset5 for SLKNN and KMC. Two datasets for MLKNN algorithm are used i.e. RCV-v15 and Yeast6. Details of each dataset are given as follows:

1) Single Label Datasets: 1) Web KB Dataset: The Web KB Dataset contain webpages

as documents. It is obtained from World Wide Knowledge Base project of the CMU text learning group. The Web KB Dataset is split as shown in Table I.

2) 20 Newsgroups Dataset: The data set is a collection of approximately twenty thousand newsgroup documents, partitioned evenly across twenty different newsgroups. Details of the dataset are given in Table II.

3) Reuters Dataset: Reuters-R8 Dataset contains the eight most frequent features of the original ninety features in the Reuters dataset. Details of the dataset are given in Table III.

2) Multi-Labeled Datasets: 1) Yeast: This dataset is obtained from the repository of

the University of California at Irvine7 and contains one thousand four hundred and eighty four instances and ten classes. The details of the Yeast dataset are given in Table IV.

2) RCV-v1: Reuters Corpus Volume I (RCV-v1) is an archive of over eight hundred thousand manually categorized newswire stories made available by Reuters Ltd. for

5Online. “Ana Cardoso-Cachopo”, http://tinyurl.com/gouuq2n 6Online.Mulan.“http://tinyurl.com/jdf49l6” 7Online.“http://tinyurl.com/zye8c9p”

TABLE II SPLITTING OF DOCUMENTS AMONG TWENTY CLASSES IN 20 NEWSGROUP

DATASET

TABLE III SPLITTING OF DOCUMENTS AMONG EIGHT CLASSES IN REUTERS-R8 DATASET

TABLE IV YEAST FEATURES AND INSTANCES DISTRIBUTION

TABLE V RCV-V1 FEATURES AND INSTANCES DISTRIBUTION

research purposes. The original data is referred to as RCV- v1. The dataset is divided class wise among documents and shown in Table V.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

188 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

TABLE VI TEN FOLD CROSS VALIDATION RESULTS OF SLKNN FOR WEB KB

TABLE VII TEN FOLD CROSS VALIDATION RESULTS OF SLKNN FOR 20 NEWSGROUP

TABLE VIII TEN FOLD CROSS VALIDATION RESULTS OF SLKNN FOR REUTERS-R8

Fig. 4. Average Accuracy for Single Label k-Nearest Neighbors Classification Plot for Similarity Measures for Web KB, 20 NewsGroup and Reuters-R8 Dataset.

B. Single Label K-Nearest Neighbors Classifier

SLKNN is derived from K-Nearest Neighbors algorithm. It is one of the most common algorithms for document classifi- cation. The K-nearest neighbors (documents) of test instance

in the training dataset are computed based on the similarity measure. The test instance is assigned the most frequent class among the K-nearest neighbors. The Acc values are obtained by implementing the SLKNN classification algorithm on Web Kb, 20Newsgroups and Reuters-R8 dataset.

1) Results Using SLKNN: The results for each dataset are shown in Table VI, VII and VIII. Ten fold cross validation has been applied on all datasets. SLKNN Algorithm is applied with K = 10, 20 · · · 80 where, K indicates the number of nearest neighbors. In Table VI, it is seen that MBSM gives better Acc than all similarity measures for Web KB Dataset. In Table VII, the MBSM gives better Acc than all prevalent measures, with Acc nearing unity. In Table VIII, the MBSM Acc values in- creases steadily when the number of K-nearest neighbors in- creases. The mean accuracies of all similarity measures for all datasets are shown in Fig. 4. Right tailed t-test is applied for comparison of the accuracies of various similarity measures with MBSM for each dataset. The results of the right tailed t- test are shown in Table IX. The p−values of the application of various similarity measures with the MBSM is given in column 2, 3, 4, 5, 6 and 7. All the p−values from columns 2–7 indicate

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

KUPPILI et al.: MECHANICS-BASED SIMILARITY MEASURE FOR TEXT CLASSIFICATION IN MACHINE LEARNING PARADIGM 189

TABLE IX PERFORMANCE EVALUATION OF MBSM FOR SLKNN

TABLE X TEN FOLD CROSS VALIDATION RESULTS OF MLKNN FOR YEAST

TABLE XI TEN FOLD CROSS VALIDATION RESULTS OF MLKNN FOR RCV-V1

Fig. 5. Average Accuracy for MLKNN Classification Plot for Similarity Mea- sures for Yeast and RCV-v1 Dataset.

that the increase in classification accuracy for MBSM is statisti- cally significant. Precision and Recall values with repect to the datasets are given in the Appendix.

C. Multi-Label K-Nearest Neighbors Classifier

MLKNN [25] classifies multi-labeled datasets. In multi- labeled datasets, instances can belong to multiple labels. For each unseen instance in a multi-labeled dataset, its K- near-

est neighbors in the training set are first identified. Statistical information is gained from the label sets of these neighboring instances for each possible class. The maximum a posteriori probability (MAP) principle is utilized to determine the label set for the unseen instance. MLKNN algorithm is applied on Yeast and RCV-v1 dataset.

1) Results Using MLKNN: The Acc values are shown in Table X and Table XI. Ten fold cross validation has been ap- plied on all datasets. The K values for each dataset chosen are K = 10, 20, . . . , 80. The Acc values for Yeast Dataset show high degree of Acc for MBSM than prevalent methods. All sim- ilarity measures for RCV-v1 show lower Acc values than Yeast Dataset due to the high sparsity and fuzzy nature of data in RCV-v1. It has been observed that, the proposed MBSM shows considerable increase in Acc when compared to other similarity measures. Average Acc values for all similarity measures for Yeast and RCV-v1 dataset are shown in Fig. 5. In terms of the Acc values for MLKNN Algorithm, right tailed t-test is applied for comparison of MBSM with other similarity measures. The p−values showing the comparison of MBSM with other sim- ilarity measures for Yeast and RCV-v1 Datasets are given in Table XII. The p-values are given in column 2, 3, 4, 5, 6 and 7. All the p-values from columns 2–7 indicate that the increase in Acc for MBSM is statistically significant. Hamming Loss and F1-score values with repect to the datasets are given in the Appendix.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

190 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

TABLE XII PERFORMANCE EVALUATION OF MBSM FOR MLKNN

TABLE XIII ACC FOR K-MEANS CLUSTERING FOR WEB KB

TABLE XIV EN FOR K-MEANS CLUSTERING FOR WEB KB

TABLE XV ACC FOR K-MEANS CLUSTERING FOR 20 NEWSGROUP

D. K-Means Clustering

In KMC, the document set is clustered using unsupervised methodology of randomly selecting K- points (Kc). In this algorithm, (Kc) random data points are selected among the dataset. The data points are then assigned to each cluster based on maximum similarity till no data points are left. The perfor- mance of proposed similarity measure has been compared with existing similarity measures when employed in KMC algorithm. The Acc and En values are adopted to judge the clustering per- formance [26] [3] [12]. The clustering Acc and En values of all similarity measures obtained from Web KB dataset using KMC is shown in Table XIII and XIV respectively.

1) Results Using KMC: Acc and En values of MBSM and other existing similarity measures have been measured us-

TABLE XVI EN FOR K−MEANS CLUSTERING FOR 20 NEWSGROUP

TABLE XVII ACC FOR K-MEANS CLUSTERING FOR REUTERS-R8

TABLE XVIII EN FOR K-MEANS CLUSTERING FOR REUTERS-R8 DATA SET

ing KMC. The K-values applied on Web KB Dataset are K = 4, 8, . . . 20 where, K denotes the number of clusters. It is observed that MBSM when used in KMC outperforms other similarity measures in terms of Acc and En values. Acc and En values of all similarity measures obtained from 20 News- Group dataset using KMC are shown in Tables XV and XVI re- spectively with K = 20, 40, . . . , 100. MBSM outperforms other similarity measures in terms of Acc and En for the 20 News- Group dataset. Acc and En results obtained using KMC al- gorithm on Reuters-R8 dataset are shown in Tables XVII and XVIII. The (K)-values K = 8, 16, . . . , 40 has been considered for experimentation. It is observed that the MBSM outperforms existing similarity measures in terms of Acc and En values for all Kc. The histogram plot for average Acc and En are given in Figs. 6 and 7. The Acc vs No. of clusters plots for Web KB, 20

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

KUPPILI et al.: MECHANICS-BASED SIMILARITY MEASURE FOR TEXT CLASSIFICATION IN MACHINE LEARNING PARADIGM 191

Fig. 6. Average Accuracy Plot for K-Means Clustering Algorithm for Simi- larity Measures for Web KB, 20 NewsGroup and Reuters-R8 Dataset.

Fig. 7. Average Entropy Plot for K-Means Clustering Algorithm for Similar- ity Measures for Web KB, 20 NewsGroup and Reuters-R8 Dataset.

Fig. 8. Accuracy Vs. no. of Clusters Plot for K-Means Clustering Algorithm for Similarity Measures for Web KB.

NewsGroup and Reuters-R8 datasets are shown in Fig. 8, Fig. 9 and Fig. 10, respectively. In terms of Acc and En values for KMC, right tailed t-test is applied for comparison for Web KB, 20 NewsGroup and Reuters-R8 Datasets. The results are shown in Table XIX. The p−value for Acc and En values are given in column 2, 3, 4, 5, 6 and 7. All the p-values from columns 2-7 indicate that the increase in Acc and decrease in En values for MBSM is statistically significant.

The following section presents a thorough performance eval- uation of the MBSM metric

Fig. 9. Accuracy Vs. no. of Clusters Plot for K-Means Clustering Algorithm for Similarity Measures for 20 NewsGroup Dataset.

Fig. 10. Accuracy Vs. no. of Clusters Plot for K-Means Clustering Algorithm for Similarity Measures for Reuters-R8 Dataset.

V. PERFORMANCE EVALUATION

This section presents performance evaluation of MBSM met- ric. This section is divided into four subsection V-A, V-B, V-D and V-E. In subsection V-A, stability analysis of MBSM met- ric is shown. Subsection V-B presents reliability analysis using variable data sizes. In subsection V-D, Acc analysis of MBSM with various λ values is given. Subsection V-E presents ROC curves of MBSM and different similarity metrics.

A. Stability Analysis

In this subsection, detailed stability analysis of MBSM and other similarity metrics is done. This experiment is performed to investigate the performance of MBSM and other similarity metrics with changing data sizes. The datasets used are Web KB and Reuters-R8 and the algorithm used is SLKNN. Since, the data size per class is not consistent for Web KB and Reuters-R8, the datasets have been divided in such a way that the dataset took a pool of the following percentages from each class: N = 20%, 40%, 60%, 80% and 100%. The five datasets for Web KB consisted of 840, 1680, 2520, 3360 and 4199 instances, while for Reuters-R8 it consisted of 1535, 3070, 4605, 6140 and 7674 instances. Fig. 11 and Fig. 12 illustrates the consequence of in- creasing data sizes on classification accuracy values. The Acc is computed by averaging accuracies> of all data sizes as shown in Table XX for Web KB dataset and Table XXI for Reuters-R8

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

192 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

TABLE XIX PERFORMANCE EVALUATION OF MBSM FOR KMC

Fig. 11. Accuracy Vs. Percentage Data Size for Web KB.

Fig. 12. Accuracy Vs. Percentage Data Size for Reuters-R8.

TABLE XX AVERAGE ACC OF SIMILARITY METRICS FOR WEB KB OF VARIOUS SIZES

(20%, 40%, 60%, 80%, 100%)

TABLE XXI AVERAGE ACC OF SIMILARITY METRICS FOR REUTERS-R8 OF VARIOUS SIZES

(20%, 40%, 60%, 80%, 100%)

TABLE XXII AVERAGE SENSITIVITY VALUES OF SIMILARITY METRICS FOR REUTERS-R8 OF

VARIOUS SIZES (20%, 40%, 60%, 80%, 100%)

TABLE XXIII AVERAGE SPECIFICITY VALUES OF SIMILARITY METRICS FOR REUTERS-R8 OF

VARIOUS SIZES (20%, 40%, 60%, 80%, 100%)

Fig. 13. Reliability Vs. Percentage Data Size for Web KB.

Fig. 14. Reliability Vs. Percentage Data Size for ReutersR8.

dataset. It is seen that the MBSM gives the best reliability per- formance among all similarity measures. The average sensitivity values and specificity values shown in Tables XXII and XXIII demonstrate better performance of MBSM over other methods.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

KUPPILI et al.: MECHANICS-BASED SIMILARITY MEASURE FOR TEXT CLASSIFICATION IN MACHINE LEARNING PARADIGM 193

TABLE XXIV AVERAGE RELIABILITY OF SIMILARITY METRICS FOR WEB KB DATASET OF

VARIOUS SIZES (20%, 40%, 60%, 80%, 100%)

TABLE XXV AVERAGE RELIABILITY OF SIMILARITY METRICS FOR REUTERS-R8 OF

VARIOUS SIZES (20%, 40%, 60%, 80%, 100%)

B. Reliability Analysis

The reliability index has been derived by observing the de- viation of the classification accuracy with respect to its mean as the data size increases [27]. The reliability index (ζNi ) is formulated as:

ζNi = (

1 − σNi μNi

) × 100 (32)

where, σ represents the standard deviation and μ represents the mean of all accuracies.

Fig. 13 and Fig. 14 shows the reliability indices of MBSM and other measures with increasing data sizes.

The system reliability is computed by averaging the reliabil- ity indices of all data sizes as shown in Table XXIV for Web KB dataset and Table XXV for Reuters-R8 dataset. The MBSM gives the best reliability performance among all similarity metrics.

C. Clustering Accuracy Versus Lambda (λ)

The curve fitting analysis for various K-means (Kc) values versus λ, is shown in Fig. 15.

D. Clustering Efficiency With Respect to Time

The total time required to run Web KB, 20NewsGroup and Reuters-R8 dataset are 32.30, 613.68 and 113.28 seconds, re- spectively.

E. ROC Curves

The ROC curves for MBSM and other similarity measures using SLKNN is shown in Fig. 16. The ROC curves for MBSM and other similarity measures using MLKNN is shown in Fig. 17. The AUC values for classification accuracy is given in Table XXVI. The high AUC values clearly indicate that MBSM is better than other similarity measures in terms of AUC.

VI. DISCUSSION

Maxwell-Boltzmann Similarity Measure: In this paper, MBSM, a new similarity measure has been discussed. The MBSM satisfies all Lin’s properties on document similar- ity. The MBSM has been applied in both, the classification

and clustering algorithms. Application of MBSM has shown improvement in classification accuracy and clustering accu- racy along with decrease in clustering entropy values over other similarity measures. Experiments have shown high ac- curacy, reliability, sensitivity and specificity of the MBSM measure.

The similarity measure gives higher classification accuracy for SLKNN given in Table VI, Table VII and Table VIII and shown in Fig. 4 for Web KB, 20 NewsGroup and Reuters-R8 datasets. All Results have gone through the statistical t-test as shown in Table IX which shows that the results of MBSM are statistically significant. The Maxwell-Boltzmann Distribu- tion Similarity Measure gives higher classification accuracy for MLKNN and is given in Table X Table XI for Yeast and RCV- v1 dataset. It is shown in the corresponding histogram Fig. 5 for Yeast and RCV-v1 dataset. All Results have gone through the the statistical t-test as shown in Table XII. The results from MBSM are statistically significant. The results show that MBSM is better than other similarity metrics. The similarity measure gives higher clustering Acc which is shown in Table XIII for Web KB dataset, Table XV for 20Newsgroup dataset and Table XVII for Reuters-R8 dataset. The results are shown in Fig. 6. MBSM gives lower entropy with respect to other sim- ilarity measures which is given in in Table XIV for Web KB dataset, Table XVI for 20Newsgroup dataset and Table XVIII for Reuters-R8 dataset. The results are shown in Fig. 7. All results have gone through the statistical t-test as shown in Ta- ble XIX which shows that the results of MBSM are statistically significant. All of the above results clearly shows that MBSM is better than prevalent similarity measures. Special note on Sta- bility, Reliability and λ: The following interpretations are made from the stability results shown in Figs. 11 and 12.

1) The MBSM shows consistent increase in classification accuracy with increase in sample sizes for both Web KB and Reuters-R8 dataset.

2) The SMTP curve showed sporadic increase and decrease in Acc values with increase in sample sizes for both Web KB and Reuters-R8 dataset.

3) The PairWise and IT-Sim measure showed decline in Acc with increase in data sizes for both Web KB and Reuters- R8 dataset.

It is inferred that MBSM performance increases with increase in data volume. Algorithms employing MBSM are more stable than others.

The following points were inferred from the reliability anal- ysis

1) The average reliability index computed over varying data sizes is given in Table XXIV for Web KB Dataset and Table XXV for Reuters-R8 Dataset.

2) The best performance is obtained by MBSM. From these points it is inferred that systems employing

MBSM tend to show more reliable behavior than systems em- ploying other similarity measures.

The following points were observed from the following curve fitting analysis for clustering Acc and λ values.

1) For every dataset, λ and K values have to be tuned to get optimum results.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

194 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

Fig. 15. (a) Curve fitting for Web KB with K= 4. (b) Curve fitting for Reuters-R8 with K= 8. (c) Curve fitting for Web KB with K= 8. (d) Curve fitting for Reuters-R8 with K= 16. (e) Curve fitting for Web KB with K= 12. (f) Curve fitting for Reuters-R8 with K= 24. (g) Curve fitting for Web KB with K= 16. (h) Curve fitting for Reuters-R8 with K= 32.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

KUPPILI et al.: MECHANICS-BASED SIMILARITY MEASURE FOR TEXT CLASSIFICATION IN MACHINE LEARNING PARADIGM 195

Fig. 16. (a) Subfigure of ROC curve for Web KB for SLKNN. (b) Subfigure of ROC curve for Reuters-R8 for SLKNN.

Fig. 17. (a) Subfigure of ROC curve for Web KB for MLKNN. (b) Subfigure of ROC curve for Reuters-R8 for MLKNN.

TABLE XXVI AUC VALUES USING SLKNN ON WEB KB AND REUTERS-R8 AND MLKNN

ON YEAST AND RCV-V1

2) Every dataset has an optimum λ and K values for best result.

3) In case of Reuters-R8 dataset, when λ > 1 and K = 24, clustering Acc improves rapidly.

4) For WbKB dataset, when Kc = 12, clustering Acc im- proves rapidly.

Strengths and Weaknesses: MBSM showed high classifica- tion accuracy results for 20 NewsGroup, Reuters-R8, Web KB dataset for SLKNN and Yeast Dataset for MLKNN. The reasons for low accuracy for MLKNN for RCV-v1 are:

1) The Class to Feature Ratio for RCV-v1 dataset is 467 features per class while in all other datasets it is 1-100, thus making the data extreme sparse and fuzzy for MLKNN to compute classification accuracy.

2) RCV-v1 needs to be processed by dimensionality reduc- tion techniques before being processed by the MLKNN algorithm using different similarity measures.

3) Scope of work does not allow for dimensionality reduc- tion, however, MBSM fared better than all other methods albeit with lesser margin.

Benchmarking: The comparative analysis of the proposed MBSM is performed against benchmark techniques available in literature on document classification and clustering. These experiments are performed on various text datasets, which are available at [28] for both classification and clustering tasks.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

196 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

TABLE XXVII BENCHMARKING OF MBSM WITH LITERATURE ON TEXT SIMILARITY MEASURE FOR CLASSIFICATION AND CLUSTERING

For classification, SLKNN is performed on different datasets namely, 20 NewsGroup, Web KB and Reuters. For clustering, K-Means is applied on 20 NewsGroup and Web KB datasets. These empirical results on benchmark classification and clus- tering techniques are presented in Table XXVII and results ob- tained from the proposed MBSM are highlighted in the table. Results from Table XXVII clearly showed that MBSM out- performs benchmarked results of SMTP, IB-Method, Pearson and Kullback-Leibler Divergence (KLD) similarity measures [29] [30]. The higher Acc values of MBSM and lower values of En demonstrate the supremacy of MBSM over other similarity metrics.

A. Special Note on Similarity Measure in Computational Intelligence

The central idea to any computer intelligence (CI)-based sys- tem is its ability to learn and apply the learning in a practical scenario. This paradigm essentially incorporates training the CI-based model in a known scenario and test it in an unknown setup. The essence of learning in the computers in current sce- nario are classification, clustering and optimization. Similarity or distance measures form the backbone of such systems. In this situation, similarity measures have been applied in trans- fer optimization [33], behavior recognition [34], learning in physics-based acoustic modeling [35], feature selection in job shop scheduling [36], defect detection in alloys [37], sunflower seed classification [38], healthcare [27] etc. Due to large volume of information flow and accumulation in the social-media driven world, text classification and clustering is emerging as a major CI challenge. In the current context, work has been done done in sentiment analysis [40], email classification [41] etc. In most of the systems, the Euclidean similarity metric is used. How- ever, the throughput, stability, robustness and accuracy can be increased by usage of the proposed similarity measure, MBSM. This is clearly evident from the results of the experiments, where MBSM increased the accuracy of K-NN for classification and K-means for clustering. The reason of its success lies in satis-

fying all Lin et al.’s properties [12] for text classification on the lines of the Maxwell-Boltzmann distribution [23].

VII. CONCLUSION

In this paper, a novel similarity measure named Maxwell- Boltzmann Similarity Measure (MBSM) has been derived from the kinetic theory of gases. It is based on the energy differ- ence between compartments of gaseous molecule which can be treated as the first implementation of statistical mechanical approaches for Document Classification and Clustering. It has been shown that the proposed similarity measure for document classification and clustering satisfies all the properties of a sim- ilarity measure. The performance evaluation of the MBSM is verified when applied with K-NN and K-means for classifica- tion and clustering tasks respectively. It has been observed that the proposed MBSM outperforms existing similarity measures like Euclidean, Cosine, Jaccard, Pairwise, It-Sim and SMTP. MBSM has wide application in solving many of the problems faced by computer scientists in the fields of image processing, computational geometry, computational physics, EEG-BCI [31] etc. Therefore, we view the work described in this paper as only the beginning of a large project. Our future work can include ap- plication of MBSM in query mining and clustering algorithms such as spherical K-means algorithm [32]. We intend to apply the MBSM in Big Data Projects having immense social and environmental impact on human beings.

ACKNOWLEDGMENT

The authors would like to thank DEITY, Govt. of India, for providing support for carrying out this work under Visvesvaraya Scheme. The authors are also thankful to Lamda Group8 for their support throughout this work.

APPENDIX

See Tables XXVIII–XXXVII.

8Online. “http://lamda.nju.edu.cn/Data.ashx”

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

KUPPILI et al.: MECHANICS-BASED SIMILARITY MEASURE FOR TEXT CLASSIFICATION IN MACHINE LEARNING PARADIGM 197

TABLE XXVIII PRECISION TABLE FOR WEB KB DATASET

TABLE XXIX PRECISION TABLE FOR 20 NEWSGROUP DATASET

TABLE XXX PRECISION TABLE FOR REUTERS-R8 DATASET

TABLE XXXI RECALL TABLE FOR WEB KB DATASET

TABLE XXXII RECALL TABLE FOR 20 NEWSGROUP DATASET

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

198 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

TABLE XXXIII RECALL TABLE FOR REUTERS-R8 DATASET

TABLE XXXIV HAMMING LOSS TABLE FOR YEAST DATASET

TABLE XXXV HAMMING LOSS TABLE FOR RCV-V1 DATASET

TABLE XXXVI F1-SCORE TABLE FOR YEAST DATASET

TABLE XXXVII F1-SCORE TABLE FOR RCV-V1 DATASET

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

KUPPILI et al.: MECHANICS-BASED SIMILARITY MEASURE FOR TEXT CLASSIFICATION IN MACHINE LEARNING PARADIGM 199

REFERENCES

[1] J. A. Aslam and M. Frost, “An information-theoretic measure for docu- ment similarity,” in Proc. 26th Annu. Int. ACM SIGIR Conf. Res. Dev. Inf. Retrieval, 2003, pp. 449–450.

[2] H. Bunke and K. Shearer, “A graph distance metric based on the maximal common subgraph,” Pattern Recognit. Lett., vol. 19, no. 3, pp. 255–259, 1998.

[3] D. Cai, X. He, and J. Han, “Document clustering using locality preserving indexing,” IEEE Trans. Knowl. Data Eng., vol. 17, no. 12, pp. 1624–1637, Dec. 2005.

[4] L. de Mántaras, “Id3 revisited: A distance-based criterion for attribute selection,” in Proc. 4th Int. Symp. Methodologies Intell. Syst., 1989, pp. 342–350.

[5] J. D’hondt, J. Vertommen, P.-A. Verhaegen, D. Cattrysse, and J. R. Duflou, “Pairwise-adaptive dissimilarity measure for document clustering,” Inf. Sci., vol. 180, no. 12, pp. 2341–2358, 2010.

[6] L. R. Dice, “Measures of the amount of ecologic association between species,” Ecology, vol. 26, no. 3, 1945, pp. 297–302.

[7] R. O. Duda and P. E. Hart, Pattern, Wiley: New-York, 1976. [8] C. G. González, W. Bonventi, Jr., and A. L. Vieira Rodrigues, “Density of

closed balls in real-valued and autometrized boolean spaces for clustering applications,” in Proc. Brazilian Symp. Artif. Intell., 2008, pp. 8–22.

[9] W. P. Jones and G. W. Furnas, “Pictures of relevance: A geometric analysis of similarity measures,” J. Amer. Soc. Inf. Sci., vol. 38, no. 6, pp. 420–442, 1987.

[10] M. Li, X. Chen, X. Li, B. Ma, and P. M. B. Vitányi, “The similarity metric,”IEEE Trans. Inf. Theory, vol. 50, no. 12, pp. 3250–3264, Dec. 2004.

[11] D. Lin, “An information-theoretic definition of similarity,” inProc. Int. Conf. Mach. Learn., 1998, pp. 296–304.

[12] Yung-Shen Lin, Jung-Yi Jiang, and Shie-Jue Lee, “A similarity measure for text classification and clustering,”IEEE Trans. Knowl. Data Eng., vol. 26, no. 7, pp. 1575–1590, Jul. 2014.

[13] L. Mazuel and N. Sabouret, “Semantic relatedness measure using object properties in an ontology,” inProc. Int. Semantic Web Conf., 2008, pp. 681–694.

[14] T. Pedersen, S. V. S. Pakhomov, S. Patwardhan, and C. G. Chute, “Mea- sures of semantic similarity and relatedness in the biomedical domain,” J. Biomed. Inform., vol. 40, no. 3, pp. 288–299, 2007.

[15] C Rajski, “A metric space of discrete probability distributions,” Inf. Con- trol, vol. 4, no. 4, pp. 371–377, 1961.

[16] S. C. Sahinalp, M. Tasan, J. Macker, and Z. M. Ozsoyoglu, “Distance based indexing for string proximity search,” inProc. 19th Int. Conf. Data Eng., 2003, pp. 125–136.

[17] N. Saitou and M. Nei, “The neighbor-joining method: a new method for reconstructing phylogenetic trees,”Mol. Biol. Evol., vol. 4, no. 4, pp. 406– 425, 1987.

[18] T. W. Schoenharl and G. Madey, Evaluation of Measurement Techniques for the Validation of Agent-Based Simulations Against Streaming Data. Berlin, Germany: Springer, 2008.

[19] T. Tanimoto, “An elementary mathematical theory of classification and prediction,” IBM, Armonk, NY, USA, Tech. Rep. IBM Int. Rep., Nov. 17, 1957.

[20] S. Tata and J. M. Patel, “Estimating the selectivity of tf-idf based cosine similarity predicates,”ACM Sigmod Rec., vol. 36, no. 2, pp. 7–12, 2007.

[21] A. Torsello, D. Hidovic-Rowe, and M. Pelillo, “Polynomial-time metrics for attributed trees,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 27, no. 7, pp. 1087–1099, Jul. 2005.

[22] J. Z. Wang, Z. Du, R. Payattakool, S. Y. Philip, and C.-F. Chen, “A new method to measure the semantic similarity of GO terms,” Bioinformatics, vol. 23, no. 10, pp. 1274–1281, 2007.

[23] B. Widom, Statistical Mechanics: A Concise Introduction for Chemists. Cambridge, U.K.: Cambridge Univ. Press, 2002.

[24] K. Zhang and D. Shasha, “Simple fast algorithms for the editing distance between trees and related problems,” SIAM J. Comput., vol. 18, no. 6, pp. 1245–1262, 1989.

[25] M.-L. Zhang and Z.-H. Zhou, “ML-KNN: A lazy learning approach to multi-label learning,” Pattern Recognit., vol. 40, no. 7, pp. 2038–2048, 2007.

[26] Y. Zhao and G. Karypis, “Comparison of agglomerative and partitional document clustering algorithms,” Defense Tech. Inf. Center Document, Fort Belvoir, VA, CA, Tech. Rep. TR-02-014, 2002.

[27] V. K. Shrivastava, N. D. Londhe, R. S. Sonawane, and J. S. Suri, “First re- view on psoriasis severity risk stratification: An engineering perspective,” Comput. Biol. Med., pp. 52–63, vol. 63, 2015.

[28] A. Cardoso-Cachopo, “Improving methods for single-label text catego- rization,” Ph.D. dissertation, Instituto Superior Tecnico, Universidade Tecnica de Lisboa, Lisboa, Portugal, 2007.

[29] A. Huang, “Similarity measures for text document clustering,” in Proc. 6th New Zealand Comput. Sci. Res. Student Conf., Christchurch, New Zealand, 2008, pp. 49–56.

[30] N. Slonim and N. Tishby, “The power of word clusters for text classifica- tion,” in Proc. 23rd Eur. Colloq. Inf. Retrieval Res., 2001, pp. 1–200.

[31] Y. Li and K. M. Wong, “EEG signal classification based on a Rieman- nian distance measure,” in Proc. IEEE Toronto Int. Conf. Sci. Technol. Humanity, 2009, pp. 268–273.

[32] C. Buchta, M. Kober, and I. Feinerer, and K. Hornik, “Spherical k-means clustering,” J. Statist. Softw., vol. 50, pp. 1–22, 2012.

[33] A. Gupta, Y.-S. Ong, and L. Feng, “Insights on transfer optimization: Be- cause experience is the best teacher,” IEEE Trans. Emerg. Topics Comput. Intell., vol. 2, no. 1, pp. 51–64, Feb. 2018.

[34] C.-H. Kuo, P.-C. Chang, and S.-W. Sun, “Behavior recognition using mul- tiple depth cameras based on a time-variant skeleton vector projection,” IEEE Trans. Emerg. Topics Comput. Intell., vol. 1, no. 4, pp. 294–304, Aug. 2017.

[35] L. Gabrielli, S. Tomassetti, C. Zinato, and F. Piazza, “End-to-end learn- ing for physics-based acoustic modeling,” IEEE Trans. Emerg. Topics Comput. Intell., vol. 2, no. 2, pp. 160–170, Apr. 2018.

[36] Y. Mei, S. Nguyen, B. Xue, and M. Zhang, “An efficient feature selection algorithm for evolving job shop scheduling rules with genetic program- ming,” IEEE Trans. Emerg. Topics Comput. Intell., vol. 1, no. 5, pp. 339–353, Oct. 2017.

[37] R. Ren, T. Hung, K. C. Tan, “Automatic microstructure defect detection of Ti-6Al-4V titanium alloy by regions-based graph,” IEEE Trans. Emerg. Topics Comput. Intell., vol. 1, no. 2, pp. 87–96, Apr. 2017.

[38] G. JayaBrindha and E. S. G. Subbu, “Ant colony technique for optimizing the order of cascaded SVM classifier for sunflower seed classification,” IEEE Trans. Emerg. Topics Comput. Intell., vol. 2, no. 5, pp. 78–88, Feb. 2018.

[39] S. K. Srivastava, S. K. Singh, and J. S. Suri, “Healthcare text classification system and its performance evaluation: A source of better intelligence by characterizing healthcare text,” J. Med. Syst., vol. 42, no. 5, pp. 1–35, 2018.

[40] E. A. Kolog, C. S. Montero, and T. Toivonen, “Using machine learning for sentiment and social influence analysis in text,” in Proc. Int. Conf. Inf. Theor. Secur., 2018, pp. 453–463.

[41] S. Liu and I. Lee, “Email sentiment analysis through k-means labeling and support vector machine classification,” Cybern. Syst., vol. 49, no. 3, pp. 181–199, 2018.

Venkatanareshbabu Kuppili received the Ph.D. de- gree. He is currently with the Machine Learning Group, Department of Computer Science and Engi- neering, National Intitute of Technology (NIT) Goa, Farmagudi, India, as an Assistant Professor. He was with Evalueserve Pvt. Ltd, as a Senior Research As- sociate. He is also actively involved in teaching and research development for the Graduate Program in the Department of Computer Science and Engineer- ing, NIT Goa. He has authored a number of research papers published in reputed international journals.

Mainak Biswas received the B.Tech degree in infor- mation technology from Government College of En- gineering and Ceramic Technology, Kolkata, India, in 2007, the M.Tech. degree in distributed and mobile computing from Jadavpur University, Kolkata, India, in 2009. He is currently working toward the Ph.D. degree in National Institute of Technology Goa, Far- magudi, India. He was Assistant Professor with O.P. Jindal University, Raigarh, India, during 2009–2013 and Madhav Institute of Technology and Science, Gwalior, India, during 2014–2015. He has authored

or coauthored and presented papers in various international journals and con- ferences.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.

200 IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE, VOL. 4, NO. 2, APRIL 2020

Damodar Reddy Edla received the B.Sc. degree from Kakatiya University, Warangal, India, in 2004, the M.Sc. degree from the University of Hyderabad, Hyderabad, India, in 2006, and the M.Tech. and Ph.D. degrees in computer science and engineering from In- dian School of Mines Dhanbad, Dhanbad, India, in 2009 and 2013, respectively. He is currently an As- sistant Professor with the Department of Computer Science and Engineering, National Institute of Tech- nology Goa, Farmagudi, India. He has authored or coauthored more than 20 research publications in re-

puted international journals and conferences. His research interests include data mining and wireless sensor networks.

K. J. Ravi Prasad received the M.Sc. degree from Indian Institute of Technology Delhi, Delhi, India, the Ph.D. degree in “diffuse optical tomography” from Indian Institute of Science, Bengaluru, India. He is currently an Assistant Professor with the De- partment of Humanities and Sciences, National In- stitute of Technology Goa, Farmagudi, India. His re- search publications have been published in reputed international journals and conferences. His research interests include diffuse optical tomography, inverse problems, and numerical optimization.

Jasjit S. Suri received the Ph.D. and M.B.A. degrees. He is an innovator, visionary, scientist, and an inter- nationally known world leader. He has authored or coauthored more than 650 peer reviewed articles and book chapters and more than 100 innovations and trademarks with an H-index of 52. He has also coau- thored more than 45 books covering healthcare and biomedical sciences. He received the Director Gen- eral’s Gold medal in 1980 and the Fellow of Ameri- can Institute of Medical and Biological Engineering, awarded by National Academy of Sciences, Washing-

ton, D.C., in 2004. He was the IEEE Chair for Denver section and is currently the Chairman of Global Biomedical Technologies, Inc., Roseville, CA, USA, while an executive board member of several organizations.

Authorized licensed use limited to: University of the Cumberlands. Downloaded on July 24,2021 at 03:49:43 UTC from IEEE Xplore. Restrictions apply.