Web Page Classification Based on Uncorrelated Semi-Supervised Intra-View and Inter-View Manifold Discriminant Feature Extraction

1 Introduction

With the rapid development of the Internet, the amount of web pages has been increasing very fast, and people benefit more and more from the information conveyed by these pages. In order to effectively utilize the information of web pages, it is necessary to classify them.

In real-world applications, web page classification has three characteristics: (1) Web page is a kind of multi-view data [Zhuang et al., 2012; Li et al., 2012a], since it usually contains two or more types of data, e.g., text, hyperlinks and images, where each type of data can be regarded as a view. (2) Web page classification is a semi-supervised application [Li et al., 2012b; Chen et al., 2012]. In the Internet, labeled pages are hard to be collected as compared with unlabeled pages, since the labeling operations are comparatively expensive and time consuming. (3) Web page data is highdimensional. It usually contains much information, and how to extract low-dimensional and useful features from this data is crucial for classification tasks.

1.1 Motivation

To the best of our knowledge, only one web page classification method has taken these three characteristics into consideration, that is semi-paired and semi-supervised generalized correlation analysis (SSGCA) [Chen et al., 2012]. Besides, there exist a few semi-supervised multi-view feature extraction methods designed for other applications, such as multiview metric learning with global consistency and local smoothness (MVML-GL) [Zhai et al., 2012], vector-valued reproducing kernel Hilbert spaces (VRKHS) [Minh et al., 2013] and multi-view hypergraph learning (MHL) [Hong et al., 2013].

Existing semi-supervised multi-view feature extraction methods have the following major drawbacks:

(a) They do not sufficiently utilize the favorable discriminant information within each view and between different views, especially the inter-view discriminant information. Here, discriminant information refers to the information of class labels and class distributions, which is useful to separate the samples with different class labels. In Figure 1, we separately employ the SSGCA, MVML-GL, VRKHS and MHL methods to extract features from the samples of WebKB database [Chen et al., 2012], and perform the principal component analysis (PCA) [Turk and Pentland, 1991] transform on the extracted features to obtain two major principal components that are used to show the sample distribution. Figure 1 shows that inter-view samples from two classes (in the green circles) tend to cluster together, leading to one of these samples, which actually belongs to one class, may be misclassified into another class, and thus is adverse to classification. This illustrates the necessity of utilizing interview discriminant information.

• (b) They do not reduce multi-view correlation. As shown in Figure 1, both labeled and unlabeled web page samples from different views usually mingle together, such that there is much correlation between views. This means much information redundancy exists between views in semisupervised scenario. The redundancy may interfere the performance of web page classification.

Hence, for the web page classification task, how to sufficiently utilize intra-view and inter-view discriminant information from web pages and effectively reduce the adverse multi-view correlation in semi-supervised scenario is an important research topic.

1.2 Contribution

We provide a novel solution for this topic. The contributions of our work are summarized as follows:

1. By incorporating the manifold discriminant learning technique into the web page classification task, we propose a feature extraction schema called semi-supervised intra-view and inter-view manifold discriminant (SI2MD) learning. It can fully utilize the intra-view and inter-view discriminant information of labeled samples and the local neighborhood structures of unlabeled samples to extract useful features from web page data. Here, local neighborhood refers to the area near a sample, which contains several nearest neighbor samples of this sample.
2. We further design a semi-supervised uncorrelation constraint for the SI2MD schema, which can effectively remove adverse multi-view correlation of the extracted features.
3. By combining the SI2MD schema with the semisupervised uncorrelation constraint, we propose a novel feature extraction approach for web page classification, which

is named uncorrelated semi-supervised intra-view and interviewmanifold discriminant (USI2MD) learning.

The proposed USI2MD approach is verified on the public web page databases, i.e. WebKB [Chen et al., 2012] and Internet advertisements [Kushmerick, 1999] databases. Experimental results demonstrate that the proposed approach performs better than several related multi-view feature extraction and web page classification methods.

2 RelatedWork

2.1 Web Page Classification

In the last decade, some methods have been presented for web page classification. They can be divided into five categories: (1) Classifier design based semi-supervised multiview learning method. For example, Muslea et al. [2006] introduced a multi-view active learning method called cotesting. Li et al. [2012a] presented a two-view transductive SVM (TTSVM) to take advantage of the unlabeled data and their multiple representations. Du et al. [2013] designed a multi-view semi-supervised learning method named local co-training (LCT). (2) Feature extraction based semisupervised multi-view learning method. Chen et al. [2012] developed a dimensionality reduction method called semipaired and semi-supervised generalized correlation analysis (SSGCA). (3) Semi-supervised methods without multiview learning. For instance, Zhou and Li [2005] designed a semi-supervised co-training algorithm named tri-training. (4) Multi-view methods without semi-supervised learning. For example, Zhuang et al. [2012] designed a new generative model for multi-view learning via probabilistic latent semantic analysis. (5) Other methods. For example, Chen and Hsieh [2006] presented a weighted vote based support vector machine to classify web pages with synonymous keywords. Hu et al. [2007] presented a framework for recognizing pornographic web pages, where texts, images and content representations of pages are jointly considered. Chen et al. [2009] designed a fuzzy ranking analysis paradigm with the discriminating power measure to reduce the dimensionality of input data. Zhang et al. [2011] presented a framework using a Bayesian method for content-based phishing web page detection.

Among the above semi-supervised multi-view web classification methods, only SSGCA employs the feature extraction technique. The difference between SSGCA and our USI2MD approach is that SSGCA neither utilizes the interview discriminant information nor reduces semi-supervised multi-view correlation, while USI2MD does.

2.2 Unsupervised and SupervisedMulti-view Feature Extraction

In recent years, multi-view feature extraction technique has attracted lots of research interest. In this field, multi-view subspace learning is an important research direction. Under this direction, canonical correlation analysis (CCA) [Hardoon et al., 2004] based and discriminant analysis based multiview subspace learning are two representative techniques. CCA based methods include multi-view CCA (MCCA) [Li et al., 2009], multiset integrated CCA [Yuan et al., 2011], multiple discriminant CCA [Gao et al., 2012], multiple principal angle (MPA) [Su et al., 2012], etc. Discriminant analysis based methods contain multi-view discriminant analysis (MvDA) [Kan et al., 2012], generalized multi-view marginal fisher analysis (GMMFA) [Sharma et al., 2012], multi-view discriminant transfer learning [Yang and Gao, 2013], viewinvariant discriminative projection [Hu et al., 2013], etc.

2.3 Semi-supervisedMulti-view Feature Extraction

Multi-view learning in semi-supervised scenario has become an important research topic [Li et al., 2012b; Liu and Tao, 2013; Richarz et al., 2014]. To the best of our knowledge, four semi-supervised multi-view feature extraction methods have been addressed. SSGCA has been introduced in Section 2.1. Multiview metric learning with global consistency and local smoothness (MVML-GL) [Zhai et al., 2012] reveals the shared latent feature space of the multi-view observations by embodying global consistency constraints and preserving local geometric structures. Vector-valued reproducing kernel Hilbert spaces (VRKHS) [Minh et al., 2013] learns an unknown functional dependency between a structured input space and a structured output space in the semi-supervised setting. Multi-view hypergraph learning (MHL) [Hong et al., 2013] constructs multi-view hypergraph Laplacian matrix and gets the dimensionality-reduced data by solving the standard eigen-decomposition to obtain the projection matrix.

The difference between these four semi-supervised multiview feature extraction methods and our USI2MD approach is that these four methods do not consider utilizing the interview discriminant information and reducing semi-supervised multi-view correlation, while USI2MD does.

3 Our USI2MDApproach

In this section, we introduce our USI2MD approach. Specifically, we detail the SI2MD schema, semi-supervised uncorrelation constraint and USI2MD approach in the following three subsections. Note that based on the preprocessed highdimensional web page data, we perform dimension reduction and feature extraction. How to obtain the preprocessed data is not the problem we discuss in this paper, and Refs. [Chen et al., 2012] and [Kushmerick, 1999] address this problem.

3.1 SI2MD Schema

Suppose that X1,X2, · · · ,XN denote the training web page sample sets of N views, where Xi (i = 1, 2, · · · ,N) contains c classes (class j comprises nji samples with class label Lj, and X1,X2, · · · ,XN contain the same c classes) and nc+1 i unlabeled samples. All unlabeled samples in each view are regarded as the (c +1)th class, and Lc+1 is used as the class label of unlabeled samples. In our approach, Xi (i = 1, 2, · · · , N) is mean-normalized (that is, the mean of all samples in Xi is a zero vector), and samples in X1,X2, · · · ,XN are all m-dimensional vectors. Let ni = ∑c+1 j=1 nji be the total sample number of Xi, and n = ∑Ni=1 ni be the total sample number of all views.

Based on the graph theory that is widely used in the fields of pattern recognition and machine learning, where "graph"

usually illustrates the relations among data samples [Wang and Chen, 2009], we use an intrinsic graph G to illustrate the intra-view and inter-view distance relations of web page samples within each class and each local neighborhood. And we use a penalty graph ¯G to illustrate the intra-view and interview distance relations of web page samples from different classes and different local neighborhoods. The graphs G and ¯G are defined as follows.

Definition 1 (Intrinsic graph G): for two training samples xps ∈ Xs and xqt ∈ Xt, whose class labels separately are Lj and Lk, (a) a solid edge is added between xps and xqt if j = k and k ̸= c + 1; (b) a dashed edge is added between xps and xqt if j = c + 1 or k = c + 1, and xps is among the K-nearest neighbors of xqt or vice versa. Here K = N × max (n11 , n21 , · · · , nc-1 N , ncN ).

Definition 2 (Penalty graph ¯G): for two training samples xps ∈ Xs and xqt ∈ Xt, whose class labels separately are Lj and Lk, (a) a solid edge is added between xps and xqt if j ̸= k, j ̸= c + 1 and k ̸= c + 1; (b) a dashed edge is added between xps and xqt if j = c + 1 or k = c + 1, and xps is outside the K-nearest neighbors of xqt or vice versa.

The affinity matrix of G, i.e. W ∈ Rn×n , whose element (wpq st ) refers to the weight of edge between xps and xqt , is defined as: if a solid edge exists between xps and xqt , then wpq st = 1; if a dashed edge exists between xps and xqt , then wpq st = exp (-‖xps -xqt ‖2/r); otherwise wpq st = 0. Here, r is an adjustable parameter of the "heat kernel" [Wang and Chen, 2009]. The affinity matrix of ¯G, i.e. ¯W ∈ Rn×n , whose element ( ¯wpq st ) refers to the weight of edge between xps and xqt , is defined in the same way as that of W.

We formulate the objective function of the SI2MD schema as

where β is a nonnegative coefficient, and v1, v2, · · · , vN denote the projective vectors of X1,X2, · · · ,XN, respectively. Formula (1) fully utilize the intra-view and inter-view discriminant information of labeled samples and the local neighborhood structures of unlabeled samples. Its first term can separate labeled samples of different classes and unlabeled samples of different neighborhoods, while its second term can congregate labeled samples within each class and unlabeled samples within each neighborhood. The second term also embodies the inter-view consistency, since when p=q (the same web page) and s̸=t (different views), samples xps and xqt are two views of the same web page, a solid edge is added between them and this term minimizes the distance between these two samples in the projected space.

Suppose that D ∈ Rn×n and ¯D ∈ Rn×n are two diagonal matrixes whose elements are separately defined as dpp ss = ∑Nt=1 ∑nt q=1 wpq st and ¯ dpp ss = ∑Nt=1 ∑nt q=1 ¯wpq st . Let Lw = D-W and Lb = ¯D- ¯W. We can divide Lw into N 2 small matrixes Lwst ∈ Rns×nt (s, t = 1, 2, · · · , N) and divide Lb into N 2 small matrixes Lbst ∈ Rns×nt (s, t = 1, 2, · · · , N),

3.2 Semi-supervised Uncorrelation Constraint

To reduce the adverse multi-view features correlation among web page samples, i.e. multi-view correlation of extracted features from samples not with the same class label, we design the semi-supervised uncorrelation constraint. It is noted that for any two samples, samples not with the same class label include three cases: (a) two samples with different class labels; (b) two unlabeled samples; (c) a labeled sample and an unlabeled sample.

We use an inter-view penalty correlation graph ˆG to illustrate the multi-view correlation relations of web page samples not with the same class label. The graph ˆG is defined as follows.

Definition 3 (Inter-view penalty correlation graph ˆG): for two training samples xps ∈ Xs and xqt ∈ Xt (s ̸= t), whose class labels separately are Lj and Lk, (a) a solid edge is added between xps and xqt if j ̸= k, j ̸= c + 1 and k ̸= c + 1; (b) a solid edge is added between xps and xqt if j = c + 1 or k = c + 1.

The affinity matrix of ˆG, i.e. ˆW ∈ Rn×n , whose element ( ˆwpq st ) refers to the weight of edge between xps and xqt , is defined as: if a solid edge exists between xps and xqt , then ˆwpq st = 1; otherwise ˆwpq st = 0.

We define the semi-supervised multi-view correlation as

Formula (3) expresses the adverse multi-view correlation among classes and unlabeled samples. To reduce this correlation, we make Corr = 0, which is equivalent to vT Q′ v = 0. Thus we use vT Q′ v = 0 as the semi-supervised uncorrelation constraint.

3.3 USI2MDApproach Description

By combining the SI2MD schema and semi-supervised uncorrelation constraint, we formulate the objective function of our USI2MD approach as

The solution of Formula (4) can be obtained by solving the following eigen-equation:

Once the eigenvectors vk (k = 1, 2, · · · , d; d <m) associated with d largest eigenvalues of Q′-1 (Q-βP) are obtained, we get vk 1 , vk 2 , · · · , vkN from vk . Let Vs = [v1 s , v2 s , · · · , vd s ], and y1, y2, · · · , yN denote N views of a query sample, where s = 1, 2, · · · ,N. Then we can obtain the projected features of training sample set Z X s and query sample Z y s separately by Z X s = V T s Xs and Z y s = V T s ys, and use the following strategy to fuse these features:

Finally, we use the nearest neighbor classifier with the cosine distance to classify Z y .

3.4 Time Complexity Analysis

Here, we analyze the time complexity of our approach and those of three related and representative semi-supervised multi-view feature extraction methods including SSGCA, MVML-GL and VRKHS. The time complexity of our approach is O (NMn2T + M 3 ), where O (NMn2T ) is the time complexity of calculating the matrixes P, Q and Q′ , and O (M 3 ) is the time complexity of calculating the matrix Q′-1 (Q-βP) and conducting the eigen-decomposition of this matrix. The time complexities of SSGCA, MVMLGL and VRKHS are O (Mn2T + M 3 ), O (n3L + M 2nL) and O (NMn2T + N 3n3T ), respectively. Here, M = N ×m, m denotes the dimensionality of samples from multiple views, N denotes the number of views, nL and nT separately denote the numbers of labeled samples and total samples (contains both labeled and unlabeled samples) in each view. It is noted that different views own the same number of samples, i.e. ni (i = 1, · · · , N) = nT , and and different views own the same number of labeled samples, i.e. nL.

The time complexity of our approach is slightly larger than that of SSGCA. Whether the time complexity of our approach is lower than that of MVML-GL is mainly determined by the values of M and nL. And whether the time complexity of our approach is lower than that of VRKHS is determined by the values of m and nT . In real-world applications, we found that the time cost of our approach is usually close to those of MVML-GL and VRKHS.

4 Experiments

4.1 Introduction of Databases

We use two publicweb page databases, i.e. theWebKB [Chen et al., 2012] and Internet advertisements [Kushmerick, 1999] databases, as test data.

The WebKB database contains 1051 web pages belonging to two categories: 230 pages in the course category and 821 pages in the non-course category. Each web page has two views: the page view that contains the textual content of this page, and the link view that contains the links from other web pages linking to this page. We use a preprocessed version of this database in our experiment, where 3000-dimensional and 1840-dimensional original features are separately extracted from the page view and link view of a web page.

The Internet advertisements (AD for short) database contains 3279 samples, among which 458 are advertisements and others are not. We use a preprocessed version of this database in the experiment, where each sample is treated as a binary vector with quite large sparsity, which consists of 1558 original features of 9 views. Here, we choose 3 views of them, i.e. 495 base URL features, 472 destination URL features and 457 image URL features, which hold comparatively more features.

4.2 ComparedMethods and Experimental Settings

In the experiment, we compare our USI2MD approach with six related and representative multi-view feature extraction and web page classification methods, which can be divided into three categories: MCCA [Li et al., 2009] and GMMFA [Sharma et al., 2012] are unsupervised or supervised multi-view subspace learning methods; MVMLGL [Zhai et al., 2012] and VRKHS [Minh et al., 2013] are semi-supervised multi-view feature extraction methods; SSGCA [Chen et al., 2012], TTSVM [Li et al., 2012a] and LCT [Du et al., 2013] are web page classification methods, in which SSGCA is also a semi-supervised multi-view feature extraction method.

For each database, we randomly select half of total samples from each class for training and the rest for testing, and further randomly choose a percentage (e.g., 10%) of the training samples as labeled samples and the rest as unlabeled ones for semi-supervised learning. Note that in the training stage: (1) all labeled and unlabeled training samples are used for unsupervised MCCA method; (2) only labeled training samples are used for supervised GMMFA method. In the AD database, the two views with best classification accuracy are used for SSGCA and TTSVM, since these two methods can deal with only two views. For our USI2MD approach, we set the coefficient β = 0.5, the parameter of heat kernel r = 140 for WebKB database and r = 3.5 for AD database, and the feature number d = 40 for WebKB database and d = 50 for AD database. The parameters of other methods are determined by using the 5-fold cross validation technique.

For all compared methods, we employ the principal component analysis (PCA) [Turk and Pentland, 1991] method to reduce the dimensionality of samples from different views to 1050 for WebKB database and 456 for AD database, because we need to analyze the relations between views for utilizing inter-view discriminant information, and thus demand the same dimensionality of inter-view samples. For all compared methods except TTSVM, we employ the nearest neighbor classifier with the cosine distance to do classification, while TTSVM itself is a classifier and can be directly used for classification.

4.3 Classification Performance Evaluation

We evaluate the classification effects of our USI2MD approach when the percent of labeled training samples varies from 10% to 90%. Figure 2 shows the corresponding average classification accuracies of all methods across 20 runs on two databases. Note that since MCCA is an unsupervised method, its classification accuracies keep unchanged. As seen in Figure 2, USI2MD always outperforms other compared methods, which verifies the effectiveness of our approach.

To statistically analyze the classification accuracies given in Figure 2, we conduct a statistical test, i.e. Mcnemar's test [Draper et al., 2002]. This test can provide statistical significance between USI2MD and other methods. It uses a significance level of 0.05, that is, if the p-value is below 0.05, the performance difference between two compared methods is statistically significant. Table 1 shows the p-values between USI2MD and other methods on two databases. According to Table 1, the proposed approach makes a statistically significant difference as compared with the related methods.

Corresponding to Figure 1, Figure 3 shows the sample distribution of two views of 20 web page samples in the feature space of our approach on WebKB database. We can find that intra-view and inter-view sample points from different classes are well separated, which demonstrates that our approach can sufficiently utilize intra-view and inter-view discriminant information of labeled samples; and sample points from different views are mostly separated, which indicates that our approach can effectively reduce the adverse multi-view correlation in semi-supervised scenario.

4.4 Effect of SI2MD Schema

To further analyze the discriminant ability of features extracted by the SI2MD schema, we define the following discriminability score:

where SbL is the between-class scatter matrix constructed by labeled samples in the feature space, St(L+U) is the total scatter matrix constructed by both labeled and unlabeled samples in the feature space, and tr(·) denotes the trace of a square matrix.

For the SI2MD schema, we use Formula (2) to calculate the projective vectors, and obtain the projected and fused features of training sample set as USI2MD does. Here we use the related semi-supervised multi-view feature extraction methods including MVML-GL, VRKHS and SSGCA as compared methods, and the percent of labeled training samples is set as 20%. Table 2 show the average discriminability scores of these three methods and the SI2MD schema across 20 runs on two databases. In comparisonwith other methods, the SI2MD schema achieves the highest discriminability scores.

4.5 Effect of Semi-supervised Uncorrelation Constraint

To further analyze the effectiveness of our semi-supervised uncorrelation constraint, we compare the classification results of the SI2MD schema (without the constraint), the USI2MD approach (the SI2MD schema and the constraint), MVMLGL, VRKHS and SSGCA. Figure 4 shows the average classification accuracies of these five methods across 20 runs on two databases. We can find that the accuracies of the SI2MD schema are lower than those of the USI2MD approach, but higher than those of other methods.

5 Conclusions

In this paper, we firstly propose a new feature extraction schema called SI2MD, which can sufficiently utilize the intraview and inter-view discriminant information of labeled samples and the local neighborhood structures of unlabeled samples to extract useful features from web page samples. Then we design a semi-supervised uncorrelation constraint to remove the adverse multi-view features correlation among samples not with the same class label. Finally, by incorporating the constraint into the SI2MD schema, we propose a novel semi-supervised multi-view feature extraction approach named USI2MD for web page classification.

Experimental results on public web page databases demonstrate that USI2MD achieves better classification accuracies than several representative multi-view feature extraction and web page classification methods. The Mcnemar's test experiment shows that the difference between USI2MD and other methods are statistically significant. In addition, experiments validate the effects of the designed SI2MD schema and semisupervised uncorrelation constraint.

In addition, it should be noted that except web page classification, the proposed approach can be also applied to other semi-supervised applications with high-dimensional multiview data.

Acknowledgements

The authors want to thank the anonymous reviewers for their constructive comments and suggestions. The work described in this paper was supported by the National Nature Science Foundation of China under Projects No. 61272273, No. 61233011, No. 61472178 and No. 61472186, and the Research Project of NJUPT (XJKY14016).