Jie Chen

Baohua Qiang
email: qiangbh@yahoo.com.cn

Yaoguang Wang

Peng Wang

Jun Huang

An Optimized Tag Recommender Algorithm in Folksonomy

Keywords: Folksonomy, tag recommender system, collaborative filtering, user retrieval motivation, k-means++

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

Introduction

Nowadays, with the development of web 2.0, a large amount of dig ital resources appear and rise. Accord to them, a new network information classification system folksonomy appears. The term fo lksonomy is generally attributed to Thomas Vander Wal [START_REF] Vander | Folksonomy Coinage and Definition[END_REF], which is a port manteau of folk and taxono my. In folksonomy, the tags and resources are created by users , and users can tag the information according to their own needs and preferences in order to make others to retrieve and share the resources. As shown in Figure 1, the resource "Baidu.co m" is tagged by user "Brown" with the tag "Search". In folksonomy, users can easily find other users with similar preferences, resources and tags which have been used.

In the existing folksonomy system, most of tags are lack o f semantic precision and not standard, which affect the use of it to a certain degree. In order to better organize Fig. 1. the structure of a folksonomy system First, we get a certain amount of datasets from the network, and use the s temmer technology [START_REF] Ben | A new stemmer to improve information retrieval[END_REF] to get more effective and useful text content of tags in the datasets. Second, according to the motivation theory proposed by Strohmaier [START_REF] Strohmaier | Why do users tag? Detecting users' motivation for tagging in social tagging systems[END_REF], we get two types of users, Categorizers and Describers [START_REF] Zubiaga | Tags vs Shelves: From Social Tagging to Social Classification [C[END_REF], wh ich have different retrieval motivations. Third, according to the new user"s retrieval mot ivation, we judge user is a Categorizer or Describer, and then cluster the tags and resources th at types of users have tagged with k-means++ algorith m [START_REF] Ell | The impact of ambiguity and redundancy on tag recommender in folksonomies[END_REF]. Finally, according to the similarity, the algorith m give the reco mmended information wh ich is more accuracy and relevant to users. The experimental results show that the optimized algorith m with user retrieval motivation can have higher accuracy and stability than traditional tag reco mmender algorith m in fo lksonomy system.

Preliminaries

Reco mmender Algorithm

Reco mmender system is a special system that it is always used to deal with some problems, such as information filtering. It act ively provided the options to users that the options are identified as the most suitable results by recommender algorithm. And all we known, the most important part of the recommender system is reco mmender algorith m, the algorithm can determine the way to wo rk and the recommended strategy. Generally speaking, reco mmender algorithm has three main types: Content-Based Filtering, Collaborative Filtering and Hybrid Recommender. In this paper, the optimized tag reco mmender algorith m belongs to the kind o f collaborative filtering. The optimized tag reco mmender algorith m is based on the behavior or interests of the user groups. Firstly, the recommender system will find the neighbor users, according to the historical data of the target users. Secondly, it ca n get the object value fro m the neighbor users' evaluations. Finally, accord ing to the previous data, the recommender system will provide the personalized reco mmender to the target user.

The traditional collaborative reco mmender algorith m usually has some problems, such as concept drift and sparse, because the limitation of a algorith m is a fact. In this paper, an optimized tag reco mmender algorith m is proposed to improve these disadvantages based on the user"s retrieval motivation. At the same time, this optimized tag reco mmender algorith m is proved to feasible after the experiment.

2.2

The user"s tagging motivation

In this paper, we add the users" motivation theory to fo lksonomy system and use the theory proposed by Strohmaier. In this theory, there are two kinds of users in the datasets, and they are called categorizers and describers. Categorizer is the users who are motivated by categorization and view tagging as a means to categorize resources according to some high-level characteristics. For example, when a popular music is tagged by categorizers, they will use tag "music" rather the tag "song", "tune" even if they have the similar mean ing. Describers are the users who are mot ivated by description view tagging as a means to accurately and precisely describe resources. For examp le, when a popular music is tagged by describers, the tag "music", "popular", and "favorite" can be used to describe the resource. We consider the tags tagged respectively rather than the tags that can"t be classified, wh ich can give the benefit to us and improve the quality of result. In next section, we will give the model to calculate the users" motivation.

Measures

In this part, we use four indicators to measure the users" tagging motivation. The four measures are respectively Tags per Post (TPP), Tag Resource Ratio (TRR), Low-frequency tagging ratio (LFTR) and Interrogative adverbs tagging ratio (IATR).

According to the results obtained by the above measures, we can get the type of the users, a categorizer or a describer. The detail description of the measures can be found in literature [START_REF] Zubiaga | Tags vs Shelves: From Social Tagging to Social Classification [C[END_REF].

 Tags per Post (TPP)

TPP u = T ui r i =1 R u (1)
Where R u is the nu mber of resources tagged by the user u, T ui is the nu mbers of tags annotated by user u on resources i, r is the total number of resources. This measure relies on the verbosity of users. So, if the TPP reflects in a higher score, the user is more likely a Describer.

 Tag Resource Ratio (TRR)

TRR u = T u R u (2)
Where T u is the number of tags annotated by the users , R u is the number of resources annotated by the users . Because a typical Categorizer would apply only a small of tags to his resources and score a low number on this measure.

 Low-frequency tagging ratio (LFTR)

LFTR u = T u 0 T u , T u 0 = t| R t ≤ n , n = R t max 100 (3)
Equation 3 shows the calculation of the final measure where are seldo m used tags. T u are all tags of the given user. t max denotes the tag which was tagging the most by the user. n means the crit ical value. If the LFTR reflects in a lower score, the user is more likely a Categorizer.

 Interrogative adverbs tagging ratio (IATR)

IAIR u = Card t ∈T str T u (4)
Where T str ={ what, who, when, where, …} is a set of Interrogative adverbs, Card(t T str ) is the number of interrogative adverbs tags annotated by user, T u is the number of tags annotated by the users. Obviously, IATR(u)(0,1), and if the IATR reflects in a lo wer score, the user is more likely a Categorizer.

An evaluation model for user"s motivation

According to the four indicators above to distinguish the users" type, categorizers or describers, we can construct a reasonable evaluation model [START_REF] Trattner | Enhancing the Navigability of Social Tagging Systems with Tag Taxonomies[END_REF] to calculate the orientation of users" motivation below. M =a*TPP(u)+b*TRR(u)+c*LFTR(u)+d*IA--TR(u),Where, a,b,c,d (0, 1). According to the results of the experiment, we find that each datasets has a different optimal coefficient. So, we choose the average score of M and use M" to denote the value of it.

M ′ = (TPP u + TRR u + LFTR u + IATR u ) 4 (5)
According to the formula 6, we find that M" is a monotonic function and it also has a threshold M t . If M" is larger than M t , we consider the user a Describer; On the contrary, the user is a Categorizer. If both are equal, he has not a special motivation and we treat the user either Describer or Categorizer; if the user who have little tagging behaviors and it is hard to get the users " retrieval motivation, we call them the users without motivation.

Porter Stemmer and K-means++

In the existing folksonomy system, most of tags and resources are created by users without restriction, so they are short of semantic precision and standardization, which affect the use of it to a certain degree. In order to reduce these interference factors, we use porter stemmer to deal with these tags.

Porter stemmer has five steps and each step defines a set of rules. To stem a wo rd, the rules are tested sequentially, if one of these rules matched the current word, then the conditions attached to that rule are tested. Once a rule is accepted; the suffix is removed and the control moves to the next step. If the rule is not accepted then the next ru le in the same step will be tested, until either a rule fro m that step is accepted or there are no more rules in that step. And the control passes to the next step. In the last step, the resultant stem is returned by the stemmer. After that, the irregular tags reduce the interference factors to understand and they can help us to improve the quality of retriev ing informat ion.

At the same time, according to the model of the users" motivation, we can get the types of users. Then, we need to deal with the resources tagged by users who have the similar mot ivation and find the similar resources which have been tagged. In this paper, we choose the k-means++ clustering [START_REF]Immune Network Based Text Clustering Algorithm[END_REF].

The k-means++ is an algorith m for choosing the initial values for the k-means clustering algorith m. It was proposed in 2007 by Dav id Arthur, as an appro ximation algorith m for the NP-hard k-means problem-a way of avoiding the sometimes poor clustering found by the standard k-means algorith m. And the k-means problem is to find cluster centers that min imize the intra-class variance, the sum of squared distances from each data point being clustered to its cluster center.

3

The optimized algorithm

According to the knowledge given above, we propose an optimized algorith m with users" retrieval mot ivation in folksonomy system. The detail procedure of the algorith m is shown in Figure 2, and the detail algorith m is shown in Table 1.

Fig. 2. The procedure of the algorithm

Table 1. The optimized algorithm An optimized algorithm with users" retrieval motivation:

Input :a folksonomy datasets,the cluster center k,a retrieved tag t u by user u.

Output:some tags(to user u). for each t j , t j ∈Q; 10) Switch(the t j (user j ) tagging motivation M uj ") 11)

{ case "categoritizers": k-means++(Q " (t j ∈categoritizers)); 12) find(sim max(Q uj ",t j ))→L; 13) tf-idf L, return the top-n to u ; 14) case "describers": k-means++(Q " (t j ∈describers)); 15) find(sim max(Q uj ",t j ))→L; 16) tf-idf L, return the top-n to u ; 17)

case "no-motive users": k-means++(Q " (t j ∈Q)); 18) find(sim max(Q uj ",t j ))→L; 19) tf-idf L, return the top-n to u; 20) deefault: system.out.print("Absence recommender.") 21) end;

There are three modules in this procedure. First, in the module of data collection, we get the data from the internet and some preprocessing will be done to get the more useful data which have less interference factors. When we get the data, we need to remove the error tags. Then, we can reduce the number of the tags which have the similar semantics by using the stemming technique that we introduced above. And then, some relatively good data is selected for the next module, with wh ich we can ensure the effectiveness of the text data and reduce the number of the text data which has the little influence on the results in the experiment. Second part, after we get the relatively good data, we classify the users into different types. According to the model given above, we can get the M" score, the value of orientation of users" motivation, with wh ich we can get a ranked lists of users, where Categorizers rank h igh, and Describers rank lo w. With the two types of users and the tags they have tagged, we can easily find the resources which have tagged by the users with the similar motivation. And this can improve the efficiency of retrieving informat ion when the system reco mmends resources to users. Third part, after we get the types of users, we need to get the smaller range of search resources, we use the k-means++ algorith m to cluster these resources tagged by users who have the similar motivation. A fter the data cluster, we calcu late the similarity between the retrieved informat ion and the clustered data and then return the resources which have the high similarity to the user. But, for users who have litt le tagging behaviors and it is hard for us to get the users " retrieval motivation, we only use TF-IDF algorith m to find the similar resources, and then recommend them to the user.

4

Experime nts

According to the optimized algorithm proposed above, we need to collect the datasets first. We use the datasets downloaded fro m http://www.flickr.co m in our experiments. This datasets has 4 classifications and 3000 docu ments. The classifications contain the following types: Resources, Tags, users, Messages of the photo.

In this experiment, we just use three classifications which are Resources, Tags and User. After data processing in the module of data collection, we get the 89 resources, 2537 users and 8478 tags.

Evaluation Measures

To evaluate the proposed approach, we introduce three measures, precision, recall and F-measure to evaluate the quality of retrieval by different methods, which are defined as follows.

Precision. In the field do main of in formation retrieval, precision is the fraction of retrieved instances that are relevant, and it is also used with recall. The definit ion is:

precision = relevant documents ∩ retrieved documents retrieved documents (6)
Recall. Recall in information retrieval is the fraction of the documents that are relevant to the query that are successfully retrieved. The definit ion is:

recall = relevant documents ∩ retrieved do cuments relevant documents (7)
F-measure. Generally speaking, a good retrieval algorith m should be able to have a higher score in precision and recall. Therefore, we use the co mpro mise value to measure, such as F-measure(β=1), that it indicates the precision and recall are equally important now. The formula is shown:

F β =1 = 2 * precision * recall precision + recall (8)
If F-measure score is higher, it means that this retrieval algorith m is better than the other.

Results and Discussion

Co mpare the F-measure score of three different algorith ms to measure them. In Algorith m 1, we use the traditional collaborative reco mmender algorith m. In Algorith m 2, we add the user motivation theory to the algorithm and use the value of orientation of users" motivation to distinguish the users" type, and then cluster the resources tagged by the users who have the similar retrieval motivation with k-means++ algorithm, and then use the same way as Algorithm 1 to get the results f-measure. In Algorithm 3, d ifferent with Algorith m 2, the value of orientation of users" motivation is not used for distinguishing the users" type, but it is used as an auxiliary value of the calculation of the similarity between relevant the tags and the tags which will be retrieved. Finally, we use the same way as Algorithm 1to get the f-measure of result.

The three algorithms can be regarded as the three models of the tag reco mmender systems. Then we choose the three types of users, Describers, Categorizers and users with no motivation. Let the three models recommend the required source retrieved by three types of users respectively. For the results the models reco mmend to the users, we take the average of the results after five times" test in order to reduce the experimental error. We can see the results fro m Figure3, Figure4 and Figure 5. In Figure 3, the users are all the Describers. At the same time, we can see that the F-measure value in Algorithm 2 and 3 have the higher score than the Algorithm 1 , which means that for the user of Describers, the algorith ms with motivation theory have the better results. In Figure 4, the users are all the Categorizers Meanwhile, and the F-measure value in A lgorith m 2 and 3 also have the higher score than the Algorith m 1, which means that the algorithm with users " motivation have a better result too. In Figure 5, the users are all those without retrieval motivation. So, we cannot use the users" mot ivation as an au xiliary value in Algorith m 2 and 3. For this reason, the three algorithms have the similar results the recommender system gives to the users and the value of F-measure stay the same level intuitively. And then, we random chose a few users to test the optimized algorith m and no longer deliberately distinguish the type of the users. Then, we can see the results from table 2. Fro m the analysis above, we can conclude that in tag reco mmender system, the optimized algorith m with users " retrieval motivation can have the better results than the traditional algorith m without users " retrieval motivation when recommend the resource to the users.

Conclusions

In fo lksonomy system, the trad itional tag reco mmender algorithm [START_REF] Harvey M | Tripartite hidden topic models for personalized tag suggestion[END_REF] need to deal with the resources tagged by all the users. For imp roving the efficiency of the recommender, the users" motivation is added to our tag reco mmender algorithm. When users retrieved the informat ion, their mot ivations were given to the model. Then, we just need to deal with the resources tagged by the users who has the similar motivation, and this need less time just to deal with the more relevant resources, mean while, the accuracy of resources recommend was imp roved. The experimental results show that this algorith m with user retrieval mot ivation can have higher accuracy and stability than traditional retrieval algorithms when recommend the resources to users.

6

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig. 3. Compared the results based on Describers

Table 2 .

 2 The F-measure score(%) results at random

	The F-measure	User1(k=260)	User2(k=260)	User3(k=260)
	score(%)	Tag1	Tag2	Tag3	Tag4	Tag5	Tag6
	Algorith m 1	56.2	57.0	62.4	71.6	46.2	58.2
	Algorith m 2	56.3	57.0	69.1	79.4	53.3	62.3
	Algorith m 3	56.3	57.1	66.1	77.7	65.7	65.5

Acknowledge ment

This work is supported by National Natural Science Foundation of China (grant 61163057), Guangxi Nature Science Foundation (grant 2012jjAA G0063), Open Fund of Guangxi Key Laboratory of Trusted Software (kx201308). The authors would also like to express their gratitude to the anonymous reviewers for providing helpful suggestions.


Guoyong Cai

Libin Peng

Yong Wang

Topic Topic Topic Topic Detection Detection Detection Detection and and and and Evolution Evolution Evolution Evolution Analysis Analysis Analysis Analysis on on on on Microblog Microblog Microblog Microblog *

Keywords: Microblog, LDA model, Topic Evolution, Topic Detection 1. 1. 1. 1.I I I Introduction ntroduction ntroduction ntroduction

bstract bstract bstract: The study on topic evolution can help people to understand the ins and outs of topics. Traditional study on topic evolution is based on LDA model, but for microblog data, the effect of this model is not significant. An MLDA model is proposed in this paper, which takes microblog document relation, topic tag and authors relations into consideration. Then, the topic evolution in content and intensity is analyzed. The experiments on microblog data have shown the effectiveness and efficiency of the proposed approach to topic detection and evolution analysis on Microblog.

users to disseminate/obtain/share information based on relationship among users. Users can set up personal community through WEB, WAP and other client terminals, update the information with no more than 140 words of text, and achieve instantly information sharing. However, the content of microblog is diverse and changing rapidly. It is a challenging problem of how to discover automatically an effective topic and to analyze the evolution of the discovered topic.

Topic is defined as a number of related events caused by a set of seed in Topic Detection and

Tracking [START_REF] Allan | Online new event detection and tracking[END_REF]. The topic model represented by LDA (Latent Dirichlet Allocation) [START_REF] Blei | Latent Dirichlet allocation[J][END_REF] is an important technology in the field of text mining in recent years. LDA model has a good ability of dimension reduction and scalability. It has achieved great success in mining traditional network news topic. Topic evolution is referred to the migration of topic content and intensity over times [START_REF] Chu | Topic Evolution Based on LDA and Topic Association[J][END_REF]. Researches on topic evolution in general are based on LDA model to extract topics, and then the topic evolution of content and intensity are analyzed. However, compared with the traditional network text, Microblog has distinct characteristics, such as a short text (usually less than 140 characters), sparse data, noise data, mixed and disorder content, etc. Besides, there also exist social relations, structural social network information. Therefore, it is not effective to use LDA model for microblog text. An MLDA model is proposed in this paper, which takes microblog document relation, topic tag and authors' relationships into consideration. The topic evolution in content and intensity are analyzed based on MLDA model.

2.Related Related Related Related Works Works Works Works

Due to its good scalability, LDA model, which proposed by Blei in 2003 [START_REF] Blei | Latent Dirichlet allocation[J][END_REF], is extended by many scholars. Researches on topic evolution based on the scalable LDA model are divided into the following three categories:

(1) Continuous time models. The information of time is taken into topic model as a variable to study the topic evolution. For example, a TOT (Topic Over Time) model is proposed by Wang [START_REF] Wang | Topic over time: A Non-Markov Continuous-Time Model of Topical Trends [C[END_REF]. In TOT model, each document is a mixture of topics that is influenced jointly by its time stamp. The main disadvantage of TOT is that it uses the beta distribution to model the topic development trends.

Therefore, for documents that don't release time, it will predict the release date of the document. For documents with given released date, it can predict the document distribution.

(2) Pre-discretization methods. In this type of method, documents are divided into some parts according to the time windows before modeling topics, and then documents are processed and the topic distribution is generated in each time window. Song and etc. [START_REF] Song | Modeling and predicting personal information dissemination behavior[END_REF] proposed a ILDA model (Incremental Latent Dirichlet Allocation) to study the content evolution of a topic and solve ILDA model with Gibbs sampling approach [START_REF] Mark | Latent Semantic Analysis: A Road to Meaning[END_REF]. Online LDA model is proposed by AlSumait [START_REF] Alsumait | On-line LDA: adaptive topic models for mining text streams with applications to topic detection and tracking[C][END_REF], history data are used as the prior distribution of the proposed model and LDA model are used to study topic evolution for the arrived data in each time interval. Hu Yanli and etc. [START_REF] Cui | LDA-based Model for Online Topic Evolution Mining[END_REF] have also implemented the online topic evolution analysis based on online LDA model, but they consider the inter-connection of topic distribution in each time slice.

(3) Post-discretization methods. In this type of method, the affect of time is not considered first.

After topics are extracted based on LDA in the document set, the topics are divided into time slice according to its time stamp. Grillffiths and Steyvers [START_REF] Griffiths | Finding scientific topics[END_REF] have proposed a post-discretization method based on LDA model, they use the intensity of topics in each time slice to indicate the topic trends. idea behind the LDA model is to assume that the words in each document were generated by a mixture of topics, where a topic is represented as a multinomial probability distribution over words [START_REF] Cui | LDA-based Model for Online Topic Evolution Mining[END_REF]. Each document has a specific mixture of topics, which generated from the Dirichlet distribution. The specific idea behind LDA is to assume that each document correspond to the multinomial distribution θ of T topics, each topic correspond with the multinomial distribution ϕ of d N words, θ is the prior of Dirichlet distribution with parameters α , ϕ is the prior of Dirichlet distribution with parameters β . For each word in a document d , topic z is extracted from the distribution θ of the document, and the word w is extracted from the distribution ϕ of topic z .This process will be repeated d N times, then the document d is generated. The generative process of LDA is shown in figure1. There are two parameters need to be inferred in this model, one is the distribution θ of document-topic and the other is the distribution ϕ of topic-word. Since it is difficult to obtain precise parameters, VEM [START_REF] Blei | Latent Dirichlet allocation[J][END_REF], Gibbs Sampling [START_REF] Mark | Latent Semantic Analysis: A Road to Meaning[END_REF] and Expectation propagation [START_REF] Minka | John Lafferty. Expectation-Propagation for the Generative Aspect Model[END_REF] are often applied to estimate the parameters. Gibbs Sampling has been widely used for its simple implementation.

3.Topic Topic Topic Topic Evolution Evolution Evolution Evolution Analysis Analysis Analysis Analysis on on on on Microblog Microblog Microblog Microblog

Topic Topic Topic Topic Discovery Discovery Discovery Discovery Model Model Model Model ----MLDA ----MLDA ----MLDA ----MLDA model model model model

Compared with other texts, microblog texts have special symbols, such as "@"、"# " and "retweet".

@ indicates the author's relationship of a microblog post. For example, a message "@Sandy Congratulations, you get a good job." and another message "@Sandy Can you teach me some IT knowledge used in a work". When considering the author's relationship, we can set a connection between these two seemingly unrelated microblogs and consider that "job" in the first message is related to "IT" in the second message. # indicates topic tag in a microblog. For example a message "Sunyang , come on! #Olympic Games#". If considering the topic tag, "Sunyang" and "Olympic Games" are related. "retweet" indicates microblog documents' relation. For example, a message "Chinese Dream, retweet @Sandy the best popular new vocabulary …". It is difficult to analyze the specific meaning for "Chinese Dream", but compared with the original microblog, we know that "Chinese Dream" is a kind of "new vocabulary".

An

) | ( ] ) | ( ) | ( [ ) , , , , | ( 1 1 α θ α θ α θ π α α α θ π π - - = (1)
If there exists a symbol "@" in microblog, the value of c (2) For each topic , d i z , we judge document relation with "retweet". If there exists "retweet", then , ~( )

π is 1, otherwise c π is 0. If
d
π is 1, else c π is 0. r α
Decide whether it is a retweet message

Algorithm Algorithm Algorithm Algorithm Implementation Implementation Implementation Implementation

We apply Gibbs sampling to estimate the parameters ϕ θ , . Gibbs sampling is one simple realization method of MCMC (Markov chain Monte Carlo), which is a fast and effective algorithm for estimating the parameters [START_REF] Blei | Visualizing Topics With Multi-Word Expressions[END_REF]. Gibbs sampling is based on posterior distribution of words given a topic

) ( ) , , , (.) ( ) , ,.
( | , , , ) *

w d i j i j i i d i d i j d i d n n P z j z w n N n N β α α β β α - - - - - + + = ∝ + + (3)
Where, ( ) , w i j n -is the word counts assigned to topic j and w .

+ = + (4)
Where,

) ( d j n
denotes the number of words that assigned to topic j in document d . denotes the number that word w is assigned to topic j . (.) j n is the number of words that assigned to topic j .

The Gibbs sampling procedure of MLDA is implemented and shown in Fig. 3. The Gibbs sampling algorithm consists of three parts: initialization, burn-in and sampling.

Algorithm: MLDA_Gibbs Sampling Input: ,,,,t c T V Output: associated topic Z , the distribution θ of document-topic, the distribution ϕ of topic-word. The evolution of topic reflects in two aspects. First, the topic intensity changes over time. For example, the topic is the Olympic Games which take place every four years, which are active for Olympic years, other years is low. On the other hand, the topic content changes with the passage of time. For example, on the eve of the Olympic Games, when we pay more attention to the Olympic preparations, on the middle of Olympic, gold medal topics will be focused. In the end of Olympic Games, more attention should be paid to the summary and inventory of the Olympic Games. We use the distribution of topic j with time t to define the intensity of topic. ,

β λ α α α , ,

//initialization

) ( d j n =0, ) ( . d n =0, ) ( w j n =0, (.) j n =0; for :all document ] , 1 [ D d ∈ do for: all word ] , 1 [ d N n ∈ in document d do , ~( ) d j dRT z Multiomial θ //computed
1 t t j d j t d D D δ θ ∈ = ∑ (5)
Where

t j
δ is the intensity of a topic, t D is the number of document,

j d , θ is the distribution of topic j .
The content of topic evolution is characterized as the degree associated with topics. The differences of the distribution of two topics is described with KL(Kullback-Leibler) distance [START_REF] Hu | OLDA-based Method for Online Topic Evolution in Network Public Opinion Analysis[J][END_REF]. The smaller the difference is, the higher degree of the two topics will be associated. Assuming that the probability distribution of topic A is

∑ = = N i i i i B A A B A D B A KL log ) || ( ) , ( (6)

4.Experiments Experiments Experiments Experiments

The experimental data are captured from a large microblog site named Sina microblog. Through API provided by Sina, about 8 million original microblog data from July 1 th 2012 to August 29 th 2012 are captured. We mark five topics, i.e., "London Olympics", "heavy rains in Beijing", "Price War", "Diaoyu Island Event", "The Voice of China". In order to save space or to speed up sampling, the punctuation and stop words in the original microblog dataset must be removed before experiments. We complete this preprocessing work by using a punctuation list and a stop words dictionary. We analyse the topics from July to August in 2012. The different change of the intensity of topics will be calculated in different times, which is divided into eight time slice by each a week. The intensity of each topic is shown in figure 3.The ordinate represents the intensity of the topic at each time slice, which is calculated with equation 5.

Figure 3 shows us that the intensity of topic 1 is higher than other topics during each time slice.

This demonstrates that the influence of topic 1 is higher and is a hot topic during the two months.

Besides, for each topic, the intensity of topics will change with time. This shows that each topic will go through a evolutional process that is consistency with reality.

Comparisons Comparisons Comparisons Comparisons of of of of algorithm algorithm algorithm algorithm performance performance performance performance

We conduct a comparative experiment between MLDA and LDA, which is a baseline model in the field of topic modeling. The metric Perplexity [START_REF] Blei | Dynamic topic models [C[END_REF] is a standard measure of performance for statistical models, which indicates the uncertainty in predicting a single word; the model with lower value is better in performance. Perplexity is defined as follows: Perplexity is used to measure the performance of LDA and MLDA under the same hyperparameters setting, and the result is shown in figure 6. Figure 6 show that the perplexity of MLDA is always lower than LDA, which show that the performance of MLDA is much better than LDA.

Figure 6 the performance of MLDA and LDA

5.Conclusion Conclusion Conclusion Conclusion

An MLDA model is proposed in this paper, which takes microblog document relation, topic tag and authors' relation into consideration. Based on MLDA, the topic evolution in content and intensity is studied. The experiments on microblog data have shown the effectiveness and efficiency of the approach to depict topic evolution. In future work, we will improve efficiency of this algorithm.

Besides, the scalability of the proposed model will be further investigated.

  LDA LDA LDA model model model model LDA model is a three-layer probability model. It consists of word, topic and document. The key

Figure 1

 1 Figure 1 LDA model

Figure 2 ( 1 )

 21 Figure 2 Bayesian network of MLDAThe description of generative process in MLDA is as follows:(1) For each document d D ∈ , if there exists "#topic#", we compute ) ( ~td d a Dri θ θ = . If

3 )zNπ

 3 For each word , d i w in a document, firstly, we choose a topic , ~( ) d j d z Multiomial θ ; and then we choose a word with , ~( ) The i th topic in document d , d i w The i th word in document d D The number of documents T The number of topics d The number of words c Bool parameter, decide whether there exists a @ message. If so, c

.

  Repeated iterations on the probability distribution, the parameters are derived. The process is computed with equation (3).

(

  the counts of words assigned to topic j in document d .( ) ,.d i n -is the counts of words assigned to topic j . All counts do not include the current iteration. After iteration finished, we can estimateθ andϕ from the value z using equation (4).

  words appeared in document d .

  the new assignment Z to the term t for word // increment counts and sums If(finish sampling) then Output ϕ θ , // according to equation 4.

Figure 3 .

 3 Figure 3. Gibbs sampling algorithm

  distance between topic A and B is computed as follow.

4.1 4 .1 4 .1 4 . 1

 4441 Topic Topic Topic Topic Discovery Discovery Discovery DiscoveryEffectiveness experiments are conducted on dataset mainly to examine the performance of MLDA.The parameters are set up with words of each topic are extracted by MLDA models. The results are shown in table 2.

Figure 3 the intensity evolution of topics 4 . 3 4.3 4 .3 4 . 3

 43443 Figure 3 the intensity evolution of topics

Figure 4 the KL distance of topic 1 Olympic

 41 Figure 4 the KL distance of topic 1

M

  is a test set with m documents, m w and m N indicate the observed words and number of words in the test document respectively.

Table 2 .

 2 The list of representative words for each topic.

	topics	Most representative words
		Olympic Games, participation, London,
	Topic1: London Olympic
		champion, gold metal
		heavy rains, disaster, rescue, flood protection,
	Topic2: Heavy rains in Beijing
		emergency
		Sunning, jingdong, price war, E-commerce,
	Topic3: Price War
		fund
		Diaoyu Island, Japan, China, Sovereignty,
	Topic4: Diaoyu Island Event
		protection
	Topic5: The Voice of China	Voice, China, music, pleasant music, jury
	4

.2 4.2 4.2 4.2 Intensity Intensity Intensity Intensity evolution evolution evolution evolution of of of of Topics Topics Topics Topics

* This work is supported by the NSFC(#61063039), Guangxi Key Lab of Trusted Software(#kx201202)


Yuexin Sun
email: sunyuexintc@163.com

Huifang Ma
email: mahuifang@yeah.netjmhuizi0424@163.com

Meihuizi Jia

Wang Peiqing

An efficient microblog hot topic detection algorithm based on two stage clustering

Keywords: Probabilistic Latent Semantic Analysis, Topic detection, Microblog, K-means

Microblog has the characteristic of short length, complex structure and words deformation. In this paper, a two stage clustering algorithm based on probabilistic latent semantic analysis (pLSA) and K-means clustering (K-means) is proposed. Besides, this paper also presents the definition of popularity and mechanism of sorting the topics. Experiments show that our method can effectively cluster topics and be applied to microblog hot topic detection..

Introduction

Nowadays, Micro-blogging is increasingly extending its role from a daily chatting tool into a critical platform of spreading real-time information during emergencies. It provides a short and convenient way for users to express and share their attitudes instantly. Since it enables users to acquire near real-time information, it has become a major source for producing and spreading hot events on the internet. However, acquisition of information regarding real-time hot events and news poses significant challenges due to the extensive irrelevant personal messages and unstructured short texts. Recent research of hot topic detection started to focused on the micro-blog [START_REF] Sakaki | Earthquake shakes Twitter users: real-time event detection by social sensors[END_REF][START_REF] Chen | Towards Topic Trend Prediction on a Topic Evolution Model with Social Connection[END_REF][START_REF] Chen | User-defined hot topic detection in microblogging[END_REF]. Vector space model is always adopted as the way to represent microblog [START_REF] Salton | The SMART retrieval system-experiments in automatic document processing[END_REF]. A great amount of efforts have been made for microblog hot topic detection in a semantic analyzed way. Some people extend short texts information by Knowledge Base, such as WordNet or Wikipedia [START_REF] Sahami | A web-based kernel function for measuring the similarity of short text snippets[END_REF][START_REF] Yih | Improving similarity measures for short segments of text[END_REF][START_REF] Zhai | An algorithm for semantic similarity of short text based on WordNet[END_REF][START_REF] Banerjee | Clustering short texts using wikipedia[END_REF]. In addition, topic model is also an effective way for microblog hot topic detection [START_REF] Ma | Microblog Online Event Analysis Based on Incremental Topic Model[END_REF]. However, all of the above methods take advantage of external knowledge and they fail to consider some prior knowledge for microblogs.

In this paper, we formulate the task of microblog hot topic detection as a twostage clustering algorithm based on probabilistic latent semantic analysis (pLSA) [START_REF] Hofmann | Unsupervised learning by probabilistic latent semantic analysis[END_REF] and K-means [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] clustering (K-means). Furthermore, the definition of popularity(hotness) and mechanism of sorting of the topics are presented.

The basic outline of this paper is as follows: Section 2 presents details of our approach. The experiments and results are given in Section 3. Lastly, we conclude our paper in Section 4.

The Proposed method

In this section, we will present the details of our algorithm for building topic model and hot microblog acquisition.

Basic Idea

The conservative pre-process approach is taken to be the first step, which means that the microblog will be filtered and segmented first. Then the stopwords are eliminated and the traditional Chinese are translated into simplified Chinese. All terms occurring less than 20 times are removed. Specifically, pLSA model is first applied on the traditional term-document matrix to estimate two matrix denoting the distribution of topic under certain document and distribution of term under given topic, respectively. Then we multiply these two matrixes to obtain the word-document matrix with latent semantics, which becomes the input for the next stage clustering algorithm. We sort the probability of a document under each topic, the biggest one will be regarded as the centre for Kmeans clustering. Figure 1 shows the entire algorithm follow:

Our Approach

Pre-process of microblogs a)

. For microblog which is directed at another user, as denoted by the use of the @username token, we believe that the content of this field has little to do with real content. Therefore we just simply delete this field. b). For microblog that contains "RT @" field, these microblogs are produced by someone else but the user copies, or forwards, them in order to spread it in his network. This is not treated as the real content. So we just keep the real content of this microblog. c). For microblog that contains "# certain topic (user) #" microblog, the field can be considered as the noise, we just delete it. d). We take advantage of stemmer for segmentation and remove the stop words at the same time. The stop list is based on 1028 stop words provided by sina.

pLSA parameter estimation and K-means Clustering

We first use TF*IDF [START_REF] Salton | The SMART retrieval system-experiments in automatic document processing[END_REF] to represent the importance of each word, and the word-document matrix is constructed. pLSA is then used to estimate the parameters: distribution of topic under document d i P(z k |d i )and distribution of term under topic z k P(w j |z k ).

pLSA uses a generative latent model to perform a probabilistic mixture decomposition. This results in a more principled approach with a solid foundation in statistical inference. More precisely, pLSA makes use of a temperature controlled version of the Expectation Maximization algorithm for model fitting, which has shown excellent performance in practice. The word-document matrix with semantic information is then obtained by multiplication of these two matrixes. This matrix also becomes the input for K-means clustering.

K-means clustering aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster. This algorithm is sensitive to the predefined centre. In our algorithm the biggest probability of a document under each topic serves as the centre for Kmeans clustering.

We also define the heat [START_REF] Sun | Chinese microblog hot topic detection and tracking technology[END_REF] of microblog:

( )

_ _ log 1 i i i i HT N com N rel fan = + + + (1)
HT i represents the heat of the microblog i, N_com i is the comment number of microblog i. N_rel i is the forward number of i. fan i is the fans number of the microblog. We therefore can sort the hottest microblog in each topic by its heat.

Experiments

Data corpus

Two thousand two hundred and twenty one microblog entries were collected in two phases. Both the training and test data of microblog entries are manually collected from sina microblog sites during 2011-11-01 to 2011-11-03 and 2013-03-10, respectively. The training dataset is composed of 37 topics.

Two baseline methods K-means and LSA+Kmeans are adopted to verify effectiveness of our model. As for the parameters of our approach, to give these algorithms some advantage, we set the number of clusters equal to the real number of microblog clusters.

The experimental results and analysis

The experiments include three parts: 1) Overall evaluation of our model by comparing with that of 2 other algorithm; 2) Clustering results of our method; 3) Hot topic Visualization. We run our algorithm on the training data. We have run 5 times for each evaluation, and the average performance scores are reported. Four clusters with largest number of documents are selected. To evaluate the performance of our Methods Precision Kmeans 0.55 LSA+Kmeans 0.65 Our method 0.72 algorithm, we use precision [START_REF] Sebastiani | Machine learning in automated text categorization[END_REF] as our measures. Table 1 and Table 2 show the results.

Overall Evaluation

From the experimental results, we can see that our method is superior to the former two algorithms in terms of precision. This is because the traditional VSM method simply considers the term occurrence information while ignores the semantic information, therefore it has difficulty in represent high dimensional and sparse vector. LSA performs decomposition of matrix with some negative numbers. All these characters are not in conformity with the microblog' feature.

Clustering Results

Figure 2 demonstrates the clustering results on the test data. In the figure, each colour stands for one topic. Since the coordinate system is two-dimensional, we select each microblogs' two largest vector dimensions to show the cluster results. We can see that the clustering result is basically in conformity with clustering standard.

Hot topic Visualization

We choose the hot topic with highest HT value from five clusters with largest number of microblogs. Table 3 lists the five hottest topics on the test data, while table 4 lists terms with highest probabilities for each topic. It is clear that our method is able to discover meaningful topics with much better readability and the experimental results are consistent to our intuition.

Conclusion

In this paper, we have described a new algorithm for hot topic detection on microblogs. While it is based on two stages clustering, the second stage Kmeans can fully take advantage of the prior information provided from the first stage pLSA. We also define the concept of topic hotness. In the future, we will take users' role into consideration.

Figure 1 .

 1 Figure 1. Algorithm process

Figure 2 .

 2 Figure 2. Cluster result

Table 1 .

 1 Performance of Precision on training datasets of our method

	Topic	Correct cluster	Incorrect cluster	Precision
	1	25	12	0.68
	2	22	13	0.63
	3	33	6	0.85
	4	26	10	0.72

Table 2 .

 2 Performance of Precision on training datasets of 3 methods

Table 3 .

 3 hot topic with highest HT value from five clusters China's government would manage melamine by the real-name system. It's estimated that Mengniu is related to melamine. Anyway, we had better not drink milk. We should not believe the words that our management is good.

	Topic	Microblog
	1	Happy New Year 2013!
		(祝大家 2013 年新年快乐! 欢度元旦节!)
	2	Since many countries' policies are difficult to change, China's Internet should find rea-
		sons from itself.
		(中国互联网应从自身找原因,很多国家政策是难改变的,只能适应。)
	3	In order to implement the value of its currency reduction goals, zero interest rate policy
		guides the domestic capital to high interest rates countries by the means of carry trade.
		(零利率政策主要借助套利交易,引导境内资本流向高利率国家,实现降低本币
		汇率的目标。)
	4	Luo Yufeng is recently named the most shameless person in China by CNN, who has
		defeated Yang Erche Namu and sister Furong, following Xiao Shenyang who has
		achieved the China's most vulgar person. It seems that Americans appear to be fair on
		the issue of shame.
		(继小沈阳被美国国家有线广播电视台 CNN 评为中国最低俗的人之后,最近罗玉
		凤凤姐一路打败杨二车娜姆和芙蓉姐姐,被 CNN 评为中国最不要脸的人,看来美国
		人在判断不要脸这个问题上非常之公正。)
	5	Yesterday, (昨天国内高调报道中央要以实名制管理三聚氰胺。虽然不知道蒙牛到底出了什么
		事,但估计又是三聚氰胺惹的祸。反正牛奶是再也不能吃了。绝不能相信说管理
		得很好的话。)

Table 4 .

 4 Terms with highest probabilities for each topic

	Topic	Keywords
	1	New Year	Wish	Promised	Adjust	Notice
		(新年)	(愿望)	(许下)	(调整)	(公告)
	2	Quantization	Lead	Carry out	Policy	domestic currency
		(量化)	(引导)	(实施)	(政策)	(本币)
	3	World	Currency	Loose	Risk	Capital
		(世界)	(货币)	(宽松)	(风险)	(资本)
	4	Entertainment	Luo Yufeng	Choose	Vulgar	Shameless
		(娱乐)	(凤姐)	(评为)	(低俗)	(不要脸)
	5	Mengniu	Find	Report	Milk	Confiscate
		(蒙牛)	(发现)	(报导)	(牛奶)	(查收)

Acknowledgement This work is supported by the National Natural Science Foundation of China (No. 61363058, 61163039), Research Foundation of Education Department of Gansu Province (No. 2013A-016), Youth science and technology support program of Gansu Province(No.145RJYA529).


Dapeng Zhang

Xiang Ji

Xinsheng Wang

An AUML State Machine Based Method for Multiagent Systems Model Checking

Keywords: Model Checking, MCMAS, AUML state machine, ISPL, Multi-agent System

This paper firstly proposes a Multi-agent System Model Checking Framework, which is based on AUML (Agent Unified Modeling Language) state machine model and temporal logics of knowledge and provides a method using AUML state machine for Multi-Agent Systems formal modeling. Then a method for the conversion from AUML state machine formal description to ISPL language is proposed. Finally a simulation is accomplished with the conversion tool AUML2ISPL.

Introduction

Currently, agent and Multi-agent has become the focus of the research in artificial intelligence. Multi-agent System has been used more widely in computer and related fields than before. So it has become a very urgent issue to ensure the correctness and reliability for Multi-agent System. As a method of automatic verification for finite-state system, model checking [START_REF] Zhang Wenhui | Model Checking: Theories, techniques, and applications[END_REF] has drawn wide attention. The basic idea for model checking is to establish finite state models for the system that is to be verified, using some logical formula to describe the specification properties of the system which are expected, then put them into model checking tools to verify whether the model meets the specification properties by automatic checking. Model checking has a high degree of automation implementation and it can provide a counter-example path when the system does not meet the specification properties. So it can decrease the workload for researchers and it is also convenient for researchers to trace the error path for the system.

Related Work and the issue

Since the idea of model checking has been proposed, many researchers have paid a lot of attention for the consistency of model checking for Multi-agent System. Dong [START_REF] Dong | Model checking UML statecharts[END_REF] has promoted a method about formal description of state machine use UML to defining the extension hierarchical automata and the label transfer system, then verified the correctness of the UML state machine model based on this method. Luo [START_REF] Luo | Automatic Detection Method for Web Services Feature Interaction[END_REF] has provided a method for automatic detection of the interaction Web service, and modeled the MTELG by 5-tuple, then proposed a rule to make the 5-tuple formal description automatic convertion to the input language for the model checking tool MCTK. Du [START_REF] Du | UML consistency and test case generation based on model checking[END_REF] has promoted a method for UML consistency and tested case generation based on model checking. Abdel and Gherb [START_REF] Gherbi | Consistency of UML/SPT Models[END_REF] have provided a consistency test framework for UML/SPT model. This framework gives a method to verify the model state chart for UML/SPT, Which includes the consistency of syntax and semantics. For Multi-Agent System, although UML is a popular modeling language, it can't describe the agents' knowledge and their collaborations well. Therefore scientists have extended the UML language and proposed a language for modeling Multi-agent System, which is called AUML (Agent Unified Modeling Language). Although scientists have developed a number of model checking tools, such as MCK [START_REF] Gammieand | Mck: Model Checking the logic of Knowledge[END_REF], MCMAS [START_REF] Lomuscio | MCMAS: A model checker for multi-agent systems[END_REF] and MCTK [START_REF] Kaile | The Interpreted System Model of knowledge, belief, desire and intention[END_REF], the input language for those tools is incompatible with UML, especially AUML.

A Model Checking framework for Multi-Agent Systems

In order to solve the problem proposed in section 2, we proposed a Multi-agent Systems Model Checking Framework that is based on AUML state machine model and temporal logics of knowledge [START_REF] Bin | Symbolic Model Checking Algorithm for Temporal Epistemic logic CTL*[END_REF]. Fig. 1 shows this framework.

In this framework, we choose MCMAS as the Model Checking tool. It is because MCMAS is more efficiency, which is based on the logic of CTLKD-A DC , It can verify the knowledge for Multi-agent System, and it has the ability to verify the correctness behaviors of agents and the collaboration among agents for Multi-agent System. MCMAS uses ISPL (Interpreted Systems Programming Language) [START_REF] Fagin | Reasoning about Knowledge[END_REF] as the input language.

This Model Checking framework can be achieved in the following steps:

(1)Symbolic the Multi-agent System model to AUML state chart.

(2)Formalize the AUML state chart into AUML state machine formal description.

(3)Making a syntax conversion between AUML state machine formal description and the ISPL language.

(4)Formalized system specifications into CTLKD-A DC formulas, respectively put the CTLK-A DC formulas and the ISPL description that the third step obtained into MCMAS to check whether this model satisfied the formulas. The conversion from AUML to ISPL language Here we decompose the description of state transition for AUML state machine, and give protocol description and evolution description for ISPL respectively. Finally we propose a conversion algorithm between AUML state machine and ISPL language. The description of protocol is represent by protocol functions: protdef::= Protocol : protdeflist. Here protdef is composed of a condition Protocol and a list of executable actions protdeist.

The evolution is represent by evolution functions: evline::= boolresult if gboolcond. Here each evolution function is composed of a group of boolresultes and the preconditions for evolution gboolcond.

The conversion algorithm is given in Algorithm 1.

Simulation

The state machine formal description for transmission system

The bit transmission system [START_REF] Raimoudi | Model Checking Multi-Agent Systems[END_REF] contains two agents (Receiver, Sender), which is shown in Figure 2. One protocol to achieve communication is as follows: S immediately starts sending a bit to R, and continues to do this until it receives an acknowledgement from R. R does nothing until it receives the bit. Then it sends acknowledging to S. S stops sending the bit to R when it receives the first acknowledgement from R, and the protocol terminates. We encode each agent for the bit transmission system in AUML state machine formal description respectively.

Here we give part of each agent encoding result in AUML state machine formal description.

Specification Verification

We use the CTLK-A D,C formula to formalize the specifications of bit transmission System. It can describe the correctness of actions and the knowledge for the Agents. The specification is usually based on system requirement. Here we manually input the following specifications.

1、 E((bit0 or bit1) U recack); 2、 EF(EG(recbit and !recack)); 3、 AF(recack); 4、 AF(recbit -> AF (recack)); 5、 AF(recbit -> K(Sender,K(Receiver,bit0) or K(Receiver,bit1))); Formulas 1-4 are CTL formulas and they can describe the correctness actions for agents. Formula 5 is CTLK-A D,C formula and it can describe the reasoning ability for agents. For example, formula 1 means if agent Sender sends message, it can get the acknowledgement. Formula 5 means it is always true. If an acknowledgement is received, then the sender knows that the receiver knows the value of the bit.

Simulation

We realize the conversion tool AUML2ISPL according to algorithm 1. Then we put the whole AUML state machine formal description for bit transmission System into this tool, and get the conversion result as Fig. 2 shows. We put the conversion result and the system specifications into MCMAS and run a simulation. The model checking result shows that out modeling is correct.

Conclusion

This paper uses AUML language for the modeling language of Multiagent System, proposes a method for AUML state machine formal description and the conversion algorithm from the AUML formal description to ISPL, and the conversion tool is realized. Simulation shows that out method is feasible.

Fig. 1 .

 1 Fig. 1. The Model Checking framework for Multi-agent System

4

 4

Fig. 2 .

 2 Fig. 2. The conversion result from AUML2ISPL

  Transition description is the instance of the connection of two states. The rules consist of the triggered state transitions preconditions and the results after transitions. The preconditions variable assignments for the state before the state transition and the other agent actions that triggered state transition (represented by the message receiving events), while the results include variable assignment after state transition and the agent collection that other agents receive messages from. Their syntax is described below.

				: ≜
	≜		≜	:	;		:			;		:
	≜	≜ ′ ′; ′ ′; ′ ′; ′ ′; ′ ′ ; ; ; ≜ ; ; ;
	Multi-agent System Model					System specifications
				Symbolic
	Formal description AUML state chart The formal description for AUML state machine ≜ : ; ≜ ≜ : ; ≜ : ; ≜ Syntax conversion ≜ : ; :	:	:	Temporal epistemic logic ; : formulas :
	4.2 The conversion from AUML state machine formal description to ISPL language
		≜ ≜	:	≜	;	:	:		;	;	:	:	;
		≜	≜
	≜			:	;				:		;

4.1 The formal description of AUML state machine

AUML state machine model is very important. It can reflect specific circumstances from the interaction of agents. We extend the AUML state machine description syntax in reference

[START_REF] Zhao | Research on Agent Unified Modeling Language[END_REF]

. Firstly we add the observed variable into AUML state machine description. Secondly we redefine the transition rules. The syntax for AUML state machine description is as follows.

MCMAS

Formal description

  For the Sender, its state is expressed by two variables: bit and ack. An emulation type bit encodes the value of the bit the Sender wants to send, which consists b0 and b1. Ack is a boolean variable encoding whether or not an ack has been received from Receiver. If the Sender receives the ack, ack equals true. The actions collection for Sender is expressed by Actions which consists sb0,sb1 and noting, respectively indicating the value of the bit the Sender sends. There are two initial state situations for the Sender: transmit b0 or transmit b1. Here we encode one state transition for Sender as follows.

	Transition = S00, S1; rule : Rule; Cdt = { boolformula: b0 }
	Agent : Environment, Receiver; Action : ( Receiver.Action = sendack and Environment.Action = R )
	or ( Receiver.Action = sendack and Environment.Action = SR ); Rst = {(b0, ack = false) }; { agent: Receiver, Environment } For Receiver, one enumeration variable is declared for the agent,
	representing whether the bit has been received or not and the value
	it's received, the collection of enumeration variable is {r0,r1,empty}. Algorithm 1 conversion from AUML state machine formal description The collection of actions is {sendack,noting}. Sendack indicates Re-to ISPL language 1. Input: StateChartModel ceiver send an acknowledgement to Sender.noting indicate Receiver don't send anything. Here we encode one state transition for Receiver 2. Output: Protocol, Evolution as follows. 3. For each transition ∈ StateChartModel.transitions Transition = R00,R0;rule:Rule; 4. if transitions.source = state , then protdeflist = protdeflist + ' ' Cdt = { boolformular:empty }; +transition.rule.act.name + ','; Agent:Sender , Environment; 5. For each boolformula ∈ state.boolformula,order protocol = protocol + Action:( Sender.Action = sb0 and Receive.state = R00 and Envi-' ' + boolformula.vas.name + ' ' + relation + ' ' + String (boolformula. vas.value) + ' and '; ronment.Action = S ) or ( Sender.Action = sb0 and Receiver.action = noting and Environment.Action = SR ) 6. Add protdef into Protocol; 8. Output protocol; 7. For each transition ∈ StateChartModel.transitions Rst = { boolformula: r0 }; { agent: Environment, Sender }
	9. For each vasassign ∈ transition.rule.result. vasassign,order boolre-
	sult = boolresult + '( ' + vasassign.vas.name + ' = ' + String
	(vasassign.value) + ' ) ' + ' and ';
	10. gboolcond = ' if ' , for every boolformla ∈ transition.rule. condi-
	tion.boolformula , order gboolcond = gboolcond + '( ' + boolformu-
	la.vas.name + ' ' + relation + ' ' + String(boolformula.value) + ' and '; 11. gboolcond = gboolcond + transition.rule.condition.action + ' )';
	12. evline = boolresult + gboolcond; 13. Add evline into Evolution;
	14. Output: Evolution

Acknowledgements

This work is supported by the Natural Science Foundation of China (No. 61303129) and Open Foundation of Guangxi Key Laboratory of Trusted Software (No. 201211)


Youzhen Han

Shifei Ding
email: dingsf@cumt.edu.cn

Research and Application Analysis of Feature Binding Mechanism

Keywords: feature binding, vision perception, perceptual learning, synchronous neural oscillations, γ-band oscillations, cognitive neuroscience

In order to recognize the object of the external world, brain need to integrate the information of different cortical areas, then form a complete world. And binding problem study on a process to percept a complete object by integrating information, which scattering on different cortical areas. As a central problem of cognitive science and neuroscience, the concept of feature binding is becoming to the focus of consciousness argument. At the beginning of this paper, we introduced the concept, characteristics and theory source of feature binding. And according to the main theoretical research methods of this mechanism, combining the latest advance at home and abroad, we made a systematical review of the research situation of feature binding problem applying in perceptual learning. At last, we pointed out the key point of the further study, which may be refined research of bundled brain mechanism on different cognition process and systematical study of general bundled brain mechanism.

Introduction

The so-called binding problem is to study a way, integrating the information scattering on different cortical areas to percept a complete object. This theory supports rich theoretical and experimental bases for the research of image understanding based on visual hierarchical perceptual mechanism. Thereby, the research on the cognitive process and practical application of feature binding mechanism has an important theoretical breakthrough and application value. This paper attempts to outline the principle theoretical bases, and make a more systematic review about the research on the binding problem and the functional relations of cognition. We hope to raise the domestic scholars' concern in this field.

The organizational structure of this paper is as follows: after outlined the basic theory of feature binding; we introduced the origin and progress of binding mechanism, and proposed the further research direction, in section 2; in section 3, we introduced the current main theory, including the feature-integration theory, neural synchronous activation theory and bundled neural network model; section 4 mainly introduced the crucial effect of binding mechanism in the cognition process, concretely include distinguish perception, the selection of perceptual information, the memory and consciousness wakeup etc.; at last, in conjunction with our own experience in the research, we made a prospect of the progress of binding mechanism.

Research Situation of Binding Mechanism

There is a long history of the exploiting of cognition; our ancestors already have thinking about the origin and nature of humans' recognition, long time ago. Limited by the level of science, the knowledge of brain is mainly stay on the observation and guesses, lacking the study of the brain's internal theory.

Until 20th century, with the breakthrough of neuron anatomy, neurophysiology and electrophysiological processes of neuron, people have a deeper understand of the structure and the basic unit of brain.In 1999, Riesenhuber and Poggi [START_REF] Riesenhuber | Hierarchical models of object recognition in cortex[END_REF] proposed a standard quatitative model based on visual perception mechanism and visual feature computering, their theory has the error-tolerant about the location, size and shape, this give people a quantitative mathematical understanding of this bio-inspired model. Shi Zhongzhi et al., based on PCNN, proposed a computering model of feature binding-Bayesian Linking Field model, research on the feature binding in visual perception. Since the PCNN extremely close to the process method which used by biological visual cortex, many scholars improved PCNN itself and have imposed a lot of modified PCNN model (Zhan et al. 2009, Huang and[START_REF] Huang | Multi-focus image fusion using pulse coupled neural network[END_REF] through analyzing this model, and made it performing excellent properties.

Main Approaches of Feature Binding

There are many theories about binding mechanism. Inside, the feature-integration theory of cognitive psychology, synchronous neuronal activation theory which influential in neuroscience and also called temporal synchronization theory, and recent years proposed bundled neural network model are some most typical theories.

Feature-integration Theory

Treisman's Feature-integration theory tries to use selective attention mechanism of visual space -the attention window to explain the feature binding problem [START_REF] Bouvier | Feature binding signals in visual cortex[END_REF]Treisman 2010, Di Lollo 2012). The theory considers the features from the parallel processing of early stage to the late integration are realized through the spatial attention model. The model includes a position main-map and a set of independent feature-maps. The position main-map is used for registering the location of the object, but not understands the features of that location. The feature maps mainly include two types of information: one is the "flag", which is used to mark whether the feature is existed in somewhere of the scope; the other is about some implicit information in the feature space arrangement. Every feature detector in feature map connected to a unit of main map. After established the unified object representation, the stored template can be matched and recognized, and the related behavior can also be completed.With further research, people realized that there are three deficiencies in the traditional feature integration theory : (1) a traditional feature binding is measured through conscious report, there is no use of unconscious implicit indicators; (2) all are inspected according to the results of immediate report, there is no inspection based on the results of the memory report; (3) the information involved only biting characteristics and location, did not involve the bundle between behavior and perception. These studies are more significance to the general bundling mechanisms.

Synchronous Neuronal Activation Theory

Synchronous neural activation theory (temporal synchronization) is currently considered the most influential binding theories. This theory is that, feature binding based on the synchronization activates neurons, realization through the synchronization activation of neural activity (Singer andGray 1995, Von Der Malsburg 1994). The neurons which are characterization of the same object or trajectory can activate the corresponding behavior in time synchronization to the millisecond. And this synchronous activation is not generated in charge of different cells or between cells. This instant synchronous activation is the key of binding mechanism. Synchronous activation can make selective mark to the neuronal that are responsible for encoding, and distinguish from other objects' activated neuronal responses. This highly selective temporal structure that allows different cell populations in the same neural networks activates synchronously and differentiates from each other. In addition, time-based synchronization binding also serves as a mechanism of selecting next processing object. Because of accurate synchronous activation, the specific content become a desired activation result, and make other brain neurons perceive such a result. These selectively activated neurons will complete binding operations in different regions , and make this activation model in the neural network get the further process. This theory is that the binding is accomplished by the synchronization of neural activity (Singer andGray 1995, Von Der Malsburg 1994).The neural basis of time synchronization is the connection of the cells which react to the features stimulating in senses at the same time. The features may be bound quickly by the connection through the accurate millisecond time synchronization and spatially parallel manner. This mechanism has the advantages of low-performance requirements to the functional structure, high flexibility and adapt to a wide range.

The Neural Network Model of Binding

The neural network model of binding was developed by Watanabe, Nakanishi and Aihara [START_REF] Watanabe | Solving the binding problem of the brain with bi-directional functional connectivity[END_REF]). The model is composed of a primary map (primary map) and two advanced modules. Two modules are responsible for two different characteristics in the primary map, and each module is divided into three different levels, between all levels are pair-wise two-way connected. The external representation of the object, it is represented by the "overall dynamic cell collection" which are distributed in the primary map and two advanced modules. The details of the information are encoded in the main map, and rough, complex feature information is characterized in the two advanced modules. Feature binding is completed in this 'overall dynamic cell clusters'.

The bases of the model are "functional links" and "two-way link" of neural networks. Functional link is dynamic link between specific neurons which use coupled sensor encoding neural network's time pulse (temporal spike). This link is different from traditional synaptic connections for its value can be changed with the excited level of neural network dynamics change, its intensity is decided by the time consistency level of occasional action potentials and each neuron, directly affected by the spatial and temporal dynamics. These cells are called the 'dynamic cell clusters' that are linked by the functional link. The model uses two-way link, it can explain time synchronization nerve release phenomena without introducing neural oscillation unit of the time synchronization theory.

The Functions of Binding Mechanism in the Perceptual Processes

As for the specific function of binding mechanism of perceptual processes, different researchers come to different conclusions. As Friedman-Hill found that right parietal is related with visual features binding in the perception report [START_REF] Friedman-Hill | Posterior parietal cortex and the filtering of distractors[END_REF]; while Ashbridge found that right parietal and binding have no direct relationship in the visual search task, related with the selection of spatial position only, the ventral temporal cortex is responsible for the feature binding [START_REF] Ashbridge | Does parietal cortex contribute to feature binding?[END_REF]; And numerous studies show that the hippocampus is related with features binding in memory [START_REF] Mitchell | fMRI evidence of age-related hippocampal dysfunction in feature binding in working memory[END_REF]; Prabhakaran, etc. observed in working memory storage consolidation feature, prefrontal got activation [START_REF] Prabhakaran | Integration of diverse information in working memory within the frontal lobe[END_REF]; Llinas etc. found that nonspecific thalamic circuits is responsible for perceiving a wake-up binding [START_REF] Lliná | The intrinsic electrophysiological properties of mammalian neurons: insights into central nervous system function[END_REF]. In addition, in the specific binding task , the left middle temporal lobe , cerebellum, left frontal lobe, the parietal lobe , left medial frontal gyrus, right anterior cingulate gyrus, right frontal gyrus , right prefrontal , anterior cingulate cortex , left center back and other brain regions can be activated. It can be seen in different cognitive clearly, brain mechanism of binding is extremely complex.

Binding and Perception Distinction

In the neurophysiologic level, it was found binding is related with the situational perception distinction height; external sensory input formed structural characterization under the function of binding. There is evidence that nerve released simultaneously depends on the presentation of stimulation. Spatially separate cells shown strong synchronization only in response to the same object . If the two cell populations made reaction to the two independent objects which were moving in the different directions, then these two cell populations' activation almost had no time relation [START_REF] Castelo-Branco | Neural synchrony correlates with surface segregation rules[END_REF]. These results indicate that each object corresponds to its own synchronous activation mode,different objects have different neural activation patterns. Therefore, it can achieve different objects' perception distinction based on synchronous neural release binding mechanism. Tallon-Baudry through EEG studies has found that the perception of the object's consistency is associated with a specific γ-band activity [START_REF] Tallon-Baudry | Stimulus specificity of phase-locked and non-phase-locked 40 Hz visual responses in human[END_REF]. This relationship between high-frequency activity and the perception of the object's consistency also confirmed by a lot of other paradigms studies. Since γ-band activities reflect the information of time synchronization, it also reflect binding mechanisms' role situation.

Binding and the Selection of Perception Information

Fries record the cat's visual cortex neural responses under the conditions of binocular rivalry [START_REF] Fries | Synchronization of oscillatory responses in visual cortex correlates with perception in interocular rivalry[END_REF]. They give two stimulations that moved in different directions to the wakefulness cats' left and right eye at the same time. According to the direction of eye movement to speculate perception advantage, making the grating deviation as identification of the eye movement direction perceives the selection result. Studies found that neuronal activity stimulated a high degree of synchronization, these neuronal activity are used to characterize the perception; while nerve cells that used to process the ignored stimulation exhibit only weak time relationship. Meanwhile, the simultaneously released of the recording point is accompanied with the advantaged γ oscillations, characterized the selected stimulated neurons, and the intensity of the γ-band increased, but the neurons which make a reaction to the neglect stimulation, its strength decreased. The results show that, at least in the early stages of visual perception, sensory information's dynamic selection and inhibition are associated with the synchronization regulation of neural activity. Thus, this also proved that binding and the selection of perception information are closely related.

Binding and Memory

Binding and Working Memory

Research shows that the function of working memory depends on the nerve cells' temporal coordination on the time (temporal coordination). Tallon-Baudry etc. studied the relationship between synchronization of γ-band and working memory [START_REF] Tallon-Baudry | Induced γ-band activity during the delay of a visual short-term memory task in humans[END_REF] They found that in a task of visual delayed matching, the accurate synchronization of ventral occipital and frontal area was strengthened. Sarnthein's etc. study found that in a visual-spatial working memory task, time consistency of forehead and posterior parietal parts' electrodes has also been strengthened. And this increase occurred in γ-band, but in the lower frequency bands (for example θ frequency) does not occur. It shows that the time binding mechanisms also plays an important role in working memory.

Recent studies of cognitive aging found that compared with the young, on the memory of binding characteristics the elderly has the obvious shortages, while on the memory of single feature there was no difference. This shows that the binding mechanism has a relationship with multi-feature combination's information coding, save or extract. This conclusion has also been supported by brain imaging studies. This shows that for normal subjects' binding capacity, the working memory tasks that need for feature binding can lead to greater hippocampus activation. The study not only proved the presence in working memory binding problems, but also made important contributions to reveal the neural basis of the binding.

Binding and Episodic Memory

Lukeu etc. pointed out that episodic memory depends on the ability of individual tied up the central message of an event with contextual information [START_REF] Lekeu | Effects of incidental and intentional feature binding on recognition: a behavioural and PET activation study[END_REF]. Center information refers to the theme of the event (such as the main content of the conversation). Contextual information includes spatial and temporal characteristics of events, encoding mode (such as visual or auditory, etc.), physical characteristics (such as pitch or color) and emotional status. Contextual information can act as the clues to extract center information. In order to form memory traces which is complete and relevant a particular event, it is not enough to code two kinds of information independently. You must also establish a binding between central feature and contextual feature. The possibility of an event extracted depends on the number and strength of these two kinds of information bundled. It was also found that there were two forms of binding to central feature and contextual feature: Intentional and unintentional binding. These two forms of binding between different characteristics have different effects. They found that under the conditions of the unintentional binding, the left middle temporal lobe and cerebellum activated in the word recognition; the left frontal and parietal areas activated in combination recognition. Under the conditions of the intentional binding, in the word recognition, the left middle frontal gyrus, right anterior cingulate and right frontal gyrus activated; in combination recognition, the right prefrontal activated.

Binding and Consciousness Awakening

Binding and Perception Awakening

Some studies have found that in the awakening state and rapid eye movement sleep (REM) state, in the EEG (electroencephalogram) or MEG (magneto encephalography) appears frequencies of γ-band. In the deep sleep state such frequencies disappears. The similarity of REM state and wakefulness on the high-frequency activity indicates that in these two states, the synchronization of the neural activity frequency band is associated with the generating process of the arousal state. Another study found that, under the height anesthesia, the high frequency components of the perception awakening also disappeared. Since γ-band activity is associated with synchronous activation of nerve cells. From the above results we can speculate that the binding mechanisms involved in the process of the sense change from the depth anesthesia or deep sleep state to the awake state.

Binding and Consciousness

At present, a main point in the study of consciousness holds that sense should be understood as a number of interacting systems' functions. These systems include sensing systems, memory structure, the executive control center and emotional and motivational systems [START_REF] Engel | Temporal binding and the neural correlates of sensory awareness[END_REF]. The specific functions of consciousness mainly for two aspects [START_REF] Huisong | affinity propagation algorithm to build context-aware learning system analysis[END_REF]): (1) cross-system coordination function, namely how a variety of different nature process integrated, and how they are in harmony and consistently organized in the distributed neural activity model; (2) dynamic selection function. Since in a given time, only a part of information can enter into the consciousness. So how consciousnesses achieve the dynamical selection to the specific content? Obviously, from the meaning of binding, these two functions of consciousness are closely related with binding mechanisms. In fact, the previously mentioned perception distinction, information selection, working memory, awakening and other mental processes are the main content of consciousness [START_REF] Engel | Temporal binding and the neural correlates of sensory awareness[END_REF]. The relationship between these processes and binding mechanisms also confirmed the function of binding in the consciousness.

Conclusion and Prospect

Basing on the mechanism of feature binding, this paper systematically introduced the present study about feature binding used in perceptual learning, combining the latest research advances at home and abroad. According to our paper, the binding problem has got more and more academic attention, also is an important field in cognitive science, neuroscience and brain science. But the current research is in its infancy, there is no theory which can perfectly solve the binding problem. In addition, the brain areas which are responsible for different forms of binding may have different working mechanism in the different cognitive tasks. Therefore, with the development of neuroscience, and the increasingly deep of the research on binding problem and relationship of cognitive function. Hence force, on one hand we need to do more in-depth and meticulous research to the brain regions which are responsible for different forms of binding, on the other hand, it must strengthen systematic study of the overall brain function which is responsible for general binding problem, making connections to the variety of fragmented brain function location research, and unifying the systematic framework.

Acknowledgements

This work is supported by the National Key Basic Research Program of China (No.2013CB329502), the National Natural Science Foundation of China (No.61379101) and the Students Innovation and Entrepreneurship Foundation of China University of Mining and Technology (No.201446).