Jaccard–Kmeans clustering

The Journal of Systems and Software 95(2014)242–251

Contents lists available at ScienceDirect

The Journal of Systems and

Software

j o u r n a l h o m e p a g e :w w w.e l s e v i e r.c o m /l o c a t e /j s

s

Scalable news recommendation using multi-dimensional similarity and Jaccard–Kmeans clustering

Lu Meilian ?,Qin Zhen,Cao Yiming,Liu Zhichao,Wang Mengxing

State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China

a r t i c l e

i n f o

Article history:

Received 30July 2013

Received in revised form 26April 2014Accepted 26April 2014

Available online 20May 2014

Keywords:

News recommendation Similarity calculation Clustering

a b s t r a c t

In order to solve the scalability problem in news recommendation,a scalable news recommen-dation method is proposed.The method includes the multi-dimensional similarity calculation,the Jaccard–Kmeans fast clustering and the Top-N recommendation.The multi-dimensional similarity cal-culation method is used to compute the integrated similarity between users,which considers abundant content feature of news,behaviors of users,and the time of these behaviors occurring.Based on traditional K-means algorithm,the Jaccard–Kmeans fast clustering method is proposed.This clustering method ?rst computes the above multi-dimensional similarity,then generates multiple cluster centers with user behavior feature and news content feature,and evaluates the clustering results according to cohesiveness.The Top-N recommendation method integrates a time factor into the ?nal recommendation.Experiment results prove that the proposed method can enhance the scalability of news recommendation,signi?-cantly improve the recommendation accuracy in condition of data sparsity,and improve the timeliness of news recommendation.

?2014Elsevier Inc.All rights reserved.

1.Introduction

With the rapid development of network technology,informa-tion becomes more and more abundant.Traditional media and network media generate large amounts of news,which makes users spend a lot of time ?nding news they are interested in (Shang et al.,2010).However,through collecting and analyzing users’features,news recommendation can excavate users’poten-tial interests and behavior rules,formulate the corresponding news ?ltering strategies,and recommend personalized news to users.As a common technology in personalized recommendation,col-laborative ?ltering recommendation is divided into user-based collaborative ?ltering (Qi et al.,2012)and item-based collabora-tive ?ltering (Ye et al.,2012).The user-based collaborative ?ltering needs to ?nd neighbors of target users,and then recommends the target users with items which the target users’neighbors are interested in but the target users do not focus on.The item-based collaborative ?ltering ?nds items that are similar with the target items,and recommends these items to the users who pay attention on the target items.

With increasing numbers of users and news,the problems that news recommendation will encounter are growing evidently.

?Corresponding author.Tel.:+861013601249792.E-mail address:mllu@https://www.wendangku.net/doc/c010410377.html, (M.Lu).

These problems mainly manifest in following two aspects.One of the problems is the data sparsity.With the increasing scale of personalized news recommendation,the number of news often reaches millions,which leads to the fact that the possibility of two users focusing on the same news becomes less.So users’near-est neighbors calculated by traditional similarity algorithm is not appropriate,which decreases the quality of personalized news rec-ommendation.The other problem is the scalability of algorithm.The increasing data scale in recommendation systems cause a large amount of calculation,which makes it dif?cult to satisfy the real-time requirement of recommendation systems.

Aiming at the data sparsity problem,current solutions mainly include default-value ?lling (Guo,2008;Sun,2005),predict ?lling (Deng et al.,2003;Zhang and Yang,2012)and improving tradi-tional similarity measurement.Default-value ?lling sets the ratings of items without appraisal as the average value of all users’ratings or the most frequent rating.However,setting default-value is a low credible method.This method eliminates the personalized users’ratings,and cannot effectively improve the quality of recommenda-tion.At the same time,a large number of ?llings will occupy larger memory space,making the space complexity of the algorithm increase rapidly.Contrasted with default-value ?lling,predict ?ll-ing predicts the ratings of items according to the similar users or items,which can reduce the sparsity of ratings.Although predict ?lling is more accurate than default-value ?lling,this method occu-pies large memory space and increases the space complexity.In

https://www.wendangku.net/doc/c010410377.html,/10.1016/j.jss.2014.04.046

0164-1212/?2014Elsevier Inc.All rights reserved.

M.Lu et al./The Journal of Systems and Software95(2014)242–251243

improving traditional similarity measurement,PIP method(Liang, 2010)is put forward to measure the similarity between users.The calculating method of PIP is composed of three factors:Proximity indicates the difference between the ratings of two users;Impact indicates the preferences of two users to items;Popularity indicates the difference of the current rating and the average ratings.PIP cal-culates the similarity between two users through the above three factors.This method solves the data sparsity problem in collab-orative?ltering.But on condition of item ratings including more factors,this method needs to calculate all possible rating factors, which makes calculation inaccurate and massive.In order to resolve the scalability issue,some researchers(Li,2011;Jing,2011)paral-lelize traditional collaborative?ltering recommendation algorithm with the help of the MapReduce model to reduce the calculat-ing time.Other researchers(Dakhel,2011;Das and Datar,2007; Roh,2003)propose to reduce the nearest neighbor search space of users or items by clustering users or items,and sequentially improving the scalability of collaborative?ltering.The main clus-tering methods include K-means cluster,LSH(Locality Sensitive Hashing)clustering,neural network,etc.Generally,the neighbors of users/items obtained by clustering are biased,which inevitably results in the decline of recommendation quality,although cluster-ing can improve the scalability.

This paper proposes a scalable news recommendation method to solve the above problems,including the multi-dimensional similarity calculation method,the Jaccard–Kmeans fast clustering method and the Top-N recommendation method.The multi-dimensional similarity calculation method computes the similarity between users combining abundant content feature of news with the behavior and time feature of users,solving the data sparsity problem in traditional collaborative?ltering.Then,based on the traditional K-means algorithm,the Jaccard–Kmeans fast cluster-ing method is proposed,which includes the above new similarity measurement method,a new multiple cluster centers genera-tion method,and a new evaluation methodology of clustering results.The Jaccard–Kmeans clustering method provides better user clustering effect and enhances the scalability of recommenda-tion systems.The Top-N recommendation method integrates the time factor into the?nal recommendation,improving the timeli-ness of news recommendation.

Subsequent content is organized as follows.Second2pro-vides a review of news recommendation methods proposed in recent years.Second3elaborates the multi-dimensional similar-ity calculation method using user behaviors and news contents, which includes modeling user interest and calculating integrated similarity.Second4describes our proposed Jaccard–Kmeans fast clustering method.Second5gives the Top-N recommendation method considering the time factor.Second6analyzes the exper-iment schemes and results from multiple perspectives to evaluate the advantages of the method in this paper.Second7concludes the method and gives prospects of the future research work.

2.Related works

Content-based news recommendation systems construct users’pro?les by extracting content features of the news which the users have read,and then recommend to users the news articles rele-vant to the news which the users have read.Therefore,building the user interest model accurately is crucial for the content-based news recommendation systems.Liu et al.(Liu et al.,2010)propose a content-based news recommendation approach which builds users’pro?les by analyzing the click behaviors of users and uses the pro?les to extract user interests.The paper drew a conclusion that the latest click behaviors of users are bene?cial for increasing the accuracy of news recommendation according to their?nding that user interests would change over time.Lv et al.(2011)propose to use a correlation function to evaluate the relativity of two news articles and recommend to users the news articles which have big-ger relativity with the news articles users have read.The correlation function takes three factors into account–relevance and novelty, connection clarity,transition smoothness.Xue et al.(2008)design a news recommendation system which builds the topic model of news taking into account the news articles and the users’com-ments and votes.The authors demonstrate that this method can mine the topic of news more accurately.Li et al.(2010a)propose a content-based news recommendation system,which takes the user comments of news into consideration.The system builds a tree of news’comment to extract news topic pro?le,in which user’s comments are taken as nodes and the original news arti-cle are taken as the root of the tree.Based on the news topic pro?le and statistical language models,the system could recom-mend relevant news to users.Capelle et al.(2012)introduce the Synset Frequency-Inverse Document Frequency(SF-IDF)method and compare this method with TF-IDF and Semantic Similarity(SS). The experiment results demonstrate that SF-IDF is superior to other traditional approaches.Collaborative?ltering is another method which has been used successfully in news recommendation.Das and Datar(2007)propose a scalable online news recommendation approach based on collaborative?ltering,which is used to rec-ommend news to users in Google News.This method combines memory-based collaborative?ltering algorithm and model-based collaborative?ltering algorithm,and uses MinHash clustering and Probabilistic Latent Semantic Indexing(PLSI).Distributed compu-tation technique MapReduce is also adopted in the system.

In recent years,many researchers tried to combine the content-based method and collaborative?ltering method.Therefore,many hybrid news recommendation approaches were proposed to improve the performance of news recommendation systems.Wen et al.(2012)builds a personalized news recommendation system on the web based on the reading preferences user de?ned.To get more accurate recommendation results,the system combines content-based method and collaborative?ltering method,and adopts the hybrid algorithm.It could recommend news pages to users based on the classi?cation of news pages and the preference model of users. Li et al.(2010b)propose a news recommendation method which models the personalized news recommendation as a contextual bandit problem.In this method,a learning algorithm sequentially selects news articles to recommend to users based on contextual information about the users and the news articles.This work also proposes the LinUCB algorithm to maximize the total users’clicks. Li et al.(2011)propose a scalable two-stage personalized news rec-ommendation system.The system consists of three modules:(1) news articles clustering,in which a two-level news architecture is constructed by clustering news into groups based on Locality Sensitive Hashing(LSH)and Hierarchical Clustering;(2)user pro-?le construction,in which the user pro?le consists of three parts –news content,similar access patterns and preferred news enti-ties;(3)personalized news recommendation,in which the news recommendation is modeled as a budgeted maximum coverage problem.

The method proposed in this paper is also a hybrid recom-mendation method.However,it is different from the methods mentioned above.In our method,we calculate the multi-dimensional similarity of users based on the behavior similarity and content similarity.Then we cluster similar users into a group based on our Jaccard–Kmeans fast clustering method.Our clus-tering method comprises the above new similarity measurement method,a new multiple cluster centers generation method,a new iteration stop condition,and a new evaluation methodology of clustering results.Our method can better solve the user cluster-ing problem in personalized news recommendation,and enhance the scalability of news recommendation.

244M.Lu et al./The Journal of Systems and Software95(2014)242–251 3.Multi-dimensional similarity calculation methods based

on user behaviors and news contents

Multi-dimensional similarity is calculated through following

steps.First,news topic eigenvectors and user topic eigenvectors are

generated by training news through the LDA(Latent Dirichlet Allo-

cation)model.Then,user interest is modeled with user behavior

feature and news content feature.Finally,behavior similarity and

content similarity are calculated and integrated as the integrated

similarity between users.

3.1.Topic model training

According to the news web URLs recorded on news logs,the

crawler grabs the titles and bodies of news.Then,the word segmen-

tation system divides news bodies into words,tags part-of-speech

and extracts nouns among the words to compose a two dimen-

sional table consisting of news identi?cation(news id)and news

nouns sequence.At last,news topic eigenvectors can be generated

by training the news id and the news noun sequence through the

LDA model and a prede?ned number of news topics k.The news

topic eigenvectors can be expressed as Eq.(1).

L=(w1,w2,...,w l,...,w k)(1)

where,

k

l=1

w l=1,the natural number subscript l is the topic

serial number and its maximum value is k(the total number of topics,the best value of k can be decided by experiment),w l is the probability that this news belongs to the l th topic.

https://www.wendangku.net/doc/c010410377.html,er interest modeling

Behavior feature records the id of news that users have operated (browsing,commenting,or publishing)and the operating time t. The mathematical representation is

list(id1,t1),(id2,t2),(id3,t3),...,(id i,t i),...)(2) where,(id i,t i)represents user operates news id i at t i.

In?uenced by personal factors,social groups and important events,user interest usually varies over time(Zuo et al.,2010), which can be expressed as a forgetting curve.The forgetting curve usually varies fast in the beginning and then slows over https://www.wendangku.net/doc/c010410377.html,er’s interest is quite obvious in the beginning,but as time goes on,if the interest does not get enhanced,it will be weaken gradually.The longer the enhancing interval is,the lower the user interest.

We use a continuous attenuation function to depict the attenu-ation process of user interest toward a news topic.

u=e? (t?t0)(3) where t is the current time,t0is the time that user operates the news, is a parameter which determines the attenuation speed of user interest to news topic.With the time difference t-t0increases, the function value decreases fast in the beginning then slowly.

User’s content eigenvector can be obtained by multiplying every topic eigenvector of all news which user has operated by the atten-uation function,and the arithmetic mean value can be calculated. The value represents a distribution of user behaviors over k topics, better re?ecting the user interest.The mathematical representation is

u(a

1,a2,...,a l,...,a k)=

L i∈Vector(n(u))

L i×e? (t?t i)

|n(u)|(4)

where n(u)={id1,id2,id3,...}is news collection operated by users, Vector(n(u))is news topic eigenvector collection corresponding to news collection,k is the number of news topics,l is the topic serial number,L is the news topic eigenvector,t is the current time,and t i is the user’operation time on news i.

Then,the ultimate user’s content eigenvector u(w

1,w2,...,w l,...,w k) can be got by normalizing the vector u(a

1,a2,...,a l,...,a k)

.The mathe-matical representation is

w I=

a I

k

i=1

a i

and

k

l=1

w I=1(5)

So users’recent operations will have greater impact on user content eigenvectors,and the early operations have less impact.

The above method can be used to calculate the initial content eigenvector for a speci?c user to solve the problem of interest drift. After that,if the user has some new operations,the user’s content eigenvector needs to be updated.However,taking the users’all operations into consideration would lead to a lot of repetitive work. In order to update the user interest model in real time,the following updating method can be adopted,as Eq.(6).

w= w +w =e? (t?t0)w +w (6) where,w is the updated content eigenvector,w is the original con-tent eigenvector,w is the content eigenvector calculated by user’s new operations,t is the current time,t0is the last time of updating the user’s interest model.After normalizing the vector w,we can get the user’s current content eigenvector.

Actually,when updating the user interest model,we should only take into account the user’s new operations occurred since last updating.Therefore,this method not only solves the problem of interest drift,but also improves the ef?ciency of updating the user interest model.

3.3.Multi-dimensional similarity calculation

The multi-dimensional similarity between all users during a period of time is computed using the user interest model.The sim-ilarity calculation is divided into three steps–behavior similarity calculation,content similarity calculation and integrated similarity calculation.The integrated similarity between two users is com-puted as the weighted sum of the?rst two similarities.This is called multi-dimensional similarity calculation method.After computing the integrated similarity between all users,the most similar p users are chosen as the user’s neighbors.

3.3.1.Behavior similarity calculation

As mentioned above,user’s behavior feature is represented as list(id1,t1),(id2,t2),(id3,t3),...,(id i,t i),...).

Now,we utilize Jaccard to calculate the behavior similarity between users.The Jaccard similarity between user u and user v is

sim(u,v)=

n(u)∩n(v)

n(u)∪n(v)

(7)

where,n(u)and n(v)respectively represent two news collections which user u and user v have operated.Meanwhile,considering the time factor,if two users operate the same news at the same time, it usually means that two users have strong similarity.So the sim-ilarity between two users is an inverse function of time difference, represented as e?ax here.According to this,the behavior similarity is modi?ed as

sim(u,v)=

i∈n(u)∩n(v)

e??|t ui?t v i|

n(u)∪n(v)

(8)

where,t ui is the time when user u operates news i,t vi is the time when user v operates news i.Coef?cient?is the time parameter of behavior similarity,and its range is[0,1].

M.Lu et al./The Journal of Systems and Software 95(2014)242–251

245

Breese et al.(1998)propose that if users take actions on unpop-ular news,the interest similarity between these users is stronger.Unpopular news contributes more bene?ts to user’s similarity than popular news.For example,it is dif?cult to declare that two users have similar interest in case that they both browse the news about the opening ceremony of the Olympic Games.The reason is that a lot of users usually focus on popular news.On the contrary,if two users have read news about the latest progress of the recommendation ?eld,it usually shows that both of them are interested in recom-mendation technology and have similar interest.According to the

proposal of Breese,we can add penalty factor 1/(log(1+ m (i ) ))to

the similarity calculation in Eq.(8),where,m (i )is user collection who have operated news i .|m (i )|is the size of user collection,which is called as the heat of news.Considering that the interest curve of the user in news ?ts the long tail distribution,we make log calcu-lation to |m (i )|.In short,the more popular the news is,the less the news contributes to the similarity between users.The less popular the news is,the more the news contributes to the similarity.So,the ?nal behavior similarity can be calculated as

sim (u,v )=

i ∈n (u )∩n (v )1

e ??|t ui ?t v i | n (u )∪n (v )

(9)

3.3.2.Content similarity calculation

Since content feature is represented in the form of a vector,the content similarity between user u and user v adopts cosine similar-ity,which is represented as

cos(u,v )=?→u ?→v ?→u × ?→v

(10)

where ?→u and ?→v are the topic eigenvectors of user u and user v

respectively.

3.3.3.Integrated similarity calculation

After integrate the behavior similarity sim (u ,v )in Eq.(9)with the content similarity cos (u ,v )in Eq.(10),we can compute the ?nal similarity between user u and v according to the following Eq.(11).

W (u,v )=ˇsim (u,v )+(1?ˇ)cos(u,v )

(11)

where,coef?cient ˇis a weight factor decided by experiments,which is the ratio parameter of similarity,and its range is [0,1].When ˇ=0,similarity calculation only takes content feature into account.When ˇ=1,similarity calculation only considers behavior feature.

In the condition that user’s behavior feature is sparse,it is dif-?cult to get similarity correctly.However,based on the mentioned method which combines behavior feature with content feature to compute similarity between users,we can acquire user’s similarity through content feature to better solve the data sparsity issue in personalized news recommendation.At the same time,time fac-tor and the news’popularity are taken into consideration when computing the similarity,improving the accuracy of similarity cal-culation.

4.Jaccard–Kmeans fast clustering method based on multi-dimensional similarity

With the growth of user scale in personalized news recommen-dation,the time of computing similarity increases dramatically.So it is necessary to cluster users ?rst and then compute user similarity within each cluster.As mentioned in Section 3.2,user interests are modeled with two kinds of user feature –behav-ior feature and content feature.Traditional clustering methods are suitable for clustering one kind of feature,instead of multi-kinds feature.In other words,traditional clustering methods are

not appropriate for constructing the user interest model mentioned above.So this paper puts forward a fast clustering method based on multi-dimensional similarity.Based on the traditional K-means algorithm,this clustering method comprises the similarity mea-surement method proposed in Section 3.3,a new multiple cluster centers generation method,a new iteration stop condition,and a new evaluation methodology of clustering results,better solving the user clustering problem in personalized news recommenda-tion.

4.1.Properties of cluster center

In the traditional K-means clustering method,the cluster center is the arithmetic mean value of all eigenvectors.However,the user interest model mentioned in Section 3.2contains multiple eigen-vectors,which cannot be calculated through arithmetic mean value.The user interest model includes behavior feature and content fea-ture,and the behavior feature consists of item information and time information.Therefore,this paper makes use of both the following features to constitute the cluster center.(1)Behavior feature

According to the occurrence number of user behaviors in current cluster,the Top-N operated items are chosen as the item informa-tion of cluster centers.The Top-N items stand for news collections which users are interested in within the cluster.The value of N will be determined by experiments.The Top-N items are expressed as:

(12)

The average value of clustering users’behavior time is selected as the time information of cluster centers.The average value of time information represents the time attributes of cluster centers,which is expressed as:

t =

t ∈(cluster )t

t (cluster )

(13)

where,cluster stands for the current cluster center.t (cluster )is the time information collection in all clusters.For instance,if the cur-rent cluster contains ?ve users,and each user operates news two

times,then ˉt

is the average value of the time of 10operations.(2)Content feature

The average value of all topic eigenvectors of users within one cluster is chosen as the content features of cluster center,which is expressed as:

u (w 1,w 2,...,wi,...,wk )=

L ∈v ector (cluster )L

v ector (cluster )

(14)

where,vector (cluster )is all users’topic eigenvectors collection in the current cluster.

4.2.Generating cluster center

At the ?rst iteration,k users are selected randomly as the initial cluster centers,each cluster only having one user.In each cluster,the Top-N items operated by the user is set as the items information of the cluster center,the average operation time of the user is set as the time information of the cluster center,and the topic eigenvector of the user is set as the content feature of cluster center.

For the following iterations,the information of cluster center may be updated.A new cluster center will be generated on condi-tion that the information of cluster center has been updated.So we need to compute the similarity of the new cluster center and the old cluster center outputted by the previous iteration.If the similarity is high enough,the clustering iteration is convergent.The method of updating cluster center is as follows.

246M.Lu et al./The Journal of Systems and Software95(2014)242–251

Firstly,for each user in the cluster,compute the multi-dimensional similarity between the user and every cluster center. During this process,the cluster center is regarded as a virtual user. The virtual user has operated N news(Top-N items of the cluster center),the operations all occur atˉi(the time information of cluster center),and the topic eigenvector of the virtual user is the content feature of the cluster center.Then we use the method mentioned in Section3to compute the similarity between each user and each cluster center,and put the user into the most similar cluster.

After the above operation,each user will belong to a cluster, and each cluster contains some users.For each cluster,we can get the new Top-N items by calculating the N news operated by most number of the users in the cluster,and compute the average value of all users’operation time in the cluster as the time information of the cluster.Meanwhile,compute the average value of all users’topic eigenvectors in the cluster as the content feature of the cluster.By the above method,the new cluster center is generated.

4.3.Stop conditions for iteration

The iterations in Section4.2will be stopped in condition that behavior features and content features of a cluster center no longer changes or changes within a certain threshold.The threshold is determined by the subsequent experiments.

We utilize multi-dimensional similarity to evaluate the change of behavior features and content features of a cluster center change(k-center)=k?

c∈k-center

W(pre(c),now(c))(15)

where,k is the number of clusters,k-center is k cluster centers,c is cluster center,pre(c)is the previous behavior features and content features of the cluster center,now(c)is the current behavior fea-tures and content features of the cluster center.change(k-center)≤threshold means that the behavior features and content fea-tures of the cluster center does not change and the iteration is stopped.

4.4.Evaluating clustering effect

The clustering effect can be evaluated by the following two methods:

In the?rst method,we estimate the clustering effect according to the cohesiveness of cluster.In other words,we evaluate the clus-tering effect through computing the multi-dimensional similarity between all users and their cluster center.According to the results, the number of clusters is determined.The cohesiveness of cluster is represented as

cohesion(cluster)=

u∈n(cluster)

W(u,center(u))(16)

where,cohesion(cluster)is the cohesiveness of cluster,n(cluster) is user collection in one cluster,center(u)is the cluster center of the cluster which user u belongs to,W(u,center(u))represents the multi-dimensional similarity between user u and the cluster center center(u).

In the second method,we determine the number of cluster according to the accuracy and recall of?nal recommendation result.

4.5.Algorithm description

Table1describes the proposed Jaccard–Kmeans fast clustering method based on multi-dimensional similarity using pseudo-code.

Clustering users can reduce time complexity and space com-plexity.Since traditional user similarity calculations need to load all users’ratings into memory,which consumes massive memory Table1

Jaccard–Kmeans fast clustering algorithm.

Algorithm:Jaccard–Kmeans fast clustering algorithm based on

multi-dimensional similarity

Input:

k:the number of clusters

D:user collection

Output:k clusters

Method:

Step1:arbitrarily select k users from D as the initial cluster centers;

Repeat

Step2:According to Eq.(11),compute the multi-dimensional similarity

between each user and each cluster center;

Step3:Assign user to the cluster whose cluster center has the biggest

similarity;

Step4:According to the behavior feature and content feature of users in

the cluster,update cluster center using cluster center generation

method mentioned in Section4.2;

Until the news feature,time feature,and content feature of the cluster

center no longer changes or changes within a certain threshold;

Step5:Stop clustering,output k clusters,compute the cohesiveness of

cluster which is used to adjust the number of clusters.

space and even leads to out of memory when the number of users or news reaches a big scale.However,through clustering user,we only need to load all users’ratings of current cluster into memory, which reduces the space complexity of recommendation algorithm greatly and demonstrates the better scalability of our recommen-dation method.

4.6.Jaccard–Kmeans fast clustering using MapReduce

MapReduce(Dean and Ghemawat,2004)is a computation model using large clusters of machines,which can effectively pro-cess a large amount of data.In order to further reduce the time complexity and increase the scalability,we use MapReduce to implement our Jaccard–Kmeans clustering algorithm.The steps are as follows.

We use a MapReduce task to accomplish the iteration,in which the input?le consists of a user interest model?le and a cluster cen-ter?le.The user interest model?le contains a list of records,which records every user’s eigenvectors.The cluster center?le contains a list of records,which records every cluster’s eigenvectors.

During the Map phase,the task reads the input?le and maps each of the records to a key-value pair.Speci?cally,the task?rst reads the cluster center?le and the user interest model?le to get the eigenvectors of every cluster center and every user’s eigen-vectors,then computes the multi-dimensional similarity between every user and every cluster center,?nally maps users to the most similar cluster according the computed similarity value.So,the key and value of every key-value pair outputted by the Map phase respectively contain a cluster-id representing a speci?c cluster and every user’s behavior eigenvector and content eigenvector.

Then,the key-value pairs outputted at the end of the Map phase are sorted according to the hash value of the keys,where the key-value pairs with the same key are sorted together.

During the Reduce phase,based on the sorted key-value pairs, a list of users’eigenvectors is merged for each key,and then is mapped to each cluster-id.Meanwhile,for each cluster,the new cluster center is generated according to method described in Sec-tion4.2.

Finally,compute the integrated similarity between the new gen-erated cluster center and the previous cluster center generated during the previous iteration.If the integrated similarity of two cluster centers does not exceed a prede?ned threshold,iteration is stopped,the cluster center generated during the last Reduce phase is regarded as the?nal result,and the Jaccard–Kmeans fast clustering is completed.

M.Lu et al./The Journal of Systems and Software95(2014)242–251247

5.Top-N recommendation based on time factor

This paper considers time factor based on traditional Top-N recommendation methods,which brings temporal effect to news recommendation results.The preference of user u to un-operated news i in the near past is de?ned as

prefer(u,i)=

v∈S(u,K)∩m(i)

W(w,v)e? (t ?t v i)(17)

where,S(u,K)is the collection of K most similar users of user u (neighbors of user u);m(i)is the user collection who have operated on news i;W(w,v)is the integrated similarity between user u and v; t is the current time;t vi is the time when user v operates on news i;coef?cient is the time parameter of recommendation,which varies in[0,1].The closer the time of neighbor user v operates on news i is to the current time t ,the more possible user u is inter-ested in news https://www.wendangku.net/doc/c010410377.html,ly,the occurring time of the neighbors’recent behaviors has greater in?uence on the recommendation results to user u.

According to the prefer(u,i)in Eq.(17),we can rank news in descending order,and select the news with high prefer(u,i)as the personalized news recommendation list to user u.

6.Experiments and analyses

6.1.Experiment schemes

News log data from ChouTi(https://www.wendangku.net/doc/c010410377.html,)is obtained to evaluate the effect of our scalable news recommendation method using the multi-dimensional similarity and the Jaccard–Kmeans clustering.ChouTi is a news aggregation website where users can edit and post news from other sources.ChouTi recommends news to users through the user behaviors of“top”or“trample”.Since ChouTi is still in infancy and owns relatively few users,the log data we can obtain is limited.The log data of40,000registered users during October2012–October2013is extracted as the exper-iment dataset.The dataset consist of900,000news and12,600,000 implicit behaviors.The time recorded in ChouTi log data is a relative value from January1,1970to the time of behaviors in milliseconds. We select the log data during the previous8months to train the model,the log data during the last4months to predict the rec-ommendation result,and assume that the system recommends50 news articles to each user.The following experiments are designed to determine the relevant parameters in the proposed news rec-ommendation method.

Experiment1:Measure the impact of time parameter?in behav-ior similarity(Eq.(8))on accuracy and recall,and determine the optimal value of?.

Experiment2:Measure the impact of behavior similarity weight factorˇin integrated similarity(Eq.(11))on recommendation results,and determine the optimal value ofˇ.

Experiment3:Measure the impact of the number of similar users K(Eq.(17))during Top-N recommendation on recommendation results,and determine the optimal value of K.

Experiment4:Measure the impact of time factor (Eq.(17)) during Top-N recommendation on recommendation results,and determine the optimal value of .

Experiment5:Utilize the proposed Jaccard–Kmeans fast clus-tering algorithm to cluster users,and verify the astringency of clustering algorithm.Where,the number of cluster k is set as10,the number of centers N is set as100.The astringency is evaluated by change(k-center)(Eq.(15)).If change(k-center)is less than a thresh-old,stop the iteration.The stop threshold of iteration is determined by computing the cohesiveness cohesion(cluster)of clusters in dif-ferent

iterations.Fig.1.Impact of behavior similarity time parameter?on recommendation results.

Experiment6:Determine the number of items in the cluster cen-ter.Different N has signi?cant impact on clustering results and recommendation effect.For example,if each cluster center only has one item in extreme case,it is obvious that the clustering results will be very bad.On the contrary,too many items in each cluster center will consume more calculation time.

Experiment7:Determine the number k of clusters.The more the number of clusters is,the less the number of users in each cluster is,the less the time consumed in calculating similar users is,and the less the time complexity is.However,the increase of k makes the number of each cluster become less and maybe fail to?nd some neighbors.This leads to the decrease of accuracy and recall eventu-ally.Therefore,it is necessary to balance the number of clusters and recommendation quality.That is,we need to determine a proper number k of clusters.

Experiment8:Measure the impact of topic number in LDA model on accuracy and recall,and determine the optimal value of topic number.This is the basic step to obtain news content feature.

Experiment9:Measure the performance of our algorithm in the case of sparse data to demonstrate that our algorithm has a sig-ni?cant effect on improving the recommendation accuracy in that case.

Experiment10:Compare the recommendation results of our proposed scalable news recommendation method with traditional personalized news recommendation based on collaborative?lter-ing.

6.2.Experiment results and analyses

6.2.1.Time parameter?in behavior similarity

?is the time parameter of behavior similarity in Eq.(8),which expresses the impact of time on users’similarity.It is obvious that two users are more similar if they read the same news during the same period.According to the function e??|t ui?t v i|,if the value of?is too small,e??|t ui?t v i|will become very big.This means that we estimate the time factor excessively,leading to the decline of rec-ommendation quality.Fig.1proves the above result,where the unit of?is10–10.As shown in Fig.1,with the increase of?,accuracy and recall increase.When?is2×10–10,both accuracy and recall reach the maximum,and then slowly decline.In the beginning,the small value of accuracy and recall is due to the excessive estimation for the impact of time factor,which makes similarity calculation incor-rect.While in the later phase,with the increase of?,the time factor becomes small.It gives rise to the under estimation for the impact of time factor,resulting in the slow decline of accuracy and recall.

248

M.Lu et al./The Journal of Systems and Software 95(2014)

242–251

Fig.2.Impact of behavior similarity weight factor ˇon recommendation results.

Eventually,the experiment determines that the optimal value of ?is 2×10–10.

6.2.2.Behavior similarity weight factor ˇin integrated similarity

In Eq.(11),when ˇis 0,user similarity only consists of the con-tent similarity.While when ˇis 1,user similarity only includes the behavior similarity.In general,collaborative ?ltering-based recommendation achieves better results than content-based rec-ommendation in personalized news recommendation.Thus,the behavior similarity should be dominant in calculating the inte-grated similarity between users.Fig.2veri?es this result.It can be seen from Fig.2,when ˇis 0.8,accuracy and recall reach the peak of 55.17%and 22.07%respectively.That is,the behavior similarity has greater in?uence on the recommendation results.However,the content similarity can further promote the recommendation effect and reduce the negative effect of data sparsity.

6.2.3.Number of similar users K during Top-N recommendation

Fig.3shows the accuracy and recall in different numbers of sim-ilar users K .It is shown in Fig.3,when K =80,accuracy and recall reach the maximum value.However,this value will change with different datasets,and we need to adjust it according to the actual

conditions.

Fig.3.Impact of the number of similar users K on recommendation

results.

Fig.4.Impact of recommendation time parameter on recommendation result.

6.2.4.Time factor during recommendation

In Fig.4,the horizontal axis is the time factor in terms of 10?10.Timeliness is the average value of current time and the release time of the recommended news,and the unit is day.With the increase of ,the accuracy and recall drop signi?cantly,and on the contrary,the timeliness gets better.Considering a reasonable compromise, is set to 3.2×10?9.Where,accuracy,recall and timeliness can achieve better values.

6.2.5.Cohesiveness of Jaccard–Kmeans clustering

Fig.5shows the situation of users’iteration clustering.The hor-izontal axis is the number of iterations,and the vertical axis is the change of cluster center.Fig.5shows that,the change of the cluster center gets smaller and smaller,and ?nally approaches a constant.We consider that the clustering converges at the time.During the prophase,the speed of convergence is fast,and the clustering result is close to the ?nal result after four iterations,while the speed of convergence becomes slow during the anaphase.During the anaphase,the value of change (k-center )will not always be reduced,while ?uctuate within a small range.This is because we use the multi-dimensional similarity to measure the distance between the current cluster center and the previous cluster center.During the iteration process,the topic eigenvector of the cluster center will always converge,while the Top-N item of the cluster center may change a little during the anaphase of iterations.We take three parts of data into account when we compute the multi-dimensional sim-ilarity:news feature data (Top-N items),time feature data

(average

Fig.5.Convergence process of clustering.

M.Lu et al./The Journal of Systems and Software 95(2014)242–251

249

Fig.6.Relationship between the number of iterations and cohesiveness.

time of user behaviors)and content feature data (topic eigenvec-tors),but not every part of the data will converge perfectly during the iteration process.

Fig.6exhibits the relationship between the number of cluster-ing iterations and the cohesiveness of clusters.For example,the change (k-center )after four iterations in Fig.5is 0.73,and the cohe-siveness after four iterations is 7781.76,which is close to the ?nal value 7865.43.Thus four iterations are suf?cient to determine the ?nal clustering.Also,the value of cohesiveness will not always increase.The reason is the same as that given in the above para-graph.We conclude that clustering iteration can be stopped when change (k-center )is not more than 0.8.

6.2.6.News number of cluster center

Fig.7reveals the impact of the item number of the cluster center on cohesiveness.In our experiment datasets,the average num-ber of news which users have read is about 315.When the item number of the cluster center is smaller than 320,the cohesiveness becomes higher with the increase of the item number.This shows that increasing the item number can improve the effect of cluster-ing.But,when the item number is bigger than 320,the cohesiveness gets smaller.

Fig.8reveals the impact of the item number of the cluster center on accuracy and recall.When the item number of cluster center is smaller than 320,the accuracy and recall increase with the item number and reach the highest value when the item number is 320.

Therefore,when the item number of the cluster center is close to the average number of news which users have read,the clustering effect and recommendation effect are both

optimal.

Fig.7.Impact of the item number of cluster center on clustering

effect.

Fig.8.Impact of the item number of cluster center on accuracy and recall.

6.2.

7.Number of clusters

Fig.9exhibits the change of accuracy and recall with the change of the cluster number.Where,the horizontal axis stands for the number of clusters k .The vertical axis is percentage,while dark gray rectangles represent accuracy and light gray rectangles stand for recall.Disregarding the dimension of news,the time complex-ity of calculating user similarity using the traditional collaborative ?ltering is O (n 2),where n is the number of users.The time complex-ity of utilizing the clustering method is O (nkt +(n 2/k ))=O (n 2/k ),where n is the number of users,k is the number of clusters,t is the number of clustering iterations.At extreme case,k =1,that is,without clustering,it is the traditional collaborative ?ltering-based recommendation.In this case,we need to calculate the similar users for every user,and the time complexity is O (n 2).However,with the increase of the number of cluster k ,the time complexity drops to 1/k ,but the accuracy and recall only decrease slightly.So when n is huge,we can increase the number of clusters to reduce the time complexity,while keeping better accuracy and recall.Thus,the pro-posed clustering method based on multi-dimensional similarity is suitable for clustering huge users in personalized recommendation.

6.2.8.Number of topics k

Fig.10exhibits the change of accuracy and recall with the change of topic number k in Section 3.1.The range of topic number k

is

Fig.9.Impact of the number of clusters on accuracy and recall.

250

M.Lu et al./The Journal of Systems and Software 95(2014)

242–251

Fig.10.Impact of the topic number in LDA on accuracy and recall.

set as [20,200].When the topic number increases from 20to 160,the accuracy and recall increases continuously,and both reach the highest value when the topic number k is 160.When k is greater than 160,the accuracy and recall begin to decline.Therefore,in our dataset,we set 160as the appropriate number of topics k .However,this value may change with the datasets;the best value of k may need to be adjusted according to the actual conditions.

6.2.9.Algorithm performance under different data density

In this experiment,we adjust the dataset by changing the data density,and test the algorithm performance under different data density.Fig.11exhibits the change of accuracy with the change of data density.The horizontal axis is the average number of users’behaviors on the dataset,ranging from 10to 320.The behavior sim-ilarity weight factor ˇ=1.0which means that only the similarity of user behaviors is taken into account.ˇ=0.8means that the similar-ity of content is taken into account and occupies 20%of integrated similarity.Fig.10shows that the accuracy of recommendation is higher in case of ˇ=0.8than in case of ˇ=1.0,especially when the number of users’behaviors is very small.Therefore,taking content similarity into account is helpful to improve the recommendation accuracy.When the dataset is sparser,the improvement is more obvious.This also proves that our similarity algorithm can reduce the negative effect of data

sparsity.

Fig.11.Impact of the data density on recommendation

effect.

https://www.wendangku.net/doc/c010410377.html,parison among different recommendation methods.

6.2.10.Recommendation effect

Fig.12compares the recommendation effect of the recommen-dation method we proposed with other https://www.wendangku.net/doc/c010410377.html,erBased is user-based recommendation utilizing the multi-dimensional sim-ilarity proposed in this paper.Jaccard–Kmeans is a method that clusters users ?rst and then recommends news (the proposed method).Kmeans–Cosine converts log data into a vector,adopts cosine distance to measure the similarity between users and the distance of cluster center,and then achieves the ?nal recommen-dation.Kmeans–Euclidean converts log data into a vector,adopts Euclidean distance to measure the similarity between users and the distance of clusters,and then achieves the ?nal recommendation.ItemBased is item-based recommendation utilizing the similarity between items;the similarity calculation between items is based on a topic eigenvector.Since the time cost of each algorithms during the process of recommendation is the same,so we only compare the time cost on calculating the similarity to re?ect the lower time complexity of our method.Fig.12shows that the accu-racy and recall of the Jaccard–Kmeans method is obviously higher than Kmeans–Cosine,Kmeans–Euclidean and ItemBased.The per-formance of UserBased is a little better than Jaccard–Kmeans in terms of accuracy and recall,but the time overhead of UserBased method is 9.75times of Jaccard–Kmeans.Considering accuracy,recall and time overhead,the Jaccard–Kmeans method has the most outstanding performance.

7.Conclusions

On account of the scalability problem in personalized news recommendation,this paper proposes a scalable news recommen-dation method using multi-dimensional similarity.The method includes the multi-dimensional similarity calculation based on user behavior and news content,the Jaccard–Kmeans fast clustering method based on multi-dimensional similarity and multiple cluster centers selection,and the Top-N recommendation method based on time factor.Firstly,we use the Jaccard–Kmeans clustering method to cluster users,and then utilize the multi-dimensional similarity calculation to compute the neighbors of https://www.wendangku.net/doc/c010410377.html,stly,we acquire the ?nal personalized news recommendation results through the improved Top-N recommendation method.The experiments on news log data from ChouTi demonstrate that the proposed scalable recommendation method can not only solve the scalability prob-lem effectively,but also reduce the negative effect of data sparsity,and obviously increase the quality of news recommendation.

Hybrid recommendation represents the future direction of per-sonalized https://www.wendangku.net/doc/c010410377.html,bining the collaborative ?ltering with content-based recommendation can get better recommen-dation results.The personalized news recommendation method proposed in this paper only adopts content-based recommendation

M.Lu et al./The Journal of Systems and Software95(2014)242–251251

during the stage of similarity calculation.However,we can consider some other ways to combine the content-based recommendation method with the collaborative recommendation method,such as adjusting proportion in the?nal results,selecting different algo-rithms according to users’preference,and utilizing the results of one method as the input of another method.

Acknowledgements

This article is partially supported by projects2012ZX03005010-003(Important National Science&Technology Speci?c Projects), 61231009(State Natural Sciences Foundation Projects)and 2014AA01A706(State863Projects).

References

Breese,J.S.,David,H.,Carl,K.,1998.Empirical analysis of predictive algorithms for collaborative?ltering.In:Proceeding UAI’98Proceedings of the Fourteenth Conference on Uncertainty in Arti?cial Intelligence,USA,pp.43–52.

Capelle,M.,Frasincar,F.,Moerland,M.,et al.,2012.Semantics-based news rec-ommendation.In:Proceedings of the2nd International Conference on Web Intelligence,Mining and Semantics,ACM,p.27.

Dakhel,G.M.,2011.A new collaborative?ltering algorithm using K-means clustering and neighbors’voting.Hyb.Intell.Syst.25(4),110–115.

Das,A.,Datar,M.,2007.Google news personalization:scalable online collaborative ?ltering.World Wide Web Pages124(20),271–280.

Dean,J.,Ghemawat,S.,2004.MapReduce:simpli?ed data processing on large clusters.In:Proc.of6th Symposium on Operating Systems Design and Imple-mentation(OSDI),San Francisco.

Deng,Ai-Lin,Zhu,Yang-yong,Shi,Bo-Le,2003.Collaborative?ltering recommenda-tion algorithm based on item rating prediction.J.Software14(9),1621–1628. Guo,Yan-Hong,2008.Research of collaborative?ltering algorithm and its applica-tion in recommendation system.DaLian University of Technology.

Jing,Jiang,2011.Scaling-up item-based collaborative?ltering recommendation algorithm based on https://www.wendangku.net/doc/c010410377.html,p.Sci.Technol.7(4),123–126.

Li,Jun-Hua,2011.Study of MapReduce in cloud computing and data mining.Uni-versity of Electronic Science and Technology of China.Li,Q.,Wang,J.,Chen,Y.P.,et al.,https://www.wendangku.net/doc/c010410377.html,er comments for news recommendation in forum-based social https://www.wendangku.net/doc/c010410377.html,rm.Sci.180(24),4929–4939.

Li,L.,Chu,W.,Langford,J.,et al.,2010b.A contextual-bandit approach to person-alized news article recommendation.In:Proceedings of the19th International Conference on World Wide Web,ACM,pp.661–670.

Li,L.,Wang,D.,Li,T.,et al.,2011.SCENE:A scalable two-stage personalized news recommendation system.In:Proceedings of the34th International ACM SIGIR Conference on Research and Development in Information Retrieval,ACM,pp.

125–134.

Liang,Shen-Yong,2010.Study of new similarity calculation method in collaborative ?ltering algorithm.Guang Xi University.

Liu,J.,Dolan,P.,Pedersen,E.R.,2010.Personalized news recommendation based on Click behavior.In:Proceedings of the15th International Conference on Intelli-gent User Interfaces,ACM,pp.31–40.

Lv,Y.,Moon,T.,Kolari,P.,et al.,2011.Learning to model relatedness for news rec-ommendation.In:Proceedings of the20th International Conference on World Wide Web,ACM,pp.57–66.

Qi,Qi,Chen,Zheng-Yu,Liu,Jia,https://www.wendangku.net/doc/c010410377.html,ing inferred tag ratings to improve user-based collaborative?ltering.In:Proceedings of the27th Annual ACM Sym-posium on Applied Computing,New York.

Roh,T.H.,2003.The collaborative?ltering recommendation based on SOM.Clust.

CBR Exp.Syst.Appl.25(3),413–423.

Shang,Ming-Sheng,Zhang,Zi-Ke,Zhou,Tao,2010.Collaborative?ltering with diffusion-based similarity on tripartite graphs.Physica A:Stat.Mech.Appl.389

(6),259–1264.

Sun,Shao-Hua,2005.Study of sparsity and cold starting problem in collaborative ?ltering system.Zhe Jiang University.

Wen,H.,Fang,L.,Guan,L.,2012.A hybrid approach for personalized recommenda-tion of news on the web.Expert Syst.Appl.39(5),5806–5814.

Xue,Y.,Zhang,C.,Zhou,C.,et al.,2008.An effective news recommendation in social media based on users’preference.In:Education Technology and Training,2008 and2008International Workshop on Geoscience and Remote Sensing.ETT and GRS2008,International Workshop on IEEE,vol.1,pp.627–631.

Ye,Ning,Zhang,Shuo,Huang,Xia,Zhu,Jian,2012.Collaborative?ltering recommen-dation algorithm based on item clustering and global similarity.Busin.Intell.

Finan.Eng.23(1),69–72.

Zhang,Hong-Xia,Yang,Yuan,2012.E-commerce recommendation system based on customer’s behaviors and interest drifts.J.Baoji Univ.Arts Sci.2(2), 1–5.

Zuo,Sai-zhe,Guo,Yu-cui,Gong,Shang-bao,Wu,Xu,Zhang,Hu,2010.Trust value update model based on the memory theory.J.Southeast Univ.(Nat.Sci.Ed.)40 (z2),307–312.

总时差双代号网络图时间计算参数-计算题及答案

总时差（用TFi-j表示），双代号网络图时间计算参数，指一项工作在不影响总工期的前提下所具有的机动时间。用工作的最迟开始时间LSi-j与最早开始时间ESi-j之差表示。 自由时差，指一项工作在不影响后续工作的情况下所拥有的机动时间。用紧后工作的最早开始时间与该工作的最早完成时间之差表示。 网络图时间参数相关概念包括： 各项工作的最早开始时间、最迟开始时间、最早完成时间、最迟完成时间、节点的最早时间及工作的时差（总时差、自由时差）。 1总时差=最迟完成时间—尚需完成时间。计算结果若大于0，则不影响总工期。若小于0则影响总工期。 2拖延时间=总时差+受影响工期，与自由时差无关。 3自由时差=紧后最早开始时间—本工作最早完成时间。 自由时差和总时差-----精选题解（免B) 1、在双代号网络计划中，如果其计划工期等于计算工期，且工作i-j的完成节点j在关键线路上，则工作i-j的自由时差（）。 A．等于零 B．小于零 C．小于其相应的总时差 D．等于其相应的总时差 答案：D 解析：

本题主要考察自由时差和总时差的概念。由于工作i-j的完成节点j在关键线路上，说明节点j为关键节点，即工作i -j的紧后工作中必有关键工作，此时工作i-j的自由时差就等于其总时差。 2、在某工程双代号网络计划中，工作M的最早开始时间为第15天，其持续时间为7天。 该工作有两项紧后工作，它们的最早开始时间分别为第27天和第30天，最迟开始时间分别为第28天和第33天，则工作M的总时差和自由时差（）天。 A．均为5 B．分别为6和5 C．均为6 D．分别为11和6 答案：B 解析： 本题主要是考六时法计算方法 1、工作M的最迟完成时间=其紧后工作最迟开始时间的最小值所以工作M 的最迟完成时间等于[28，33]=28 2、工作M的总时差=工作M的最迟完成时间-工作M的最早完成时间等于28-（15+7）=6 3、工作M的自由时差=工作M的紧后工作最早开始时间减工作M的最早完成时间所得之差的最小值： [27-22；30-22]= 5。 3、在工程网络计划中，判别关键工作的条件是该工作（）。

数据挖掘领域的十大经典算法原理及应用

数据挖掘领域的十大经典算法原理及应用 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1.C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV 机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面

K-means算法的实现与应用举例

K-means 算法的实现与应用举例 1 K-means 方法 K-means 算法如下： S1：初始化，聚类中心k c ,,c c 21，标号集 k I I I 21； S2： 分类： end ;i I I ; c x c x j n i for j j T j i j i k j **1*min arg :1 S3：重新计算聚类中心： end ;x I c k j for j I i i j j 1 :1 S4：迭代S2-S3，直至收敛。 其matlab 程序见附录1。 2实验 实验1 随机生成300个 44, 之间的二维数对，用K-means 算法将其分为两类（其matlab 程序见附录2），如fig1，由图1(b)可看出，离群点对聚类中心的位置有明显的影响。 实验2 随机生成600个二维数对，其中300个落于以（0,0）为圆心的单位圆，另外300 (a) (b) fig1 实验1

个落入（2,2）为圆心的单位圆，用K-means 算法将其分为两类（其matlab 程序见附录2），如fig2(a)，而fig2(b)则为在以上实验的基础上增加了30个干扰点之后的分类图，可见K-means 算法不能对其很好的分类，离群点对聚类中心的位置有明显的影响。 实验3 随机生成600个二维数对，其中300个落于以（0,0）为圆心的单位元，另外300个落入以（0,0）为圆心的单位圆，长半径为3短半径为2的圆盘，用K-means 算法将其分为2类（其matlab 程序见附录2），结果见fig3，可见K-means 算法同样不能对其很好的分类。 3 K-means 算法修正 修正一：实验2中增加离群点后，K-means 算法失效，是因为采用2范数计算距离，使计算出的重心与实际重心存在较大的误差。为减小误差，可以采用1-范数计算距离，或是采用中值代替均值计算新的聚类中心，即 k ,j , I i x medium c j i j 1 (a) (b) fig2 实验2 fig3 实验3

【重磅】双代号网络图时间参数计算

双代号网络图时间参数计算 双代号网络图时间参数计算 双代号网络图是应用较为普遍的一种网络计划形式。它是以箭线及其两端节点的编号表示工作的网络图。 双代号网络图中的计算主要有六个时间参数： ES：最早开始时间，指各项工作紧前工作全部完成后，本工作最有可能开始的时刻； EF：最早完成时间，指各项紧前工作全部完成后，本工作有可能完成的最早时刻 LF：最迟完成时间，不影响整个网络计划工期完成的前提下，本工作的最迟完成时间；LS：最迟开始时间，指不影响整个网络计划工期完成的前提下，本工作最迟开始时间；TF：总时差，指不影响计划工期的前提下，本工作可以利用的机动时间； FF：自由时差，不影响紧后工作最早开始的前提下，本工作可以利用的机动时间。 双代号网络图时间参数的计算一般采用图上计算法。下面用例题进行讲解。 例题：试计算下面双代号网络图中，求工作C的总时差？ 早时间计算： ES，如果该工作与开始节点相连，最早开始时间为0，即A的最早开始时间ES=0； EF，最早结束时间等于该工作的最早开始+持续时间，即A的最早结束EF为0+5=5； 如果工作有紧前工作的时候，最早开始等于紧前工作的最早结束取大值，即B的最早开始FS=5，同理最早结束EF为5+6=11，而E工作的最早开始ES为B、C工作最早结束（11、8）

取大值为11。 迟时间计算： LF，如果该工作与结束节点相连，最迟结束时间为计算工期23，即F的最迟结束时间LF=23；LS，最迟开始时间等于最迟结束时间减去持续时间，即LS=LF-D； 如果工作有紧后工作，最迟结束时间等于紧后工作最迟开始时间取小值。 时差计算： FF，自由时差=（紧后工作的ES-本工作的EF）； TF，总时差=（本工作的最迟开始LS-本工作的最早开始ES）或者=（本工作的最迟结束LF-本工作的最早结束EF）。 该题解析： 则C工作的总时差为3. 总结： 早开就是从左边往右边最大时间 早结=从左往右取最大的+所用的时间 迟开就是从右边往右边最小时间 迟开=从右往左取最小的+所用的时间 总时差=迟开-早开；或者；总时差=迟结-早结 自由差=紧后工作早开-前面工作的早结 希望你看懂啦。呵呵 工作最早时间的计算:顺着箭线，取大值 工作最迟时间的计算：逆着箭线，取小值 总时差：最迟减最早 自由时差：后早始减本早完 1．工作最早时间的计算（包括工作最早开始时间和工作最早完成时间）：“顺着箭线计算，依次取大”（最早开始时间--取紧前工作最早完成时间的最大值），起始结点工作最早开始时间为0。用最早开始时间加持续时间就是该工作的最早完成时间。 2．网络计划工期的计算：终点节点的最早完成时间最大值就是该网络计划的计算工期，

数据挖掘算法综述

数据挖掘方法综述 [摘要]数据挖掘（DM，DataMining）又被称为数据库知识发现（KDD,Knowledge Discovery in Databases）,它的主要挖掘方法有分类、聚类、关联规则挖掘和序列模式挖掘等。 [关键词]数据挖掘分类聚类关联规则序列模式 1、数据挖掘的基本概念 数据挖掘从技术上说是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。这个定义包括好几层含义: 数据源必须是真实的、大量的、含噪声的、发现的是用户感兴趣的知识, 发现的知识要可接受、可理解、可运用, 并不要求发现放之四海皆准的知识, 仅支持特定的发现问题, 数据挖掘技术能从中自动分析数据进行归纳性推理从中发掘出潜在的数据模式或进行预测, 建立新的业务模型帮助决策者调整策略做出正确的决策。数据挖掘是是运用统计学、人工智能、机器学习、数据库技术等方法发现数据的模型和结构、发现有价值的关系或知识的一门交叉学科。数据挖掘的主要方法有分类、聚类和关联规则挖掘等 2、分类 分类（Classification）又称监督学习（Supervised Learning）。监

督学习的定义是：给出一个数据集D，监督学习的目标是产生一个联系属性值集合A和类标（一个类属性值称为一个类标）集合C的分类/预测函数，这个函数可以用于预测新的属性集合（数据实例）的类标。这个函数就被称为分类模型（Classification Model），或者是分类器（Classifier）。分类的主要算法有：决策树算法、规则推理、朴素贝叶斯分类、支持向量机等算法。 决策树算法的核心是Divide-and-Conquer的策略，即采用自顶向下的递归方式构造决策树。在每一步中，决策树评估所有的属性然后选择一个属性把数据分为m个不相交的子集，其中m是被选中的属性的不同值的数目。一棵决策树可以被转化成一个规则集，规则集用来分类。 规则推理算法则直接产生规则集合，规则推理算法的核心是Separate-and-Conquer的策略，它评估所有的属性-值对（条件），然后选择一个。因此，在一步中，Divide-and-Conquer策略产生m条规则，而Separate-and-Conquer策略只产生1条规则，效率比决策树要高得多，但就基本的思想而言，两者是相同的。 朴素贝叶斯分类的基本思想是：分类的任务可以被看作是给定一个测试样例d后估计它的后验概率，即Pr（C=c j︱d），然后我们考察哪个类c j对应概率最大，便将那个类别赋予样例d。构造朴素贝叶斯分类器所需要的概率值可以经过一次扫描数据得到，所以算法相对训练样本的数量是线性的，效率很高，就分类的准确性而言，尽管算法做出了很强的条件独立假设，但经过实际检验证明，分类的效果还是

数据挖掘分类算法比较

数据挖掘分类算法比较 分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。通过对当前数据挖掘中具有代表性的优秀分类算法进行分析和比较，总结出了各种算法的特性，为使用者选择算法或研究者改进算法提供了依据。 一、决策树（Decision Trees） 决策树的优点： 1、决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。 2、对于决策树，数据的准备往往是简单或者是不必要的.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。 3、能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。 4、决策树是一个白盒模型。如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。 5、易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。 6、在相对短的时间内能够对大型数据源做出可行且效果良好的结果。 7、可以对有许多属性的数据集构造决策树。 8、决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小。 决策树的缺点： 1、对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。 2、决策树处理缺失数据时的困难。 3、过度拟合问题的出现。 4、忽略数据集中属性之间的相关性。 二、人工神经网络 人工神经网络的优点：分类的准确度高,并行分布处理能力强,分布存储及学习能力强，对噪声神经有较强的鲁棒性和容错能力，能充分逼近复杂的非线性关系，具备联想记忆的功能等。 人工神经网络的缺点：神经网络需要大量的参数，如网络拓扑结构、权值和阈值的初始值；不能观察之间的学习过程，输出结果难以解释，会影响到结果的可信度和可接受程度；学习时间过长,甚至可能达不到学习的目的。

学习18大经典数据挖掘算法

学习18大经典数据挖掘算法 本文所有涉及到的数据挖掘代码的都放在了github上了。 地址链接: https://https://www.wendangku.net/doc/c010410377.html,/linyiqun/DataMiningAlgorithm 大概花了将近2个月的时间，自己把18大数据挖掘的经典算法进行了学习并且进行了代码实现，涉及到了决策分类，聚类，链接挖掘，关联挖掘，模式挖掘等等方面。也算是对数据挖掘领域的小小入门了吧。下面就做个小小的总结，后面都是我自己相应算法的博文链接，希望能够帮助大家学习。 1.C4.5算法。C4.5算法与ID3算法一样，都是数学分类算法，C4.5算法是ID3算法的一个改进。ID3算法采用信息增益进行决策判断，而C4.5采用的是增益率。 详细介绍链接：https://www.wendangku.net/doc/c010410377.html,/androidlushangderen/article/details/42395865 2.CART算法。CART算法的全称是分类回归树算法，他是一个二元分类，采用的是类似于熵的基尼指数作为分类决策，形成决策树后之后还要进行剪枝，我自己在实现整个算法的时候采用的是代价复杂度算法， 详细介绍链接：https://www.wendangku.net/doc/c010410377.html,/androidlushangderen/article/details/42558235 3.KNN(K最近邻)算法。给定一些已经训练好的数据，输入一个新的测试数据点，计算包含于此测试数据点的最近的点的分类情况，哪个分类的类型占多数，则此测试点的分类与此相同，所以在这里,有的时候可以复制不同的分类点不同的权重。近的点的权重大点，远的点自然就小点。 详细介绍链接：https://www.wendangku.net/doc/c010410377.html,/androidlushangderen/article/details/42613011 4.Naive Bayes(朴素贝叶斯)算法。朴素贝叶斯算法是贝叶斯算法里面一种比较简单的分类算法，用到了一个比较重要的贝叶斯定理，用一句简单的话概括就是条件概率的相互转换推导。 详细介绍链接：https://www.wendangku.net/doc/c010410377.html,/androidlushangderen/article/details/42680161 5.SVM(支持向量机)算法。支持向量机算法是一种对线性和非线性数据进行分类的方法，非线性数据进行分类的时候可以通过核函数转为线性的情况再处理。其中的一个关键的步骤是搜索最大边缘超平面。 详细介绍链接：https://www.wendangku.net/doc/c010410377.html,/androidlushangderen/article/details/42780439 6.EM(期望最大化)算法。期望最大化算法，可以拆分为2个算法，1个E-Step期望化步骤,和1个M-Step最大化步骤。他是一种算法框架，在每次计算结果之后，逼近统计模型参数的最大似然或最大后验估计。

大数据时代的空间数据挖掘综述

第37卷第7期测绘与空间地理信息 GEOMATICS ＆SPATIAL INFOＲMATION TECHNOLOGY Vol．37，No．7收稿日期：2014－01－22 作者简介：马宏斌（1982－），男，甘肃天水人，作战环境学专业博士研究生，主要研究方向为地理空间信息服务。 大数据时代的空间数据挖掘综述 马宏斌1 ，王 柯1，马团学 2（1．信息工程大学地理空间信息学院，河南郑州450000；2．空降兵研究所，湖北孝感432000） 摘 要：随着大数据时代的到来，数据挖掘技术再度受到人们关注。本文回顾了传统空间数据挖掘面临的问题， 介绍了国内外研究中利用大数据处理工具和云计算技术，在空间数据的存储、管理和挖掘算法等方面的做法，并指出了该类研究存在的不足。最后，探讨了空间数据挖掘的发展趋势。关键词：大数据；空间数据挖掘；云计算中图分类号：P208 文献标识码：B 文章编号：1672－5867（2014）07－0019－04 Spatial Data Mining Big Data Era Ｒeview MA Hong －bin 1，WANG Ke 1，MA Tuan －xue 2 （1．Geospatial Information Institute ，Information Engineering University ，Zhengzhou 450000，China ； 2．Airborne Institute ，Xiaogan 432000，China ） Abstract ：In the era of Big Data ，more and more researchers begin to show interest in data mining techniques again．The paper review most unresolved problems left by traditional spatial data mining at first．And ，some progress made by researches using Big Data and Cloud Computing technology is introduced．Also ，their drawbacks are mentioned．Finally ，future trend of spatial data mining is dis-cussed． Key words ：big data ；spatial data mining ；cloud computing 0引言 随着地理空间信息技术的飞速发展，获取数据的手 段和途径都得到极大丰富，传感器的精度得到提高和时空覆盖范围得以扩大，数据量也随之激增。用于采集空间数据的可能是雷达、红外、光电、卫星、多光谱仪、数码相机、成像光谱仪、全站仪、天文望远镜、电视摄像、电子 显微镜、CT 成像等各种宏观与微观传感器或设备，也可能是常规的野外测量、人口普查、土地资源调查、地图扫描、 地图数字化、统计图表等空间数据获取手段，还可能是来自计算机、 网络、GPS ，ＲS 和GIS 等技术应用和分析空间数据。特别是近些年来，个人使用的、携带的各种传感器（重力感应器、电子罗盘、三轴陀螺仪、光线距离感应器、温度传感器、红外线传感器等），具备定位功能电子设备的普及，如智能手机、平板电脑、可穿戴设备（GOOGLE GLASS 和智能手表等），使人们在日常生活中产生了大量具有位置信息的数据。随着志愿者地理信息（Volunteer Geographic Information ）的出现，使这些普通民众也加入到了提供数据者的行列。 以上各种获取手段和途径的汇集，就使每天获取的 数据增长量达到GB 级、 TB 级乃至PB 级。如中国遥感卫星地面站现在保存的对地观测卫星数据资料达260TB ，并以每年15TB 的数据量增长。比如2011年退役的Landsat5卫星在其29年的在轨工作期间，平均每年获取8．6万景影像，每天获取67GB 的观测数据。而2012年发射的资源三号（ZY3）卫星，每天的观测数据获取量可以达到10TB 以上。类似的传感器现在已经大量部署在卫 星、 飞机等飞行平台上，未来10年，全球天空、地空间部署的百万计传感器每天获取的观测数据将超过10PB 。这预示着一个时代的到来，那就是大数据时代。大数据具有 “4V ”特性，即数据体量大（Volume ）、数据来源和类型繁多（Variety ）、数据的真实性难以保证（Veracity ）、数据增加和变化的速度快（Velocity ）。对地观测的系统如图1所示。 在这些数据中，与空间位置相关的数据占了绝大多数。传统的空间知识发现的科研模式在大数据情境下已经不再适用，原因是传统的科研模型不具有普适性且支持的数据量受限， 受到数据传输、存储及时效性需求的制约等。为了从存储在分布方式、虚拟化的数据中心获取信息或知识，这就需要利用强有力的数据分析工具来将

数据挖掘算法

数据挖掘的10大经典算法 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在 构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持向量机和其他分类器进行了比较。 4. The Apriori algorithm

数据挖掘十大算法

数据挖掘十大算法 数据挖掘十大算法—K 近邻算法 k -近邻算法是基于实例的学习方法中最基本的，先介绍基于实例学习的相关概念。 一、基于实例的学习。 1、已知一系列的训练样例，很多学习方法为目标函数建立起明确的一般化描述；但与此不同，基于实例的学习方法只是简单地把训练样例存储起来。 从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。 2、基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上，很多技术只建立目标函数的局部逼近，将其应用于与新查询实例邻近的实例，而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂，但它可用不太复杂的局部逼近描述时，这样做有显著的优势。 3、基于实例方法的不足： （1）分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。所以，如何有效地索引训练样例，以减少查询时所需计算是一个重要的实践问题。（2）当从存储器中检索相似的训练样例时，它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时，那么真正最“相似”的实例之间很可能相距甚远。 二、k-近邻法基于实例的学习方法中最基本的是k -近邻算法。这个算法假定所有的实例对应于n 维欧氏空间?n 中的点。一个实例的最近邻是根据标准欧氏距离定义的。更精确地讲，把任意的实例x 表示为下面的特征向量：其中a r (x ) 表示实例x 的第r 个属性值。那么两个实例x i 和x j 间的距离定义为d (x i , x j ) ，其中： 说明： 1、在最近邻学习中，目标函数值可以为离散值也可以为实值。 2、我们先考虑学习以下形式的离散目标函数。其中V 是有限集合 {v 1，... v s }。下表给出了逼近离散目标函数的k-近邻算法。 3、正如下表中所指出的，这个算法的返回值f' (x q ) 为对f (x q ) 的估计，它就是距离x q 最近的k 个训练样例中最普遍的f 值。 4、如果我们选择k =1，那么“1-近邻算法”

K-MEANS算法(K均值算法)

k-means 算法 一．算法简介 k -means 算法，也被称为k -平均或k -均值，是一种得到最广泛使用的聚类算法。 它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。 二．划分聚类方法对数据集进行聚类时包括如下三个要点： （1）选定某种距离作为数据样本间的相似性度量 k-means 聚类算法不适合处理离散型属性，对连续型属性比较适合。因此在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。下面我给大家具体介绍一下欧式距离。 假设给定的数据集 ，X 中的样本用d 个描述属性A 1,A 2…A d 来表示，并且d 个描述属性都是连续型属性。数据样本x i =(x i1,x i2,…x id ), x j =(x j1,x j2,…x jd )其中，x i1,x i2,…x id 和x j1,x j2,…x jd 分别是样本x i 和x j 对应d 个描述属性A 1,A 2,…A d 的具体取值。样本xi 和xj 之间的相似度通常用它们之间的距离d(x i ,x j )来表示，距离越小，样本x i 和x j 越相似，差异度越小；距离越大，样本x i 和x j 越不相似，差异度越大。 欧式距离公式如下： （2）选择评价聚类性能的准则函数 k-means 聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X ，其中只包含描述属性，不包含类别属性。假设X 包含k 个聚类子集X 1,X 2,…X K ； {} |1,2,...,m X x m total ==() ,i j d x x =

大数据常用的算法

大数据常用的算法（分类、回归分析、聚类、关联规则） 在大数据时代，数据挖掘是最关键的工作。大数据的挖掘是从海量、不完全的、有噪声的、模糊的、随机的大型数据库中发现隐含在其中有价值的、潜在有用的信息和知识的过程，也是一种决策支持过程。其主要基于人工智能，机器学习，模式学习，统计学等。通过对大数据高度自动化地分析，做出归纳性的推理，从中挖掘出潜在的模式，可以帮助企业、商家、用户调整市场政策、减少风险、理性面对市场，并做出正确的决策。目前，在很多领域尤其是在商业领域如银行、电信、电商等，数据挖掘可以解决很多问题，包括市场营销策略制定、背景分析、企业管理危机等。大数据的挖掘常用的方法有分类、回归分析、聚类、关联规则、神经网络方法、Web 数据挖掘等。这些方法从不同的角度对数据进行挖掘。 (1)分类。分类是找出数据库中的一组数据对象的共同特点并按照分类模式将其划分为不同的类，其目的是通过分类模型，将数据库中的数据项映射到摸个给定的类别中。可以应用到涉及到应用分类、趋势预测中，如淘宝商铺将用户在一段时间内的购买情况划分成不同的类，根据情况向用户推荐关联类的商品，从而增加商铺的销售量。 (2)回归分析。回归分析反映了数据库中数据的属性值的特性，通过函数表达数据映射的关系来发现属性值之间的依赖关系。它可以应用到对数据序列的预测及相关关系的研究中去。在市场营销中，回归分析可以被应用到各个方面。如通过对本季度销售的回归分析，对下一季度的销售趋势作出预测并做出针对性的营销改变。 (3)聚类。聚类类似于分类，但与分类的目的不同，是针对数据的相似性和差异性将一组数据分为几个类别。属于同一类别的数据间的相似性很大，但不同类别之间数据的相似性很小，跨类的数据关联性很低。(4)关联规则。关联规则是隐藏在数据项之间的关联或相互关系，即可以根据一个数据项的出现推导出其他数据项的出现。关联规则的挖掘过程主要包括两个阶段：第一阶段为从海量原始数据中找出所有的高频项目组;第二极端为从这些高频项目组产生关联规则。关联规则挖掘技术已经被广泛应用于金融行业企业中用以预测客户的需求，各银行在自己的ATM 机上通过捆绑客户可能感兴趣的信息供用户了解并获取相应信

10大算法R实现

10大算法R实现 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继 承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过 程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它 是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面

单代号搭接网络计划时间参数计算

单代号搭接网络计划时间参数计算 在一般的网络计划（单代号或双代号）中，工作之间的关系只能表示成依次衔接的关系，即任何一项工作都必须在它的紧前工作全部结束后才能开始，也就是必须按照施工工艺顺序和施工组织的先后顺序进行施工。但是在实际施工过程中，有时为了缩短工期，许多工作需要采取平行搭接的方式进行。对于这种情况，如果用双代号网络图来表示这种搭接关系，使用起来将非常不方便，需要增加很多工作数量和虚箭线。不仅会增加绘图和计算的工作量，而且还会使图面复杂，不易看懂和控制。例如，浇筑钢筋混凝土柱子施工作业之间的关系分别用横道图、双代号网络图和搭接网络图表示，如下图所示。 施工过程 名 称 施工进度（天） 1 2 3 4 5 6 7 8 9 10 11 一．搭接关系的种类及表达方式 单代号网络计划的搭接关系主要是通过两项工作之间的时距来表示的，时距的含义，表示时间的重叠和间歇，时距的产生和大小取决于工艺的要求和施工组织上的需要。用以表示搭接关系的时距有五种，分别是STS （开始到开始）、STF （开始到结束）、FTS （结束到开始）、FTF （结束到结束）和混合搭接关系。 （一）FTS （结束到开始）关系 结束到开始关系是通过前项工作结束到后项工作开始之间的时距（FTS ）来表达的。如下图所示。 扎钢筋 浇筑混凝土 支模1 支模2 支模3 1 2 4 3 5 6 8 7 9 10 支模1 2 支模2 2 支模3 2 扎筋2 1 扎筋3 1 扎筋1 1 浇筑混凝土1 2 浇筑混 凝土2 2 浇筑混 凝土3 2 支模 6 扎钢筋 3 浇筑 6 STS=4 FTF=1 STS=1 FTF=4 i j FTS i j FTS D i D j

实验三报告实验三-Kmeans算法实现

实验三报告实验三-Kmeans算法实现

北华大学开放实验报告 实验名称：实验三Kmeans算法实现 所属课程：模式识别 班级：信息10—1 学号：36 姓名：张慧

实验三、K_means算法实现 一、背景知识简介： Kmeans算法是一种经典的聚类算法，在模式识别中得到了广泛的应用，基于Kmeans的变种算法也有很多，模糊Kmeans、分层Kmeans 等。 Kmeans和应用于混合高斯模型的受限EM算法是一致的。高斯混合模型广泛用于数据挖掘、模式识别、机器学习、统计分析。Kmeans的迭代步骤可以看成E步和M步，E：固定参数类别中心向量重新标记样本，M：固定标记样本调整类别中心向量。K均值只考虑（估计）了均值，而没有估计类别的方差，所以聚类的结构比较适合于特征协方差相等的类别。 二、k-means聚类算法 k-means 算法接受参数 k ；然后将事先输入的n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点

为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。 （1）算法思路： 首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。 （2）算法步骤： step.1---初始化距离K个聚类的质心（随机产生） step.2---计算所有数据样本与每个质心的欧氏距离，将数据样本加入与其欧氏距离最短的那个质心的簇中（记录其数据样本的编号） step.3---计算现在每个簇的质心，进行更新，判断新质心是否与原质心相等，若相等，则迭代结束，若不相等，回到step2继续迭代。 （3）算法流程图

数据挖掘中的文本挖掘的分类算法综述

数据挖掘中的文本挖掘的分类算法综述 摘要 随着Internet上文档信息的迅猛发展，文本分类成为处理和组织大量文档数据的关键技术。本文首先对数据挖掘进行了概述包括数据挖掘的常用方法、功能以及存在的主要问题；其次对数据挖掘领域较为活跃的文本挖掘的历史演化、研究现状、主要内容、相关技术以及热点难点问题进行了探讨；在第三章先分析了文本分类的现状和相关问题，随后详细介绍了常用的文本分类算法，包括KNN 文本分类算法、特征选择方法、支持向量机文本分类算法和朴素贝叶斯文本分类算法；；第四章对KNN文本分类算法进行深入的研究，包括基于统计和LSA降维的KNN文本分类算法；第五章对数据挖掘、文本挖掘和文本分类的在信息领域以及商业领域的应用做了详细的预测分析；最后对全文工作进行了总结和展望。 关键词：数据挖掘，文本挖掘，文本分类算法 ABSTRACT With the development of Web 2.0, the number of documents on the Internet increases exponentially. One important research focus on how to deal with these great capacity of online documents. Text classification is one crucial part of information management. In this paper we first introduce the basic information of data mining, including the methods, contents and the main existing problems in data mining fields; then we discussed the text mining, one active field of data mining, to provide a basic foundation for text classification. And several common algorithms are analyzed in Chapter 3. In chapter 4 thorough research of KNN text classification algorithms are illustrated including the statistical and dimension reduction based on LSA and in chapter 5 we make some predictions for data mining, text mining and text classification and finally we conclude our work. KEYWORDS： data mining, text mining, text classification algorithms，KNN 目录 摘要 (1) ABSTRACT (1) 目录 (1)

数据挖掘中十大经典算法

数据挖掘十大经典算法 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和Barnard 将支持向量机和其他分类器进行了比较。 4. The Apriori algorithm Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。 5. 最大期望(EM)算法 在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。 6. PageRank PageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里?佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个