基于MapReduce的关联规则数据挖掘在电信网络运营分析中的应用

1、基于MapReduce的关联规则数据挖掘在电信网络运营分析中的应用? /.基于MapReduce的关联规则数据挖掘在电信网络运营分析中的应用苗宇，侯春萍北京邮电大学大学电子工程学院，北京市100876摘要：本文基于电信运营商建设大数据共享平台的应用需求和现状，研究相关技术，提出了利用开源框架Hadoop对海量信令数据进行挖掘，以弥补传统作业系统在这方面的缺陷与不足，设计并实现了基于MapReduce的并行化Apriori算法，通过关联规则挖掘发现移动通信网络业务量和业务质量的数据突变状况。实验结果表明，该方法能够有效地从海量数据中发现数据突变的相关业务因素和场景，为上层

2、应用有针对性解决数据突变问题提供依据。关键词：数据挖掘; 关联规则; 海量数据; Hadoop; 运营分析中图分类号： TP391Application of MapReduce-Based AssociationRule Data Mining on Operation ofTelecommunication NetworkMiao Yu, Hou Chun-PingDepartment of Electronic Engineering, Beijing University of Posts and Telecommunications,Beijing 100876Abstract: T

3、his paper based on the requirements and status of constructing data-sharingplatform for telecom operators, proposed using the Hadoop open source framework formassive signaling data mining analysis to make up for the defects and deficiencies oftraditional monitoring system. A Hadoop-based signaling m

4、ining platform and aMapReduce-based Apriori Algorithm is designed and implemented to discover the associationrules on network service quality and data mutation. The experimental results show that, themethod can effectively discover a variety of business factors and scenarios which lead to themutatio

5、n, and provide support for the upper application to solve the problem.Key words: Data Mining; Association Rule; Big Data; Hadoop; Operation Analysis- 1 -? /.0 IntroductionWith the rapid development of mobile communication, coexisting of 2G/3G/4G system,appearence of comlpex types of tele

6、communication equipments, and dispersive mode of con-straction, the traditional network management system of operators are facing great challenges.Network management system ought to be cloud-based, integrated, intelligent, automatic infuture. One of the significant directions for the evolution of NM

7、S is 3-layered architectureincluded Network Element and Equipment Layer, Acquisition layer and Data-Sharing Layer.Among them, the Data-Sharing Layer is responsible for integrating various types of data andproviding unified data service for all of upper layer applications. Therefore operators will ha

8、vea natural advantage of collecting big data1.However, as the dramatic increasing in data size, the traditional method of signaling mon-itoring is no longer applicable under the new data sharing platform. Meanwhile, huge amountsof data need to refine and sublimate into useful infomation to be provid

9、ed to analysts ordecision-makers. Thus it is necessary to collect and mine big data to get valuable information.The Apache Hadoop software library is a framework that allows for the distributed pro-cessing of large data sets across clusters of computers using simple programming models. Itprovides a

10、solution for deal with massive data.In this paper, we proposed a big data processing framework based on R and Hadoop,then operated data mining for data mutation on Gn signaling. Association rule data miningalgorithm Apriori and its parallelization in MapReduce framework are described in Section 1.Se

11、ction 2 proposed some pre-processing methods on Gn interface signaling as the data source.In Section 3, we built up a data mining platform on Hadoop and achieve association rulesmining to find data mutation. By analyzing results, we discovered that .1 MapReduce-Based Association Rule Data MiningAlgo

12、rithm1.1 Fundamental Principle of Association RuleAssociation rule2 learning is a popular and well researched method for discovering inter-esting relations between variables in large databases by R.Agrawal in 1993. Association rulegeneration is usually split up into two separate steps: First, minimu

13、m support is applied tofind all frequent itemsets in a database; Second, these frequent itemsets and the minimumconfidence constraint are used to form rules.Assume that I = i1, i2, . . . , ik is a collection of items, called itemset. A k?itemset is a setof items which contains k items. Task-related

14、data set D is a collection of database transactionswhere each transaction T composed by item, and T ? I. Each transaction has an identifier,- 2 -? /.called TID. Assume that X is an itemset and transaction T contains X, iff X ? T . Associationrules are shaped like the implication X ? Y ,

15、X ? I, Y ? I, and X Y 6= . To make X ? Yfounded in the transaction set D should have Support and Confidence. Support means thepercentage of transactions in D contain X Y , that is probability P (X Y ). Confidencerepresents that the percentage of transactions contain X in D contain Y , that is probab

16、ilityP (X|Y ). If an itemset meets the minimun support threshold (minSupport), this itemset is afrequent itemset. A rule which meeting the minimum support threshold (minSupport) andthe minimum confidence threshold (minConfidenct) at the same time is called a strong rule.Strong rules are not always i

17、nterested, Support?Confidence framework is not enough to filerout the association rules that are not interested. To deal with this problem, correlation measurecould be used to expand. The lift is a simple correlation measure. Itemset X is independentof Y , if P (X X) = P (X)P (X), otherwise X is dep

18、endent of Y . list is defined as follows:lift(X,Y ) =P (X Y )P (X)P (Y )(1)If the value is less than 1, then X and Y are inversely correlated, it means ones apperancecould lead to another does not appear. If greater than 1, X and Y are positive correlated,it means that ones appearance contains anoth

19、ers appearance. If equal to 1, X and Y areindependent.1.2 Apriori AlgorithmAssociation rules are present in the reaction between two or more correlation attributes,which are designed to predict the value of some properties from other attribute values. Atthe same time it can be promoted to reflect th

20、e knowledge of dependence or relation betweenevents. The most famous association rule data mining algorithm is called Apriori3 whichwas proposed by R.Agrawal. Apriori algorithm uses a property called Apriori Property toscan the databases for multiple times. Frequent 1-itemset L1 is generated from th

21、e first tripto the database. Before the kth scan, the candidate itemset Ck will be generated from Lk?1.Then calculate the Support of each item in Ck by the kth scanning. Lk is an itemset which iscomposed by the items meeting he minSupport. The whole process terminates when Ck = or Lk = . The Apriori

22、 Property and pseudo code as Fig.1.Theorem 1 (Apriori Property). Any subset of frequent itemset must be frequent.1.3 MapReduce-Based Association RuleMapReduce4 using the idea of ”divide and conquer” to operate on large data sets, a jobis distributed to each node under the management of a master node

23、 to complete, and thenthrough the integration of the intermediate results of the sub-node to get the final result.Above- 3 -? /.Data: Transaction database DResult: Frequent itemset of size k1 Ck: Canidate itemset of size k;2 Lk: Frequent itemset of size k;3 L1 = frequent items;4 int k =

24、1;5 while Lk 6= do6 Ck+1 = Lk ./ Lk;7 foreach t D do8 c.count+ + c Ck+1;9 Lk+1 = c Ck+1|c.count minSupport;10 end11 k + +;12 end13 return kLk;1: Apriori Algorithmprocess is highly abstracted into two functions, map and reduce.The map function is in chargeof spliting task into multiple subtasks, and

25、the reduce function responsible for aggregating theresults of subtasks. As for other kinds of complex problems in parallel programming, such asdistributed storage, job scheduling, load balancing, fault tolerance, network communications,responsible for processing by the MapReduce framework.The map fu

26、nction and the reduce function are the core part of MapReduce Frame. Specificfunctions of these two function achieve by the user according to their demand. Just follow theuser-defined rules to put < key, value > into and get another < key, value > or a group.In the Map phase, data stored

27、 in HDFS is divided into fixed-size split(64M default).Hadoop create a Mapper for each split to run the user-defined map function. Map function geta < K1, V 1 > as input, and output the intermediate results < K2, V2 >. Next, the intermediateresults are sorted by the key of them, results

28、which have the same key are grouped together toa new list, namely < K2, list < V >>.In the Reduce phase, Reducer reveives output data from different Mapper and sorted.Then call the user-defined reduce function to process < K2, list < V >> to obtain < K3, V3 >.Finally, r

29、esults are wrote to HDFS as file.Fig.2 is the pseudo of MapReduce?based Apripri Algorithm5 that runs on Map/Reduceframework. prune(Ck+1) function is to remove the non-frequent item set Ck+1 by eliminatingnon-frequent item sets CK with AprioriProperty.- 4 -Fig.? /.Data: Transaction databa

30、se DResult: Frequent itemset of size k1 Map transaction t in data source to all Map nodes;/* In each Map node m */2 Cm1 = size 1 frequent items at the node m;/* In Reduce, compute C1 and L1 with all Cm1 */3 C1 = frequent 1 items;/* minSupport = num / total items */4 L1 = size 1 frequent items minSup

31、port;5 k = 1;6 while Lk 6= do/* In each Map node m */* Lmk Lk mapped to each node m */* sort to remove duplicated items */7 Cm(k+1) = Lk ./ Lmk;/* In Reduce, use Apriori Property */* compute Ck+1 with all sorted Cm(k+1) */8 if k 3 then9 prune(Ck+1);10 end11 foreach t Ck+1 do/* In each Map node m */1

32、2 increment the count of all candidates in Lm(k+1) that are contained in t;13 end/* In Reduce, find Lk+1 with Lm(k+1) and minSupport */14 Lk+1 = sizek + 1frequentitems minSupport;15 k + +;16 end17 return kLk;2: MapReduce-Based Apriori- 5 -Fig.? /.2 Data Analysis and PreprocessingIn this

33、paper, we use Gn signaling as the sample data. Gn interface is an interface betweenSGSN and GGSN. It can provide WEB/WAP services access business data, user-level access list,included start-time/end-time/msisdn/UserIP/APN/LAC/CI/Protocol/Upbytes/Downbytes etc.It is transactional, line on behalf of a

34、 users access record, so it is conducive to the applicationof Apriori Algorithm. In order to ensure the quality and validity of data mining results, thereis a need for data preprocessing.1. Processing of Vacant and Error ValuesThe raw data contains a large number of vacancies values, they need to be

35、 addressedbefore the data mining. Because of the records in data set are arranged in chronologicalorder, adjacent records are not relevant, and the data which share the same cell or thesame user are dispersed in the entire data set, so we unified ignored the missing values.2. Redundant ProcessingSig

36、naling data includes 62 fields, some of the fields contain a large amount of redundantinformation, for example, telnumber/class/service etc. These fields are useless for datamining and statistic analysis on our data set,therefore they will be reduced.3. StandardizationSome of the sample data type is

37、 text-based, text-based data only for qualitative analysis,numerical calculation can not be made for this type of data ,so we converted them into textdata enumeration. In addition, some time-related fields contains data/hour/minute/second,these values are spread too thin to analysis, and in condider

38、ation of analysis demand, wereserve two fields to represent time, hour and minute. For the minute, conver them tofive minutes granularity as the starting minute.4. TransformationIn order to analyze mutations of data, we need to generate a new difference indicatorin accordance with the quantized valu

39、e difference between neighboring time granularity.As analizing the data mutation under one cell, first, to all users for each cell calculateits quantify fields as a summation field and calculate its ratio fields as averaging field.For example, one cell whose lac is 22852 and ci id 4414, sum upbytes

40、as a new fieldupbytesSum, averaging upflow as a new field upflowAvg; Then, make the difference onthese statistical fields between record in this granularity and the previous granularity. Ifthe corresponding field in previous granularity is none, use zero instead. For example,assume that the upbytes

41、in this 5-minutes-granularity is 10, and it is 2 five minutes before,then upbytesc(difference field) is 8 in current granularity.- 6 -? /.5. DiscretizationAs Apriori algorithm is a Boolean Association rule, so we need to discrete quantitativefields in sample data. The traditional method

42、usually discrete coninuous values intoequivalent intervals. But we can not determine the levels of values in our sample datajust on the basis of equivalent partition, because their probability distribution is unknown.Thus we adopt the method of k-means6 clustering to obtain the division of the inter

43、vals,and then discrete data into them, labels of intervals in 1-5.After pre-processing, we obtain the following main fields in Table 1.3 Experiment and Result3.1 Experimental Platform IntroductionTo achieve our proposed method, we set up a Hadoop-based data mining platform anduse RHadoop as the inte

44、rface between Hadoop and R. RHadoop is an open source product tocombine Hadoop and R. It allows us to use the R language environment on a Hadoop cluster,by making use of the natural advantages of the R language for data analysis, which greatlysimplifies the complexity of writing data mining algorith

45、m program. RHadoop includes threepackages, rhdfs/rmr2/rhbase, corresponding to HDFS/MapReduce/HBase in Hadoop architec-ture respectively.1: Data fields and format after pre-processingIndex Field Format Sample1 s hour 24? hour 132 s minute 5?minute 553 lac decimal integer 228524 ci decimal integer 44

46、145 area string ”residential”6 city string ”Fuzhou”7 upbytesc decimal integer 21034208 downbytesc decimal integer 86669119 delaytimec decimal integer 311710 upflowc decimal fraction 546.2511 downflowc decimal integer -106.5412 uperrratec decimal fraction 0.0913 downerrratec decimal fraction -0.01Ove

47、rall architecture of experimental platform in Fig 3. On the basis of the platform- 7 -Tab.? /.3: Architecture of Experimental Platformabove, we realized the data pre-processing, data mining and visualization components. Datacleaning and reduction phrase are executed in reading stage. Dat

48、a transformation is achievedby hives analytic function LAG like used in Oracle Database. MapReduce-based AssociationRule Algorithm Apriori and MapReduce-based Clustering Algorithm Kmeans are implementedboth in R language. The input data and the output results are stored into HDFS.3.2 Data Mining Ope

49、ration and Result AnalysisIn this experiment,the Gn signaling data is used as an analysis object. Data is stored inHDFS in csv format, each record represents a row in files. The originnal data size is 130G, con-tains 1675829442 records, stored in 5 data nodes with 3 redundant backup. Fields 1-6 from

50、 Ta-ble 1 were assgined to be the rhs(right hand side) of result rules, and 7-13 as lhs(left hand side).We set minSupport as 0.001 and minConfidence as 0.9. The top 20 rules sorted by lift asshown in Fig.4. Each circle represents a rule, arrows point to it are lhs. And rhs is representedby the arrow

51、s starting from the circle. The size of the circle on behalf of the Support, colordepth on behalf of lift. As can be seen from the results, three rules which has the high lift sharedownbytesc = 1 as the rhs. One cell(lac = 24581, ci = 13332, area = commercial centre)has suffered from a DownLoad Drop

52、 during the period of 14 with confidence = 1, lift = 78.DownLoad Flow dramatically increased in cell(lac = 24579, ci = 48062, area = urban road)the period of 12. By querying the log in existing networks, we verified these results.- 8 -Fig.? /.s_hour=12s_hour=13s_hour=14lac=23005lac=24579

53、lac=24581lac=24834ci=13332ci=17717ci=48062ci=48303ci=55412ci=55662ci=56023ci=56631ci=56692ci=64231area=commercial centrearea=high speedarea=office buildingarea=public institutionarea=railway stationarea=urban roaddownbytesc=1downbytesc=2 downbytesc=5downflowc=54: Top 20 rules sorted by lift4 ConclusionThis paper researched the big data proce