داده کاوی، هوش مصنوعی ۲۵۸۱ بازدید

در داده‌کاوی (Data Mining)، به فرآیند شناسایی نمونه‌ها، رویدادها یا مشاهداتی که با الگوها یا دیگر نمونه‌های موجود در مجموعه داده مطابقت نداشته باشند، «تشخیص ناهنجاری» (Anomaly detection) یا «تشخیص دورافتادگی» (Outlier Detection) گفته می‌شود. معمولا ناهنجاری‌ها بسته به نوع مساله، مربوط به کلاهبرداری بانکی، حملات سایبری ساختاریافته، مشکلات پزشکی یا وجود خطا در متن هستند. به ناهنجاری، «دورافتادگی»، الگوی نوظهور، «نویز» (noise)، انحراف (deviation) و استثنا (exception) نیز گفته می‌شود.

به طور کلی، در بحث تشخیص سو استفاده و نفوذ در شبکه‌های کامپیوتری، نمونه داده‌های جذاب نه موارد نادر بلکه انفجارهای غیر منتظره در فعالیت‌ها هستند. این مفهوم با تعریف متداول آمار از دورافتادگی (به عنوان یک نمونه نادر) مطابقت ندارد و ممکن است روش‌های تشخیص دورافتادگی (که معمولا نظارت نشده هستند) برای تشخیص ناهنجاری در داده‌ها با شکست مواجه شوند. این در حالیست که الگوریتم‌های تحلیل خوشه اغلب قادر به شناسایی خوشه‌های کوچکی (Micro Clusters) هستند که به وسیله داده‌های ناهنجار شکل گرفته‌اند.

تشخیص ناهنجاری

سه دسته گسترده از روش‌های تشخیص ناهنجاری وجود دارد. روش‌های تشخیص ناهنجاری نظارت نشده، قادر به تشخیص ناهنجاری‌ها در مجموعه داده‌های تست بدون برچسب با این فرض هستند که اکثریت نمونه‌های داده در مجموعه داده بهنجار محسوب می‌شوند و به آنچه در مجموعه داده موجود است شباهت دارند.

روش‌های تشخیص ناهنجاری نظارت شده، نیازمند یک مجموعه داده دارای برچسب «بهنجار» (Normal) یا «ناهنجار» (Abnormal) و آموزش یک دسته‌بند هستند (تفاوت کلیدی با دیگر مسائل دسته‌بندی آماری طبیعت نامتوازن ذاتی تشخیص دورافتادگی است). روش‌های تشخیص ناهنجاری نیمه نظارت شده مدل رفتار طبیعی یک مجموعه داده بهنجار را از یک مجموعه داده (بهنجار) ارائه شده می‌سازند و سپس درست‌نمایی (likelihood) یک نمونه تست به‌منظور تولید شدن توسط مدلی که مرحله یادگیری را طی کرده ارزیابی می‌کنند.

کاربردها

تشخیص ناهنجاری در طیف وسیعی از کاربردها مانند تشخیص نفوذ، تشخیص ناهنجاری، تشخیص خطا، سیستم‌های نظارت بر سلامت (تشخیص تومور بدخیم در تصویر MRI)، تشخیص رویداد در شبکه‌های حسگر، و تشخیص اختلالات اکوسیستم مورد استفاده قرار می‌گیرد. همچنین در پیش‌پردازش داده‌ها به منظور حذف داده‌های ناهنجار از مجموعه داده، که اغلب به لحاظ آماری منجر به رشد قابل توجهی در صحت می‌شود مورد استفاده قرار می‌گیرند.

کاربردهای تشخیص ناهنجاری

انواع ناهنجاری

پیش از ورود به مباحث تخصصی‌تر تشخیص ناهنجاری، بهتر است که مرزهایی برای تعریف ناهنجاری در نظر گرفته شود. ناهنجاری‌ها را می‌توان در حالت کلی در سه دسته «ناهنجاری‌های نقطه‌ای» (Point anomalies)، «ناهنجاری‌های زمینه‌ای» (Contextual anomalies) و «ناهنجاری‌های تجمعی» (Collective anomalies) قرار داد. در ادامه هر یک از این موارد به طور خلاصه بیان شده‌اند.

ناهنجاری‌های نقطه‌ای: اگر یک نمونه داده از اکثریت داده‌ها فاصله زیادی داشته باشد، ناهنجاری نقطه‌ای محسوب می‌شود. برای مثال در کارت‌های اعتباری می‌توان از ناهنجاری نقطه‌ای برای تشخیص برداشت‌های عجیب و احتمالا مجرمانه استفاده کرد. در واقع، اگر اغلب برداشت‌های دارنده کارت در طیف مشخصی باشد و یک برداشت با تفاوت مبلغ بسیار زیاد (نسبت به سایر برداشت‌ها) انجام شود، به آن ناهنجاری نقطه‌ای گفته می‌شود.

ناهنجاری نقطه‌ای

ناهنجاری زمینه‌ای: چنین ناهنجاری‌هایی وابسته به زمینه‌ای هستند که داده‌کاوی و تشخیص ناهنجاری در آن انجام می‌شود. وقوع چنین ناهنجاری‌هایی در داده‌های سری زمانی متداول است. برای مثال دمای هوای منفی بیست درجه (۲۰-) ممکن است در فصل زمستان کاملا طبیعی باشد اما همین دما در فصل تابستان ناهنجاری در نظر گرفته می‌شود. به عنوان مثالی دیگر باید گفت که پرداخت روزانه بالغ بر ۳۰۰ هزار تومان هزینه ناهار در تعطیلات نوروزی ممکن است امری طبیعی باشد اما پرداخت روزانه این مبلغ برای ناهار در دیگر زمان‌های سال می‌تواند ناهنجاری زمینه‌ای محسوب شود.

ناهنجاری تجمعی: یک مجموعه از نمونه داده‌های دارای تجمع به شناسایی ناهنجاری‌ها کمک می‌کند. برای مثال، فعالیت شخصی که تلاش می‌کند داده‌ها را از یک ماشین دور به کامپیوتر خود منتقل کند ناهنجاری محسوب می‌شود. مثال بهتری از ناهنجاری تجمعی، نوار قلب انسان است. وجود مقادیر پایین در نوار قلب به خودی خود ناهنجاری نیست، اما هنگامی که تعداد زیادی از این مقادیر پایین به صورت تجمعی اتفاق می‌افتند ناهنجاری در نظر گرفته می‌شوند.

ناهنجاری تجمعی

تشخیص ناهنجاری بسیار شبیه به «حذف نویز» (Noise removal) و تشخیص الگوهای نوظهور است اما با این دو تفاوت دارد. در تشخیص الگوهای نوظهور به شناسایی الگوهایی پیش‌تر مشاهده نشده پرداخته می‌شود. به عنوان مثالی از این امر، می‌توان به علاقه شدید کاربران به یک کانال یوتیوب در طول کریسمس اشاره کرد. حذف نویز، فرآیند ایمن‌سازی تحلیل‌ها از مشاهدات ناخواسته محسوب می‌شود. مثالی از این مورد، حذف نویز از یک سیگنال دارای معنا است.

روش‌های تشخیص ناهنجاری

ساده‌ترین رویکرد برای تشخیص بی‌قاعدگی‌ها در مجموعه داده، پرچم‌گذاری نقاط داده‌ای است که از مشخصه‌های آماری متداول یک توزیع مانند میانگین، میانه، مُد و چارک‌ها فاصله دارند. در واقع می‌توان در تعریف نقطه داده ناهنجار گفت نمونه داده‌ای که با انحراف معیار مشخصی از میانه فاصله داشته باشد، ناهنجار محسوب می‌شود. استفاده از میانه در داده‌های سری زمانی (به دلیل ایستا بودن آن) نمی تواند گزینه خوبی جهت تشخیص ناهنجاری باشد.

بنابراین به یک پنجره غلتان (متحرک) برای محاسبه میانگین در میان نقاط داده نیاز است. به این روش میانگین متحرک گفته می‌شود و در آن گرایش به روان‌سازی نوسانات کوتاه مدت و برجسته کردن مقادیر دراز مدت وجود دارد. به بیان ریاضی، یک میانگین متحرک ساده n-دوره‌ای را می‌توان به عنوان «فیلتر پایین‌گذر» (low pass filter) نیز در نظر گرفت. فیلتر Kalman نسخه پیچیده‌تری از همین سنجه محسوب می‌شود.

چالش‌ها

فیلترهای پایین‌گذر امکان شناسایی ناهنجاری‌ها در مثال‌های ساده را می‌دهند، اما موقعیت‌هایی نیز وجود دارد که این روش در آن‌ها کار نمی‌کند. برخی از این موارد در ادامه بیان شده‌اند.

  • داده‌های حاوی نویز ممکن است دارای رفتاری مشابهی با نمونه‌های ناهنجار باشند، زیرا مرزهای بین رفتار بهنجار و ناهنجار معمولا دقیق نیست.
  • تعریف بهنجار و ناهنجار ممکن است مکررا تغییر کنند. ناهنجاری‌های مخرب به طور مداوم خود را با داده‌های بهنجار تطبیق می‌دهند. بنابراین تعیین آستانه بر اساس میانگین متحرک نمی‌تواند همیشه گزینه مناسبی باشد.
  • برای الگوهایی که فصل محور هستند، انجام این کار شامل روش‌های پیچیده‌تری مانند تجزیه داده‌ها به گرایش‌های گوناگون به منظور شناسایی تغییرات موجود در فصل‌ها است.

رویکردهای مبتنی بر یادگیری ماشین

در ادامه خلاصه‌ای از روش‌های تشخیص ناهنجاری برپایه یادگیری ماشین ارائه می‌شود.

تشخیص ناهنجاری مبتنی بر چگالی

روش تشخیص ناهنجاری مبتنی بر چگالی برپایه الگوریتم k-نزدیک‌ترین همسایگی است.

فرض: نقاط داده طبیعی در نزدیکی همسایگی‌های چگال و ناهنجاری‌ها بسیار دورتر از آن‌ها هستند.

نزدیک‌ترین مجموعه از نقاط داده به وسیله یک امتیاز ارزیابی می‌شود. این امتیاز می‌تواند فاصله اقلیدسی یا سنجه مشابهی متناسب با نوع داده‌ها باشد (داده دسته‌ای یا عددی است). روش‌های تشخیص ناهنجاری مبتنی بر چگالی را می‌توان به طور کلی در دو دسته قرار داد.

  • K-نزدیک‌ترین همسایگی: KNN یک روش یادگیری ساده، غیر پارامتری و تنبل است که برای دسته‌بندی داده‌ها براساس مشابهت‌های موجود در متریک‌های فاصله مانند اقلیدسی (Eucledian)، منهتن (Manhattan)، مینکوفسکی (Minkowski) یا همینگ (Hamming) عمل می‌کند.

تراکم نسبی داده‌ها: این روش بیشتر با عنوان «فاکتور دورافتادگی محلی» شناخته می‌شود. این مفهوم بر اساس سنجه فاصله‌ای که به آن «فاصله دسترسی‌پذیری» (eachability distance) گفته می‌شود بنا نهاده شده است.

روش‌های تشخیص ناهنجاری مبتنی بر خوشه‌بندی

خوشه‌بندی یکی از متداول‌ترین مفاهیم در یادگیری نظارت نشده است.

فرض: نقاط داده مشابه گرایش به تعلق به گروه‌ها یا خوشه‌های مشابهی دارند که براساس فاصله آن‌ها از «مرکزوارها» (centroid) تعیین می‌شوند.

K-میانه، الگوریتم خوشه‌بندی است که به طور گسترده در مسائل مختلف داده‌کاوی و تشخیص ناهنجاری مورد استفاده قرار می‌گیرد. این روش، K خوشه مشابه از نقاط داده می‌سازد. نقاط داده‌ای که خارج از این گروه‌ها قرار گیرند پتانسیل آن را دارند که به عنوان ناهنجار برچسب‌گذاری شوند.

روش‌های مبتنی بر ماشین بردار پشتیبان

ماشین بردار پشتیبان دیگر روش موثر برای تشخیص ناهنجاری است. SVM معمولا با یادگیری نظارت شده مرتبط است اما افزونه‌ای مانند OneClassCVM نیز دارد که برای شناسایی ناهنجاری‌ها به عنوان یک مساله نظارت نشده (که در آن داده‌های آموزش برچسب‌گذاری نشده‌اند) قابل استفاده است. الگوریتم، مرزهای نرم را برای خوشه‌بندی نمونه داده‌های بهنجار با استفاده از مجموعه آموزش می‌آموزد و سپس با بهره‌گیری از نمونه‌های تست خود را برای شناسایی ناهنجاری‌هایی که خارج از ناحیه آموخته شده قرار دارند تنظیم می‌کند. بسته به مساله، خروجی یک تشخیص دهنده ناهنجاری می‌تواند یک مقدار اسکالر برای فیلتر کردن آستانه مبتنی بر دامنه یا برچسب‌های متنی (مانند برچسب‌های دودویی/چندگانه) باشد.

ساخت یک تشخیص دهنده ناهنجاری ساده با استفاده از فیلتر پایین گذر

در این بخش بر ساخت یک بسته تشخیص ناهنجاری با استفاده از میانگین متحرک برای شناسایی ناهنجاری‌ها در تعدادی از لکه‌های خورشیدی طی چندین ماه در یک مجموعه داده نمونه تمرکز شده است. این مجموعه داده را می‌توان از این مسیر و با استفاده از دستور زیر دانلود کرد (wget برنامه‌ای رایانه‌ای برای دریافت محتوا از وب است. این نرم‌افزار بخشی از پروژه گنو محسوب می‌شود).

wget -c -b http://www-personal.umich.edu/~mejn/cp/data/sunspots.txt

این مجموعه داده دارای ۳۱۴۳ سطر است که شامل اطلاعاتی پیرامون لکه‌های خورشیدی گردآوری شده در طول سال‌های ۱۷۴۹ تا ۱۹۸۴ می‌شود. لکه‌های خورشیدی به عنوان نقاط تیره‌ای روی خورشید تعریف می‌شوند. مطالعه لکه‌های خورشیدی به دانشمندان کمک می‌کند که مشخصه‌های خورشید را در دوره‌ای از زمان درک کنند. به طور کلی، لکه خورشیدی یک مشخصه مغناطیسی محسوب می‌شود.

میانگین متحرک با استفاده از همگشت خطی گسسته

«همگشت» (Convolution ) یک عمیات ریاضی است که روی دو تابع برای تولید سومین تابع انجام می‌شود. به بیان ریاضی، همگشت را می‌توان به عنوان انتگرال حاصل‌ضرب دو تابع پس از آنکه یکی از توابع معکوس و شیفت شد، تعریف کرد. فرمول مربوط به این عملیات در ادامه ارائه شده است.

$f*g(t)$ = $\int_{-\infty}^{\infty} f(T)*g(t-T) dT$ که در آن (f(T یک تابع ورودی شامل کمیت  quantity of interest است (برای مثال لکه‌های خورشیدی در زمان T محاسبه می‌شوند). (g(t —T یک تابع وزن‌دهی است که بر اساس مقدار t شیفت پیدا می‌کند. بدین شکل، با تغییر T، وزن‌های گوناگون به تابع ورودی (f(T تخصیص داده می‌شود. در بررسی موردی این مطلب، (f(T تعداد لکه‌های خورشیدی در زمان T را ارائه می‌کند. (g(t —T کرنل میانگین متحرک است.

from __future__ import division
from itertools import izip, count
import matplotlib.pyplot as plt
from numpy import linspace, loadtxt, ones, convolve
import numpy as np
import pandas as pd
import collections
from random import randint
from matplotlib import style
style.use('fivethirtyeight')
%matplotlib inline
# 1. Download sunspot dataset and upload the same to dataset directory
#    Load the sunspot dataset as an Array
!mkdir -p dataset
!wget -c -b http://www-personal.umich.edu/~mejn/cp/data/sunspots.txt -P dataset
data = loadtxt("dataset/sunspots.txt", float)

# 2. View the data as a table
data_as_frame = pd.DataFrame(data, columns=['Months', 'SunSpots'])
data_as_frame.head(
)

 

SunSpots Months
۵۸.۰ ۰.۰ ۰
۶۲.۶ ۱.۰ ۱
۷۰.۰ ۲.۰ ۲
۵۵.۷ ۳.۰ ۳
۸۵.۰ ۴.۰ ۴
# 3. Lets define some use-case specific UDF(User Defined Functions)

def moving_average(data, window_size):
    """ Computes moving average using discrete linear convolution of two one dimensional sequences.
    Args:
    -----
            data (pandas.Series): independent variable
            window_size (int): rolling window size

    Returns:
    --------
            ndarray of linear convolution

    References:
    ------------
    [1] Wikipedia, "Convolution", http://en.wikipedia.org/wiki/Convolution.
    [2] API Reference: https://docs.scipy.org/doc/numpy/reference/generated/numpy.convolve.html

    """
    window = np.ones(int(window_size))/float(window_size)
    return np.convolve(data, window, 'same')


def explain_anomalies(y, window_size, sigma=1.0):
  """ Helps in exploring the anamolies using stationary standard deviation
    Args:
    -----
        y (pandas.Series): independent variable
        window_size (int): rolling window size
        sigma (int): value for standard deviation

    Returns:
    --------
        a dict (dict of 'standard_deviation': int, 'anomalies_dict': (index: value))
        containing information about the points indentified as anomalies

    """
    avg = moving_average(y, window_size).tolist()
    residual = y - avg
    # Calculate the variation in the distribution of the residual
    std = np.std(residual)
    return {'standard_deviation': round(std, 3),
            'anomalies_dict': collections.OrderedDict([(index, y_i) for
                                                       index, y_i, avg_i in izip(count(), y, avg)
              if (y_i > avg_i + (sigma*std)) | (y_i < avg_i - (sigma*std))])}


def explain_anomalies_rolling_std(y, window_size, sigma=1.0):
    """ Helps in exploring the anamolies using rolling standard deviation
    Args:
    -----
        y (pandas.Series): independent variable
        window_size (int): rolling window size
        sigma (int): value for standard deviation

    Returns:
    --------
        a dict (dict of 'standard_deviation': int, 'anomalies_dict': (index: value))
        containing information about the points indentified as anomalies
    """
    avg = moving_average(y, window_size)
    avg_list = avg.tolist()
    residual = y - avg
    # Calculate the variation in the distribution of the residual
    testing_std = pd.rolling_std(residual, window_size)
    testing_std_as_df = pd.DataFrame(testing_std)
    rolling_std = testing_std_as_df.replace(np.nan,
                                  testing_std_as_df.ix[window_size - 1]).round(3).iloc[:,0].tolist()
    std = np.std(residual)
    return {'stationary standard_deviation': round(std, 3),
            'anomalies_dict': collections.OrderedDict([(index, y_i)
                                                       for index, y_i, avg_i, rs_i in izip(count(),
                                                                                           y, avg_list, rolling_std)
              if (y_i > avg_i + (sigma * rs_i)) | (y_i < avg_i - (sigma * rs_i))])}


# This function is repsonsible for displaying how the function performs on the given dataset.
def plot_results(x, y, window_size, sigma_value=1,
                 text_xlabel="X Axis", text_ylabel="Y Axis", applying_rolling_std=False):
    """ Helps in generating the plot and flagging the anamolies.
        Supports both moving and stationary standard deviation. Use the 'applying_rolling_std' to switch
        between the two.
    Args:
    -----
        x (pandas.Series): dependent variable
        y (pandas.Series): independent variable
        window_size (int): rolling window size
        sigma_value (int): value for standard deviation
        text_xlabel (str): label for annotating the X Axis
        text_ylabel (str): label for annotatin the Y Axis
        applying_rolling_std (boolean): True/False for using rolling vs stationary standard deviation
    """
    plt.figure(figsize=(15, 8))
    plt.plot(x, y, "k.")
    y_av = moving_average(y, window_size)
    plt.plot(x, y_av, color='green')
    plt.xlim(0, 1000)
    plt.xlabel(text_xlabel)
    plt.ylabel(text_ylabel)

    # Query for the anomalies and plot the same
    events = {}
    if applying_rolling_std:
        events = explain_anomalies_rolling_std(y, window_size=window_size, sigma=sigma_value)
    else:
        events = explain_anomalies(y, window_size=window_size, sigma=sigma_value)

    x_anomaly = np.fromiter(events['anomalies_dict'].iterkeys(), dtype=int, count=len(events['anomalies_dict']))
    y_anomaly = np.fromiter(events['anomalies_dict'].itervalues(), dtype=float,
                                            count=len(events['anomalies_dict']))
    plt.plot(x_anomaly, y_anomaly, "r*", markersize=12)

    # add grid and lines and enable the plot
    plt.grid(True)
    plt.show()
# 4. Lets play with the functions
x = data_as_frame['Months']
Y = data_as_frame['SunSpots']

# plot the results
plot_results(x, y=Y, window_size=10, text_xlabel="Months", sigma_value=3,
             text_ylabel="No. of Sun spots")
events = explain_anomalies(y, window_size=5, sigma=3)

# Display the anomaly dict
print("Information about the anomalies model:{}".format(events))

تشخیص ناهنجاری

در ادامه این مساله مورد بررسی قرار می‌گیرد که آیا تابع تشخیص ناهنجاری ارائه شده در بالا را می‌توان برای دیگر بررسی‌های موردی استفاده کرد یا خیر. فرض می‌شود که یک مجموعه داده تصادفی متعلق به ارزش گذاری سهام شرکت A در طول زمان است. محور X زمان (روزها) و محور y مقدار سهام را به دلار نشان می‌دهد.

# Convenience function to add noise
def noise(yval):
    """ Helper function to generate random points """
    np.random.seed(0)
    return 0.2*np.asarray(yval)*np.random.normal(size=len(yval))

# Generate a random dataset
def generate_random_dataset(size_of_array=1000, random_state=0):
    """ Helps in generating a random dataset which has a normal distribution
    Args:
    -----
        size_of_array (int): number of data points
        random_state (int): to initialize a random state

    Returns:
    --------
        a list of data points for dependent variable, pandas.Series of independent variable
    """
    np.random.seed(random_state)
    y = np.random.normal(0, 0.5, size_of_array)
    x = range(0, size_of_array)
    y_new = [y_i + index**((size_of_array - index)/size_of_array) +  noise()
     for index, y_i in izip(count(), y)]
    return x, pd.Series(y_new)


# Lets play
x1, y1 = generate_random_dataset()
# Using stationary standard deviation over a continuous sample replicating
plot_results(x1, y1, window_size=12, title_for_plot="Statinoary Standard Deviation",
                    sigma_value=2, text_xlabel="Time in Days", text_ylabel="Value in $")

# using rolling standard deviation for
x1, y1 = generate_random_dataset()
plot_results(x1, y1, window_size=50, title_for_plot="Using rolling standard deviation",
             sigma_value=2, text_xlabel="Time in Days", text_ylabel="Value in $", applying_rolling_std=True)

تشخیص ناهنجاری

به نظر می‌رسد که تشخیص دهنده ناهنجاری معرفی شده عملکرد خوبی دارد. این تشخیص دهنده قادر به شناسایی نقاط داده‌ای که دو سیگما از منحنی برازش شده فاصله دارند است. بسته به توزیع داده‌های یک مساله، در تنظیمات سری زمانی و پویایی محیط ممکن است نیاز به استفاده از انحراف معیار مانا (سراسری) یا غیر مانا (محلی) برای تثبیت یک مدل باشد. تابع ریاضی حول محور انحراف معیار را می‌توان به سادگی برای استفاده از فرمول‌سازی سفارشی ویرایش کرد.

تذکر: روش ارائه شده در بالا صرفا برای نشان دادن مفاهیم تشخیص ناهنجاری است و بهینه‌ترین راهکارهای موجود برای این کار محسوب نمی‌شود.

اگر نوشته بالا برای شما مفید بوده، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۶ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد.

مشاهده بیشتر