Chao Pan

Wenxian Peng

Huilong Duan

Ning Deng
email: zju.dengning@gmail.com

Complex Proteomes Analysis Using Label-Free Mass Spectrometry-Based Quantitative Approach Coupled with Biomedical Knowledge

Keywords: Complex Proteomes, Label-free Quantitation, Mass Spectrometry, Biomedical Knowledge

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Relative quantitative proteomics is aiming at quantifying and detecting differential protein expression between various biological samples of interest, such as biomarkers discovery, signalling pathway or drug discovery [START_REF] Zhao | Quantitative proteomics and biomarker discovery in human cancer[END_REF][START_REF] Dong | Quantitative mass spectrometry identifies insulin signaling targets in C. elegans[END_REF][START_REF] Lill | Proteomic tools for quantitation by mass spectrometry[END_REF] . Generally, quantitative proteomics can be separated into two major approaches: the use of stable isotope labelling and label-free techniques [START_REF] Schulze | Quantitation in mass-spectrometry-based proteomics[END_REF] . Particularly, label-free approaches, which directly use MS feature of abundance such as spectral or peptide count or chromatographic peak area, is a reliable, versatile, and cost effective alternative to labelled quantitation [START_REF] Zhu | Mass spectrometry-based label-free quantitative proteomics[END_REF] . However, issues arise with peptides that are shared between multiple proteins [START_REF] Zhang | Refinements to label free proteome quantitation: how to deal with peptides shared by multiple proteins[END_REF] . Which protein did they originate from and how should these shared peptides be used in a quantitative proteomics workflow [START_REF] Zhang | Refinements to label free proteome quantitation: how to deal with peptides shared by multiple proteins[END_REF] ? In addition, post-translational modifications, isoforms, and splice variants are not captured by the mere analysis of transcript abundances. Protein mixtures today can routinely be characterized in terms of proteins present in the sample, but in order to allow biological interpretation, quantitative analyses are necessary [START_REF] Schulze | Quantitation in mass-spectrometry-based proteomics[END_REF] .

In this paper, we used Normalized Spectral Abundance Factor (NSAF) based peptide count as starting point for our analysis [START_REF] Zybailov | Statistical Analysis of Membrane Proteome Expression Changes in Saccharomyces c erevisiae[J][END_REF] and proposed a new method for shared peptides to accurately evaluate abundance of Isoforms [START_REF] Zhang | Refinements to label free proteome quantitation: how to deal with peptides shared by multiple proteins[END_REF] . Label-free quantitative approaches can accurately describe abundance of complex proteins, and quantitative proteomics is not only a way for data processing, but a method for comprehending and explaining functions and relationships of proteins. Therefore, large-scale functional annotations were extracted from biomedical knowledge by g:Profiler [START_REF] Reimand | Profiler-a web-based toolset for functional profiling of gene lists from large-scale experiments[END_REF] and were assigned to 12 functional clusters due to the biochemical properties of mitochondrial proteins. We found that the new strategy with shared peptides overcame inaccurate and overestimated results for low-abundant isoforms to improve accuracy, and analysis of biomedical knowledge based quantitative proteomics contributed to discovering biomarkers and targets.

Data and Methods

Data acquisition

All MS/MS spectral we used were from the preliminary work of authors [START_REF] Zhang | Systematic characterization of the murine mitochondrial proteome using functionally validated cardiac mitochondria[END_REF][START_REF] Zhang | Altered proteome biology of cardiac mitochondria under stress conditions[J][END_REF][START_REF] Zhang | Mitochondrial proteome design: From molecular identity to pathophysiological regulation[J][END_REF] . Mitochondria were treated with 0.5% DDM to extract membrane proteins, separated by SDS-PAGE followed by CBB G250 staining. Bands were sequentially cut from the continuum of the gel lane and were labelled to obtain much more accurate results in the peptide shared quantitation. Proteins were digested with trypsin, and peptides were analysed by LTQ-Orbitrap.

Data preparation

All MS/MS spectra including mouse heart mitochondrial dataset, mouse liver mitochondrial dataset and human heart mitochondrial dataset were searched against the IPI mouse database (version 3.47) and IPI human database (version 3.68) [START_REF] Kersey | The International Protein Index: an integrated database for proteomics experiments[END_REF] using the pFind software kit (version 2.6) [START_REF] Wang | pFind 2.0: a software package for peptide and protein identification via tandem mass spectrometry[END_REF] . Detailed search parameters were performed using as follows: partial tryptic digest allowing two missed cleavages; fixed modification of cysteine with carbamidomethylation (57.021 Da) and variable modification of methionine with oxidation (15.995 Da), the precursor and fragment mass tolerances were set up at 1.5 and 0.5 Da, respectively. Peptides matching the following criteria were used for protein identification: DeltaCN≥0.1; FDR≤1.0%; peptide mass was 600.0~6000.0; peptide length was 6~60.

Label free quantitative algorithm

NSAF which was described by Old et al [START_REF] Zybailov | Statistical Analysis of Membrane Proteome Expression Changes in Saccharomyces c erevisiae[J][END_REF] gained popularity because it used protein length to rectify spectral counts to improve accuracy. We used the normalized spectral abundance factor (NSAF) based peptide count for quantitative proteomics. All peptide spectral counts were summed for each identified protein, and then divided by protein length, generating the values of Spectral Abundance Factor (SAF); the SAF value of each identified subunit was then normalized against the sum of all SAFs within an individual biological sample, resulting in the Normalized SAF (NSAF) value; all NSAF values were then calculated separately for all biological samples. The average value of NSAF for each identified protein was used for further quantitative and biological analyses. The normalization process, as a routine operation to eliminate systematic errors, can only be applied in some certain circumstances, for instance, when comparing relative changes between two complex mixture samples [START_REF] Wu | NSI and NSMT: usages of MS/MS fragment ion intensity for sensitive differential proteome detection and accurate protein fold change calculation in relative label-free proteome quantification[END_REF] . Meanwhile, we proposed a new method with shared peptides to explore how to accurately estimate abundance of isoforms for complex proteomes. We used distinct peptides as a proportional factor and allocated shared peptides to isoforms. Corresponding with NSAF, we similarly used protein length to rectify distinct peptides and obtained the proportional factor by normalizing distinct peptides, then allocated shared peptides to isoforms to obtain the final spectral count.

      1 / / J s N J i i Sc L NSAF Sc L    (1)
    band 1 1 cu / = / B band band band n band k k k S L Sc Scu Scs R Scu L        , and R (2)
In first equation, where Sc was the spectral count for protein J and L was the length of protein J, N was the total proteins; in the second equation, B was the total bands, Scu was the count of distinct peptide, Scs was the count of shared peptide, R was the proportional factor.

Functional analysis

g:Profiler is a web-based toolset for functional profiling of gene lists from large-scale experiments [START_REF] Reimand | Profiler-a web-based toolset for functional profiling of gene lists from large-scale experiments[END_REF] . It adopts the Benjamin-Hochberg statistic method to control false discovery rate (FDR) [START_REF] Benjamini | The control of the false discovery rate in multiple testing under dependency[J][END_REF] to improve accuracy. According to these properties, g:Profiler was used to obtain functional annotation of complex proteomes in large-scale experiments.

We extracted gene name of each protein from IPI fasta database, and analysed these files including gene names by g:Profiler, then outcomes were analysed by inhouse software toolkit to obtain functional annotation of complex proteomes. In this paper, we used pValue as a key factor to filter functional annotation. For the protein with multiple functions, the functional annotation corresponding to the smallest pValue was filtered. According to the biochemical properties of mitochondrial proteins, all mitochondrial proteins were assigned to 12 functional clusters.

Results and Discussion

In order to completely test the above methods, we selected mitochondrial proteins for analysis. Mitochondria have received extensive attention due to their importance in cellular function and known causative role in diseases. Mammalian mitochondria are double-membrane organelles, serving as the metabolic power houses of eukaryotic cells [START_REF] Mcdonald | Mitochondrial proteomics[J][END_REF][START_REF] Weiss | Role of the mitochondrial permeability transition in myocardial disease[J][END_REF][START_REF] Honda | Mitochondria and ischemia/reperfusion injury[J][END_REF] . In this paper, mouse heart mitochondrial dataset, mouse liver mitochondrial dataset and human heart mitochondrial dataset were selected to obtain all MS/MS spectra, then each group was analysed by NSAF and its optimization algorithm. We found that the new strategy with shared peptides overcame inaccurate and overestimated results for low-abundant isoforms. Meanwhile, functional annotations of mitochondrial proteins in large-scale experiments were assigned to 12 functional clusters due to the biochemical properties of mitochondrial proteins. The work flow was shown as Figure 1.

Assessment of label -free quantitative algorithm

Spectral count, defined as the total number of spectra identified for a protein, has recently gained acceptance, therefore we evaluated the label-free approach based spectral count, especially the new strategy with shared peptides. We selected a group of mouse heart mitochondrial proteins to obtain MS/MS spectra by LTQ-Oribitrap, and this group of proteins were repeated three times, named as Group A, Group B, Group C. All proteins were searched by pFind toolkit to identify total counts of proteins and the counts of proteins with shared peptides. Then each group was quantified by NSAF and the new method, and quantitative results were sorted in descending order. We found that proteins with shared peptide were accounted twenty five to forty percent of total proteins, as table 1 shows; especially those proteins which rank have dramatic changes nearly had shared peptides. Importantly, we found that such identified proteins even came from a same family, such as proteins belonging to acyl-CoA dehydrogenase family. Proteins in the family play an important role in life event due to their biochemical properties of fatty acid metabolism and lipid metabolism. As table 2 shows, proteins with shared peptides reached 90%. Ranking of these proteins in the family generally ascended after approaching by the new strategy. Additionally, if all peptides of a protein were shared, the quantitative results were extremely different, such as IPI00331251. Therefore, we concluded that normalized processes we designed eliminated systematic errors and should be considered when dealing with MS/MS spectra. Simultaneously, new strategy with shared peptide overcame inaccurate and overestimated results for low-abundant isoforms.

3.2.Functional annotation of identified proteins

According to the biochemical properties of mitochondrial proteins, all mitochondrial proteins were assigned to 12 functional clusters including apoptosis, DNA/RNA/protein synthesis, metabolism, oxidative phosphorylation, protein binding/folding, proteolysis, redox, signal transduction, structure, transport, cell adhesion and cell cycle. As table 3 shows, metabolic proteins have highest abundance in mouse liver mitochondrial dataset, while oxidative phosphorylation proteins show highest abundance in cardiac mitochondrial dataset. This explains that liver is important in metabolic process including nutrients synthesis, transformation and decomposition, however, heart promotes blood flowing to provide adequate blood to the organs or tissues, supplies oxygen or various nutrients and takes metabolic products away. Functional clustering for complex proteomes contributes to comprehending physiological and pathological characteristics of mitochondrial proteins.

Biochemical properties of identified proteins

We analysed the biochemical proprieties of identified proteins including: MW (in kDa) and IEF point (pI) based NSAF value to discovery some new regularity using heat map. The heat map generated from software which was designed by us, as figure 2 shows. We found that three groups of proteins did not express much more differences, and most of abundant proteins with low molecular weight fall into the area of high pI value.

Conclusions

The method using peptide count can accurately describe abundance of proteins, in addition, the strategy dealing with shared peptides can estimate relative abundance of isoforms for complex proteomes and overcame inaccurate and overestimated results for low-abundant isoforms. According to the biochemical properties of mitochondrial proteins, large-scale functional annotations which were extracted from biomedical knowledge were assigned to 12 functional clusters. We provided a new method based on quantitative analysis to explain functions and relationships of complex proteomes and contribute to bioinformatics research including quantitative expression, difference comparison and diseased proteomics. Even though, NSAF could achieve the best precision using spectral as abundant features of isoforms, it seriously underestimate the actual fold change [START_REF] Wu | NSI and NSMT: usages of MS/MS fragment ion intensity for sensitive differential proteome detection and accurate protein fold change calculation in relative label-free proteome quantification[END_REF] .Therefore, in order to precisely estimate quantitative results of low-abundant isoforms and further explore the deep relationship between peptides and MS/MS spectral, developing a new method becomes extremely important for complex proteomes.

Fig 1 .

 1 Fig 1. Workflow of label free quantitative proteomics with biomedical knowledge

Table 1

 1 Analysis of proteins with shared peptides in sample

	Sample	Total Count of Proteins	Total Count of Proteins with Shared Peptides		Rate (%)
	Group A	1589		614			38.64
	Group B	1569		593			37.79
	Group C	1397		362			25.91
		Table 2 Analysis of proteins in acyl-CoA dehydrogenase family
	Protein ID	Gene Symbol	Total Count of Peptides	Total Count of Shared Peptides	Rate (%)	Rank (NSAF Only)	Rank (with Shared Peptides)
	IPI00119203	Acadvl	3033	3000	98.91	8	8
	IPI00119114	Acadl	1449	1419	97.93	11	12
	IPI00134961	Acadm	1150	1131	98.35	51	39
	IPI00116591	Acads	705	692	98.16	63	63
	IPI00274222	Acad8	200	188	94.00	140	100
	IPI00331251	Acads	180	180	100	157	1444
	IPI00331710	Acad9	155	144	92.90	182	111
	IPI00119842	Acadsb	113	105	92.92	228	165
	IPI00170013	Acad10	85	80	94.12	395	289

Table 3

 3 Analysis of functional clustering for mitochondrial proteins

	Functional Clusters	% of Total Abundance (Mouse Liver)	% of Total Abundance (Mouse Heart)	% of Total Abundance (Human Heart)
	OXPHOS	19.13	37.20	28.62
	Metabolism	46.27	34.86	36.35
	Transport	7.66	8.39	6.79
	Apoptosis	1.82	2.56	5.70
	Redox	6.82	1.94	3.94
	Binding	4.20	3.47	7.40
	Signaling	1.83	2.95	1.82
	Biosynthesis	4.35	2.91	3.44
	Structure	0.73	0.31	3.49
	Proteolysis	1.22	0.74	0.37
	Cell Adhesion	0.17	0.03	0.00
	Cell Cycle	0.03	0.06	0.01
	Unknown	5.76	2.40	1.89

Acknowledgements

This work was supported by the National High Technology Research and Development Programs of China (863 Programs, no. 2012AA02A601, no. 2012AA02A602, no. 2012AA020201), the National Science and Technology Major Project of China (No. 2013ZX03005012), and the National Natural Science Foundation of China, no. 31100592.


Yuanren Song

Zhijun Li

Online Migration Solver based on Instructions Statistics Algorithm for deciding offload function set on mobile cloud system

Keywords: Mobile Cloud, migrate, offload

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

With the development of smartphone and the growing number of the users. Lots of sensors are deployed on the mobile devices. Of course, more applications will acquire the data, analyse the data and use the data. But it will cost much computing resources which are tight on the mobile devices too. Another problem is power shortage. In MAUI system, the battery dried up in 2 hours by downloading 100kb file repeatedly.

There are several systems based on migrating the whole virtual machine. MAUI is based on Microsoft .Net Framework. The system propose a method to partition the program by functions. Then profile the energy consumption for each function. At last, it uses a solver to decide which part of functions needs to be offloaded to Server. The system is released on CLR, which can save 90% energy when running face recognition programme, and has a speed up of 9.5x. Comparing to MAUI, Clonecloud system doesn't need any annotations when programming. It have a speed-up of 14.05x when running virus scan program.

Joule Benchmark style system model the energy consumption. The model indicates energy consumption is in proportional to the CPU cycles. So in the paper, we use CPU cycles to calculate the running time, and use running time as the optimization objective. We propose an algorithm to solve such a problem.

In Section 2, we give the definition of the problem and give an algorithm to solve the problem. In Section 3, we provides some details when we implement the system. In Section 4, three groups of experiments are conducted to evaluate the system performance.

Function Migration Problem

Definition

The problem is based on a FIT (Function Invoking Tree). FIT is used to reflect the construction of the program. Each function can form a node in FIT. When Function A calls Function B, B will be one of A's children. When a function is invoked by different function, there will be several node in FIT to present the function in different context. Here we import (V, E) to present the FIT. V means the nodes for function, and E= {u, v} means Function u called Function v. We also needs some other symbols to complete the model. Ii presents where should the Function i be run. Ii =0 means it will be run on mobile device, and Ii =1 means it will be run on cloud. The instruction length of Function i is presents by Fi. The number of called times is presents by Ri. And SL and SR represents the CPU speed of mobile device and cloud server. Δi presents the time used to synchronize the memory between the mobile device and the cloud. The variables Fi, Ri, SL, SR, Δi, all can be measured or counted by statistics. Then we use the running time migration can save as the optimization objective, and the problem is as above:

  ( , ) maximize subject to 0, 1 i i i i i i j j j i V i j E L R i R F R F I II R S S i N I                    (1)

Algorithm

Comparing to former problem, energy is replaced by time, so there's no constraint in this problem. So it isn't a 0-1 ILP strictly, and it's a P problem. Here we propose a dynamic programming algorithm, which will cost O(|V|) time to calculate the optimal solution. In the algorithm, there's a weight w(T, IT) for each node T. It means the time migration can save when node T chooses IT as the schedule. The weight equals the optimization objective, and the proof will be shown in next chapter.

The algorithm start from the root node of the FIT. And the algorithm can be divided into 2 parts: calculate weight for each node, and decide whether to offload for each node. The algorithm is as below:

      ( ,0) max ,0 , ,1 ( , ) R i w T CalcWeight i CalcWeight i i R T T i E       (2) End if If node T is native function then w(T, 1) := -∞ Else       1 1 ( ,1) : max ,0 , ,1 ( , ) T T L R R i w T w i w i F i R S S T i E               (3)

End if End if end

Proof

Theory 1. The root node weight calculated by the algorithm is equal to the optimization objective.

Proof: The root node weight is decided by max function in the algorithm. Then the max function can be replaced by I and 1-I. So the root weight w can be written:

                                        , , , , ,1 1 ,0 1 1 ,1 1 ,0 1 1 , 1 1 , 0 ,1 1 root root root root i root i i i i root root root i E root L R i root i i i i root i E root j root i j root i root i E i j E root w I w root I I w root R I I w i Iw i I I F R S S R I I w i I I w i R R I I I w i I I R                                                                                 ,1 1 ,0 1 1 , 0 1 , 1 1 1 , 1 1 1 1 1 ,0 1 1 1 ,0 1 1 1 1 1 1 j root i j root j i root i i root j j i j root i j root root root L R root i j j root i j j root i
I                                                           , , , , 1 1 1 1 1 ,1 1 ,0 i i i root i oot i i root i E root i E root root L R L R j j j i j j root i E i j E root R R I F I I F R S S R S S R I w i I w i I I R                                  (4)   , 1 1 1 1 i i root root i root i E root L R L R R I F I F S S R S S                      
Expand all the node in FIT and let R root = 1, we'll get:

  , 1 1 i i i i j j i V i j E L R w IRF I I S S i V                    (5)
Theory 2. This problem satisfies dynamic programming property.

Proof: For one node i and one of its son Node j. Let the weight for i be w i which includes largest weight w j , but w i isn't the largest weight for i. Let the largest weight for i be w i ', and it includes Node j's solution w j '. Then we have f i ' = f i -f j + f j ' < f i , which is contradict with that fi' is the largest weight for i.

System Implements

The system is realized based on COMET which is published by 2013. Comparing to the Clonecloud system, COMET uses DSM (Distributed Shared Memory) instead of migrating whole stack. So all the threads can access the same block memory simultaneous in a synchronized way. And more than one threads can be migrated to the cloud server at the same time.

COMET is an open source project which modifies the Dalvik Virtual Machine used in Android system. We save the part of network transportation and DSM synchronization, and add our features on it.

First we run a group of test program to get the real instructions in the program and measure the running time to model the CPU speed on both mobile devices and cloud server. Then we start to run our algorithm to calculate the set of function to offload. When calculating the function set, we need to know the length of instructions F for each function. We just count the running time of the function, then use the mobile speed to evaluate the length of instructions. Another variables Δ should be measured during migration. For each function we set Δ be the RTT between mobile devices and cloud server. As the migration done, we update Δ for each migrated function.

For native method, we use the dictionary provided by COMET to judge which to offload or not. The offloadable methods include some math library, thread library and so on. So this part of method can be run on the cloud server, which can save lots of work for the mobile device.

In COMET, it uses migration code to trigger migration. The code is handled by a method, and when the thread is migrated back it calls another such method to handle the migration code. So the original method will never return (Fig 1a). With more times of migration, the stack grows. We add the function of return, in order to solve the problem and we can add some other work after the migration (Fig 1b).

4

Experiments and Results

CPU Speed Measure

We program the test program with basic arithmetic instructions, control instructions and loop instructions. The loop is used to control the whole length of the instructions.

In order not to increase any extra waste of CPU cycles, we counts length of instructions when a jump instruction comes. The measure of the CPU speed is shown as Fig 2. The result means we can't use linear model for the functions that have few instructions. But when instructions' length grows more than 106 bytes, the CPU speed becomes stable. And the mobile device and server speed SL, SR is:

Further, when the length is less than 106 bytes, the running time is less than 106/SL=68ms. So the functions runs less than 68ms on mobile are ignored. And when the length is less than 106 bytes, the migration saves time less than 106 / SL -106 / SR = 59ms. In ordinary wireless channel, the RTT time usually more than 59ms. So the ignoring is reasonable.

Matrix Multiplication

Matrix Multiplication experiment is designed for situation that we want to run specific length of instructions as soon as possible. As shown above, the first migration cost much time, because the memory data needs to be synchronized is accumulated. After the first migration, the memory modification is much less, so the running time on server falls into an acceptable threshold. Another question is why it can still offload again after the first migration cost much of the time. Because it first chooses thread creating function as the migration function, then it chooses matrix multiplication function. And we have an average speed-up of 7.11x.

Seeking Primes

Seeking Primes experiment is designed for situation that we want to get the result as better as possible. We modify sieve algorithm to satisfy the requirement. We divide the positive integers into intervals, and each interval have 8192 integers. The program seeks an interval and test the time then. The length of the interval sought is used as the result. The result is shown in Fig 4.

When the RTT is more than 200ms, when we ask the program run 200ms, it will not be offloaded. Until RTT is less than 150ms, it can be offloaded. The speed-up increases obviously, and average speed-up is 23.23x.

IO Test

IO Test experiment is designed for situation that we process the file on the mobile device. We modify the text statistics program provided by Bell Lab. The input file is a 64K english essay. We test for different length of buffer size, and the result is shown in Fig 5.

The running time on mobile is always 6s. When it comes to offloading, it will be stable when the buffer size is 10000 bytes. In this situation, the time for network communication is minimum. When the buffer size is too small, server will require the file for many times, which cost much time for network communication. When the buffer size is too large, it will need more memory, which will causes more errors during synchronization. So the running time become larger and more unstable. The average speed-up is 8.24x, according to the 7 experiments in the middle.

Conclusion

The paper proposes a problem with the time migration can save as the optimization objective. And a dynamic programming algorithm solves the problem. Then we implement the algorithm on COMET system. 3 groups of experiment are conducted, which shows speed-up of 7.11x, 23.23x, 8.24x.

program

  CalcWeight(w(T, I)) {Assuming Input the Node T and Decision I}; begin If w(T, I) is calculated then Return w(T, I) Else If T is leaf node then w(T, 0) := 0 Else

Fig. [ 1

 1 Fig. [1]. (a) COMET migration procedure (b) Our system migration procedure

Fig. [ 2

 2 Fig. [2]. The CPU speed becomes stable with the growth of the instruction length

  The experiment use with native algorithm time cost of O(N 3 ). Multiply the 200*200 matrixes 20, 50, 100, 200 times. The result is shown in Fig 3.

Fig. [ 3

 3 Fig. [3]. The time cost of matrix multiplication 20, 50, 100, 200 times on mobile and server

Fig. [ 4 ].

 4 Fig.[START_REF] Huang | Mobicloud: building secure cloud framework for mobile computing and communication[END_REF]. The relation between the running time and length of interval

Fig. [ 5 ].

 5 Fig. [5]. The relation between running time and buffer size

  /www.economist.com/node/12411882, 2008. 2. E. Cuervo, A. Balasubramanian, D.-K. Cho, A. Wolman, S. Saroiu, R. Chandra, P. Bahl, Maui: making smartphones last longer with code offload, in: Proceedings of the 8th International Conference on Mobile Systems, Applications, and Services, MobiSys'10, ACM, New York, NY, USA, 2010, pp. 49-62. 3. B.-G. Chun, S. Ihm, P. Maniatis, M. Naik, A. Patti, Clonecloud: elastic execution between mobile device and cloud, in: Proceedings of the Sixth Conference on Computer Systems, EuroSys'11, ACM, New York, NY, USA, 2011, pp. 301-314.

	6	References
	1. L.	Siegele,	Let	it	rise:	a	special	report	on	corporate	it,
	http:/


Wenhua Liu

Yongquan Liang

Jiancong Fan

Zheng Feng

Yuhao Cai

Improved Hierarchical K-means clustering algorithm without iteration based on distance measurement

Keywords: basic K-means, traditional HK, iHK, Clustering Algorithm

Hierarchical K-means has got rapid development and wide application because of combining the advantage of high accuracy of hierarchical algorithm and fast convergence of K-means in recent years. Traditional HK clustering algorithm first determines to the initial cluster centers and the number of clusters by agglomerative algorithm, but agglomerative algorithm merges two data objects of minimum distance in dataset every time. Hence, its time complexity can not be acceptable for analyzing huge dataset. In view of the above problem of the traditional HK, this paper proposes a new clustering algorithm iHK. Its basic idea is that the each layer of the N data objects constructs       2 N clusters by running K-means algorithm, and the mean vector of each cluster is used as the input of the next layer. iHK algorithm is tested on many different types of dataset and excellent experimental results are got.

Introduction

Traditional HK algorithm has the advantage of simple and easy to convergence, but also it has some obvious deficiencies. For instance, HK would have a high computational complexity when the k value is uncertain. Agglomerative algorithm only mergers two clusters having minimum distance every time, which leads to have a higher time complexity at high dimension and big data. To overcome the shortcoming of traditional HK, some researchers have done different degrees of improvement for HK algorithm [START_REF] Wang | Hierarchical k-means clustering using new support vector machines for multi-class classification[END_REF][START_REF] Arai | Hierarchical K-means: an algorithm for centroids initialization for K-means[END_REF][START_REF] Lu | Hierarchical initialization approach for K-Means clustering[END_REF][START_REF] Celebi | Deterministic initialization of the k-means algorithm using hierarchical clustering[END_REF] . But most of researchers have modified HK algorithm for their specific research fields [START_REF] Archetti | A Hierarchical document clustering environment bases on the induced bisecting k-means [M]. Flexible Query Answering System[END_REF][START_REF] Liu | An improved hierarchical K-means algorithm for web document clustering[END_REF][START_REF] Murthy | Application of hierarchical and K-means techniques in Content based image retrieval[END_REF][START_REF] Chen | Flexible hardware architecture of hierarchical K-means clustering for large cluster number [J]. Very Large Scale Integration (VLSI) Systems[END_REF][START_REF] Hu | Hierarchical K-means algorithm for modeling visual area V2 neurons[END_REF][START_REF] Mantena | Speed improvements to information retrieval-based dynamic time warping using hierarchical k-means clustering[END_REF][START_REF] Chen | Using Hybrid Hierarchical K-means (HHK) clustering algorithm for protein sequence motif Super-Rule-Tree (SRT) structure construction[END_REF][START_REF] Ghwanmeh | Applying Clustering of Hierarchical K-means-like Algorithm on Arabic Language[END_REF][START_REF] Chehata | LIDAR data classification using hierarchical K-means clustering [C[END_REF] .

Now society is rapidly being from information era to age of data, it is significant to accurately grasp the valuable information in dataset. Therefore clustering analysis has become a hot research field chased by researchers. To precisely and quickly analyze the data information carried by the dataset, this paper presents a new clustering algorithm iHK, which is a easily convergent and quite accurate clustering algorithm by integrating with the feature of the K-means and hierarchical algorithm. Moreover, iHK algorithm is not limit to a particular research field. In essence, iHK clustering algorithm is an improved HK.

Section 1 describes the summary of iHK algorithm. Section 2 briefly introduces some improved HK algorithm in recent years. Section 3 details iHK algorithm proposed by this paper. And Section 4 presents the experimental results . Section 5 makes a conclusion.

Related work

The training set is divided into two parts, a part of the dataset uses hierarchical algorithm to obtain distribution information of data, then runs K-means at another part. This hybrid algorithm was put forward for the first time by Bernard Chen et al. [START_REF] Chen | Novel hybrid hierarchical-K-means clustering method (HK-means) for microarray analysis[END_REF] at 2005. Due to its accuracy, simplicity and convergence, the method attracted wide attention after it has been proposed. He Ying et al. [START_REF] Ying | Study on PCA based Hierarchical K-means Clustering Algorithm[END_REF] presented HK based on PCA, the general idea of algorithm is that on the whole dataset (rather than two parts), it first makes use of PCA technology to reduce dimension of the dataset and then determines the initial cluster center by executing agglomerative algorithm. Finally it gets clustering results by using K-means. Improved HK based on PCA has more accuracy than traditional HK. To overcome the limitation of a binary tree constructed by hierarchical algorithm, a kind of divisive clustering algorithm was come up with by Lamrous S, Taileb M et al. [START_REF] Lamrous | Divisive hierarchical k-means[END_REF] . The algorithm generates an non-binary tree where each node can split more than two branches by employing K-means, where the k value of K-means is determined by Silhouette index. Kohei Arai et al. [START_REF] Arai | Hierarchical K-means: an algorithm for centroids initialization for K-means[END_REF] studied on an integrated HK algorithm to cluster high-dimensional data set. An improved HK algorithm was put forward by Yongxin Liu et al. [START_REF] Archetti | A Hierarchical document clustering environment bases on the induced bisecting k-means [M]. Flexible Query Answering System[END_REF] to solve the problem of document clustering possessing big data and high-dimension. Li Zhang et al. [START_REF] Zhang | Hybird clustering algorithm based on partitioning and hierarchical method[END_REF] combined divisive algorithm with agglomerative algorithm to address irreversibility of HK. Divisive algorithm gets several clusters by executing K-means at each layer, then utilizes agglomerative algorithm to merger clusters. Bernard Chen et al. [START_REF] Chen | Protein Sequence Motif Super-Rule-Tree (SRT) Structure Constructed by Hybrid Hierarchical K-means Clustering Algorithm[END_REF] added fuzzy theory into traditional HK for boosting the precision of finding protein sequences theme and reducing the time complexity of HK algorithm.

According to the above related work, some ideas about significantly improving efficiency and accuracy are drawn which they can be applied to iHK. Such as, when using agglomerative algorithm no longer relies on binary tree rules and similarity measure between clusters would adopt mean distance rather than minimum distance to avoid serious impact of noise data on precision of algorithm. In iHK algorithm, the number of clusters produced by K-means always varies with the change of layer (data size). So cluster center can present the distribution of data as far as possible.

iHK clustering algorithm

Normalization of data

Paper gives a new algorithm iHK on the basis of learning a large number of improved HK clustering algorithms. iHK firstly standardizes attributes by formula (1), because diverse attributes may adopt different units of measurement in some dataset.

f f if if S m x Z   (1.1) In (1.1), f S and f m is given in detail in the following (1.2) and (1.3). ) ( 1 2 1 f nf f f f f f m x m x m x n S          (1.2)
where

nf f f x x x , , , 2 1   is n values of the f attribute and f m is average of f attribute. n x x x m nf f f f       2 1 (1.

Traditional Hierarchical Algorithm

Assuming that dataset is D and the total number of data object is N . At first, treat- ing every data as a single cluster, hence there are N clusters. Similarity measure be-

tween cluster i C and j C is shown by (2). } { ) , ( min , min q p C C dist j i C q C p j i      (2)
The number of clusters just reduces one at a time through merging two clusters by (2). This process is being performed continually until meeting the given threshold or all data are in one cluster. The time complexity of hierarchical algorithm is

) ( 2 N O
, thus it is not suitable for processing huge dataset.

iHK Clustering Algorithm

iHK overcomes limit of merely aggregating two clusters one time at hierarchical algorithm so that traditional hierarchical algorithm can be better applied to clustering big data. In addition, iHK no longer merges clusters in a minimum distance manner at each layer, but it makes use of K-means algorithm based on mean distance measurement. Supposing that th h layer has L data objects, the process of iHK algorithm based above assumption is that it selects cluster center by employing (3) before Ldata

objects are divided into       2 L clusters through K-means algorithm.               number even is , 1 , 2 , , 5 , 3 , 1 number odd is , , 2 , , 5 , 3 , 1
L L i i L L i i (3) where i   , 3 , 1
is a sequence of data objects.

By comparing the distance between the remaining data and cluster centers, data is divided into the closest cluster center. However, attributes may be mixed, therefore it can't adopt simple distance metric value as a criterion. New standard is defined

(4.1). n d y x dist n i i y x i i    1 , ) , ( (4.1)
where x is a data object with n attributes, namely ) , , , (

2 1 n x x x x   
, and y is a cluster center with n attributes, namely ) , , , ( 2

1 n y y y y    . If the th i attribute of x is discrete data type, then 0 ,  i y x i i d iff i i y x  . Otherwise 1 ,  i y x i i d . If this at- tribute is numeric type, then i y x i i d is calculated by (4.2). i i i y x y x d i i   , (4.2)
After merging, altogether forms

      2 L clusters. Mean vector ) , , , ( 2 1 n x x x x   
is used to represent cluster and the calculation formula of mean vector is given by (5).

              attriute type discrete a is ), ) ( max( attribute type numeric a is , ) ( 1 i ij k ij i C x i ij k i x x count C x x x x C count x k ij In formula (5), ) ( k C count is applied to count the number of data object in k C cluster and ) ( ij x count is used to compute how many values equal ij x . If i x is (5) numeric type, i x is a average of i x in k C . If i
x is a discrete type, then i x equals to the value of attribute appearing most times in dataset . iHK algorithm is being executed until satisfying given condition or threshold. iHK algorithm performs N 2 log times K-means in total, in which K-means just compares half of the input data in this layer. Through the above details, the overall description of the iHK algorithm is shown in Figure 1.

Input: data set D , the total number of data object n .

Output: Data object are divided into different clusters.

Step1:preprocessing attributes in data set D by (1).

Step2:employing step length 2 to select cluster center by according to the order of the data storage.

Step3:computing distance by (4.2) if attribute is numeric type.

Step4:comparing discrete attribute values whether or not they are the same. Distance is 0,iff their value is the same. Otherwise, the value of distance is 1.

Step5:Performing K-means on the basis of step3-4.

Step6: Treating the results of K-means clustering as new dataset.

Step7:Implementing (5) to process dataset formed by Step6.

Step8:Repeat Step2-7 until meeting the given conditions. In Figure 1, Step1 is to standardize the numeric type data so that between attributes of different measure units can make the correct comparison. Distance calculation between data and cluster center is completed by Step3-4. Mean vectors generated by ( 5) are used to represent clusters and use them as input of next circulation.

The pseudocode of the algorithm is described by Figure 2.

Experimental results

This paper tests the performance of iHK at some typical dataset of diverse type. In iHK algorithm, K-means based on new distance metric is executed at each layer. Among, the value of k is different, which is half size of each layer input data.

Accuracy rate changes with different k values, which is shown in Figure 3.

The accuracy of iHK algorithm on five large dataset is shown at top of the Figure 3 and Accuracy on relatively small dataset is displayed at the bottom.

Input: dataset D , the total number of data object n .

Output: several clusters.

for each numeric attribute f do for i←0 to n standardizing attribute value; do for i←0 to n/2

datacenter[i][t]=datacenter[i*2][t]; exdata[i][t]=datacenter[(i*2)+1][t]; end;
dividing exdata[i] into appropriate cluster by defined distance formula;

; ) ) ( max( ; ) ( 1 en th ) attribute type numeric a is ( ij k ij i C x ij k i i x count C x x else x C count x x if k ij     
forming new dataset by the mean vector of each cluster; until meeting the given conditions. The overall trend of all line chart is that they begin to rise gradually and reach maximum at some value, then decrease. Besides, accuracy obviously varies with the change of k values on some dataset, as Figure 3 expresses. 1.

Experimental results in Table 1 show that iHK clustering algorithm has higher accuracy than the basic K-means and HK algorithm at most dataset. Now most of the data come from Web and Web data is mainly big data. When these data are clustered, the time complexity of the algorithm is also considered as a significant indicator of performance of prediction algorithm. In Table 2, time complexity of HK algorithm, basic K-means, iHK algorithm are compared.

Data

The time complexity of HK algorithm should be the sum of the time complexity of Hierarchical algorithm and K-means', it is greater than

) ( 2 N O .
The time complexity of basic K-means is linear, where m is the number of iter- ation. iHK is similar to K-means. It is also linear, where N is the total number of data objects. By comparison, this conclusion can be drawn, which the time complexity of iHK algorithm is minimum, basic K-means follows and HK algorithm's is maximum .

The different time complexity are generated by three algorithms at experimental data set, which use Figure 4 to show.

The time complexity of HK algorithm is significantly higher than iHK at most dataset. iHK and Basic K-means are about equal at all dataset, which can be clearly observed from Figure 4. generalization in that it is not limited to a particular field. And it can be used to clustering big data since it has low time complexity.

From accuracy, efficiency and the time complexity acquired by comparing these three algorithms, a conclusion can be drawn that iHK has the advantage of high accuracy and easy to convergence. In addition, its performance is distinctly superior to other algorithms, but time complexity is similar to basic K-means's. The important point is that iHK is not based on any special application areas and easy to integrate to other clustering algorithm. However, iHK algorithm still can not solve irreversibility of HK algorithm. The next mainly task is that iHK algorithm is further improved.

3 )

 3 Then data objects obtained by above-mentioned steps are used as clustering data. iHK algorithm greatly promotes execution efficiency by combining the idea of 2-way merge, because running algorithm can reduce half the number of clusters at every time. To improve traditional HK algorithm would use K-means algorithm to clustering data at each layer rather than simply merger two clusters by adopting minimum distance between clusters. Next, traditional Hierarchical clustering algorithm and iHK algorithm are simply introduced.

2 L

 2 clusters are produced after the aforementioned process has been executed, then mean vectors obtained at th h layer are used as the new input of th h 1  layer.

Fig. 1 .

 1 Fig. 1. A complete description of the iHK clustering algorithm.

Fig. 2 .

 2 Fig. 2. The pseudocode of iHK algorithm.

Fig. 3 .

 3 Fig. 3. The line chart of clustering accuracy rate.

Fig. 4 .Table 2 .

 42 Fig. 4. The time complexity of three algorithms at some data set.

Table 1 .

 1 Accuracy of three algorithms.

		basic	HK iHK
	Sets	k-mean
	Abalone	57.4%	50.8% 83.4%
	Wine	68.1%	68.5% 75.3%
	Seeds	75.7%	82.8% 85.7%
	Iris	70.2%	88.5% 75.3%
	Credit
	Approval	54.7%	54.6% 72.9%
	Haberman
	Survival	73%	73.5% 75.2%
	Teaching
	Assistant	65.2%	40%	67.6%
	Evaluation
	Ecoli	75%	78.3% 76%
	MONK	67.6%	66.7% 70.2%
	Problem
	Balance	90%	62.2% 92.2%
	scale
	balloons	65.4%	80%	80%

Acknowledgment: This paper is supported by State Key Laboratory of Mining Disaster Prevention and Control Co-founded by Shandong Province and the Ministry of Science and Technology, Shandong University of Science and Technology, Leading talent development program of Shandong University of Science and Technology, National Natural Science Foundation of China under Grant 61203305 and Natural Science Foundation of Shandong Province of China under Grant ZR2012FM003.


Fei Xia

Cungen Cao
email: cgcao@ict.ac.cn

Extracting Part-Whole Relations from Online Encyclopedia

Keywords: part-whole relations, lexico-syntactical patterns, online encyclopedia, edit distance, clustering 1

Automatic discovery of part-whole relations is a fundamental problem in the area of information extraction. In this paper, we present an unsupervised approach to learning lexical patterns from online encyclopedia for extracting part-whole relations. The only input is a few part-whole instances. To tackle the term recognition problem, terms from the domain of the seeds are extracted taking use of the semantic information contained in the online encyclopedia. Instead of collecting sentences that contain relation instances from the seeds, we introduce a novel process to select sentences that may indicate part-whole relations. Patterns are produced from these sentences with terms replaced by Part and Whole tags. A similarity measurement based on a new edit distance is used and an algorithm is described to cluster similar patterns. We rank the pattern clusters according to their frequencies, and patterns from the top-k clusters are chosen to be applied to identify the new part-whole relations. Experimental results show that our method can extract abundant part-whole relations and achieve a preferable precision compared to the other state-of-the-art approaches.

Introduction

Part-whole relations, also known as meronymy, are fundamental semantic relations that exist in many semantic networks, such as WordNet and HowNet. Those semantic networks play a key role in many natural language processing (NLP) systems like information retrieval, and automatic question answering. One of the traditional approaches to automatically extracting part-whole relations is pattern-based, which identifies the relation from patterns like "Y consists of X" that indicates Part-Whole(X, Y) (means X is a part of Y). Those patterns are either designed manually by experts [START_REF] Hearst | Automatic acquisition of hyponyms from large text corpora[END_REF], which is very low efficient, or learned from sentences that contain the given part-whole relation instances [START_REF] Van Hage | A method for learning part-whole relations[END_REF], which needs massive corpora such as the Web.

In recent years, online encyclopedias have drawn attention to many researchers and become an ideal source for semantic information extraction, since they have both broad coverage and high accuracy. BaiduBaike is one of the largest Chinese Wikipedia-like online encyclopedias, and it contains more This paper presents an approach to learning lexical patterns from BaiduBaike to extract part-whole relations. The only input are some part-whole instance pairs, and we firstly extract domain terms of both parts and wholes using their related entries and tags. Sentences from pages of domain terms are labeled and those contain both part-terms and whole-terms are selected and transferred into patterns. A similarity formula based on edit distance is used to cluster patterns. Pattern clusters are ranked according to their frequencies, and patterns from the top-k clusters are chosen to be applied to identify the new part-whole relations.

The paper is organized as follows. Section 2 presents an overview of some related work. The details of our procedure are described in section 3. In section 4, the experimental design and results are presented. Finally, section 5 summarizes the work, and proposes future work.

Related Work

Several taxonomies of part-whole relations exist since researchers believe part-whole relations "should be treated as a collection of relations, not as a single relation" [START_REF] Iris | Problems of the part-whole relation[END_REF]. One of the most widely accepted taxonomies is developed by Winston et al. [START_REF] Winston | A taxonomy of partwhole relations[END_REF], and they mentioned six types of part-whole relations based on the way that the parts contribute to the structure of the wholes: component-integral, member-collection, stuffobject, place-area, portion-mass, and feature-activity. Automatic acquisition of part-whole relations from unlabeled corpora was first presented in [START_REF] Berland | Finding parts in very large corpora[END_REF]. A few part-whole instance pairs as initial seeds were used to learn lexical patterns, and then they extracted the corresponding "parts" of six "whole" instances by these patterns from the North American News Corpus (NANC), which achieves an accuracy of 55%. The low accuracy is due to the noisy patterns they used that tend to indicate both part-whole and non-part-whole relations. Patterns extracted in [START_REF] Van Hage | A method for learning part-whole relations[END_REF] are more reliable since they were learned from the web by using 503 part-whole seeds derived from a special thesaurus. The Espresso algorithm in [START_REF] Pantel | Espresso: Leveraging generic patterns for automatically harvesting semantic relations[END_REF] uses a novel measurement of pattern reliability based on point-wise mutual information to rank all patterns and keep the top-k ones. Both of the latter two approaches achieve higher precision.

Instead of generating more reliable patterns, some researchers spent more effort on verifying the new extracted part-whole instances. Algorithms developed in [START_REF] Girju | Automatic discovery of part-whole relations[END_REF] improved the performance by using the part-whole relations from WordNet to train a decision-tree classifier which was used to predict the previously unseen instance pairs, and they provided a superior precision rate (83%) and recall rate (98%). However, the supervised approach they used requires extensive manual work and relies heavily on external tools like word-sense disambiguation. Other verification methods include heuristic rules [START_REF] Cao | Extracting Part-Whole Relations from Unstructured Chinese Corpus[END_REF] and graph models [START_REF] Wu | Acquisition and verification of mereological knowledge from Web page texts[END_REF].

With the rapid growth of online encyclopedias, more and more work emerged to extract semantic relations from them. [START_REF] Ruiz-Casado | Automatising the learning of lexical patterns: An application to the enrichment of wordnet by extracting semantic relationships from wikipedia[END_REF] first introduced an algorithm to extract part-whole relationships from the Wikipedia. Sentences containing two terms that share part-whole relation in WordNet were collected and transferred to lexical patterns. Similar patterns were generalized using the edit-distance algorithm and were used to extract new part-whole relations from the Wikipedia. The precision they reported is around 60% with different thresholds in the generalization step.

Our Method

Our method to learn part-whole relations from online encyclopedia consists of three steps:

(1) Domain Terms Extraction: terms from domains of part and whole instances are extracted using the semantic information in online encyclopedia. (2) Pattern Learning: sentences from web pages in the online encyclopedia are analyzed and transferred to patterns if both part-terms and whole-terms are found. Patterns are clustered if they are similar. (3) Identification of New Part-Whole Relations: those patterns with high frequency learned in step 2 are used to discover new part-whole relation instances. The details of all the steps are described in the following sections.

Domain Terms Extraction

One of the critical problems in relation extraction is term recognition, which lies in both pattern learning and new relation identification phrases. Some approaches recognize terms with the help of specialized thesauri [START_REF] Van Hage | A method for learning part-whole relations[END_REF] or online dictionaries [START_REF] Girju | Automatic discovery of part-whole relations[END_REF][START_REF] Ruiz-Casado | Automatising the learning of lexical patterns: An application to the enrichment of wordnet by extracting semantic relationships from wikipedia[END_REF][START_REF] Hearst | Automated discovery of WordNet relations[END_REF]].

An online encyclopedia can be treated as a dictionary since it consists of tremendous entries and most of them can be seen as terms. The aim of this step is to extract as many domain terms as possible by giving some entries as seeds. We'll go through the related entries of seeds and pick all the relevant ones. To do this, several relevance measurements are defined as follows.

Tags-based relevance

The tags are a collection of keywords that refer to the category of that entry or other useful information. For example, the tags of the entry 香蕉 (banana) consists of 农产品 (agricultural product), 水果 (fruit), 食品 (food), 绿色植物 (greenery) and so on. The more tags that two entries have in common, the more relevant they are considered to be. Based on this hypothesis, we use a tags-based relevance measurement as follows.

( )

| | | | (1)
Where Tags(e i ) means all the tags of the entry e i .

Related-entries-based relevance

As depicted in Fig 1b, many related entries are listed in the bottom of an entry's page. We use related(e i →e j ) to denote that e j is one of the related entries of e i . Clearly, two entries e i and e j are relevant if related(e i →e j ) or related(e j →e i ).

( ) { ( ) ( ) (2)
On the other side, the more related entries that two entries have in common, the more relevant they are considered to be. So, another relevance measurement based on related entries is defined.

( ) | | | | (3)
Where RelatedEntries(e i ) means all the related entries of the entry e i . Finally, we developed a relevance measurement using the above three measurements.

( ) ∑ ( ) (4)
Where are tunable parameters, and . Giving a set of entries E from a certain domain Domain(E), the probability of a new entry e belongs to Domain(E) is estimated by the following formula:

( ) ∑ | | (5)
Therefore, the iterative algorithm to extract domain terms with a set of seeds E is described in Algorithm We use this algorithm to extract two set of terms, one of them from the domain of part instances in the seeds, and the other from the domain of wholes. We name them DV(p) and DV(w), respectively. So the output of this step is DV(p) and DV(w).

Pattern Learning

The goal of this step is to extract patterns that indicate a part-whole relation. Traditionally, patterns are learned from those sentences that contain both part and whole instances from the seeds. However, this needs a massive corpus that contains lots of duplicated pieces of text that provides cues for relations between two terms. Compared to the whole Web, an online encyclopedia is a small corpus and the content is not so abundant. So with a small set of seeds, only a few sentences can be extracted from the online encyclopedia. We collect the sentences that imply part-whole patterns in a different way. After the previous step, two set of terms are build. Sentences that contain terms from DV(p) and terms from DV(w) are selected and patterns are produced from them. The sentence selection process works in the following way:

(1) Go through all sentences from the web pages of entries from DV(p) and DV(w). (2) Sentences are segmented and part-of-speech tagged using ictclas [START_REF] Zhang | ICTCLAS. Institute of Computing Technology[END_REF].

(3) If an entry from DV(p) appears in the sentence, replace it by the tag Part. A list of Part tags appearing in a coordinate structure will be replaced with only one Part. (4) If an entry from DV(w) appears in the sentence, replace it by the tag Whole. A list of Whole tags appearing in a coordinate structure will be replaced with only one Whole.

(5) Select all sentences that contain both Part and Whole tags. After this process, the selected sentences are transferred into patterns; for example, sentence (s1c) contains an entry 苹果 (apple) from DV(w), and two entries 维生 素C (vitamin C) and 果胶 (pectin) in a coordinate structure from DV(p):

(s1c) 苹果/n 富含/v 维生素/n C/x 和/c 果胶 (s1e) Apples are high in vitamin C and pectin Therefor pattern (p1c) produced from (s1c) is:

(p1c) Whole 富含/v Part (p1e) Whole are high in Part.
Usually, a reliability measurement will be chosen to rank those produced patterns, and the top-k most reliable patterns are selected. Instead of measuring a single pattern, we firstly cluster similar patterns and then pattern-clusters are ranked according to their frequency, and then the patterns in the top-k most frequent clusters are selected.

We use a similarity measurement based on edit distance to judge whether two patterns are similar:

( ) ( ) | | | (6)
Where EditDist(p i , p j ) is the edit distance between two patterns p i and p j , | p i | is the length of p i which is defined as the number of the words it contains. A pattern p with length m can be expressed as p(1…m), and the k-th word in p is expressed as p [k]. The edit distance between two patterns p i and p j is defined as the minimum number of changes (word insertion, deletion and replacement) to transfer p i to p j :

( ) ( ) ( ( ) ( ) ( ) ) (7)
Where m is the length of p i and n is the length of p j , and

( ) { (8)
Where POS(p i [m]) means the part-of-speech tag of p i , and we use a Chinese synonymy dictionary "TongYiCiCiLin" (Extension Version) [START_REF] Mei | Chinese Synonym Thesaurus[END_REF] to judge whether two words are synonymous or not.

The algorithm to cluster similar patterns is described in Algorithm 2. take the two clusters with the biggest similarity, c i and c j , the max similarity is max 5.

if max < λ 2 6. return 7. else 8.

merge c i and c j to a new cluster c' 9.

recalculate the similarities between c' and all the other clusters 10. Repeat (2)~( 9) 11. End

The similarity between two clusters is calculated using the average-linkage method; that is, their similarity is computed as the average similarity between every pair of patterns from the two clusters:

∑ ( ) | | | | (9)
We rank those generalized patterns according to their frequencies which are computed as the sum of the frequencies of the patterns before generalization. Finally, patterns in the top-k clusters are chosen as the output of this step.

Identification of New Part-Whole Relations

We apply the patterns learned in the previous step to the online encyclopedia corpus to identify new part-whole relations. The corpus is split into individual sentences and preprocessed with word segmentation and part-of-speech tagging. Once a sentence matches a pattern, substrings corresponding to the Part and Whole tags are extracted, and then terms are recognized using DV(p) and DV(w).

Since part instances are always showed in coordinate structures, one sentence may contain several pairs of part-whole relations. The output of this step is a list of pairs of candidate part-whole relations.

Experimental Results

We evaluate the performance of our method in extracting stuff-object relation from the BaiduBaike corpus. Our method also can be applied to other types of part-whole relations and we plan to do it in the future work. The five pairs of part-whole relation seeds used in the experiment are listed in Table 1. They are also entries in the online encyclopedia. , and 330 patterns from top-15 clusters are chosen to be applied to extract new part-whole relations. Table 2 shows some of the patterns learned by our approach. Two types of common errors are identified in our experimental results: 1) Unable to recognize some of the multiword terms. For example, the partwhole pair extracted from the following sentence (s2c) is Part-Whole(酸, 黄 瓜) (Part-Whole(acid, cucumber)), while the correct part instance should be 丙醇二酸 (tartronic acid). This accounts for over 50% of the errors. (s2c) 黄瓜/n 中/f 含有/v 丙醇/n 二/m 酸/a (s2e) Cucumbers contain tartronic acid 2) Some errors are due to the lack of anaphora resolution algorithm. For example, sentence (s3c) returns the relation Part-Whole(胡萝卜素, 蔬菜) (Part-Whole(carotene, vegetable)), but the whole instance has to be the specific vegetable it referred to, which may be contained in the previous sentence. (s3c) 这些/rz 蔬菜/n 富含/v 胡萝卜素/n (s3e) These vegetables are high in carotene To improve the performance of our approach, external tools like term recognition and anaphora resolution will be used in the future work.

Conclusions and Future Work

In this paper, we present an unsupervised approach to learning lexical patterns from online encyclopedia to extract part-whole relations. The only input is 5 pairs of partwhole instances. The major contributions of this paper include: 1) An algorithm to extract domain terms taking use of the semantic information contained in online encyclopedia is proposed, these terms are of great help for term recognition in relation identification; 2) A novel method to collect sentences that may indicate part-whole relation is described, compared to those approaches used in previous work, which set a high requirement for the corpus; 3) A new method to select reliable patterns. Similar patterns are clustered and pattern clusters are ranked according to their frequencies, those patterns from the top-k clusters are chose to be applied to identify the new part-whole relations.

Experimental results show that our method can extract abundant part-whole relations and achieve a preferable precision compared to the other approaches.

Future work focuses on improving the accuracy of our approach and applying the method to other relations.

Fig. 1 .

 1 Fig. 1. The corresponding web page of the entry "banana"

Algorithm 2 .

 2 Clustering patterns Input: set of patterns P={p 1 , p 2 , …, p n }, threshold λ 2 Output: clusters of patterns C={c 1 , c 2 , …} 1. C is initialized as {c 1 , c 2 , …, c n } where c i ={p i } 2. Do Begin 3. calculate the similarities of each pair of clusters 4.

Table 1 .

 1 Part-whole relation seeds is 2070, and the size of DV(w) is 2556. We randomly chose 200 terms from each set, and the precisions all exceed 95%, which shows the efficiency of our domain terms extraction algorithm.After the sentence selection process, 11003 sentences that contain both terms from DV(p) and DV(w) are extracted and 9235 distinct patterns are produced, which indicates that online encyclopedia really contain few duplicated sentences. Similar patterns are clustered by Algorithm 2 with λ

		Whole	Part
	苹果 (apple)	维生素C (vitamin c)
	香蕉 (banana)	钾 (potassium)
	橘子 (orange)	柠檬酸 (citric acid)
	栗子 (chestnut)	蛋白质 (protein)
	龙眼 (longan)	葡萄糖 (glucose)
	Two set of domain terms are extracted using Algorithm 1 with
	λ	. The size of DV(p)

Table 3 .

 3 Relation extraction results 8% relations are extracted by the above patterns and 80% of them are identified by the first one. We have got a preferable precision compared to other reported algorithms, such as Girju's[START_REF] Girju | Automatic discovery of part-whole relations[END_REF] 83%.

	Part-whole pattern	Cnt(all-extracted)	precision
	Whole 含有 Part	6776	82.1%
	Whole 所含的 Part	788	84.6%
	Whole 中的 Part 含量	698	87.7%
	Whole 含 Part 量	169	95.9%
	Part 的 主要 来源 是 Whole	35	91.4%
	食用 Whole 可以 补充 Part	13	100%
	Over 85.

Acknowledgments

This work is supported by the National Natural Science Foundation of China under grant No.91224006, 61173063, 61035004, 61203284, 30973716 and National Social Science Foundation of China under grant No.10AYY003.

Table 2. Samples of part-whole patterns

In the new-relation identification step, 5184 sentences match at least one of the patterns, 9868 pairs of candidate part-whole relations are extracted. We calculate the precision of each pattern manually according to the following equation: [START_REF] Ruiz-Casado | Automatising the learning of lexical patterns: An application to the enrichment of wordnet by extracting semantic relationships from wikipedia[END_REF] Where Cnt(all-extracted) means the number of all the part-whole relations extracted by that pattern and Cnt(correct-extracted) means the number of the correct ones among them. Table 3 shows the results of those patterns listed in the above table:


Weiqiang Sun

Weizhong Zhao
email: zhaoweizhong@gmail.com

Wenjia Niu
email: niuwenjia@iie.ac.cn

Liang Chang

A DBN-based Classifying Approach to Discover the Internet Water Army

Keywords: Internet Water Army, DBN, Downpour SGD, Collaboration, Hadoop

The Internet water army (IWA) usually refers to hidden paid posters and collusive spammers, which has already generated big threats for cyber security. Many researchers begin to study how to effectively identify the IWA. Currently, most efforts to distinguish non-IWA and IWA in data mining context focus on utilizing classification-based algorithms, including Bayesian Network, SVM, KNN and etc... However, Bayesian Network need strong conditional independence assumption, KNN has big computation costs, above approach may affect the effectiveness to some extent in real industrial applications. Hence, Neural Networks-like deep approach for IWA identification gradually becomes an emerging but possible direction and attempt. Unfortunately, there also exists one main problem, which is how to balance the deep learning and computation costs in hierarchical architecture. More specially, combine leaning-level heuristic training design and computing-level concurrent computation is a challenging issue. In this paper, we propose a collaborative hierarchical approach based on the deep belief network (DBN) for IWA identification. Firstly, a DBN-based collaborative model with hierarchical classifying mechanism is built. Then towards Hadoop platform, the Downpour Stochastic gradient descent (Downpour SGD) is exploited for DBN pre-training. Finally, the dynamical workflow will be designed for managing the whole learning-based classifying process. The experimental evaluation shows that the valid of our approach.

Introduction

With the rapid development of the Internet, cyber security issues become more and more prominent. Recently, the internet water army (IWA) draws more and more attentions. The IWA refers to post online comments or articles with particular content on social media for some hidden purpose in order to affect public opinion. They intentionally or unintentionally spread rumors and attack others, causing extreme emotions and national antagonism, which belong to an emerging threat for cyber security. Therefore, effective regulatory on IWA is desperately needed.

To defend the IWA, the basic challenge is to identify IWA firstly. Actually, IWA identification is essentially a classification, which should analyze the users' historical behaviors and compute the inner-class and inter-class differences between IWA and normal user. Most common classification algorithms have been exploited in IWA identification, such as Bayesian Network, SVM, KNN, and Neural Networks and so on. However, for real industrial application of big data context, these approaches have some disadvantages to some extent. For instance, the Bayesian network is based on probability and statistics, which predict samples classes using Bayesian principles. However, Bayesian principles need a strong conditional independence assumption which is always invalid for IWA in real scenario. SVM requires prior calculation of the samples' space vector and the weight of each dimension, while the weight setting always relies on experience and problem analysis and directly affects the accuracy of the result. KNN is a lazy learning method, which stores samples until they are needed to learning. It may lead to a large computational overhead if the sample set is complex.

With the development of deep learning, the work based on neural network algorithm draws special attention again. As a commonly used classification algorithm, it determines its model parameters by training and objectively reflects the impact of various factors on the final result. However the basic neural network model is so complicated. When the training date set scales up, the training process will take too much time to complete, and furthermore, improper initializations of weight easily result in the local minimum problem. These disadvantages can bring poor convergence, low accuracy, time-consuming problems when using neural network-type algorithm to detect IWA.

Hence, a collaborative hierarchical approach based on DBN will be proposed in this work. Our approach will build a parallel-improved DBN model and defines the mechanism of DBN collaboration between the various parts of the model. The model mainly consists of three modules: user data pre-processing module, DBN model training module and the collaboration module. Especially for the collaboration module, we define the feedback process of the convergence and accuracy of the DBN in the form of workflow. Beside, parallel computing model are used in user data pre-processing module and DBN model training module. We hope that this approach can not only improve the convergence and accuracy of IWA detection, but also solves the problem of costing too much time in the model training process with the mass of sample data.

The rest of the paper is organized as follows. Section 2 discusses related work, followed by the presentation of a DBN-based classifying approach and its details in Sec-tion 3. Section 4 presents the experimental results that illustrate the benefits of the proposed scheme compared to other approaches. Finally, Section 5 provides the concluding remarks and future work.

2

Related work

The related work of IWA identification can be grouped into two aspects: behaviorbased recognition and content-based recognition. In addition, spam detection work in Web 2.0 also has close and significant inspiration for IWA identification.

Behavior-based work can be further divided into two categories: direct calculation type [START_REF] Chen | Method for capturing water armies on microblog platforms[END_REF][START_REF] Zhang | Microblog ghostwriter identifying method and device[END_REF] and training-leaning type [START_REF] Han | Microblog water army identifying method based on probabilistic graphical model[END_REF]. In the direct calculation type, Chen Kai et al [START_REF] Chen | Method for capturing water armies on microblog platforms[END_REF] aimed at the account list which has forwarded hot topic. They determine the initial IWA sample collection S and fans of S by artificial judgments and choose part of the fans of S to join in S through a sample filter in next epochs. This method uses the social relations of the IWA to identify more IWA. However, it has some limitations that it ignores the few relations between the IWA. Zhang Guoqing et al [START_REF] Zhang | Microblog ghostwriter identifying method and device[END_REF] extend the feature vector to 16 dimensions and identify IWA by comparing the pre-set threshold to the result of the calculation of the weighted dimensions. However, in this method, the weight of dimensions is set relatively subjective. In the leaning-training type, Han Zhongming et al [START_REF] Han | Microblog water army identifying method based on probabilistic graphical model[END_REF] transform the behavior and features of the micro-blog users to characteristic vector, constructing a probabilistic graph of features and behavior: P(D|w)P(w)=(P(z (i) ,y (i) |x 1 (i) ,…x n (i) ,w))P(w), where D is the number of samples, x n (i) is the feature characteristic of dimension n of the i th user, yn (i) is the behavioural characteristics of dimension n of the i the user, w is the weight of each feature weight, z is the probability for user is IWA. Finally, use the Maximum Likelihood Estimation to get parameter w and so on in probabilistic graph, which can calculate the probability of that a given user is IWA. The above methods are largely dependent on the selected characteristics which will result in selection too artificial and subjective.

Content-based work mainly focus on posting content itself, through distinguishing IWA through statistics of normal and abnormal posting depending on language characteristic. There are three mainly ideas in this approach: the first one4 is to use emotional tendency for a single posting. In this idea, they consider IWA has a strong emotional tendency to beautify or demonize something; the second [START_REF] Zhang | Detection and determination method of network navy, ANHUI BORYOU INFORMATION TECHNOLOGY CO LTD[END_REF][START_REF] Xu | Using Deep Linguistic Features for Finding Deceptive Opinion Spam[END_REF][START_REF] Lau R Y K | Text mining and probabilistic language modeling for online review spam detecting[END_REF][START_REF] Harris | Detecting deceptive opinion spam using human computation[END_REF] is based on the tendency to deceive of a single posting. In this idea, posting of IWA is deceptive opinion spam with some statistical law. The work [START_REF] Bhattarai | Characterizing comment spam in the blogosphere through content analysis[C]//Computational Intelligence in Cyber Security[END_REF] is based on similarity of multiple posts. In this idea, they consider IWA tend not to write multiple posts in order to pursue post speed. Instead, IWA prefers to make slight changes to the same post and forward largely. However, these methods based on the content analysis have a common defect that a simple analysis of contents would not be conclusive evidence for IWA identification. In addition, in the evolution of fighting with IWA, count of the machine post decreased and manual post increased, which makes identification based on content analysis extremely difficult.

Spam is the term widely used to describe the phenomenon that spam messages spread everywhere. Spam, broadly defined, refers the behavior of sending information actively with no specific target through the electronic information system, involving micro-blog and forums. Non-target greedy spread for behavior and spam for content, there are similarities between Spam and IWA. Anti-Spam research has a history of ten years, mainly including text-based, behavior-based and image-based feature extraction. There has been a lot of typical work: a) text-based mainly uses bag-of-words (BoW) [START_REF] Gansterer | Anti-spam methods-state of the art[END_REF], space binary polynomial hashing (SBPH) [START_REF] Guzella | A review of machine learning approaches to spam filtering[END_REF], orthogonal space bigrams (OSB) [START_REF] Siefkes | Combining winnow and orthogonal sparse bigrams for incremental spam filtering[M]//Knowledge Discovery in Databases: PKDD 2004[END_REF], and biological immune system (BIS) [START_REF] Ruan | A three-layer back-propagation neural network for spam detection using artificial immune concentration[END_REF]; b) behavior-based spam detection is to filter spam by extracting the behavioral characteristics of the email. These commonly used methods are based on system log and message header information [START_REF] Yeh | Effective spam classification based on metaheuristics[C]//Systems, Man and Cybernetics[END_REF], attachment [START_REF] Hershkop | Behavior-based email analysis with application to spam detection[END_REF], and the network [START_REF] Ramachandran | Understanding the network-level behavior of spammers[C][END_REF]; c) image-based feature extraction mainly focuses on extracting the key characteristics of the picture. There are a lot of the typical approaches to extract e-mail feature based on machine learning in intelligent spam detection, involving Bayesian [START_REF] Ming | Spam filtering by stages[C]//Convergence Information Technology[END_REF][START_REF] Wang | An improved Bayes algorithm for filtering spam email[END_REF], K-nearest neighbor [START_REF] Li | Implementation and evaluation of Chinese spam filtering system[END_REF][START_REF] Sakkis | A memory-based approach to anti-spam filtering for mailing lists[END_REF], Boosting Trees [START_REF] Schapire | BoosTexter. A boosting-based system for text categorization[END_REF], SVM [START_REF] Drueker | Support vector machines for spam categorization[END_REF][START_REF] Tang Zhao-Hui | Design and Analysis of Spam-Filtering System Based on Words Segmentation[END_REF], Rcchio [START_REF] Schapire | Boosting and Rocchio applied to text filtering[END_REF] and Artificial Neural Networks [START_REF] Clark | A Neural Network Based Approach to Automated E-Mail Classification[END_REF], and so on.

It is worth noting that the Neural Network has been a very special research in social media Spam, due to the surprising improved recognition effect. However, it is difficult to be widely used because of the non-ignorable locally optimal, slow convergence [START_REF] Xu | When does online BP training converge?[END_REF] and other problem. In the works of J.Clark et al [START_REF] Clark | A Neural Network Based Approach to Automated E-Mail Classification[END_REF], the email classification based on the artificial neural network received 99.13% recognition accuracy on Ling-Spam corporace10 dataset. Guangchen Ruan et al [START_REF] Guangchen | A three-layer back-propagation neural network for spam detection using artificial immune concentration[END_REF] use BP Neural Network to identify Spam. First, they extract feature from email using KLGA algorithm and reduce the dimension of the vector space model of message. Then they classify the message by three layers BP Neural network. This approach has a 97%-99% recognition rate on PU and Ling-Spam corpora10 dataset. But its main shortcomings include the need for more time to compute and the great impact on network convergence the initial settings have.

With the breakthrough that Hinton et al did on Neural Network in 2006, deep learning technology, especially DBN [START_REF] Hinton | A fast learning algorithm for deep belief nets[END_REF], gained success in image recognition, voice recognition, and natural language content comprehension. So this has inspired us to take advantage of the new generation of neural networks to extract behavior and feature, exchanging time for the calculation of neurons for accuracy and adaptive performance in IWA recognition.

Overview of the classifying approach

The classifying approach is designed to consist of three modules:

Data pre-processing

User information needs to be expressed in the form of a mathematical transformation before the classification. Objectively, the user relevant information contains user name, user registration time, previous login time, login IP, browsing history records, post history records, replies history records, friends' records, followers' records, followings' records. We select the representative information as the reference to classify users and accordingly propose a multi-attribute description user information framework.

Using the multi-attribute descriptive user information framework, user descriptive information can be transformed into a vector which is mathematical representations of the user information. In addition, in order to facilitate setting initial weights in DBN model training, value of each dimension in user information vector need to be in [-1,1]. We present a normalization to deal with each dimension of the vector. That is to say we extract the value range of each dimension of the vector, find and normalized the dimensions which value range is beyond [-1, 1].

As shown in Figure .2, the vector generation process and normalization process can use parallel computing model. In user descriptive vector generation phase, all user information is randomly divided into m group to parallel process. Each group will be responsible for transforming user descriptive information to descriptive vector and each vector will be assigned an ID number then. Finally, we obtain a collection which contains pairs of user ID and descriptive vector. In the user descriptive vector normalization process, we first use MapReduce parallel frame to find the dimensions which value range is beyond [-1, 1] of the vector as well as the biggest absolute values of these dimensions. Then we use these values to normalize these dimensions. Normalization process can also divide user descriptive vector into m group to normalize in parallel. Through the above process, the normalized descriptive user vector collection can be obtained. A part of the collection data is classified, that is, this part of users has been marked as IWA or normal. This type of date is called "classified data sets". The "classified data sets" is divided into two parts for the subsequent DBN model training. One part called "training data set" is for the training while the other part called "test data set" is for accuracy tests for the DBN model obtained after training. As the DBN model needs enough samples to learn so that hiding law in these samples can be simulate, the "training data set" generally is given more samples. However, too many samples will increase the amount of computation and bring an over calculate disadvantage. Pre-training phase use layer by layer unsupervised greedy learning methods to train the two RBM layers in the model: First, use the input data and the first layer if hidden layers as a RBM to train to get the parameters, then fix the parameter of the RBM and take the first hidden layer as the visible layer and the second as the hidden layer to train the new RBM. Finally, we obtain the parameters of the second RBM and determine the parameters of the two RBM at the moment and complete the pre-training process of the DBN model. In this process, the training process of each RBM is independent, which greatly simplifies the process of training the model.

……

Original user description information

DBN Training

DBN (Deep

A DBN-based Classifying Approach to Discover the Internet Water Army 7

After the pre-training, the entire network is equivalent to BP neural network. This BP neural network contains two layers of hidden nodes, network parameters between the input layer and the first layer of hidden nodes, as well as the parameters between the two layers of hidden node, has completed initialization. You only need to randomly initialize the network parameters of the second hidden layer nodes and output nodes, you can take error back propagation trainings according to the normal BP neural network training methods until the model reaches convergence or termination conditions, this process is called fine-tuning.

In For parallel processing algorithms used in RBM, we examined the following three kinds of schemes: MapReduce model, the traditional SGD mode and Downpour SGD model. MapReduce model is good at data parallel processing in the usual sense, but not suitable for depth iterative calculation in deep network training; Traditional SGD (Stochastic gradient descent) model is the most commonly used optimized method for training the Deep Neural Networks. However, this model is essentially serial, which means data movement between machines would be very time-consuming; Downpour SGD is a parallel optimization to the traditional model and is an asynchronous stochastic gradient descent variant which use single DistBelief model and has many distributed copies. It is a good choice for large-scale data parallel computing. Accordingly, we choose DownPour SGD for parallel processing to train RBM training process.

As shown in Figure 4, parallel RBM training based on Downpour SGD has a basic idea: the training data is divided into several subsets and distributed on multiple Worker servers; each Worker server runs a copy of RBM model and just simply does communication with parameter server. The parameter server stores the current state of model parameters. Parameters of the model can be updated by updating the parameters storing in the parameter server. At training phase, each Worker server obtains the parameters of current state of the model from the parameter server and performs minbatch according to these parameters, calculate the gradient and push the results back to parameter server. In a simple implementation of Downpour SGD, you can set the Work server to obtain the updated parameters from parameter server after every "nfetch" times of mini-batch and push the new calculated gradient back to parameter server to update.

The gradient update process is performed asynchronously in DownPour SGD, in this way, even a Worker server is down, it will not affect the work of other Worker servers. Although asynchronous update process will lead to the parameters of each Worker server slight difference, the algorithm has a good stability in current implementation.

After the training of the two RBM, the pre-training process of the DBN model is complete. The model is equivalent to a four-layer BP neural network now. The parameters between the three bottom layers have been initialized. Initialize the parameters between the top two layers and train the BP neural network with the training data set, which is fine-tuning process of the DBN model.

Workflow-based Collaborative Learning

In the model training process, different settings of parameters in each module may affect the output of subsequent module so that it will affect the accuracy of the final DBN model. For example, if the proportion of the training data set is too low, it will prevent the IWA feature extraction, resulting in a low accuracy; if the maximum number of epochs is too low, it will make the network immature. In the collaborative module, we define the feedback process of the convergence and accuracy of the first two modules in the form of workflow. According to the convergence and accuracy of DBN model, we determine whether to make a reverse adjustment to the parameters of the user data pre-processing module and DBN training module or not, finally, improving the performance of the DBN model. Workflow is a class of business processes that can be completely or partially performed automatically. Documents, information, and tasks can be passed and executed between different actors based on a series of procedural rules. The workflow we defined is shown as Figure 5.

Output data BP Classification information • • • • • • • • • • • • • • • • • • • • • • • • • • • • RBM RBM Input

Experiment

Setting Up

We get 3019 user information from Sina WeiBo by using web crawlers. The information contains 26 behaviour related dimensions which including duration of registration, total number of micro-blog, the number of forwards, the number of collections, member level, the number of Tab, location information, the number of selfdescribing words, total number of links contained in all blogs, the number of followers, the number of followings, the ratio of mutual followers, rate of interactions, the time of most blogs, and so on. Then we try to mark these users manually which includes 588 IWA and 2431 normal users in three months, this is very challenging. All DBNs, which containing 4 hidden layers each with 2048 units, were trained using SGD with a mini-batch size of 128 training cases in pre-training. For simplicity, we use a default learning rate of 0.005 in Gaussian-binary RBMs while using a learning rate of 0.08 in binary-binary RBMs. For fine-tuning, we used SGD with the same mini-batch size in pre-training. The learning rate started at 0.1. If the accuracy fells at the end of each epoch, the learning rate is halved. This process continues until the leaning rate fell below 0.001.

To evaluate the performance, we designed two experiments. We hope to check: 1) whether our improved DBN has acceptable training cost;2)whether our improved DBN has an averagely better identification accuracy than normal DBN.

Training Cost

We used 60% of the 3019 user information as the training data while the rest 40% as test data both in our improved DBN and normal DBN. In this experiment, we ran 100 epochs for Gaussian-binary RBMs and 50 epochs for binary-binary RBMs in pretraining. We determined that our improved DBN should take an accuracy of 85% to 90% as a threshold in DBN model checking part of the workflow. Figure 6 shows the time cost of DBN models in pre-training and fine-tuning when our improved DBN complete training and achieve the accuracy goal. We can observe that the time under the accuracy of 90% is just double of the time under 85%. It is acceptable to get more five percent accuracy to archive an accuracy of 90%.

Identification Accuracy

The second experiment was designed to show identification Accuracy with different number of training data and test data. The proportion of the training data in this experiment increased from 10% to 90% and the rest were used as test data. The figure 7 shows that our improved DBN always has an averagely better accuracy than normal DBN, especially when the proportion of training data is small than 40%. We can see that the accuracy will begin falling when the proportion is larger than 75%. When the proportion is 60%, both our improved DBN and normal DBN nearly have the same accuracy. This paper proposes a collaborative hierarchical approach based on the DBN for IWA identification. We found that parallel computing can accelerate the user data preprocess and the training process when the simple set is complex and large. We believe that this research still runs its beginning stage, and in the future, we will put more study and discussion on how to control the balance point between computing cost and identification accuracy.

Fig. 1 .

 1 Fig. 1. Schematic Approach Overview

Fig. 2 .

 2 Fig. 2. Figure.2 Parallel Pre-processing Diagram

  Belief Network) model is a kind of deep neural network model and is a probability generation model that consists of multilayer random variables. Basic DBN model consists of two layers of RBM (Restricted Boltzmann Machines) and a layer of BP neural network (Back Propagation Neural Network). The training process of the DBN model is divided into two phases: pre-training phase and fine-tuning phase.

  the DBN model pre-training phase, we use layer by layer greedy unsupervised learning methods to train two RBM. Compared to the traditional multi-feedback training model, this approach simplifies the training process model, accelerating the training speed of the model to a certain extent. However, In the face of massive training data set, single RBM layer training still takes a long time. So, parallel processing is applied to accelerate the single RBM layer training and speed up the pre-training of DBN model, shortening the DBN model pre-training stage time.

Fig. 5 .

 5 Fig. 3. Basic DBN Model

  Fig. 7. Identification Accuracy

Fig. 6 .

 6 Fig. 6. Training Cost

Acknowledgements

This research is supported by the National Natural Science Foundation of China (No. 61105052, 61103158, 61202398, 61272295), the Strategic Priority Research Program of the Chinese Academy of Sciences Grant (XDA06030200), Guangxi Key Laboratory of Trusted Software.