1 Introduction

Hierarchies Taxonomies are popular for organizing large volume data sets in various application domains [9, 15]. For example, ImageNet is an image database organized refer to the WordNet hierarchy (currently only the nouns), in which hundreds and thousands of images are used to depict each node of the hierarchy. It also has been used in many areas including biology data [9], Wikipedia [24], geographical data [39], and text data [3, 6, 44]. Therefore, large-scale hierarchical classification learning is an important and popular learning paradigm in machine learning and data mining communities [9, 15].

From the viewpoint of biologists, the discovery of new species is attributed to the new features detected. Furthermore, these new features are now available in the existed species [50]. Therefore, the challenge of hierarchical classification learning is that the full feature space is unknown before learning begins. As we know, the full feature space determines the final label category of the samples. For example, in the diagnosis of lung cancer, through clinical testing in a period, doctors can gradually obtain clinical signs of lung cancer patients. Further, these patients may need to be diagnosed with small cell lung cancer, which is the subcategory of lung cancer. This phenomenon suggests that it is infeasible to collect all features of disease before diagnosis beginning. Therefore, the dynamic characteristic of feature might make the feature space of training data become high dimensional and uncertain. In order to explore online knowledge discovery with a dynamic feature space, some streaming feature selection algorithms are proposed.

Contrary to traditional feature selection methods, streaming feature assumes that all features are precomputed and presented to a learner before feature selection takes place, and streaming feature selection is defined as features that flow in one by one over time whereas the number of training examples is fixed [5, 28, 48, 55,56,57]. For example, hot topics are continuously changing in the social network platforms such as Twitter, and Facebook. When a popular topic appears, it accompanies with a set of new keywords. These new keywords may act as key features to distinguish the popular topic. At present, a number of existing online streaming feature selection algorithms have been proposed. Wu et al. [48] presented an online streaming feature selection framework based on Markov blanket. Lin et al. [35] proposed a multi-label online streaming feature selection algorithm based on fuzzy mutual information. Currently, existing online streaming feature selection algorithms assume that classes are independent of each other, and often ignore the hierarchical structure between classes in hierarchical classification data.

Motivated by the above discussion, a new algorithm named KFOHFS, i.e., K ernelized F uzzy rough sets based O nline H ierarchical streaming F eature S election, is proposed in this paper, due to the kernelized fuzzy rough sets model can effectively measure the fuzzy relation between samples under the hierarchical label space. More specifically, KFOHFS conducts online streaming feature selection for large-scale hierarchical classification through three intuitive steps. Firstly, we define a new kernelized fuzzy rough sets model for large-scale hierarchical classification learning, and design a novel dependency function to determine whether the candidate feature on the flow is important to the label space relative to the selected features. Secondly, we present two steps for online streaming feature selection, i.e, online important feature selection, and online redundant feature recognition, which can be used to obtain discriminative features and discard redundant and useless features, respectively. Finally, an online heuristic streaming feature selection algorithm is proposed. Extensive experiments show the competitive performance of KFOHFS against some state-of-the-art online streaming feature selection algorithms.

The remainder of this paper is organized as follows. Section II discuses related work. Section III introduces kernelized fuzzy rough sets. In Section IV, we present a kernelized fuzzy rough sets based online streaming feature selection algorithm for large-scale hierarchical classification. Our experiments on several hierarchical classification data sets are demonstrated in Section V. Section VI summarizes this paper and outlines the future directions for this work.

2 Related work

In the feature selection process of large-scale hierarchical classification learning, hierarchical class information are helpful for selecting a feature subset [2, 7, 51]. There are many proposed feature selection algorithms that leverage the hierarchical class in a tree. For instance, Freeman et al. [22] proposed a method using genetic algorithms for combining feature selection and hierarchical classifier. Song et al. [42] developed a feature selection algorithm for hierarchical text classification. Zhao et al. [53] presented a feature selection framework with recursive regularization for hierarchical classification.

However, the above mentioned feature selection algorithms assume that global features are precomputed and presented to a learner before feature selection takes place [4]. In many real-life applications, features may exist in a streaming format and arrive one feature at a time. At present, a number of existing online streaming feature selection algorithms have been proposed. Roughly speaking, according to the number of labels associated with the instances, online streaming feature selection algorithms can be grouped into streaming feature selection for traditional single-label learning and multi-label learning [46], respectively.

For traditional single-label learning, Yu et al. [49] proposed a scalable and accurate online feature selection approach(SAOLA) for high dimensional data. The proposed algorithm employs an online pairwise comparison to maintain a parsimonious model over time. Nevertheless, SAOLA ignores the hierarchical structure of the classes. Javidi and Eskandari [29] proposed a method(SFS-RS) from the rough set perspective via considering the problem of streamwise feature selection, in which, Rough Set Theory is used to control the unknown feature space in SFS-RS. Eskandari and Javidi [14] proposed a new rough set model(OS-NRRSARA-SA) for online streaming feature selection. However, SFS-RS and OS-NRRSARA-SA cannot deal with numerical features and ignore the hierarchical structure of the classes. Rahmaninia and Moradi [40] proposed two online stream feature selection methods based on mutual information(OSFSMI and OSFSMI-k, respectively). However, these methods ignore the hierarchical structure of the classes and need domain knowledge before learning. Zhou et al. [57] proposed an online streaming feature selection algorithm(OFS-Density) based on a new neighborhood relation which using the density information of the surrounding instances. OFS-Density uses a fuzzy equal constraint for redundant analysis to make the selected feature subset with low redundancy but ignores the hierarchical structure of the classes. For multi-label learning, Lin et al. [35] proposed a multi-label online streaming feature selection algorithm based on fuzzy mutual information. Liu et al. [36] proposed an online multi-label streaming feature selection algorithm based on neighborhood rough sets.

Nevertheless, all aforementioned online streaming feature selection methods assume that classes are independent of each other and often ignore the hierarchical structure between classes in hierarchical classification data. Motivated by these factors, we utilize the hierarchical class structure and present an online streaming feature selection framework. Under this framework, we propose a kernelized fuzzy rough sets based online streaming feature selection algorithm for large-scale hierarchical classification learning.

3 Preliminary on kernelized fuzzy rough sets

In this section, we will review the notations and definitions of kernelized fuzzy rough sets. Fuzzy rough sets is a feasible method used to deal with numerical and fuzzy data [1, 17, 25, 26, 34, 37, 45]. However, how to effectively generate fuzzy similarity relations from data is still an important problem. Therefore, Hu et al. [27] proposed a kernelized fuzzy rough sets (KFRS) model, which used kernel function to measure the relation between samples.

Formally, a kernel fuzzy approximation space can be written as < U,A,D,k >, where U called a universe, A is the set of condition attributes, D is the set of decision attributes, and k is a kernel function satisfying reflexive, symmetric, and Tcos-transitive. All samples can be divided into subset {d1,d2,...,dm} according to D, where m is the number of classes. For ∀x ∈ U,

$$d_{i}(x)=\left\{ \begin{array}{ccccccccc} 1, & x \notin d_{i};\\ 0, & x \in d_{i}. \end{array} \right. $$

Definition 1

[27] Given a kernel fuzzy approximation space < U,A,D,k >, x ∈ U, k is a kernel function satisfying reflexive, symmetric, and Tcos-transitive, the fuzzy lower and upper approximation operators are defined as

$$ \begin{array}{@{}rcl@{}} \begin{array}{llll} \underline {k_{S}}d_{i}(x)=\inf\limits_{y \notin d_{i}} (1-k(x, y));\\ \underline {k_{\theta}}d_{i}(x)=\inf\limits_{y \notin d_{i}} (\sqrt{1-k^{2}(x,y)});\\ \overline{k_{T}}d_{i}(x)=\sup_{y \in d_{i}} k(x, y);\\ \overline{k_{\sigma}d}_{i}(x)=\sup_{y \in d_{i}}(1-\sqrt{1-k^{2}(x, y)}). \end{array} \end{array} $$
(1)

where T, S, 𝜃, and σ stand for fuzzy triangular norm, fuzzy triangular conorm, T −rediduated implication and its dual, respectively.

For simplicity, we only use select fuzzy triangular conorm in the rest of paper.

Definition 2

[27] Given a kernel fuzzy approximation space < U,A,D,k >, let \(B \subseteq A\) be a subset of attributes. The kernel fuzzy positive region of D in term of B is defined as

$$ {PO{S_{B}^{S}}}(D)=\bigcup\limits_{i=1}^{m} \underline {k_{S}}d_{i}. $$
(2)

Definition 3

[27] Given a kernel fuzzy approximation space < U,A,D,k >, let \(B \subseteq A\) be a subset of attributes. The kernel fuzzy dependency function of D in term of B is defined as

$$ {\gamma^{S}_{B}}(D)=\frac{|\bigcup\limits_{i=1}^{m} \underline {k_{S}}d_{i}|}{|U|}. $$
(3)

Definition 4

[27] Given a kernel fuzzy approximation space < U,A,D,k >, let \(B \subseteq A\) be a subset of attributes. The significance of a feature f ∈ A − B relative to D under B is defined as

$$ SIG(f, B, D)=\gamma^{S}_{B \cup f}(D) - {\gamma^{S}_{B}}(D). $$
(4)

The significance reflects the approximation ability of kernel fuzzy equivalence class induced by conditional attributes with respect to the decision attribute.

4 The proposed algorithms

4.1 Kernelized fuzzy rough sets for hierarchical classification

There exist different categories of hierarchical classification learning, such as graph-based and tree-based. In this paper, we propose a kernelized fuzzy rough sets for tree-based hierarchical classification learning. For simplicity, Table 1 describes the symbols most commonly used in this paper. Given a tree-based hierarchical class structure kernel fuzzy approximation space < U,C,Dtree,k >, U is a non-empty set of samples, C is a set of condition attributes, Dtree is the decision attribute which divides the samples into subset {d1,d2,...,dm} (m is the number of the classes), and a kernel function k satisfying reflexive, symmetric, and Tcos-transitive. In these symbols, Dtree satisfies a pair (Dtree,≺), where ``≺” represents the ``IS-A” relationship, which is the subclass-of relationship with the following properties [31]:

  1. (1)

    Asymmetry: if di ≺ dj then dj⊀di for every di,dj ∈ Dtree;

  2. (2)

    Anti-reflexivity: di⊀di for every di ∈ Dtree;

  3. (3)

    Transitivity: if di ≺ dj and dj ≺ dk, then di ≺ dk for every di,dj,dk ∈ Dtree.

Table 1 Description of symbols
Full size table

Given the hierarchical class structure, there are several methods used to define the set of positive (same) and negative (different) classes for a target sample, as shown in Table 2. Compared with other strategies, sibling strategy based hierarchical class can reduce the search scope of the negative samples via using the pre-defined class hierarchy [52].

Table 2 Three strategies of positive and negative samples’ definitions
Full size table

In this paper, we adopt sibling strategy as the final strategy. For ∀x ∈ U, we have

$$ d_{i}(x)=\left\{ \begin{array}{ll} 0 &{x \in sib(d_{i});}\\ 1 &{x \in \{d_{i}\}.} \end{array} \right. $$
(5)

Definition 5

Given < U,C,Dtree,k >, ∀x ∈ U, let di be a class of samples labeled with i, the fuzzy lower and upper approximation operators with sibling strategy are respectively defined as

$$ \begin{array}{llll} \underline {k_{S}}_{sib}d_{i}(x)=\inf\limits_{y \in sib(d_{i})} (1-k(x, y));\\ \underline {k_{\theta}}_{sib}d_{i}(x)=\inf\limits_{y \in sib(d_{i})} \left( \sqrt{1-k^{2}(x, y)}\right);\\ {{k_{T}}_{sib}}d_{i}(x)=\sup\limits_{\frac{k}{y\in \{d_{i}\}}} (x, y);\\ {k_{\sigma}}_{sib}d_{i}(x)=\sup\limits_{y \in \{d_{i}\}}(1-\sqrt{1-{k}^{2}(x, y)}). \end{array} $$
(6)

Example 1

Considering the example data in Table 3, we have 12 samples and each sample is characterized by a condition attribute C. Dtree is the decision attribute which divides the samples into subset {d1,d2,d3,d4,d5,d6}. The tree structure of example data is shown in Fig. 1. Assume Gaussian kernel \(k(x, y)=exp(-\frac {{||x-y||}^{2}}{\sigma })\) is used to compute the lower approximation with sibling strategy, and the parameter σ is set as 0.2. For x3 with class d2, we have sib(d2) = {d3,d4}. Then, we can compute the lower approximation with the sibling strategy as follow:

$$ \begin{array}{@{}rcl@{}} \underline {k_{S}}_{sib}d_{2}(x_{3}) &=& \inf\limits_{y \in sib(d_{2})} (1-k(x_{3}, y)) = \inf\limits_{y \in \{d_{3}, d_{4}\}} (1-k(x_{3}, y))\\ &=& 1-exp(-\frac{-||x_{3}-x_{7}||}{0.2}) = 0.0695\\ \end{array} $$
Table 3 Example data
Full size table
Fig. 1
figure 1

Tree structure of example data

Full size image

Several properties of the kernelized fuzzy rough sets for hierarchical classification are discussed as follows.

Proposition 1

Given <U,C,Dtree,k >, let di be a class of samples labeled with i, ∀x ∈ U, we have

$$ \begin{array}{cc} \underline {k_{S}}_{sib}d_{i}(x) \geq \underline {k_{S}}d_{i}(x),\\ \underline {k_{\theta}}_{sib}d_{i}(x) \geq \underline {k_{\theta}}d_{i}(x). \end{array} $$
(7)

Proof

Suppose yi is the sample with class yi ∈ sib(di) such that \(\underline {k_{S}}_{sib}d_{i}(x)=1-k(x, y_{i})\). Suppose yj is the sample with class yj ∈ Dtree∖di such that \(\underline {k_{S}}d_{i}(x)=1-k(x, y_{j})\). Since \(sib(d_{i}) \subseteq D_{tree} \backslash d_{i}\), we have k(x,yi) ≤ k(x,yj). Therefore, \(\underline {k_{S}}_{sib}d_{i}(x) \geq \underline {k_{S}}d_{i}(x)\). Analogically, we can also obtain \(\underline {k_{\theta }}_{sib}d_{i}(x) \geq \underline {k_{\theta }}d_{i}(x)\). □

Proposition 2

Given < U,C,Dtree,k >, x ∈ U. If di is a class of samples labeled with i and ∀x ∈ U, we have

$$ \begin{array}{cc} {\overline{k_{T}}}_{sib}d_{i}(x) = \overline{k_{T}}d_{i}(x),\\ \overline{k_{\sigma}}_{sib}d_{i}(x) = \overline{k_{\sigma}}d_{i}(x). \end{array} $$
(8)

Proof

Since \(\overline {k_{T}}d_{i}(x)=\sup \limits _{y \in d_{i}} k(x, y)\) and \(\overline {k_{T}}_{sib}d_{i}(x)=\sup \limits _{y \in d_{i}} k(x, y)\). Therefore, \(\overline {k_{T}}_{sib}d_{i}(x) =\overline {k_{T}}d_{i}(x)\). Analogically, \(\overline {k_{\sigma }}_{sib}d_{i}(x) =\overline {k_{\sigma }}d_{i}(x)\). □

4.2 Kernelized fuzzy rough sets using sibling strategy based feature evaluation

As we know, the kernelized fuzzy rough sets theory is an effective tool for selective discriminative features, and feature evaluation is a main step in the process of feature selection.

Definition 6

Given < U,C,Dtree,k >, let \(B \subseteq C\) be a subset of attributes. Dtree = {d0,d1,d2,...,dm}, where d0 is the root of the tree and is not the real class, and U is divided into {d1,d2,...,dm} by the decision attribute, where m is the number of classes. The kernel fuzzy positive region of Dtree in term of B is defined as

$$ {PO{S_{B}^{S}}}_{sib}(D_{tree})=\bigcup_{i=1}^{m} \underline {k_{S}}_{sib}d_{i}. $$
(9)

Definition 7

Given < U,C,Dtree,k >, let \(B \subseteq C\) be a subset of attributes, and U is divided into {d1,d2,...,dm} by the decision attribute, where m is the number of classes. The quality of classification approximation is defined as

$$ {{\gamma^{S}_{B}}}_{sib}(D_{tree})=\frac{|\cup_{i=1}^{m} \underline {k_{S}}_{sib}d_{i}|}{|U|}. $$
(10)

As \(\underline {k_{S}}_{sib}d_{i}(x)=\inf \limits _{y \in sib(d_{i})}(1-k(x, y))\), we can get

$$ |\cup_{i=1}^{m} \underline {k_{S}}_{sib}d_{i}|=\sum\limits_{j=1}^{|U|}\sum\limits_{i=1}^{m} \underline {k_{S}}_{sib}d_{i}(x_{j}). $$
(11)

Let xj∉{di}, we have \(\underline {k_{S}}d_{i}(x_{j}) = 0\). We also have \(\underline {k_{S}}_{sib}d_{i}(x_{j}) = 0\) according to Proposition 1. Thus, we have

$$ \begin{array}{cccc} {\sum}_{j=1}^{|U|}{\sum}_{i=1}^{m} \underline {k_{S}}_{sib}d_{i}(x_{j}) &=& {\sum}_{j=1}^{|U|}\underline {k_{S}}_{sib}d(x_{j})\\ &=& {\sum}_{j=1}^{|U|}\inf\limits_{x_{j} \in \{d\}, y \in sib(d)}(1-k(x_{j}, y)), \end{array} $$
(12)

where d is the class label of xj.

The coefficient of classification quality manifests the approximation ability of the approximation space, or the ability that the decision attribution is defined by the granulated space, contained in feature subset [27]. The coefficient named the dependency between decision attribute and condition attribute is able to evaluate the condition attributes with degree \({{\gamma ^{S}_{B}}}_{sib}(D_{tree})\).

figure f

4.3 Online streaming feature selection for large-scale hierarchical classification via kernelized fuzzy rough sets

In this section, we propose a framework of online streaming feature selection for large-scale hierarchical classification learning. This framework consists of two-phase: online important feature selection and online redundant feature update. The details of the proposed method is shown in the following sections.

4.3.1 Online important feature selection

In order to measure the significance of feature relative to the decision attribute under the selected features, the kernel fuzzy dependency with respect to Dtree can be employed. Because the dependency reflects the discernibility of feature, and the greater the dependency is, the greater the recognition power of feature has. The significance of feature in a tree-based hierarchical class structure using kernel fuzzy approximation space < U,C,Dtree,k >, can be defined as follow.

Definition 8

Given the decision attribute Dtree, St− 1 is the selected feature subset at time t − 1, and Ft is a new arrived feature at time t. Therefore, the significance degree of feature Ft can be defined as

$$ SD(F_{t}, S_{t-1}, D_{tree})=\frac{|{\gamma^{S}_{S_{t-1} \cup F_{t}}}_{sib}(D_{tree})-{\gamma^{S}_{S_{t-1}}}_{sib}(D_{tree})|}{|{\gamma^{S}_{S_{t-1}}}_{sib}(D_{tree})|}. $$
(13)

As \({\gamma ^{S}_{S_{t-1}}}_{sib}(D_{tree}) \in [0, 1]\), and \({\gamma ^{S}_{S_{t-1} \cup F_{t}}}_{sib}(D_{tree}) \geq {\gamma ^{S}_{S_{t-1}}}_{sib}(D_{tree})\), we have SD(Ft,St− 1,Dtree) ∈ [0,1]. We say that feature Ft is superfluous relative to the currently selected features if SD(Ft,St− 1,Dtree) = 0; Otherwise, Ft has a positive impact on the selected features St− 1.

Definition 9

Given the decision attribute Dtree, St is the selected feature subset at time t. For each feature Fi ∈ St, we can calculate the dependency between Fi and Dtree, and the mean value of all dependency values between each feature Fi and the decision attribute Dtree can be defined as

$$ \Re(S, D_{tree})=\frac{{\sum}_{F_{i} \in S_{t}}{\gamma^{S}_{S_{t}}}_{sib}(D_{tree})}{|S|}. $$
(14)

Definition 10

Assume St− 1 is the selected feature subset at time t − 1, Ft is a new feature at time t. If \({\gamma ^{S}_{F_{t}}}_{sib}(D_{tree})\ge \Re (S_{t-1}, D_{tree})\), Ft is identified as an important feature with respect to the decision attribute Dtree; Otherwise, Ft is abandoned as a nonsignificant feature.

From Definitions 8 and 10, the local optimum is an important analysis process, i.e., it is meaningful for the arrival sequence of features to choose the new feature. What is more, it is hard to get a satisfied condition in the following features if there is a high discriminative capacity in the former arrived features. In addition, Ft is redundant but links with the currently selected features. Besides, Ft can not be identified worthless since it would be much more precious compared with its corresponding superfluous features. Accordingly, a further online redundancy updation is necessary.

4.3.2 Online redundant feature updation

In this section, online redundant feature updation can get an optimal feature subset by reevaluating the newly arrived feature Ft. Ft is considered as an superfluous feature in the online important feature selection period. Reevaluating feature can be completed in two steps: (1) selecting the redundant feature within new features, i.e., redundancy recognition, and (2)ensuring the preserved features, i.e., redundancy updation. In order to clearly filter out superfluous features, pairwise comparisons are used to online calculate the correlations between features and the decision attribute.

Definition 11 (Redundancy recognition)

Assume St− 1 is the selected feature subset at time t − 1, and an important threshold δ is given. If ∃Fk ∈ St− 1 such that SD(Fi,Fk,Dtree) ≤ δ(0 ≤ δ ≤ 1), it proves that adding Fi alone to Fk does not enhance the predictive capability of Fk. That is, Fk is redundant with Fi.

Definition 12 (Redundancy updation)

Assume St− 1 is the selected feature subset at time t − 1, Fk ∈ St− 1, Ft is a new feature at time t, and an important threshold δ is given. If SD(Ft,Fk,Dtree) ≤ δ(0 ≤ δ ≤ 1) holds, then Ft should be added into St− 1 if \({\gamma ^{S}_{F_{t}}}_{sib}(D_{tree}) \ge {\gamma ^{S}_{F_{k}}}_{sib}(D_{tree})\); Otherwise, Fk should be preserved if \({\gamma ^{S}_{F_{t}}}_{sib}(D_{tree}) \leq {\gamma ^{S}_{F_{k}}}_{sib}(D_{tree})\).

4.4 Kernelized Fuzzy rough sets based online hierarchical streaming feature selection(KFOHFS)

To illustrate the process of online hierarchical streaming feature selection, a flowchart of online streaming feature selection framework is given in Fig. 2. Under this framework, we propose the KFOHFS algorithm in detail, as shown in Algorithm 2.

Fig. 2
figure 2

The process of online hierarchical streaming feature selection

Full size image
figure g

5 Experimental analysis

In this section, we first describe the information of data sets, evaluation measures, and comparative methods respectively. Then, the influence of parameter δ is reported. Moreover, we compare the performance of four evaluation metrics among 6 algorithms to verify the effectiveness of the proposed method. Finally, statistical analysis and time complexity analysis are adopted to further explore the performance analysis.

5.1 Data sets and experimental settings

5.1.1 Data sets

There are six data sets in the experiments, and their basic information is listed in Table 4. For these data sets, AWAphog [33] has 10 classes and 9,607 samples, which is collected from Animals. Bridges [10] is from the University of Colifornia-Irvine (UCI) library. Cifar [32] is labeled subsets of the 80 million tiny image data sets. VOC [20] provides the vision and machine learning communities with a standard data set of images and annotation as well as standard evaluation procedures. DD [16] is a protein data set, which has 27 real classes and four major structural classes. F194 [47] is also a protein data set, which has 194 classes, which are all leaf nodes.

Table 4 Dataset description
Full size table

5.1.2 Hierarchical classification evaluation measures

To evaluate the performance of the proposed algorithm, three additional hierarchical classification evaluation measures, i.e., Tree Induced Error (TIE) [13], Hierarchical-F1[11] and Lowest Common Ancestor-F1 (LCA − F1) [43], are introduced to describe the degree of misclassification in hierarchical structure, respectively.

Let D and \(\hat {D}\) denote true classes and predicted classes of instances respectively. Then, the augmentation of D and \(\hat {D}\) is defined as

$$ D_{aug}=D \cup anc(D), \hat{D}_{aug}=\hat{D} \cup anc(\hat{D}), $$
(15)

and the lowest common ancestor augmentation of D and \(\hat {D}\) is defined as

$$ D^{LCA}_{aug} = D \cup LCA(D,\hat{D}), \hat{D}^{LCA}_{aug} = \hat{D} \cup LCA(D,\hat{D}). $$
(16)

Hierarchical Precision and Hierarchical Recall are defined as

$$ P_{H}=\frac{|\hat{D}_{aug} \cap D_{aug}|}{|\hat{D}_{aug}|}, R_{H}=\frac{|\hat{D}_{aug} \cap D_{aug}|}{|D_{aug}|}. $$
(17)

Lowest Common Ancestor Hierarchical Precision and Lowest Common Ancestor Hierarchical Recall are defined as

$$ P_{LCAH}=\frac{|\hat{D}^{LCA}_{aug} \cap D^{LCA}_{aug}|}{|\hat{D}^{LCA}_{aug}|}, R_{LCAH}=\frac{|\hat{D}^{LCA}_{aug} \cap D^{LCA}_{aug}|}{|D^{LCA}_{aug}|}. $$
(18)

where |⋅| denotes the count of elements.

The TIE is computed by predicting class \(\hat {D_{i}}\) when the true classes is Di

$$ TIE(D, \hat{D})=\frac{1}{|D|}{\sum}_{i=1}^{|D|} |E_{H}(D_{i}, \hat{D}_{i})|, $$
(19)

where \(E_{H}(D_{i}, \hat {D}_{i})\) is the set of edges along the path from Di to \(\hat {D}_{i}\) in the hierarchy, and |⋅| denotes the count of elements.

The Hierachical − F1 is the F1-measure of hierarchical precision and recall, and defined as

$$ Hierachical-F_{1}=\frac{2 \cdot P_{H} \cdot R_{H}}{P_{H} + R_{H}}. $$
(20)

The LCA − F1 is the F1-measure of lowest common ancestor hierarchical precision and recall, and defined as

$$ LCA-F_{1}=\frac{2 \cdot P_{LCAH} \cdot R_{LCAH}}{P_{LCAH} + R_{LCAH}}. $$
(21)

5.1.3 Experimental settings

To explain the effectiveness of the proposed algorithm, five state-of-the-art online streaming feature selection methods, including OFS-Density [57], OFS-A3M [54], Fast-OSFS [48], OSFS [48], and SAOLA [49] are selected as baselines. For OSFS, Fast-OSFS, and SAOLA, the significance level α is set as 0.01, as suggested in the literature. For KFOHFS, the parameter δ is acquiescently set to 0.01% and more details refer to Section 5.2. Besides, the basic classifier LSVM is used to evaluate the classification performance of all feature selection algorithms. Ultimately, Predictive Accuracy, LCA − F1, Hierachical − F1, and TIE are selected as criteria to evaluate the performance of feature selection. Since the four criteria come from different evaluate viewpoints, and few algorithms are superior to the algorithms based on the above four criteria.

5.2 The influence of δ

In this section, we will analyze the influence of δ in KFOHFS. Four values (0.01%, 0.05%, 0.1% and 0.5%) of δ and the absolutely equivalent constraint (δ = 0) are selected as compared objects. Fig. 3 demonstrates the experimental results of five different δ values (0, 0.01%, 0.05%, 0.1% and 0.5%) on these data sets (AWAphog, DD, VOC, F194), in which, Fig. 3(e) and Fig. 3(f) represent the running time and the mean of selected features on these data sets, respectively.

Fig. 3
figure 3

Comparison of KFOHFS (control algorithm) with different values δ

Full size image

From Fig. 3, we have the following observations: (1) There is no significant difference between different values of δ. In which, δ = 0 and δ = 0.01% get the best performance in three data sets (AWAphog, DD, F194), and δ = 0.01% gets the best performance in all data sets; (2) With the augment of values of δ, the corresponding running time fleetly increases in two data sets (DD, F194); (3) For the number of selected features, δ = 0 selects more features than others, which denotes some redundant features are caused by the exactly equal constraint.

In summary, the exactly equal restriction is able to eliminate redundant features and improve predictive accuracy. Therefore, in the following experiments, we set δ = 0.01%.

5.3 Performance analysis on evaluation measures

In this section, we group experiments into two parts: (1) We make comparison on the performance of four evaluation metrics (Predictive Accuracy, LCA − F1, Hierachical − F1, and TIE) among OFS-Density, OFS-A3M, Fast-OSFS, OSFS, SAOLA, and KFOHFS; (2) Based on the statistical analysis in the comparison algorithms, we analyze performance in a systematic way.

Tables 5-8 show the performance of OFS-Density, OFS-A3M, Fast-OSFS, OSFS, SAOLA, and KFOHFS with respect to four evaluation metrics. Among these tables, bold font embodies the optimum performance of each data set, italics shows the average performance of each algorithm on all data sets, ↑ manifests the larger the better, and ↓ demonstrates the smaller the better, respectively. The experiments show that, in all four evaluation measures, KFOHFS dramatically outperforms other online streaming feature selection algorithms for all datasets.

Table 5 Predictive accuracy using the LSVM classifier
Full size table
Table 6 LCA − F1 score using the LSVM classifier (↑)
Full size table
Table 7 Hierachical − F1 score using the LSVM classifier (↑)
Full size table
Table 8 TIE score using the LSVM classifier (↓)
Full size table

The Friedman test [21] and Bonferroni-Dunn test [18] are adopted to further explore the performance analysis over the six feature selection algorithms. Given k comparing algorithms and N data sets, the average rank of algorithm j on all data sets is \(R_{j}=\frac {1}{N}{\sum }_{i=1}^{N}{r^{j}_{i}}\), where \({r_{i}^{j}}\) is the rank of the j-th algorithm on the i-th data set. Under the null-hypothesis, the Friedman statistic following a Fisher distribution with (k − 1) and (k − 1)(N − 1) degrees of freedom can be defined as

$$ \begin{array}{@{}rcl@{}} &&F_{F}=\frac{(N-1){{\chi^{2}_{F}}}}{N(k-1)-{\chi^{2}_{F}}},\\ &&where \quad {\chi^{2}_{F}}=\frac{12N}{k(k+1)}\left( \sum\limits_{i=1}^{k}{R^{2}_{i}}-\frac{k(k+1)^{2}}{4}\right) \end{array} $$
(22)

Table 9 presents the Friedman statistic FF on different evaluation metrics and the corresponding critical values. In accordance with Table 9, the null hypothesis of ``equal” performance among all algorithms is obviously rejected on all different evaluation measures at significance level α = 0.10. Afterwards, we select given post-hoc tests, such as the Bonferroni-Dunn test, to further analyze the related performance among the comparing algorithms. Here, the difference between the average ranks of KFOHFS and one baseline is compared with the following critical difference (CD):

Table 9 Summary of the Friedman statistics FF(k = 6,N = 6) and the critical value on different evaluation measures(k : comparing algorithms; N : data sets)
Full size table
$$ CD_{\alpha}=q_{\alpha}\sqrt{\frac{k(k+1)}{6N}}. $$
(23)

Hence, we have qα = 2.3260 at significance level α = 0.10, and thus CD= 2.5124 (k = 6,N = 6).

To visually display the relative performance of KFOHFS and other algorithms, Fig. 4 clarifies the CD diagram on different evaluation metrics, where the average ranks of each comparing algorithm are signed along the axis. From Fig. 4, we can observe that KFOHFS performs obviously better than OFS-Density, SAOLA, and OSFS on all evaluation measures. In conclusion, KFOHFS is not statistically better than OFS-A3M and Fast-OSFS, but it outperforms all competing algorithms on all data sets, due to KFOHFS utilizes the hierarchical class information.

Fig. 4
figure 4

Comparison of KFOHFS (control algorithm) against other comparing algorithms with the Bonferroni-Dunn test

Full size image

5.4 Time complexity analysis

To illustrate the efficiency of each algorithm, we compare the time complexity of each algorithm (OFS-Density, OFS-A3M, Fast-OSFS, OSFS, SAOLA) in this section. As we know, the dependency between features is taken as the main time complexity of KFOHFS. According to Section 4.2, the time complexity of SSFE is O(|U|2 ⋅ log|U|). |C| is the total number of features. Thus, the time complexity of KFOHFS is O(|C|2 ⋅|U|2 ⋅ log|U|). The time complexity of both OFS-Density and OFS-A3M is \(O(|C|^{2} \cdot {|U|}^{2} \cdot \log |U|)\), where |C| is the total number of features and |U| is the number of samples. The time complexity of OSFS is O(|C|2 ⋅ k|C|), where k|C| is all subsets of size and is less than or equal to k(1 ≤ k ≤|C|). The worst time complexity of Fast-OSFS is O(|CR|⋅|C|⋅ k|C|), where |CR| is the number of all relevant features in |C|. The time complexity of SAOLA is O(|C|2).

From the above theoretical analysis of time complexity, it can be observed that the time complexity of OFS-Density, OFS-A3M, and KFOHFS is equal. Compared with other comparison algorithms, the influence of the total number of samples should be considered in the calculation process, which need more calculation time. Therefore, the time complexity of Fast-OSFS, OSFS and SAOLA is relatively optimal.

6 Conclusions

In this paper, we presented a kernelized fuzzy rough sets based online streaming feature selection for large-scale hierarchical classification learning. We first used sibling nodes as the nearest samples from different classes to granulate all instances, and define a new dependency function to evaluate the features. Then, two phases were divided in the proposed online hierarchical streaming feature selection, i.e., online important feature selection and online redundant feature updation. Specially, KFOHFS did not need the domain knowledge before learning, and measured the fuzzy relation between samples effectively. In addition, KFOHFS took advantage of hierarchical class structure for classification learning. Compared with the other five state-of-the-art online streaming feature selection algorithms, KFOHFS achieves competitive performance against all competitors in all flat and hierarchical evaluations. However, the current implementation of the algorithm is limited to a tree structure of class labels. In the future, we will design online streaming feature selection algorithms for general graph structures.