JP6018024B2 - CHANGE DETECTION DEVICE, CHANGE DETECTION SYSTEM, CHANGE DETECTION METHOD, AND PROGRAM - Google Patents

Description

  The present invention relates to a change detection device, a change detection system, a change detection method, and a program.

  In recent years, microblogging services that allow users to easily post (entry) and share impressions and awareness in short documents have become widespread. This microblogging service is attracting attention as a judgment material for marketing business policies, etc., because it allows timely feedback from the general public. Some typical microblog services publish an API (Application Programming Interface) that can automatically acquire data by a computer, and microblog stream data (hereinafter referred to as a set of data sequentially entered in a microblog). , Called stream data) is becoming widespread.

  Since the above-mentioned stream data is written by many general users as a formal feature, the amount of data generated as a whole service is large. In addition, as a characteristic feature, since the target of writing covers all the interests of the user, there are various types of content.

  In general, in order to perform data analysis with certain data characteristics in real time (timely) and efficiently at a minimum cost, predetermined data to be analyzed (for example, terms that serve as judgment materials for marketing business policies) Filter product names only)) in real time to reduce the amount of data to be processed. In addition, during a period when the change in the amount of data generated within a certain period is drastic, there is a high probability that unusual content will appear. Is the data to be analyzed.

  However, since a user who subscribes to the microblog service, that is, a human being is a data generation subject, the amount of data to be generated fluctuates periodically according to the human life cycle in the short term. In the long run, it will change according to the popularity of microblogging services. In addition, the amount of data generated for each analysis target varies. Therefore, the reference (threshold value) for determining the period in which the change in the appearance frequency pattern of the predetermined data to be analyzed is drastically changes according to the state of the element. For this reason, it is difficult for an analyst to consider all factors in advance, and to set and maintain a standard for determining a period in which the change in the appearance frequency pattern of the predetermined data to be analyzed is a severe change as the data appearance frequency change period. It is difficult to detect changes autonomously in real time.

  As the simplest technique of the above-mentioned stream data, the real-time detection method that detects the time when the data appearance frequency pattern of the predetermined data to be analyzed changes, and the time when the appearance frequency of the predetermined data suddenly changes is detected at almost the same time. There is a method in which a threshold value is set in advance, and the moment when the appearance frequency of the predetermined data exceeds the threshold value is regarded as a change time point and notified.

  In addition, in the sensor network composed of a large number of individual sensors that measure the surrounding environment without interruption and transmit the measured values in a stream, the data transmission amount reduction algorithm that reduces the data transmission amount of the sensor is used for the real-time detection described above. There is also a technique. The data transmission reduction algorithm focuses on the fact that data values measured in nature often have periodicity. First, the period is divided into a plurality of partial periods that do not suffer from each other, and the average and standard deviation of the values for each partial period are calculated from the accumulated past data. The individual sensor reduces the data transmission amount by transmitting data when the actually measured value exceeds the range calculated from the average and the standard deviation. In addition, in order to prevent the calculated range from becoming obsolete, the range is updated by using past data at regular intervals. In this data transmission amount reduction algorithm, the case in which the sensor transmits data is replaced with a case in which a change has occurred, and is used for real-time detection.

Energy-Efficient Sensor Data Acquisition based on Periodic Patterns, Guan-Rong Lin, Yao-Chung Fan, En Tzu Wang, Tao Zou, Arbee L.P. Chen, 2009 15th International Conference on Parallel and Distributed Systems, IEEE COMPUTER SOCIETY, 2009

  However, since the threshold value is fixed in the method in which the threshold value is set in advance, the detection accuracy in an environment in which the appearance frequency of the predetermined data to be analyzed is different, which can be regarded as normal depending on the passage of time and the time zone. It was not good.

  In addition, since the method using the data transmission amount reduction algorithm is based on an algorithm aimed at reducing the data transmission amount in the first place, measurement of a value outside the threshold range does not necessarily change the appearance frequency of the predetermined data. It is not shown. In response to the problem of improving the accuracy of detecting sudden changes in the frequency of data appearance, detailed evaluation in the method using the data transmission amount reduction algorithm and the improvement of accuracy by feedback of the evaluation are subject to the above-mentioned issues Therefore, there is a case where it does not contribute to improvement of change detection accuracy. In addition, past data is used at regular intervals and the range is updated, so it is necessary to accumulate past data. If the criteria (threshold) changes before the update timing, the change is reflected until the update timing. There are things that cannot be done.

  The present invention has been made in view of the above, and includes a change detection apparatus and a change detection system that can accurately detect in real time a change in the appearance frequency of predetermined data to be analyzed included in stream data. An object of the present invention is to provide a change detection method and program.

  In order to solve the above-described problems and achieve the object, the change detection device according to the embodiment is based on the appearance frequency of predetermined data included in stream data, which is aggregated for each divided period within a predetermined period. A prediction unit for calculating a predicted value of the frequency of occurrence of the predetermined data in a future segment period, a predicted value in a current segment period among the calculated forecast values, and an aggregation in the current segment period In addition, when the difference from the appearance frequency of the predetermined data exceeds a threshold value based on the appearance frequency pattern of the predetermined data aggregated for each of the division periods, it is determined that the appearance frequency of the predetermined data has changed. And a determination unit.

  According to the change detection device according to the embodiment, there is an effect that it is possible to accurately detect the appearance frequency of the predetermined data to be analyzed included in the stream data in real time.

FIG. 1 is a diagram illustrating an example of a configuration of a change detection system according to the embodiment. FIG. 2 is a ladder chart illustrating an example of the operation of the change detection system according to the embodiment. FIG. 3 is a diagram for explaining a cycle for the number of appearances of predetermined data. FIG. 4 is a graph illustrating the relationship between the acceleration of the appearance frequency of the predetermined data and the passage of time. FIG. 5 is a diagram illustrating an example of a storage area. FIG. 6A is a graph illustrating a normal prediction update method. FIG. 6B is a graph illustrating an example of a modified prediction update method. FIG. 7 is a graph illustrating the drift effect. FIG. 8 is a graph illustrating erroneous detection of a burst due to a scale. FIG. 9 is a graph illustrating bursts in successive appearances of MACD differences equal to or less than a threshold value. FIG. 10 is a graph illustrating detection of bursts such as drift. FIG. 11 is a diagram illustrating notification by the notification unit. FIG. 12 is a diagram illustrating that the processing in the change detection device of the change detection system according to the embodiment is specifically realized using a computer.

  Hereinafter, a change detection device, a change detection system, a change detection method, and a program according to embodiments will be described in detail with reference to the accompanying drawings. In the following description, common constituent elements are given common reference numerals, and redundant description is omitted.

  FIG. 1 is a diagram illustrating an example of a configuration of a change detection system 1 according to the embodiment. FIG. 2 is a ladder chart illustrating an example of the operation of the change detection system 1 according to the embodiment.

  As shown in FIG. 1, the change detection system 1 includes a pattern detection device 10, a frequency counting device 20, and a change detection device 30. In the stream data that many users enter without interruption in a micro block service or the like, The appearance pattern of the predetermined data is recognized and the appearance status of the pattern is monitored. Then, the change detection system 1 detects and notifies the time point at which the appearance frequency of the predetermined data suddenly changes (burst) as a pattern change occurrence time at approximately the same time as the change time. The predetermined data to be analyzed here is a term or the like that is a material for determining the marketing business policy, and may be a product name as an example. This predetermined data is registered in advance by a user input operation or the like.

  The pattern detection apparatus 10 sequentially monitors input stream data, and detects a pattern of appearance frequency of predetermined data registered in advance for the stream data (FIG. 2: S1). The pattern detection apparatus 10 notifies the frequency counting apparatus 20 of the appearance information indicating the description of the detected pattern and the detected fact in real time for each detection (FIG. 2: S2). The real-time notification in the pattern detection apparatus 10 indicates that the time difference between detection and notification is within a predetermined time. In this embodiment, it is assumed that this time difference is 10 seconds or less.

  It is assumed that the appearance frequency of the predetermined data detected by the pattern detection apparatus 10 has an environment showing periodicity. One example of the periodicity is a life rhythm of a user who enters data. For example, when the predetermined data is a food name or the like, many entries are expected in the meal time zone of the user in the daily cycle, and no entries are expected outside the meal time zone. Therefore, when the appearance frequency is aggregated in the partial period (segment period) divided by a predetermined interval, the appearance frequency of the predetermined data in the partial period corresponding to the meal time zone is large, and it corresponds to other time zones The appearance frequency of the predetermined data in the partial period is reduced.

  FIG. 3 is a diagram for explaining a cycle of appearance frequency of predetermined data. In FIG. 3, each cycle is Tn (n is a natural number, and the cycle at the start of observation is 1). One period is composed of a fixed number of partial periods having the same length and not sharing each time. The number of the partial periods is the same in all the cycles that are the division sources. Each partial period is given a serial number in the order of constituting the period. For example, in FIG. 3, the cycle has three partial periods, and the partial periods constituting each cycle are assigned serial numbers 1, 2, and 3 according to the order of the components.

  Accordingly, in each cycle, the partial periods having the same number of serial numbers assigned to the partial periods are partial periods corresponding to each other in the past, the present, and the future. For example, when the current time corresponds to the partial period T2-2 of the period T2, the past partial period one period before corresponding to the partial period T2-2 is T1-2. Further, the partial period of the future cycle Tn corresponding to the partial period T2-2 is Tn-2. As shown in FIG. 3, the appearance frequency of the predetermined data shows a periodicity that is large in the partial periods T1-2, T2-2,..., Tn-2 and decreases in the other partial periods.

  The frequency counting device 20 totals the appearance frequencies of the detected predetermined data for each partial period divided within a predetermined period. Specifically, the frequency counting device 20 holds a list of patterns registered in the pattern detection device 10, and counts notifications from the pattern detection device 10 for each pattern (FIG. 2: S3). Then, the frequency counting device 20 outputs the counting result as frequency information to the change detecting device 30 when the partial period changes based on the time measured by the RTC (Real Time Clock) function (FIG. 2: S4).

  In addition, about a period and a partial period, an appropriate value shall be preset through a user's operation input. For example, the period may be a daily unit, a weekly unit, a monthly unit, or the like. In addition, the partial period may divide the cycle into equal parts, and may be in units of 10 minutes or 1 hour when the period is set in units of one day.

  The frequency tabulation device 20 outputs the tabulation result as frequency information to the change detection device 30, and then resets the tabulation result for each pattern to 0 and continues the tabulation.

  For example, it is assumed that the pattern detection apparatus 10 notifies the pattern A three times, the pattern B twice, the pattern C zero times during a certain partial period (T2-1). Then, during the subsequent partial period (T2-2), it is assumed that the pattern detection device 10 notifies the pattern A twice, the pattern B zero times, and the pattern C once.

  The frequency counting device 20 indicates that the pattern A appears 3 times, the pattern B 2 times, and the pattern C 0 times at the time of transition to a partial period (T2-2) following a certain partial period (T2-1). Output to the change detection device 30. In addition, the frequency counting device 20 shows that the pattern A appears twice, the pattern B appears zero, and the pattern C appears once at the time of transition from the subsequent partial period (T2-2) to the subsequent partial period (T2-3). This fact is output to the change detection device 30. In this embodiment, in order to simplify the description, the case of 0 times is also notified. However, when not notified, it is assumed that 0 is calculated, and in the case of 0 times, it is not necessary to notify.

  Further, in the present embodiment, the frequency counting device 20 uses an exponential moving average (Exponential Moving Average) of appearance frequencies using short windows and long windows of different sizes instead of simple aggregation of appearance frequencies for each appearance frequency pattern of predetermined data. Calculate Average). Then, the frequency counting device 20 sets the EMA value using the short window among the calculated EMA values as the appearance frequency (number of appearances) regarding the predetermined data, and the EMA value using the long window from the EMA value using the short window. The subtracted difference, MACD (Moving Average Convergence and Divergence) exponential smoothing moving average (MACD Histogram) is used.

  This MACD Histogram is the acceleration of the appearance frequency number change. The calculation of the EMA value uses appearance frequency data of predetermined data measured in a plurality of continuous partial periods as an input, and a plurality of continuous partial periods serving as inputs for the calculation correspond to windows. The window size is a value that determines how many sub-periods are traced back from “now”. For example, in the present embodiment, the length of the short window is set to 7, the length of the long window is set to 9, and the length of the window used for calculating the MACD histogram is set to 5, but this value is an area to which the system is applied. It is possible to give a more appropriate value.

  The change detection device 30 includes a prediction unit 31 and a determination unit 32. Based on the frequency information output from the frequency counting device 20, the change detection device 30 uses the prediction unit 31 and the determination unit 32 to determine the burst time point at which the appearance frequency of the predetermined data changes rapidly as the pattern change occurrence time point. Then, a process of detecting and notifying at approximately the same time as the change time (FIG. 2: S5) is executed.

  The prediction unit 31 calculates a predicted value of the appearance frequency of the predetermined data in the future partial period based on the appearance frequency of the predetermined data included in the stream data, which is aggregated for each partial period by the frequency totaling device 20 (FIG. 2: S51). The determination unit 32 has a difference between a prediction value in the current partial period in the prediction values calculated by the prediction unit 31 and an appearance frequency of the predetermined data tabulated as the current partial period by the frequency tabulation device 20. When the threshold based on the appearance frequency pattern of the predetermined data aggregated for each partial period is exceeded, it is determined that the burst has changed in the appearance frequency of the predetermined data (FIG. 2: S52).

  When it is determined as a burst by the determination unit 32, it is output to a display or the like as a notification of a change that a burst is currently occurring, and is notified to the user. Further, the determination result (change determination) by the determination unit 32 is notified to the prediction unit 31. The prediction unit 31 updates the predicted value of the appearance frequency of the predetermined data in the future segment period corresponding to the current segment period based on the determination result.

  FIG. 4 is a graph illustrating the relationship between the acceleration of the appearance frequency of the predetermined data and the passage of time. Specifically, FIG. 4 is a graph for specifically illustrating detection of a point in time when a burst, which is a rapid change in the data appearance frequency pattern (= point of occurrence of an abnormality in the data appearance frequency pattern). In FIG. 4, the vertical axis of the graph represents the value of MACD histogram (acceleration), and the horizontal axis represents the passage of time. Further, the cycle is in units of one day, and one of the bar graphs corresponds to one partial period.

  Since the microblog information is generated (written) by a human user, for example, when the information is limited to a certain region such as Japan, the appearance frequency of a certain pattern varies depending on the time zone. For example, food-related topics have many meal time periods, and the frequency of appearance in other time periods is greatly reduced compared to meal time periods.

  Therefore, in the world such as microblogging, even if the appearance frequency suddenly increases in a certain time zone as in the second bar graph from the left in FIG. This is because, as in the seventh bar from the left in FIG. 4, it may increase as much in the same time zone on other days. Therefore, in this embodiment, in the above-described case, it is not regarded as a burst, and unlike the same time zone on other days as in the eighth bar from the left in FIG. Then, it is detected that a burst has occurred.

  Therefore, the prediction unit 31 manages the predicted value of the future partial period based on the frequency information of the partial period actually measured up to the present time. Then, the determination unit 32 evaluates the predicted value of the partial period and the frequency information measured in the current partial period, and determines whether or not a burst is occurring in the current partial period.

  The prediction unit 31 secures a storage area for managing the predicted value of the partial period. FIG. 5 is a diagram illustrating an example of the storage area R.

  As shown in FIG. 5, the prediction unit 31 provides a storage area R that manages a partial period constituting at least one period. Note that the prediction unit 31 may provide a storage area R that manages a partial period for each of a plurality of periods. In this embodiment, one period is composed of 144 (6 × 24) partial periods, but the user can select a value suitable for the application environment. In the partial period secured in the storage area R, the predicted value calculated by the prediction unit 31 is stored. This predicted value is updated to a new predicted value at the timing when the current measured value (frequency information) for the corresponding partial period is obtained.

  Specifically, one cycle is one day, and each day is composed of 144 partial periods each having a length of 10 minutes. Here, assuming that the current time is 10:08, predictions of the future (tomorrow) are stored in the partial period from 61 (00:00 to 10:10), and from 62 to 144 The predictions from 10:10 to 24:00 today are stored in the partial period until. Then, the prediction unit 31 calculates the actual value of the appearance frequency data regarding the predetermined data from 10:00 to 10:10 at 10:10, and the 61st prediction value, the calculated actual value, and the determination by the determination unit 32 Using the result, the predicted value (the predicted value from 10:00 to 10:10 tomorrow) of the 61st partial period is calculated and updated.

  Here, calculation of the predicted value (update of the predicted value) in the prediction unit 31 will be described in detail. FIG. 6A is a graph illustrating a normal prediction update method. FIG. 6B is a graph illustrating an example of a modified prediction update method.

  As shown in FIGS. 6A and 6B, the prediction unit 31 measures the actual value of the appearance frequency data of the current partial period (the first bar graph of (today)) and the predicted value of the appearance frequency data of the partial period. Is used to calculate the predicted value of the appearance frequency data in the future partial period (the first bar graph of (tomorrow)). The prediction unit 31 gives different weights to the actual measurement value and the prediction value in the prediction. In general, by assigning weights based on actual measurement values, future prediction values reflect the current change (trend) while reflecting existing measurement history.

  Specifically, the prediction unit 31 is one of (update method 1. as it is), (update method 2. normal prediction), and (update method 3. modified prediction) based on the following equation (1). The predicted value is calculated using the formula.

  In Equation (1), MACDHistogramReal (p, t) means an actual measurement value of MACD Histogram for the pth partial period of period p, and MACDHHistogramPrediction (p, t) means a predicted value of MACD Histogram for the tth partial period of period p. To do. Α means a weighting value.

  In the present embodiment, the weight α is 0.5, but an appropriate value can be selected by the application destination system. Thus, in anticipating the future, it is necessary to consider two abnormal cases described later. If it is not an abnormal case, a weight α (= 0.5) is given by (update method 2. normal prediction), so that the future prediction value reflects the existing actual measurement history, and more current change (trend) A predicted value reflecting the above is calculated.

  One of the abnormal cases is a case where the current measured value is a burst and it can be seen that it is a burst. Another abnormal case is a case where a partial period in the past (partial period one period before the current partial period) is a burst and a predicted value of the corresponding partial period does not exist. For example, the second abnormal case appears early in system operation.

  In the first abnormal case, since the actual measurement value is abnormal, if the future including the abnormal actual measurement value is predicted, the future prediction has a value larger than the actual value. Therefore, in the first abnormal case, the existing predicted value is used as the future predicted value as it is, as in the formula (1) (update method 1. as it is).

  The second abnormal case needs to be corrected because the predicted value is overestimated. Specifically, as shown in FIG. 6B, the current measured value is reflected in the prediction of the future value. In this case, the prediction unit 31 calculates a predicted value by (update method 3. modified prediction) in the equation (1).

  Here, the threshold value of (update method 3. corrected prediction) is obtained by the following equation (2).

なお、（更新方式３．修正予測）の閾値は、差分のスケールは実測値と予測値の差分のｌｏｇ値を用いているが、適用先システムにより適切な値を選択可能である。

As the threshold of (update method 3. modified prediction), the difference scale uses the log value of the difference between the actual measurement value and the prediction value, but an appropriate value can be selected by the application system.

  In addition, the prediction unit 31 calculates the maximum appearance frequency predicted value (MaximumAppearanceCountPredict (p + 1)) of the predetermined data in the latest future cycle using the following equation (3) for the determination assistance of the determination unit 32.

  In addition, the prediction unit 31 calculates a current frequency prediction value (AppearanceCountPredict (p + 1, t)) of predetermined data in a future partial period using the following equation (4).

  Here, the calculation method of AppearanceCountPredict is as the following equation (5).

  Note that MaximumAppearanceCountPredict (p) is a predicted value of the maximum appearance frequency of the predetermined data in the period p, MaximumAppearanceCount (p) is an actually measured value of the maximum appearance frequency of the predetermined data in the period p, and AppearanceCountPredict (p, t) is a period of p, t. A predicted value of the maximum appearance frequency of the predetermined data in the partial period t, AppearanceCount Real (p, t) indicates a measured value of the maximum appearance frequency of the predetermined data in the period p and the partial period t, respectively.

  In the verification based on this embodiment, ACCEPTANCE_RATIO is 1.3 and T2 is 30. However, the present invention is not limited to this value, and an appropriate value can be given depending on the area to which the system is applied.

  The determination unit 32 includes a determination unit 321, a notification unit 322, and a feedback unit 323. The determination unit 321 uses the predicted value in the current partial section calculated by the prediction unit 31 and the actual measurement value of the current partial period calculated by the frequency counting device 20, and determines whether the actual measurement value of the current partial period is a burst. Determination is made (FIG. 2: S52). The notification unit 322 notifies the determination result of the determination unit 321 to the user and the prediction unit 31 (FIG. 2: S53).

  The feedback unit 323 receives evaluation (user evaluation) of the determination result notified to the user by the notification unit 322 from the user by an operation input or the like (FIG. 2: S54). Then, the feedback unit 323 feeds back the received user evaluation to the prediction unit 31 (FIG. 2: S55). In the prediction unit 31, based on the feedback of the feedback unit 323, an evaluation (currently, an update method 1. as it is), (update method 2. normal prediction), and (update method 3. modified prediction) selection (current (Existence of occurrence of bursts in the partial period).

  The determination unit 321 determines that a case in which the difference between the predicted value in the current partial section calculated by the prediction unit 31 and the actual measurement value of the current partial period calculated by the frequency counting device 20 exceeds a preset threshold is a burst. judge. However, the threshold value is not fixed, but is automatically adjusted in consideration of the feature of the pattern of the appearance frequency of the target predetermined data.

  In the present embodiment, for each pattern, the ratio between the frequency of appearance (short window EMA) in each partial period and the maximum value in that period (appearance frequency), the size of the MACD histogram in the partial period, immediately before The threshold is determined in consideration of the history of the difference in MACD histogram (the difference in MACD histogram between the latest partial periods). The scale here is the number of digits. For example, in the case of the appearance frequency, the number of digits of the value of the appearance frequency is indicated, the appearance frequency is large when the number of digits is large, and the appearance frequency is small when the number of digits is small.

  Here, events to be considered in burst determination will be described with reference to FIGS. FIG. 7 is a graph illustrating the drift effect. FIG. 8 is a graph illustrating erroneous detection of a burst due to a scale. FIG. 9 is a graph illustrating bursts in successive appearances of MACD differences equal to or less than a threshold value. FIG. 10 is a graph illustrating detection of bursts such as drift. Here, the dotted line graphs in FIGS. 7, 8, 9, and 10 indicate the appearance frequency pattern of the predetermined data calculated by prediction for a certain period. The solid line graph shows the appearance frequency pattern of the measured predetermined data.

  One of the events that should be considered in determining a burst is the drift effect. Specifically, as shown in FIG. 7, the drift effect is the same in the characteristics of the periodic pattern between the prediction and the actual measurement, but the partial period in which the pattern appears is faster between the prediction and the actual measurement. It is a nature that slows down or slows down.

  The transition of the change between the dotted line graph and the solid line graph of FIG. 7 as seen by human eyes can be determined to be the same although there is a shift in the change time. However, when the MACD histogram difference is mechanically compared and a burst equal to or greater than a certain threshold is used as a burst, there is a high possibility that the portion indicated as “Drift” in FIG. However, as shown in FIG. 10, it is necessary to correctly detect a burst like a drift as a burst.

  Also, one of the events that should be taken into account in burst determination is false detection based on an average scale. Specifically, as shown in FIG. 8, when the average scale of the frequency pattern of the predetermined data is different (Small scale) and (Big scale), erroneous detection of a burst may occur.

  For example, when the difference between the measured value and the predicted value MACD histogram (acceleration) is the same as in the graphs (Small scale) and (Big scale) in FIG. 8, the difference in the appearance frequency is also the same. However, even if a graph with a small scale of appearance frequency (Small scale) can be determined as a burst, it is difficult to determine the same difference as a burst with a graph with a large scale of appearance frequency (Big scale).

  Also, one of the events to be considered in burst determination is the continuous appearance of MACD histograms below the threshold. As shown in FIG. 9, bursts may occur depending on the continuous appearance of MACD histograms below the threshold. Here, the upper graph of FIG. 9 shows the actual measurement value and the predicted value of the pattern of the appearance frequency of the predetermined data within a certain period. Further, the lower graph of FIG. 9 shows the difference between the corresponding MACD histograms. The thick horizontal line in the lower graph is a fixed threshold for detecting a burst. As shown in FIG. 9, although it is actually a burst, there is a case where the corresponding MACD histogram is not detected as a burst because the corresponding MACD histogram is equal to or smaller than the threshold value.

  In order to determine a burst in consideration of the above-described event, the determination unit 321 determines whether the burst is performed using the following equations (a) to (d).

  Basically, as shown in equation (a), the determination unit 321 performs burst when the determination score (IdentificationScore (p, t, w)) of the partial period t of the period p is equal to or greater than the threshold value T, and It is determined that it is not a burst.

  The judgment score is the sum of the partial period t of the period p and the partial period score (Partial period scores (p, t)) of the partial period w before t as shown in the equation (b). However, in the process of subtracting t−1, t−2,..., T−w, when the value becomes x of 0 or less, the partial period uses the partial period of the previous cycle (p = p−1). , I = maximum partial period number-w).

  As shown in equation (c), the partial period score is obtained by subtracting the predicted value of MACDHistogram from the actual measured value of MACDHistogram of the partial period of the corresponding period t, and the weight based on the current appearance frequency counter (the parenthesis on the right side of the equation) The first), the weight by the ratio between the current appearance frequency counter and the maximum appearance frequency counter (predicted value) (the second parenthesis on the right side of the expression), the cancel function of the second weight on the parenthesis (the third parenthesis on the right side of the expression, This is a value obtained by multiplying the expression (d), hereinafter referred to as a cancel function.

  The weight due to the scale of the appearance frequency counter is to solve the scale problem described with reference to FIG. Thereby, even if the difference (acceleration difference) between the actual measured value of MACDHHistogram and the predicted value of MACDHHistogram is the same, a smaller data appearance frequency is more likely to be determined as a burst.

  The weight based on the ratio between the current appearance frequency counter and the maximum appearance frequency counter (predicted value) is for solving the drift problem described with reference to FIG. Thus, even if the difference (acceleration difference) between the actual measured value of MACDHistogram determined as a burst and the predicted value of MACDHistogram is not close to the current appearance frequency counter and the maximum appearance frequency counter, the burst component is low. Be evaluated.

  The cancellation function is for detecting a burst case such as drift as shown in FIG. 10 on the assumption that the drift problem described with reference to FIG. 7 is solved. In the case where the difference between the actual measurement value and the predicted value is greater than or equal to the threshold ratio W3, in order to make the determination as a burst rather than a drift, the third weight of the parenthesis on the right side of the equation (c) is cancelled. ing.

  In addition, in order to solve the problem of continuous appearance of MACDistogram below the threshold described with reference to FIG. 9, the basis of the burst determination is whether or not the sum of the latest partial period scores exceeds the threshold as shown in equation (b) And

  In the verification based on this embodiment, w is 3, T is 8, W1 and W2 are 1, and W3 is 0.5. However, the user can select a value suitable for the application environment. is there.

  Since the determination unit 321 performs the above-described calculation for burst determination for each occurrence frequency change pattern of predetermined data, the determination unit 321 manages the scores of the last w partial periods calculated in the past for each pattern and acquires the value. It has a possible device (storage area). Further, for the burst determination, the appearance frequency counter actual measurement value and prediction value, the appearance frequency count prediction value, the MACD Histogram actual measurement value and the prediction value of the predetermined data of the partial period are received from the prediction unit 31.

  The notification unit 322 notifies the user and the prediction unit 31 of the determination result of the determination unit 321. Here, notification to the user is performed, for example, by display output on a display. FIG. 11 is a diagram illustrating notification by the notification unit 322.

  As shown in FIG. 11, the absolute values of the actual measurement value and the predicted value are obtained for the partial period determined by the determination unit 321 as a burst, and notification is given when the absolute value of the actual measurement value is smaller than the absolute value of the predicted value. The unit 322 notifies the prediction unit 31 of [Update method 3: modified prediction] and notifies the user of normality. When the absolute value of the predicted value is high, the notification unit 322 notifies the prediction unit 31 [update method 1: as it is] and notifies the user of the burst. In a case where the determination unit 321 determines that the burst is not present, the notification unit 322 notifies the prediction unit 31 [update method 1: normal prediction] and notifies the user of normality.

  The feedback unit 323 determines the determination result of the system (for example, the contents of the “user” item in FIG. 11) and information (for example, illustrated in FIG. 9) in a random partial period with respect to the appearance frequency change pattern of the predetermined data. A graph or the like) is presented to the user by a display display or the like. Then, the feedback unit 323 receives the user evaluation during the presented partial period via an operation input such as a console.

  The feedback unit 323 does nothing when the determination result of the system matches the user evaluation (for example, the user evaluation “burst” with respect to the determination result “burst”). When the determination result of the system is burst and the user evaluation is not burst, the feedback unit 323 increases the threshold value T of the expression (a) in the determination unit 32 by a certain amount. When the determination result of the system is not a burst and the user evaluation is a burst, the feedback unit 323 reduces the threshold value T of the expression (a) in the determination unit 32 by a certain amount. This makes it possible to perform burst determination reflecting user evaluation.

  As described above, the change detection device 30 calculates the appearance frequency of the predetermined data in the future partial period based on the appearance frequency of the predetermined data included in the stream data, which is aggregated for each partial period divided within the predetermined period. The predicted value of is calculated. Then, the change detection device 30 calculates, for each partial period, a difference between the predicted value in the current partial period and the appearance frequency of the predetermined data totaled in the current partial period among the calculated predicted values. If the threshold based on the pattern of appearance frequency of the predetermined data is exceeded, it is determined that a change has occurred in the appearance frequency of the predetermined data. Therefore, the change detection device 30 can accurately detect in real time the appearance frequency of the predetermined data to be analyzed included in the stream data while minimizing the storage of data for calculation.

  In addition, by using the change detection device 30, it is possible for a general operation person who is not a specialist of system computing and a small amount of computing resources such as a server to recognize a change in an appearance frequency pattern related to predetermined data with high accuracy in a stream data environment. become. As a result, companies can easily analyze large-scale stream data, and companies can create new business opportunities, conduct product reputation surveys, and market trend surveys. Further, by reducing as much information necessary for the analysis work as possible, it is possible to reduce the amount of calculation resources such as servers required for constructing the system.

  Note that the current partial period in which the change detection device 30 determines that the frequency of occurrence of the predetermined data has changed has been analyzed in real time in the present embodiment, so that the current partial period Although it is a period, it is not limited to the current partial period. Specifically, the current partial period may mean a partial period that is currently a processing target for determination. For example, data (stream data) necessary for processing may be stored in a storage device such as a buffer or a hard disk drive, and the stream data may be analyzed later. In this case, the partial period which is read from the storage device and is the target of processing whether or not the appearance frequency of the predetermined data has changed is the current partial period.

  It is also possible to create a program in which the processing executed by the pattern detection device 10, the frequency counting device 20, and the change detection device 30 described in the above-described embodiments is described in a language that can be executed by a computer. In this case, when the computer executes the program, the same effect as the process in the change detection device 30 of the change detection system 1 according to the above-described embodiment can be obtained. Further, such a program may be recorded on a computer-readable recording medium, and the program recorded on the recording medium may be read by the computer and executed to realize the same processing as that of the above-described embodiment. An example of a computer that executes the above-described program will be described below.

  FIG. 12 is a diagram illustrating that the processing in the change detection device of the change detection system according to the embodiment is specifically realized using a computer. As illustrated in FIG. 12, the computer 1000 includes, for example, a memory 1010, a CPU 1020, a hard disk drive interface 1030, a disk drive interface 1040, a serial port interface 1050, a video adapter 1060, and a network interface 1070. These units are connected by a bus 1080.

  The memory 1010 includes a ROM (Read Only Memory) 1011 and a RAM (Random Access Memory) 1012. The ROM 1011 stores a boot program such as BIOS (Basic Input Output System). The hard disk drive interface 1030 is connected to the hard disk drive 1031. The disk drive interface 1040 is connected to the disk drive 1041. For example, a removable storage medium such as a magnetic disk or an optical disk is inserted into the disk drive. The serial port interface 1050 is connected to a mouse 1051 and a keyboard 1052, for example. The video adapter 1060 is connected to the display 1061, for example.

  The hard disk drive 1031 stores, for example, an OS 1091, an application program 1092, a program module 1093, and program data 1094. That is, the above program is stored in, for example, the hard disk drive 1031 as a program module 1093 in which a command to be executed by the computer 1000 is described. For example, a program module 1093 for executing the same information processing as the prediction unit 31 and the determination unit 32 illustrated in FIG. 1 is stored in the hard disk drive 1031.

  Further, the storage area R and the like described in the above-described embodiment are secured in the RAM 1012. Setting data necessary for processing is stored as program data 1094 in, for example, the memory 1010 or the hard disk drive 1031. Then, the CPU 1020 reads the program module 1093 and the program data 1094 stored in the memory 1010 and the hard disk drive 1031 to the RAM 1012 as necessary, and executes them.

  The program module 1093 and the program data 1094 are not limited to being stored in the hard disk drive 1031, but may be stored in a removable storage medium, for example, and read by the CPU 1020 via the disk drive or the like. Alternatively, the program module 1093 and the program data 1094 are stored in another computer connected via a network (LAN (Local Area Network), WAN (Wide Area Network), etc.) and read by the CPU 1020 via the network interface 1070. May be issued. Needless to say, the change detection system 1 including the pattern detection device 10, the frequency counting device 20, and the change detection device 30 may be realized by the one computer described above.

  DESCRIPTION OF SYMBOLS 1 ... Change detection system, 10 ... Pattern detection apparatus, 20 ... Frequency totaling apparatus, 30 ... Change detection apparatus, 31 ... Prediction part, 32 ... Determination part, 321 ... Determination part, 322 ... Notification part, 323 ... Feedback part, R ... storage area, 1000 ... computer.

Claims (7)

Aggregated by division period divided by the predetermined period, based on the exponential smoothing moving average of frequency of occurrence of predetermined data included in the stream data is post data, the frequency of occurrence of said predetermined data at a future sectional period A predicted value of change acceleration is calculated, and the predicted value weighted with a first value and the measured acceleration value of the change in appearance frequency weighted with a second value greater than the first value. Based on the prediction unit for updating the prediction value ,
Of the calculated predicted values, the difference between the predicted value in the current segment period and the acceleration of the change in the appearance frequency of the predetermined data aggregated in the current segment period is aggregated for each segment period. A determination unit that determines that a change has occurred in the appearance frequency of the predetermined data when a threshold based on a pattern of the appearance frequency of the predetermined data is exceeded,
A change detection device comprising: The determination unit includes a ratio between the appearance frequency scale of the predetermined data aggregated for each of the segment periods and the maximum value of the appearance frequency in the period of the segment period, the acceleration scale of the change in the appearance frequency, and the latest The threshold value is determined based on the difference in acceleration between the segment periods.
The change detection apparatus according to claim 1. The information processing apparatus further includes a notification unit that notifies the determination result of the determination unit to the prediction unit, the prediction unit based on the notified determination result, the predetermined data in a future segment period corresponding to the current segment period Update the predicted acceleration of the change in the appearance frequency of
The change detection apparatus according to claim 1 or 2, wherein A feedback unit that accepts a user input about a change in the appearance frequency of the predetermined data and feeds back a value based on the input result to the threshold;
The change detection device according to any one of claims 1 to 3, wherein A detection device that detects the appearance frequency of predetermined data included in the stream data based on the stream data that is the input post data ;
An aggregation device that aggregates the frequency of appearance of the detected predetermined data for each divided period divided within a predetermined period;
Based on the exponential smoothing average of the appearance frequency of the predetermined data aggregated for each segment period, a predicted value of the acceleration of the change in the appearance frequency of the predetermined data in the future segment period is calculated and weighted with the first value A prediction unit that updates the predicted value based on the predicted value that has been calculated, and the actual value of the acceleration of the change in the appearance frequency that is weighted with a second value that is greater than the first value , and the calculated Among the predicted values, the difference between the predicted value in the current segment period and the acceleration of the change in the appearance frequency of the predetermined data aggregated in the current segment period is aggregated for each segment period. A change detection device comprising a determination unit that determines that a change has occurred in the appearance frequency of the predetermined data when a threshold value based on the pattern of the appearance frequency is exceeded,
A change detection system comprising: A change detection method executed by a change detection device,
Aggregated by division period divided by the predetermined period, based on the exponential smoothing moving average of frequency of occurrence of predetermined data included in the stream data is post data, the frequency of occurrence of said predetermined data at a future sectional period A predicted value of change acceleration is calculated, and the predicted value weighted with a first value and the measured acceleration value of the change in appearance frequency weighted with a second value greater than the first value. Based on the prediction step of updating the prediction value ;
Of the calculated predicted values, the difference between the predicted value in the current segment period and the acceleration of the change in the appearance frequency of the predetermined data aggregated in the current segment period is aggregated for each segment period. A determination step of determining that a change has occurred in the appearance frequency of the predetermined data when exceeding a threshold based on the pattern of the appearance frequency of the predetermined data;
The change detection method characterized by including. In the computer of the change detection device,
Aggregated by division period divided by the predetermined period, based on the exponential smoothing moving average of frequency of occurrence of predetermined data included in the stream data is post data, the frequency of occurrence of said predetermined data at a future sectional period A predicted value of change acceleration is calculated, and the predicted value weighted with a first value and the measured acceleration value of the change in appearance frequency weighted with a second value greater than the first value. Based on the prediction step of updating the prediction value ;
Of the calculated predicted values, the difference between the predicted value in the current segment period and the acceleration of the change in the appearance frequency of the predetermined data aggregated in the current segment period is aggregated for each segment period. A determination step of determining that a change has occurred in the appearance frequency of the predetermined data when exceeding a threshold based on the pattern of the appearance frequency of the predetermined data;
A program for running

Images